research-article

Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions

Authors:

Vahab Mirrokni,

Michael Schapira,

Jan VondrakAuthors Info & Claims

EC '08: Proceedings of the 9th ACM conference on Electronic commerce

Pages 70 - 77

https://doi.org/10.1145/1386790.1386805

Published: 08 July 2008 Publication History

Abstract

We provide tight information-theoretic lower bounds for the welfare maximization problem in combinatorial auctions. In this problem, the goal is to partition m items among k bidders in a way that maximizes the sum of bidders' values for their allocated items. Bidders have complex preferences over items expressed by valuation functions that assign values to all subsets of items.

We study the "black box" setting in which the auctioneer has oracle access to the valuation functions of the bidders. In particular, we explore the well-known value query model in which the permitted query to a valuation function is in the form of a subset of items, and the reply is the value assigned to that subset of items by the valuation function.

We consider different classes of valuation functions: submodular,subadditive, and superadditive. For these classes, it has been shown that one can achieve approximation ratios of 1 -- 1/e, 1/√m, and √ m/m, respectively, via a polynomial (in k and m) number of value queries. We prove that these approximation factors are essentially the best possible: For any fixed ε > 0, a (1--1/e + ε)-approximation for submodular valuations or an 1/_m1/2-ε-approximation for subadditive valuations would require exponentially many value queries, and a log^1+ε m/ m-approximation for superadditive valuations would require a superpolynomial number of value queries.

References

[1]

L. Blumrosen and N. Nisan. On the computational power of iterative auctions I: Demand queries. In Proc. of the 6th ACM Conference on Electronic Commerce (EC), 2005.

Digital Library

[2]

L. Blumrosen and N. Nisan. On the computational power of iterative auctions I: Ascending auctions. In Proc. of the 6th ACM Conference on Electronic Commerce (EC), 2005.

Digital Library

[3]

S. Dobzinski. Private communication, 2006.

[4]

S. Dobzinski and M. Schapira. An improved approximation algorithm for combinatorial auctions with submodular bidders. In Proc. of the 18rd Annual ACM Symposium on Discrete Algorithms (SODA), 2006, 1064--1073.

Digital Library

[5]

S. Dobzinski, N. Nisan and M. Schapira. Approximation algorithms for combinatorial auctions with complement-free bidders. In Proc. of the 37th Annual ACM Symposium on Theory of Computing (STOC), 2005, 610--618.

Digital Library

[6]

U. Feige. On maximizing welfare when utility functions are subadditive. In Proc. of the 38th Annual ACM Symposium on Theory of Computing (STOC), 2006, 41--50.

Digital Library

[7]

U. Feige and J. Vondrák. Approximation algorithms for combinatorial allocation problems:Improving the factor of 1--1/e. In Proc. of the 47th Annual IEEE Symposium on the Foundationsof Computer Science (FOCS), 2006, 667--676.

Digital Library

[8]

U. Feige, V. Mirrokni and J. Vondrák. Maximizing non-monotone submodular functions. In Proc. of the 47th Annual IEEE Symposium on the Foundationsof Computer Science (FOCS), 2007, 461--471.

Digital Library

[9]

R. Holzman, N. Kfir-Dahav, D. Monderer and M. Tennenholtz. Bundling equilibrium in combinatorial auctions. Games and Economic Behavior 47, 2004, 104--123.

[10]

S. Khot, R. Lipton, E. Markakis and A. Mehta.Inapproximability results for combinatorialauctions with submodular utility functions. In Proc. of WINE 2005.

Digital Library

[11]

B. Lehmann, D. Lehmann and N. Nisan. Combinatorial auctions with decreasing marginal utilities In Proc. of the 3rd ACM Conferenceon Electronic Commerce (EC), 2001.

Digital Library

[12]

N. Nisan. Bidding and allocation in combinatorial auctions. In Proc. of the 2nd ACM Conferenceon Electronic Commerce (EC), 2000.

Digital Library

[13]

N. Nisan and I. Segal. The communication requirements of efficient allocations and supportingprices. Journal of Economic Theory, 129:1, 2006, 192--224.

[14]

G. Nemhauser and M. Fisher, and L. Wolsey. An analysis of approximations for maximizing submodular set functions II. Math. Programming Study 8, 1978, 73--87.

[15]

J. Vondrák. Optimal approximation for the Submodular Welfare Problemin the value oracle model. To appear in Proc. of the 40th Annual ACM Symposium on Theory of Computing (STOC), 2008.

Digital Library

Cited By

Rafiey ASalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Decomposable submodular maximization in federated settingProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693772(41841-41866)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3693772
Qiu FWeinberg SMohar BShinkar IO'Donnell R(2024)Settling the Communication Complexity of VCG-Based Mechanisms for All Approximation GuaranteesProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649706(1192-1203)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649706
Fawzi OFermé P(2024)Broadcast Channel Coding: Algorithmic Aspects and Non-Signaling AssistanceIEEE Transactions on Information Theory10.1109/TIT.2024.341004770:11(7563-7580)Online publication date: Nov-2024
https://doi.org/10.1109/TIT.2024.3410047
Show More Cited By

Index Terms

Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Item pricing for revenue maximization
EC '08: Proceedings of the 9th ACM conference on Electronic commerce

We consider the problem of pricing n items to maximize revenue when faced with a series of unknown buyers with complex preferences, and show that a simple pricing scheme achieves surprisingly strong guarantees.

We show that in the unlimited supply ...
Bayesian Combinatorial Auctions

We study the following simple Bayesian auction setting: m items are sold to n selfish bidders in m independent second-price auctions. Each bidder has a private valuation function that specifies his or her complex preferences over all subsets of items. ...
Truthful randomized mechanisms for combinatorial auctions

We present a new framework for the design of computationally-efficient and incentive-compatible mechanisms for combinatorial auctions. The mechanisms obtained via this framework are randomized, and obtain incentive compatibility in the universal sense (...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '08: Proceedings of the 9th ACM conference on Electronic commerce

July 2008

332 pages

ISBN:9781605581699

DOI:10.1145/1386790

General Chair:
Lance Fortnow
Northwestern University, USA
,
Program Chairs:
John Riedl
University of Minnesota, USA
,
Tuomas Sandholm
Carnegie-Mellon University, USA

Copyright © 2008 ACM.

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 ACM 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

EC '08

Sponsor:

EC '08: ACM Conference on Electronic Commerce

July 8 - 12, 2008

Il, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

99
Total Citations
View Citations
273
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)4

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Rafiey ASalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Decomposable submodular maximization in federated settingProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693772(41841-41866)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3693772
Qiu FWeinberg SMohar BShinkar IO'Donnell R(2024)Settling the Communication Complexity of VCG-Based Mechanisms for All Approximation GuaranteesProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649706(1192-1203)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649706
Fawzi OFermé P(2024)Broadcast Channel Coding: Algorithmic Aspects and Non-Signaling AssistanceIEEE Transactions on Information Theory10.1109/TIT.2024.341004770:11(7563-7580)Online publication date: Nov-2024
https://doi.org/10.1109/TIT.2024.3410047
Ron SThomas CWeinberg SZhang Q(2024)Communication Separations for Truthful Auctions: Breaking the Two-Player Barrier2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00032(386-405)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00032
Mavrov IMunagala KShen YLeyton-Brown KSamuelson LHartline J(2023)Fair Multiwinner Elections with Allocation ConstraintsProceedings of the 24th ACM Conference on Economics and Computation10.1145/3580507.3597685(964-990)Online publication date: 9-Jul-2023
https://dl.acm.org/doi/10.1145/3580507.3597685
Zdun UQueval PSimhandl GScandariato RChakravarty SJelic MJovanovic A(2023)Microservice Security Metrics for Secure Communication, Identity Management, and ObservabilityACM Transactions on Software Engineering and Methodology10.1145/353218332:1(1-34)Online publication date: 13-Feb-2023
https://dl.acm.org/doi/10.1145/3532183
Arrieta AValle PAgirre JSagardui G(2023)Some Seeds Are Strong: Seeding Strategies for Search-based Test Case SelectionACM Transactions on Software Engineering and Methodology10.1145/353218232:1(1-47)Online publication date: 13-Feb-2023
https://dl.acm.org/doi/10.1145/3532182
Ojdanic MSoremekun EDegiovanni RPapadakis MLe Traon Y(2023)Mutation Testing in Evolving Systems: Studying the Relevance of Mutants to Code EvolutionACM Transactions on Software Engineering and Methodology10.1145/353078632:1(1-39)Online publication date: 13-Feb-2023
https://dl.acm.org/doi/10.1145/3530786
Khatoonabadi SCosta DAbdalkareem RShihab E(2023)On Wasted Contributions: Understanding the Dynamics of Contributor-Abandoned Pull Requests–A Mixed-Methods Study of 10 Large Open-Source ProjectsACM Transactions on Software Engineering and Methodology10.1145/353078532:1(1-39)Online publication date: 13-Feb-2023
https://dl.acm.org/doi/10.1145/3530785
Leichtmann BLottermoser ABerger JNitsch V(2022)Personal Space in Human-Robot Interaction at Work: Effect of Room Size and Working Memory LoadACM Transactions on Human-Robot Interaction10.1145/353616711:4(1-19)Online publication date: 8-Sep-2022
https://dl.acm.org/doi/10.1145/3536167
Show More Cited By

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten