extended-abstract

The Cost of Simple Bidding in Combinatorial Auctions

Authors:

Vitor Bosshard,

Sven SeukenAuthors Info & Claims

EC '21: Proceedings of the 22nd ACM Conference on Economics and Computation

Page 157

https://doi.org/10.1145/3465456.3467609

Published: 18 July 2021 Publication History

Abstract

We study a class of manipulations in combinatorial auctions where bidders fundamentally misrepresent what goods they are interested in. Prior work has largely assumed that bidders only submit bids on their bundles of interest, which we call simple bidding: strategizing over the bid amounts, but not the bundle identities. However, we show that there exists an entire class of auction instances for which simple bids are never optimal in BNE, always being strictly dominated by complex bids (where bidders bid on goods they are not interested in). We show this result for the two most widely used auction mechanisms:first price andVCG-nearest. We also explore the structural properties of the winner determination problem that cause this phenomenon, and we use the insights gained to investigate how impactful complex bidding manipulations may be. We find that, in the worst case, a bidder's optimal complex bid may require bidding on an exponential number of bundles, even if the bidder is interested only in a single good. Thus, this phenomenon can greatly impact the auction's outcome, and should not be ignored by bidders and auction designers alike.

References

[1]

Lawrence Ausubel and Oleg Baranov. 2017. A practical guide to the combinatorial clock auction. The Economic Journal, Vol. 127, 605 (2017).

[2]

Lawrence Ausubel, Peter Cramton, et al. 2011. Auction design for wind rights. Report to Bureau of Ocean Energy Management, Regulation and Enforcement (2011).

[3]

Lawrence Ausubel, Peter Cramton, and Paul Milgrom. 2006. The Clock-proxy Auction: A Practical Combinatorial Auction Design. In Combinatorial Auctions, P. Cramton, Y. Shoham, and R. Steinberg (Eds.). MIT Press.

[4]

Lawrence Ausubel and Paul Milgrom. 2002. Ascending auctions with package bidding. Advances in Theoretical Economics, Vol. 1, 1 (2002), 1--42.

[5]

Lawrence Ausubel and Paul Milgrom. 2006. The Lovely but Lonely Vickrey Auction. In Combinatorial Auctions, Peter Cramton, Yoav Shoham, and Richard Steinberg (Eds.). MIT Press.

[6]

Lawrence M Ausubel and Oleg Baranov. 2020. Core-selecting Auctions with Incomplete Information. International Journal of Game Theory, Vol. 49, 1 (2020), 251--273.

Digital Library

[7]

Marissa Beck and Marion Ott. 2013. Incentives for Overbidding in Minimum-Revenue Core-Selecting Auctions. Annual Conference 2013 (Duesseldorf): Competition Policy and Regulation in a Global Economic Order (2013).

[8]

Tilman Börgers and Jiangtao Li. 2019. Strategically simple mechanisms. Econometrica, Vol. 87, 6 (2019), 2003--2035.

[9]

Vitor Bosshard, Benedikt Bünz, Benjamin Lubin, and Sven Seuken. 2020. Computing Bayes-Nash Equilibria in Combinatorial Auctions with Verification. Journal of Artificial Intelligence Research, Vol. 69 (2020), 531--570.

[10]

Benedikt Bünz, Benjamin Lubin, and Sven Seuken. 2018. Designing Core-selecting Payment Rules: A Computational Search Approach. In Proceedings of the 19th ACM Conference on Electronic Commerce (EC). Ithaca, NY, USA.

Digital Library

[11]

Estelle Cantillon and Martin Pesendorfer. 2007. Combination bidding in multi-unit auctions. (2007).

[12]

Edward Clarke. 1971. Multipart pricing of public goods. Public Choice, Vol. 11, 1 (1971), 17--33.

[13]

Peter Cramton. 2013. Spectrum auction design. Review of Industrial Organization, Vol. 42, 2 (2013), 161--190.

[14]

Peter Cramton, Yoav Shoham, and Richard Steinberg. 2006. Combinatorial Auctions .MIT Press.

[15]

Robert W. Day and Peter Cramton. 2012. Quadratic Core-Selecting Payment Rules for Combinatorial Auctions. Operations Research, Vol. 60, 3 (2012), 588--603.

Digital Library

[16]

Robert W. Day and Paul Milgrom. 2008. Core-selecting Package Auctions. International Journal of Game Theory, Vol. 36, 3 (2008), 393--407.

Digital Library

[17]

Robert W. Day and S. Raghavan. 2007. Fair Payments for Efficient Allocations in Public Sector Combinatorial Auctions. Management Science, Vol. 53, 9 (2007), 1389--1406.

Digital Library

[18]

Rafael Epstein, Lysette Henr'iquez, Jaime Catalán, Gabriel Y Weintraub, Cristián Mart'inez, and Francisco Espejo. 2004. A combinatorial auction improves school meals in Chile: a case of OR in developing countries. International Transactions in Operational Research, Vol. 11, 6 (2004), 593--612.

[19]

Andor Goetzendorff, Martin Bichler, Robert Day, and Pasha Shabalin. 2015. Compact bid languages and core-pricing in large multi-item auctions. Management Science, Vol. 61(7) (2015), 1684--1703.

Digital Library

[20]

T. Groves. 1973. Incentives in Teams. Econometrica, Vol. 41, 4 (1973), 617--631.

[21]

Maarten Janssen and Vladimir Karamychev. 2016. Spiteful bidding and gaming in combinatorial clock auctions. Games and Economic Behavior, Vol. 100 (2016), 186--207.

[22]

Gian-Marco Kokott, Martin Bichler, and Per Paulsen. 2017. Combinatorial first-price auctions: Theory and experiments. Technical Report. Working Paper. Technical University of Munich.

[23]

Shengwu Li. 2017. Obviously strategy-proof mechanisms. American Economic Review, Vol. 107, 11 (2017), 3257--87.

[24]

Paul Milgrom. 2007. Package Auctions and Exchanges. Econometrica, Vol. 75, 4 (2007), 935--965.

[25]

Noam Nisan. 2006. Bidding Languages for Combinatorial Auctions. In Combinatorial Auctions, Peter Cramton, Yoav Shoham, and Richard Steinberg (Eds.). MIT Press.

[26]

Noam Nisan and Ilya Segal. 2006. The communication requirements of efficient allocations and supporting prices. Journal of Economic Theory, Vol. 129, 1 (2006), 192--224.

[27]

Marek Pycia and Peter Troyan. 2019. A Theory of Simplicity in Games and Mechanism Design. (2019).

[28]

Zinovi Rabinovich, Victor Naroditskiy, Enrico H. Gerding, and Nicholas R. Jennings. 2013. Computing pure Bayesian-Nash equilibria in games with finite actions and continuous types. Artificial Intelligence, Vol. 195 (2013), 106--139.

Digital Library

[29]

Tuomas Sandholm. 2013. Very-Large-Scale Generalized Combinatorial Multi-Attribute Auctions: Lessons from Conducting $60 Billion of Sourcing. In The Handbook of Market Design, Nir Vulkan, Alvin E. Roth, and Zvika Neeman (Eds.). Oxford University Press, Chapter 16.

[30]

Tobias Scheffel, Alexander Pikovsky, Martin Bichler, and Kemal Guler. 2011. An experimental comparison of linear and nonlinear price combinatorial auctions. Information Systems Research, Vol. 22, 2 (2011), 346--368.

Digital Library

[31]

William Vickrey. 1961. Counterspeculation, Auctions, and Competitive Sealed Tenders. The Journal of Finance, Vol. 16(1) (1961), 8--37.

Cited By

Fritsch RLee YMeier AWang YWattenhofer R(2023)Understanding the Relationship Between Core Constraints and Core-Selecting Payment Rules in Combinatorial AuctionsFrontiers of Algorithmics10.1007/978-3-031-39344-0_1(1-14)Online publication date: 26-Aug-2023
https://doi.org/10.1007/978-3-031-39344-0_1

Index Terms

The Cost of Simple Bidding in Combinatorial Auctions
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Algorithmic game theory and mechanism design

Recommendations

Uniform Price Auctions: Equilibria and Efficiency

We study the Uniform Price Auction, one of the standard sealed-bid multi-unit auction formats in Auction Theory, for selling multiple identical units of a single good to multi-demand bidders. Contrary to the truthful and efficient multi-unit Vickrey ...
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. ...
Revenue monotonicity in deterministic, dominant-strategy combinatorial auctions

In combinatorial auctions using VCG, a seller can sometimes increase revenue by dropping bidders. In this paper we investigate the extent to which this counterintuitive phenomenon can also occur under other deterministic, dominant-strategy combinatorial ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '21: Proceedings of the 22nd ACM Conference on Economics and Computation

July 2021

950 pages

ISBN:9781450385541

DOI:10.1145/3465456

General Chair:
Péter Biró
Hungarian Academy of Sciences
,
Program Chairs:
Shuchi Chawla
University of Wisconsin-Madison and University of Texas at Austin
,
Federico Echenique
California Institute of Technology

Copyright © 2021 Owner/Author.

Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Sponsors

SIGecom: Special Interest Group on Economics and Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 July 2021

Check for updates

Author Tags

Qualifiers

Extended-abstract

Conference

EC '21

Sponsor:

SIGecom

EC '21: The 22nd ACM Conference on Economics and Computation

July 18 - 23, 2021

Budapest, Hungary

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
45
Total Downloads

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

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fritsch RLee YMeier AWang YWattenhofer R(2023)Understanding the Relationship Between Core Constraints and Core-Selecting Payment Rules in Combinatorial AuctionsFrontiers of Algorithmics10.1007/978-3-031-39344-0_1(1-14)Online publication date: 26-Aug-2023
https://doi.org/10.1007/978-3-031-39344-0_1

View Options

Get Access

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.

Media

Figures

Other

Tables

View Table of Contents