skip to main content
10.1145/1807342.1807345acmconferencesArticle/Chapter ViewAbstractPublication PagesecConference Proceedingsconference-collections
research-article

Auctions with online supply

Published: 07 June 2010 Publication History

Abstract

We study the problem of selling identical items to n unit-demand bidders in a setting in which the total supply of items is unknown to the mechanism. Items arrive dynamically, and the seller must make the allocation and payment decisions online with the goal of maximizing social welfare. We consider two models of unknown supply: the adversarial supply model, in which the mechanism must produce a welfare guarantee for any arbitrary supply, and the stochastic supply model, in which supply is drawn from a distribution known to the mechanism, and the mechanism need only provide a welfare guarantee in expectation.
Our main result is a separation between these two models. We show that all truthful mechanisms, even randomized, achieve a diminishing fraction of the optimal social welfare (namely, no better than a Ω(log log n) approximation) in the adversarial setting. In sharp contrast, in the stochastic model, under a standard monotone hazard-rate condition, we present a truthful mechanism that achieves a constant approximation. We show without any condition on the supply distribution, no mechanism can achieve a constant fraction approximation. We also characterize a natural subclass of truthful mechanisms in our setting, the set of online-envy-free mechanisms. All of the mechanisms we present fall into this class, and we prove almost optimal lower bounds for such mechanisms. Since auctions with unknown supply are regularly run in many online-advertising settings, our main results emphasize the importance of considering distributional information in the design of auctions in such environments.

References

[1]
Susan Athey and Jonathan Levin. Information and competition in u.s. forest service timber auctions. Journal of Political Economy, 109(2):375--417, 2001.
[2]
Susan Athey and Ilya Segal. An efficient dynamic mechanism, 2007. Working paper.
[3]
D. Bergemann and J. Valimaki. Efficient dynamic auctions, 2006. Cowles Foundation Discussion Paper 1584.
[4]
R. Cavallo, D. C. Parkes, and S. Singh. Optimal coordinated planning amongst self-interested agents with private state. In Conference on Uncertainty in Artificial Intelligence (UAI), pages 55--62, 2006.
[5]
S. Chawla, J. D. Hartline, and R. Kleinberg. Algorithmic pricing via virtual valuations. In ACM conference on Electronic Commerce (EC), pages 243--251, 2007.
[6]
R. Cole, S. Dobzinski, and L. Fleischer. Prompt Mechanisms for Online Auctions. Symposium on Algorithmic Game Theory (SAGT): LNCS, 4997:170, 2008.
[7]
Nikhil R. Devenur and Thomas P. Hayes. The adwords problem: online keyword matching with budgeted bidders under random permutations. In ACM conference on Electronic Commerce (EC), pages 71--78, 2009.
[8]
S. Dobzinski, N. Nisan, and M. Schapira. Truthful randomized mechanisms for combinatorial auctions. In ACM Symposium on Theory Of Computing (STOC), 2006.
[9]
B. Edelman, M. Ostrovsky, and M. Schwarz. Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords. American Economic Review, 97(1):242--259, 2007.
[10]
Jon Feldman, Aranyak Mehta, Vahab Mirrokni, and S. Muthukrishnan. Online stochastic matching: Beating 1-1/e. In IEEE Symposium on Foundations of Computer Science (FOCS), 2009.
[11]
Alex Gershkov and Benny Moldovanu. Learning about the future and dynamic efficiency. American Economic Review, forthcoming., 2008.
[12]
Alex Gershkov and Benny Moldovanu. Optimal search, learning, and implementation. Discussion paper, university of Bonn., 2009.
[13]
A. V. Goldberg and J. D. Hartline. Envy-free auctions for digital goods. In ACM conference on Electronic commerce (EC), pages 29--35, 2003.
[14]
V. Guruswami, J. D. Hartline, A. R. Karlin, D. Kempe, C. Kenyon, and F. McSherry. On profit-maximizing envy-free pricing. In ACM-SIAM symposium on Discrete algorithms (SODA), pages 1164--1173, 2005.
[15]
M. Hajiaghayi, R. Kleinberg, M. Mahdian, and D. C. Parkes. Online auctions with re-usable goods. In ACM Conf. on Electronic Commerce (EC), pages 165--174, 2005.
[16]
J. D. Hartline and T. Roughgarden. Optimal mechanism design and money burning. In ACM Symposium on Theory Of Computing (STOC), pages 75--84, 2008.
[17]
Jason D. Hartline and Anna R. Karlin. In N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani (eds.) Chapter 13, Profit Maximization in Mechanism Design. Cambridge University Press., 2007.
[18]
Thomas D. Jeitschko. Equilibrium price paths in sequential auctions with stochastic supply. Economics Letters, 64(1):67--72, 1999.
[19]
V. Krishna. Auction theory. Academic press, 2002.
[20]
R. Lavi and N. Nisan. Competitive analysis of incentive compatible on-line auctions. Theoretical Computer Science., 310(1):159--180, 2004.
[21]
R. Lavi and N. Nisan. Online ascending auctions for gradually expiring items. In ACM-SIAM Symposium On Discrete Algorithms (SODA), pages 1146--1155, 2005.
[22]
M. Mahdian and A. Saberi. Multi-unit Auctions with Unknown Supply. ACM conference on Electronic Commerce (EC), pages 243--249, 2006.
[23]
R. P. McAfee and Vincent Daniel. The declining price anomaly. Journal of Economic Theory (JET), 60(1):191--212, 1993.
[24]
Paul R. Milgrom and Robert J. Weber. A theory of auctions and competitive bidding. Econometrica, 50(5):1089--1122, 1982.
[25]
R. B. Myerson. Optimal Auction Design. Mathematics of Operations Research, 6(1):58--73, 1981.
[26]
Tibor Neugebauer and Paul Pezanis-Christou. Equilibrium price paths in sequential auctions with stochastic supply. Journal of Economic Behavior and Organization, 63(1):55--72, 2007.
[27]
N. Nisan and A. Ronen. Algorithmic Mechanism Design. Games and Economic Behavior (GEB), 35(1-2):166--196, 2001.
[28]
David C. Parkes. In N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani (eds.) Chapter 16, Online Mechanisms. Cambridge University Press., 2007.
[29]
David C. Parkes and Satinder Singh. An mdp-based approach to online mechanism design. In Annual Conf. on Neural Information Processing Systems (NIPS), 2003.
[30]
Robert Wilson. Game-Theoretic Approaches to Trading Processes. In Advances in Economic Theory: Fifth World Congress, ed. by T. Bewley, chap. 2,. Cambridge University Press., 1987.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
EC '10: Proceedings of the 11th ACM conference on Electronic commerce
June 2010
400 pages
ISBN:9781605588223
DOI:10.1145/1807342
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: 07 June 2010

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. approximation
  2. mechanism design
  3. online supply
  4. truthful auction

Qualifiers

  • Research-article

Conference

EC '10
Sponsor:
EC '10: ACM Conference on Electronic Commerce
June 7 - 11, 2010
Massachusetts, Cambridge, USA

Acceptance Rates

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

Upcoming Conference

EC '25
The 25th ACM Conference on Economics and Computation
July 7 - 11, 2025
Stanford , CA , USA

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2020)Non‐Clairvoyant Dynamic Mechanism DesignEconometrica10.3982/ECTA1553088:5(1939-1963)Online publication date: 2020
  • (2019)Multi-unit supply-monotone auctions with bayesian valuationsProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310447(173-192)Online publication date: 6-Jan-2019
  • (2017)Optimal Dynamic Auctions for Display AdvertisingOperations Research10.1287/opre.2017.159265:4(897-913)Online publication date: Aug-2017
  • (2017)THEMIS: Collusion-Resistant and Fair Pricing Spectrum Auction Under Dynamic SupplyIEEE Transactions on Mobile Computing10.1109/TMC.2016.260942516:7(2051-2064)Online publication date: 2-Jun-2017
  • (2016)An online incentive mechanism for emergency demand response in geo-distributed colocation data centersProceedings of the Seventh International Conference on Future Energy Systems10.1145/2934328.2934331(1-13)Online publication date: 21-Jun-2016
  • (2016)Two ways to auction off an uncertain goodJournal of Economics10.1007/s00712-016-0483-7119:1(1-15)Online publication date: 13-Apr-2016
  • (2015)Fair rewarding in colocation data centers: Truthful mechanism for emergency demand response2015 IEEE 23rd International Symposium on Quality of Service (IWQoS)10.1109/IWQoS.2015.7404755(359-368)Online publication date: Jun-2015
  • (2014)Free riding and participation in large scale, multi-hospital kidney exchangeTheoretical Economics10.3982/TE13579:3(817-863)Online publication date: 3-Oct-2014
  • (2014)Fair Pricing in the SkyProceedings of the 2014 IEEE 22nd International Conference on Network Protocols10.1109/ICNP.2014.45(245-256)Online publication date: 21-Oct-2014
  • (2013)Clinching auctions with online supplyProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627861(605-619)Online publication date: 6-Jan-2013
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media