Efficiency bounds for sequential resource allocation auctions

Junjik Bae; Eyal Beigman; Randall Berry; Michael L. Honig; Rakesh Vohra

doi:10.1109/CDC.2007.4434913

Efficiency bounds for sequential resource allocation auctions

Junjik Bae^*, Eyal Beigman, Randall Berry, Michael L. Honig, Rakesh Vohra

^*Corresponding author for this work

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

6 Scopus citations

Abstract

Market-based mechanisms such as auctions have been widely considered for various network resource allocation problems. We consider such a mechanism motivated by dynamic spectrum sharing applications. In this model multiple homogeneous units of a given resource are to be allocated to two agents. We study a sequential second price auction for allocating these resource units. It is well known that such auctions can have inefficient equilibria. For the case of two bidders, we show that the value of the allocation obtained in the unique subgame perfect equilibrium is at least 1 - e^-1 of the value of the efficient allocation. Furthermore, we show that this bound is asymptotically tight as the number of goods increases.

Original language	English (US)
Title of host publication	Proceedings of the 46th IEEE Conference on Decision and Control 2007, CDC
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	765-770
Number of pages	6
ISBN (Print)	1424414989, 9781424414987
DOIs	https://doi.org/10.1109/CDC.2007.4434913
State	Published - 2007
Event	46th IEEE Conference on Decision and Control 2007, CDC - New Orleans, LA, United States Duration: Dec 12 2007 → Dec 14 2007

Publication series

Name	Proceedings of the IEEE Conference on Decision and Control
ISSN (Print)	0743-1546
ISSN (Electronic)	2576-2370

Other

Other	46th IEEE Conference on Decision and Control 2007, CDC
Country/Territory	United States
City	New Orleans, LA
Period	12/12/07 → 12/14/07

ASJC Scopus subject areas

Control and Systems Engineering
Modeling and Simulation
Control and Optimization

Access to Document

10.1109/CDC.2007.4434913

Cite this

Bae, J., Beigman, E., Berry, R., Honig, M. L., & Vohra, R. (2007). Efficiency bounds for sequential resource allocation auctions. In Proceedings of the 46th IEEE Conference on Decision and Control 2007, CDC (pp. 765-770). [4434913] (Proceedings of the IEEE Conference on Decision and Control). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC.2007.4434913

@inproceedings{868464b93e664c188745059a5d2ee24c,

title = "Efficiency bounds for sequential resource allocation auctions",

abstract = "Market-based mechanisms such as auctions have been widely considered for various network resource allocation problems. We consider such a mechanism motivated by dynamic spectrum sharing applications. In this model multiple homogeneous units of a given resource are to be allocated to two agents. We study a sequential second price auction for allocating these resource units. It is well known that such auctions can have inefficient equilibria. For the case of two bidders, we show that the value of the allocation obtained in the unique subgame perfect equilibrium is at least 1 - e-1 of the value of the efficient allocation. Furthermore, we show that this bound is asymptotically tight as the number of goods increases.",

author = "Junjik Bae and Eyal Beigman and Randall Berry and Honig, {Michael L.} and Rakesh Vohra",

year = "2007",

doi = "10.1109/CDC.2007.4434913",

language = "English (US)",

isbn = "1424414989",

series = "Proceedings of the IEEE Conference on Decision and Control",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "765--770",

booktitle = "Proceedings of the 46th IEEE Conference on Decision and Control 2007, CDC",

address = "United States",

note = "46th IEEE Conference on Decision and Control 2007, CDC ; Conference date: 12-12-2007 Through 14-12-2007",

}

Bae, J, Beigman, E, Berry, R , Honig, ML & Vohra, R 2007, Efficiency bounds for sequential resource allocation auctions. in Proceedings of the 46th IEEE Conference on Decision and Control 2007, CDC., 4434913, Proceedings of the IEEE Conference on Decision and Control, Institute of Electrical and Electronics Engineers Inc., pp. 765-770, 46th IEEE Conference on Decision and Control 2007, CDC, New Orleans, LA, United States, 12/12/07. https://doi.org/10.1109/CDC.2007.4434913

Efficiency bounds for sequential resource allocation auctions. / Bae, Junjik; Beigman, Eyal; Berry, Randall et al.
Proceedings of the 46th IEEE Conference on Decision and Control 2007, CDC. Institute of Electrical and Electronics Engineers Inc., 2007. p. 765-770 4434913 (Proceedings of the IEEE Conference on Decision and Control).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Efficiency bounds for sequential resource allocation auctions

AU - Bae, Junjik

AU - Beigman, Eyal

AU - Berry, Randall

AU - Honig, Michael L.

AU - Vohra, Rakesh

PY - 2007

Y1 - 2007

N2 - Market-based mechanisms such as auctions have been widely considered for various network resource allocation problems. We consider such a mechanism motivated by dynamic spectrum sharing applications. In this model multiple homogeneous units of a given resource are to be allocated to two agents. We study a sequential second price auction for allocating these resource units. It is well known that such auctions can have inefficient equilibria. For the case of two bidders, we show that the value of the allocation obtained in the unique subgame perfect equilibrium is at least 1 - e-1 of the value of the efficient allocation. Furthermore, we show that this bound is asymptotically tight as the number of goods increases.

AB - Market-based mechanisms such as auctions have been widely considered for various network resource allocation problems. We consider such a mechanism motivated by dynamic spectrum sharing applications. In this model multiple homogeneous units of a given resource are to be allocated to two agents. We study a sequential second price auction for allocating these resource units. It is well known that such auctions can have inefficient equilibria. For the case of two bidders, we show that the value of the allocation obtained in the unique subgame perfect equilibrium is at least 1 - e-1 of the value of the efficient allocation. Furthermore, we show that this bound is asymptotically tight as the number of goods increases.

UR - http://www.scopus.com/inward/record.url?scp=62749161530&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=62749161530&partnerID=8YFLogxK

U2 - 10.1109/CDC.2007.4434913

DO - 10.1109/CDC.2007.4434913

M3 - Conference contribution

AN - SCOPUS:62749161530

SN - 1424414989

SN - 9781424414987

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 765

EP - 770

BT - Proceedings of the 46th IEEE Conference on Decision and Control 2007, CDC

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 46th IEEE Conference on Decision and Control 2007, CDC

Y2 - 12 December 2007 through 14 December 2007

ER -

Efficiency bounds for sequential resource allocation auctions

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this