2018/09/05 by Dimitris Fotakis, Fotakis, Dimitris, Kyriakos Lotidis +3
Decision Sciences · Economics, Econometrics and Finance · Social Sciences · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Experimental Behavioral Economics Studies #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.1809.01803
openalex publication_date 2018/09/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study incentive compatible mechanisms for Combinatorial Auctions where the\nbidders have submodular (or XOS) valuations and are budget-constrained. Our\nobjective is to maximize the \liquid welfare, a notion of efficiency for\nbudget-constrained bidders introduced by Dobzinski and Paes Leme (2014). We\nshow that some of the known truthful mechanisms that best-approximate the\nsocial welfare for Combinatorial Auctions with submodular bidders through\ndemand query oracles can be adapted, so that they retain truthfulness and\nachieve asymptotically the same approximation guarantees for the liquid\nwelfare. More specifically, for the problem of optimizing the liquid welfare in\nCombinatorial Auctions with submodular bidders, we obtain a universally\ntruthful randomized O(\log m)-approximate mechanism, where m is the number\nof items, by adapting the mechanism of Krysta and V "ocking (2012).\n Additionally, motivated by large market assumptions often used in mechanism\ndesign, we introduce a notion of competitive markets and show that in such\nmarkets, liquid welfare can be approximated within a constant factor by a\nrandomized universally truthful mechanism. Finally, in the Bayesian setting, we\nobtain a truthful O(1)-approximate mechanism for the case where bidder\nvaluations are generated as independent samples from a known distribution, by\nadapting the results of Feldman, Gravin and Lucier (2014).\n