research-article

Auctions for Heterogeneous Items and Budget Limits

Authors:

Paul Dütting,

Monika Henzinger,

Martin StarnbergerAuthors Info & Claims

ACM Transactions on Economics and Computation (TEAC), Volume 4, Issue 1

Article No.: 4, Pages 1 - 17

https://doi.org/10.1145/2818351

Published: 02 December 2015 Publication History

Get Access

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.

References

[1]

A. Archer and É. Tardos. 2001. Truthful mechanisms for one-parameter agents. In Proceedings of the 42nd Symposium on Foundations of Computer Science. 482--491.

Digital Library

Google Scholar

[2]

L. M. Ausubel. 2004. An efficient ascending-bid auction for multiple objects. The American Economic Review 94, 5 (2004), 1452--1475.

Crossref

Google Scholar

[3]

L. M. Ausubel. 2006. An efficient dynamic auction for heterogeneous commodities. The American Economic Review 96, 3 (2006), 602--629.

Crossref

Google Scholar

[4]

S. Bhattacharya, V. Conitzer, K. Munagala, and L. Xia. 2010. Incentive compatible budget elicitation in multi-unit auctions. In Proceedings of the 21st Symposium on Discrete Algorithms. 554--572.

Digital Library

Google Scholar

[5]

S. Bikhchandani, R. Lavi, A. Mu, N. Nisan, and A. Sen. 2006. Weak monotonicity characterizes deterministic dominant-strategy implementation. Econometrica 74, 4 (2006), 1109--1132.

Crossref

Google Scholar

[6]

R. Colini-Baldeschi, M. Henzinger, S. Leonardi, and M. Starnberger. 2012. On multiple keyword sponsored search auctions with budgets. In Proceedings of the 39th International Colloquium on Automata, Languages and Programming. 1--12.

Digital Library

Google Scholar

[7]

S. Dobzinski, R. Lavi, and N. Nisan. 2012. Multi-unit auctions with budget limits. Games and Economic Behavior 74, 2 (2012), 486--503.

Crossref

Google Scholar

[8]

A. Fiat, S. Leonardi, J. Saia, and P. Sankowski. 2011. Single-valued combinatorial auctions with budgets. In Proceedings of the 12th Conference on Electronic Commerce. 223--232.

Digital Library

Google Scholar

[9]

G. Goel, V. Mirrokni, and R. P. Leme. 2012. Polyhedral clinching auctions and the adwords polytope. In Proceedings of the 44th Symposium on Theory of Computing. 107--122.

Digital Library

Google Scholar

[10]

R. Lavi and M. May. 2012. A note on the incompatibility of strategy-proofness and Pareto-optimality in quasi-linear settings with public budgets. Economic Letters 115, 1 (2012), 100--103.

Crossref

Google Scholar

[11]

R. Myerson. 1981. Optimal auction design. Mathematics of Operations Research 6, 1 (1981), 58--73.

Digital Library

Google Scholar

Cited By

View all

Hirai HSato R(2023)Polyhedral Clinching Auctions for Indivisible GoodsWeb and Internet Economics10.1007/978-3-031-48974-7_21(366-383)Online publication date: 31-Dec-2023
https://doi.org/10.1007/978-3-031-48974-7_21
Feng ZNarasimhan HParkes DAndre EKoenig SDastani MSukthankar G(2018)Deep Learning for Revenue-Optimal Auctions with BudgetsProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237439(354-362)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3237439
Habiba UHossain E(2018)Auction Mechanisms for Virtualization in 5G Cellular Networks: Basics, Trends, and Open ChallengesIEEE Communications Surveys & Tutorials10.1109/COMST.2018.281139520:3(2264-2293)Online publication date: Nov-2019
https://doi.org/10.1109/COMST.2018.2811395
Show More Cited By

Index Terms

Auctions for Heterogeneous Items and Budget Limits
1. Applied computing
  1. Law, social and behavioral sciences
    1. Economics

Recommendations

Budget constrained auctions with heterogeneous items
STOC '10: Proceedings of the forty-second ACM symposium on Theory of computing

In this paper, we present the first approximation algorithms for the problem of designing revenue optimal Bayesian incentive compatible auctions when there are multiple (heterogeneous) items and when bidders have arbitrary demand and budget constraints (...
Core-competitive Auctions
EC '15: Proceedings of the Sixteenth ACM Conference on Economics and Computation

One of the major drawbacks of the celebrated VCG auction is its low (or zero) revenue even when the agents have high value for the goods and a competitive outcome would have generated a significant revenue. A competitive outcome is one for which it is ...
Corruption in Auctions: Social Welfare Loss in Hybrid Multi-Unit Auctions
AAMAS '22: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems

We initiate the study of the social welfare loss caused by corrupt auctioneers, both in single-item and multi-unit auctions. In our model, the auctioneer may collude with the winning bidders by letting them lower their bids in exchange for a (possibly ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Economics and Computation

ACM Transactions on Economics and Computation Volume 4, Issue 1

December 2015

169 pages

ISSN:2167-8375

EISSN:2167-8383

DOI:10.1145/2852252

Editors:
Vincent Conitzer
Duke University
,
Preston McAfee
Google

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 December 2015

Accepted: 01 May 2015

Revised: 01 October 2014

Received: 01 March 2013

Published in TEAC Volume 4, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Vienna Science and Technology Fund

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
182
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hirai HSato R(2023)Polyhedral Clinching Auctions for Indivisible GoodsWeb and Internet Economics10.1007/978-3-031-48974-7_21(366-383)Online publication date: 31-Dec-2023
https://doi.org/10.1007/978-3-031-48974-7_21
Feng ZNarasimhan HParkes DAndre EKoenig SDastani MSukthankar G(2018)Deep Learning for Revenue-Optimal Auctions with BudgetsProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237439(354-362)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3237439
Habiba UHossain E(2018)Auction Mechanisms for Virtualization in 5G Cellular Networks: Basics, Trends, and Open ChallengesIEEE Communications Surveys & Tutorials10.1109/COMST.2018.281139520:3(2264-2293)Online publication date: Nov-2019
https://doi.org/10.1109/COMST.2018.2811395
Bichler MMerting S(2018)Truthfulness in advertising? Approximation mechanisms for knapsack biddersEuropean Journal of Operational Research10.1016/j.ejor.2018.04.001270:2(775-783)Online publication date: Oct-2018
https://doi.org/10.1016/j.ejor.2018.04.001

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Budget constrained auctions with heterogeneous items

Core-competitive Auctions

Corruption in Auctions: Social Welfare Loss in Hybrid Multi-Unit Auctions

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Funding Sources

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations