Paper Info
Title
Bayesian Budget Feasibility with Posted Pricing
Abstract
We consider the problem of budget feasible mechanism design proposed by Singer, but in a Bayesian setting. A principal has a public value for hiring a subset of the agents and a budget, while the agents have private costs for being hired. We consider both additive and submodular value functions of the principal. We show that there are simple, practical, ex post budget balanced posted pricing mechanisms that approximate the value obtained by the Bayesian optimal mechanism that is budget balanced only in expectation. A main motivating application for this work is crowdsourcing, e.g., on Mechanical Turk, where workers are drawn from a large population and posted pricing is standard. Our analysis methods relate to contention resolution schemes in submodular optimization of Vondràk et al. and the correlation gap analysis of Yan.
Year
DOI
Venue
2015
10.1145/2872427.2883032
WWW '16: 25th International World Wide Web Conference Montréal Québec Canada April, 2016
Keywords
Field
DocType
Bayesian mechanism design, budget feasible mechanism design, crowdsourcing, posted pricing, submodular optimization
Population,Optimal mechanism,Computer science,Crowdsourcing,Bayesian mechanism design,Operations research,Submodular set function,Mechanism design,Artificial intelligence,Public value,Machine learning,Bayesian probability
Journal
Volume
ISBN
Citations 
abs/1506.04198
978-1-4503-4143-1
7
PageRank 
References 
Authors
0.48
12
2
Name
Order
Citations
PageRank
eric balkanski1386.13
Jason D. Hartline21447125.76