research-article

Limited and online supply and the bayesian foundations of prior-free mechanism design

Authors:

Nikhil R. Devanur,

Jason D. HartlineAuthors Info & Claims

EC '09: Proceedings of the 10th ACM conference on Electronic commerce

Pages 41 - 50

https://doi.org/10.1145/1566374.1566381

Published: 06 July 2009 Publication History

Get Access

Abstract

We study auctions for selling a limited supply of a single commodity in the case where the supply is known in advance and the case it is unknown and must be instead allocated in an online fashion. The latter variant was proposed by Mahdian and Saberi [12] as a model of an important phenomena in auctions for selling Internet advertising: advertising impressions must be allocated as they arrive and the total quantity available is unknown in advance. We describe the Bayesian optimal mechanism for these variants and extend the random sampling auction of Goldberg et al. [8] to address the prior-free case.

References

[1]

S. Alaei, A. Malekian, and A. Srinivasan. On random sampling auctions for digital goods. In Proc. 11th ACM Conf. on Electronic Commerce, 2009.

Digital Library

Google Scholar

[2]

M. Babaioff, L. Blumrosen, and A. Roth. Auctions with online supply. Working paper.

Google Scholar

[3]

S. Baliga and R. Vohra. Market research and market design. Advances in Theoretical Economics, 3, 2003.

Google Scholar

[4]

S. Chakraborty and N. Devanur. An Online Multi-unit Auction with Improved Competitive Ratio. ArXiv e-prints, January 2009.

Google Scholar

[5]

U. Feige, A. Flaxman, J. Hartline, and R. Kleinberg. On the Competitive Ratio of the Random Sampling Auction. In Proc. 1st Workshop on Internet and Network Economics, pages 878--886, 2005.

Digital Library

Google Scholar

[6]

A. Fiat, A. Goldberg, J. Hartline, and A. Karlin. Generalized competitive auctions. In Proc. 34th ACM Symp. on Theory of Computing, pages 72--81. ACM Press, 2002.

Digital Library

Google Scholar

[7]

A.V. Goldberg, J.D. Hartline, A. Karlin, M. Saks, and A. Wright. Competitive auctions. Games and Economic Behavior, 55:242--269, 2006.

Crossref

Google Scholar

[8]

A.V. Goldberg, J.D. Hartline, and A. Wright. Competitive auctions and digital goods. In Proc. 12th ACM Symp. on Discrete Algorithms, pages 735--744. ACM/SIAM, 2001.

Digital Library

Google Scholar

[9]

J. Hartline and A. Karlin. Profit maximization in mechanism design. In N. Nisan, T. Roughgarden, É. Tardos, and V. Vazirani, editors, Algorithmic Game Theory, chapter 13, pages 331--362. Cambridge University Press, 2007.

Google Scholar

[10]

J. Hartline and R. McGrew. From optimal limited to unlimited supply auctions. In Proceedings of the 7th ACM Conference on Electronic Commerce, pages 175--182, 2005.

Digital Library

Google Scholar

[11]

J. Hartline and T. Roughgarden. Optimal mechanism design and money burning. In Proc. 39th ACM Symp. on Theory of Computing, 2008.

Digital Library

Google Scholar

[12]

M. Mahdian and A. Saberi. Multi-unit auctions with unknown supply. In Proc. 8th ACM Conf. on Electronic Commerce, 2006.

Digital Library

Google Scholar

[13]

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

Digital Library

Google Scholar

Cited By

View all

Li GCai JNi S(2022)Truthful Deep Mechanism Design for Revenue-Maximization in Edge Computing With Budget ConstraintsIEEE Transactions on Vehicular Technology10.1109/TVT.2021.312909871:1(902-914)Online publication date: Jan-2022
https://doi.org/10.1109/TVT.2021.3129098
Mirrokni VPaes Leme RTang PZuo S(2020)Non‐Clairvoyant Dynamic Mechanism DesignEconometrica10.3982/ECTA1553088:5(1939-1963)Online publication date: 2020
https://doi.org/10.3982/ECTA15530
Bhattacharya SKoutsoupias EKulkarni JLeonardi SRoughgarden TXu X(2020)Prior-free multi-unit auctions with ordered biddersTheoretical Computer Science10.1016/j.tcs.2020.09.030Online publication date: Sep-2020
https://doi.org/10.1016/j.tcs.2020.09.030
Show More Cited By

Index Terms

Limited and online supply and the bayesian foundations of prior-free mechanism design
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Prior-free auctions for budgeted agents
EC '13: Proceedings of the fourteenth ACM conference on Electronic commerce

We consider prior-free auctions for revenue and welfare maximization when agents have a common budget. The abstract environments we consider are ones where there is a downward-closed and symmetric feasibility constraint on the probabilities of service ...
Prior-free auctions for budgeted agents
EC '13: Proceedings of the fourteenth ACM conference on Electronic commerce

We consider prior-free auctions for revenue and welfare maximization when agents have a common budget. The abstract environments we consider are ones where there is a downward-closed and symmetric feasibility constraint on the probabilities of service ...
An Auction Mechanism for Cloud Spot Markets

Dynamic forms of resource pricing have recently been introduced by cloud providers that offer Infrastructure as a Service (IaaS) capabilities in order to maximize profits and balance resource supply and demand. The design of a mechanism that efficiently ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

EC '09: Proceedings of the 10th ACM conference on Electronic commerce

July 2009

376 pages

ISBN:9781605584584

DOI:10.1145/1566374

General Chair:
John Chuang
University of California at Berkeley, USA
,
Program Chairs:
Lance Fortnow
Northwestern University, USA
,
Pearl Pu
Ecole Polytechnique Fédérale de Lausanne, Switzerland

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

EC '09

Sponsor:

EC '09: ACM Conference on Electronic Commerce

July 6 - 10, 2009

California, Stanford, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
214
Total Downloads

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

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Li GCai JNi S(2022)Truthful Deep Mechanism Design for Revenue-Maximization in Edge Computing With Budget ConstraintsIEEE Transactions on Vehicular Technology10.1109/TVT.2021.312909871:1(902-914)Online publication date: Jan-2022
https://doi.org/10.1109/TVT.2021.3129098
Mirrokni VPaes Leme RTang PZuo S(2020)Non‐Clairvoyant Dynamic Mechanism DesignEconometrica10.3982/ECTA1553088:5(1939-1963)Online publication date: 2020
https://doi.org/10.3982/ECTA15530
Bhattacharya SKoutsoupias EKulkarni JLeonardi SRoughgarden TXu X(2020)Prior-free multi-unit auctions with ordered biddersTheoretical Computer Science10.1016/j.tcs.2020.09.030Online publication date: Sep-2020
https://doi.org/10.1016/j.tcs.2020.09.030
Deng YPanigrahi DChan T(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
https://dl.acm.org/doi/10.5555/3310435.3310447
Li BElkind EVeloso MAgmon NTaylor M(2019)Mechanism Design with Unstructured BeliefsProceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3306127.3332136(2429-2431)Online publication date: 8-May-2019
https://dl.acm.org/doi/10.5555/3306127.3332136
Devanur NSivan BSyrgkanis VCzumaj A(2018)Truthful multi-parameter auctions with online supplyProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175319(753-769)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175319
Tong YWang LZhou ZChen LDu BYe JDas GJermaine CBernstein P(2018)Dynamic Pricing in Spatial CrowdsourcingProceedings of the 2018 International Conference on Management of Data10.1145/3183713.3196929(773-788)Online publication date: 27-May-2018
https://dl.acm.org/doi/10.1145/3183713.3196929
Chen JLi BLi Y(2018)Information Elicitation for Bayesian AuctionsAlgorithmic Game Theory10.1007/978-3-319-99660-8_5(43-55)Online publication date: 27-Aug-2018
https://doi.org/10.1007/978-3-319-99660-8_5
Chen NGravin NLu PRoughgarden TFeldman MSchwarz M(2015)Competitive Analysis via Benchmark DecompositionProceedings of the Sixteenth ACM Conference on Economics and Computation10.1145/2764468.2764491(363-376)Online publication date: 15-Jun-2015
https://dl.acm.org/doi/10.1145/2764468.2764491
Kesselheim TKleinberg RTardos ERoughgarden TFeldman MSchwarz M(2015)Smooth Online MechanismsProceedings of the Sixteenth ACM Conference on Economics and Computation10.1145/2764468.2764487(203-220)Online publication date: 15-Jun-2015
https://dl.acm.org/doi/10.1145/2764468.2764487
Show More Cited By

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.

Cited By

Index Terms

Recommendations

Prior-free auctions for budgeted agents

Prior-free auctions for budgeted agents

An Auction Mechanism for Cloud Spot Markets