2017/03/30 by Pooya Jalaly, Éva Tardos, Jalaly, Pooya +1 · 2 citations
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Complexity and Algorithms in Graphs #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Voting Systems #Mobile Crowdsensing and Crowdsourcing #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1703.10681
openalex publication_date 2017/03/30 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
We study the problem of a budget limited buyer who wants to buy a set of\nitems, each from a different seller, to maximize her value. The budget feasible\nmechanism design problem aims to design a mechanism which incentivizes the\nsellers to truthfully report their cost, and maximizes the buyer's value while\nguaranteeing that the total payment does not exceed her budget. Such budget\nfeasible mechanisms can model a buyer in a crowdsourcing market interested in\nrecruiting a set of workers (sellers) to accomplish a task for her.\n This budget feasible mechanism design problem was introduced by Singer in\n2010. There have been a number of improvements on the approximation guarantee\nof such mechanisms since then. We consider the general case where the buyer's\nvaluation is a monotone submodular function. We offer two general frameworks\nfor simple mechanisms, and by combining these frameworks, we significantly\nimprove on the best known results for this problem, while also simplifying the\nanalysis. For example, we improve the approximation guarantee for the general\nmonotone submodular case from 7.91 to 5; and for the case of large markets\n(where each individual item has negligible value) from 3 to 2.58. More\ngenerally, given an r approximation algorithm for the optimization problem\n(ignoring incentives), our mechanism is a r+1 approximation mechanism for\nlarge markets, an improvement from 2r2. We also provide a similar\nparameterized mechanism without the large market assumption, where we achieve a\n4r+1 approximation guarantee.\n