Auctions for Heterogeneous Items and Budget Limits

Paul Dütting, Monika Henzinger, Martin StarnbergerACM Trans. Economics and Comput 2015 · OpenReview

Abstract

We study individual rational, Pareto-optimal, and incentive compatible mechanisms for auctions with heterogeneous items and budget limits. We consider settings with multiunit demand and additive valuations. For single-dimensional valuations we prove a positive result for randomized mechanisms, and a negative result for deterministic mechanisms. While the positive result allows for private budgets, the negative result is for public budgets. For multidimensional valuations and public budgets we prove an impossibility result that applies to deterministic and randomized mechanisms. Taken together this shows the power of randomization in certain settings with heterogeneous items, but it also shows its limitations.
BibTeX
@article{dutting2015auctions,
  author = {Paul Dütting and Monika Henzinger and Martin Starnberger},
  title = {{Auctions for Heterogeneous Items and Budget Limits}},
  journal = {ACM Trans. Economics and Comput.},
  year = {2015},
  url = {https://openreview.net/forum?id=Umtvj4M_Qv},
}

Loading related content...

Figure