Existence and computation of equilibria of first-price auctions with integral valuations and bids

Guillaume Escamocher; Peter Bro Miltersen; Rocio Santillan

Existence and computation of equilibria of first-price auctions with integral valuations and bids

Guillaume Escamocher, Peter Bro Miltersen, Rocio Santillan

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

Abstract

We consider existence and computation of symmetric Pure Strategy Nash Equilibrium (PSNE) in single-item, sealed-bid, first-price auctions with integral valuations and bids. For the most general case, we show that existence of PSNE is NP-hard. Then, we present algorithmic results for the case of independent valuations and two ways of breaking ties: Vickrey tie-breaking and random tie-breaking.

Original language	English
Title of host publication	Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS'09) : SESSION: Interactions
Editors	Keith S. Decker, Jaime Simão Sichman, Carles Sierra, Cristiano Castelfranchi
Number of pages	2
Volume	2
Publisher	International Foundation for Autonomous Agents and Multiagent Systems
Publication date	2009
Pages	1227-1228
ISBN (Print)	978-0-9817381-7-8
Publication status	Published - 2009
Event	International Conference on Autonomous Agents and Multiagents Systems (AAMAS'09) - Budapest, Hungary Duration: 10 May 2009 → 15 May 2009 Conference number: 8

Conference

Conference	International Conference on Autonomous Agents and Multiagents Systems (AAMAS'09)
Number	8
Country/Territory	Hungary
City	Budapest
Period	10/05/2009 → 15/05/2009

Keywords

AAMAS proceedings
economics
interaction::auctions and related structures
theoretical

Access to Document

http://delivery.acm.org/10.1145/1560000/1558225/p1227-escamocher.pdf?key1=1558225&key2=4204373621&coll=GUIDE&dl=GUIDE&CFID=73345521&CFTOKEN=52226755

Cite this

Escamocher, G., Miltersen, P. B., & Santillan, R. (2009). Existence and computation of equilibria of first-price auctions with integral valuations and bids. In K. S. Decker, J. S. Sichman, C. Sierra, & C. Castelfranchi (Eds.), Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS'09): SESSION: Interactions (Vol. 2, pp. 1227-1228). International Foundation for Autonomous Agents and Multiagent Systems. http://delivery.acm.org/10.1145/1560000/1558225/p1227-escamocher.pdf?key1=1558225&key2=4204373621&coll=GUIDE&dl=GUIDE&CFID=73345521&CFTOKEN=52226755

Escamocher, Guillaume ; Miltersen, Peter Bro ; Santillan, Rocio. / Existence and computation of equilibria of first-price auctions with integral valuations and bids. Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS'09): SESSION: Interactions. editor / Keith S. Decker ; Jaime Simão Sichman ; Carles Sierra ; Cristiano Castelfranchi. Vol. 2 International Foundation for Autonomous Agents and Multiagent Systems, 2009. pp. 1227-1228

@inproceedings{26baddd0bfda11de82fe000ea68e967b,

title = "Existence and computation of equilibria of first-price auctions with integral valuations and bids",

abstract = "We consider existence and computation of symmetric Pure Strategy Nash Equilibrium (PSNE) in single-item, sealed-bid, first-price auctions with integral valuations and bids. For the most general case, we show that existence of PSNE is NP-hard. Then, we present algorithmic results for the case of independent valuations and two ways of breaking ties: Vickrey tie-breaking and random tie-breaking.",

keywords = "AAMAS proceedings, economics, interaction::auctions and related structures, theoretical",

author = "Guillaume Escamocher and Miltersen, {Peter Bro} and Rocio Santillan",

year = "2009",

language = "English",

isbn = "978-0-9817381-7-8",

volume = "2",

pages = "1227--1228",

editor = "{S. Decker}, Keith and Sichman, {Jaime Sim{\~a}o} and Carles Sierra and Cristiano Castelfranchi",

booktitle = "Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS'09)",

publisher = "International Foundation for Autonomous Agents and Multiagent Systems",

note = "International Conference on Autonomous Agents and Multiagents Systems (AAMAS'09) ; Conference date: 10-05-2009 Through 15-05-2009",

}

Escamocher, G, Miltersen, PB & Santillan, R 2009, Existence and computation of equilibria of first-price auctions with integral valuations and bids. in K S. Decker, JS Sichman, C Sierra & C Castelfranchi (eds), Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS'09): SESSION: Interactions. vol. 2, International Foundation for Autonomous Agents and Multiagent Systems, pp. 1227-1228, International Conference on Autonomous Agents and Multiagents Systems (AAMAS'09), Budapest, Hungary, 10/05/2009. <http://delivery.acm.org/10.1145/1560000/1558225/p1227-escamocher.pdf?key1=1558225&key2=4204373621&coll=GUIDE&dl=GUIDE&CFID=73345521&CFTOKEN=52226755>

Existence and computation of equilibria of first-price auctions with integral valuations and bids. / Escamocher, Guillaume; Miltersen, Peter Bro; Santillan, Rocio.
Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS'09): SESSION: Interactions. ed. / Keith S. Decker; Jaime Simão Sichman; Carles Sierra; Cristiano Castelfranchi. Vol. 2 International Foundation for Autonomous Agents and Multiagent Systems, 2009. p. 1227-1228.

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Existence and computation of equilibria of first-price auctions with integral valuations and bids

AU - Escamocher, Guillaume

AU - Miltersen, Peter Bro

AU - Santillan, Rocio

N1 - Conference code: 8

PY - 2009

Y1 - 2009

N2 - We consider existence and computation of symmetric Pure Strategy Nash Equilibrium (PSNE) in single-item, sealed-bid, first-price auctions with integral valuations and bids. For the most general case, we show that existence of PSNE is NP-hard. Then, we present algorithmic results for the case of independent valuations and two ways of breaking ties: Vickrey tie-breaking and random tie-breaking.

AB - We consider existence and computation of symmetric Pure Strategy Nash Equilibrium (PSNE) in single-item, sealed-bid, first-price auctions with integral valuations and bids. For the most general case, we show that existence of PSNE is NP-hard. Then, we present algorithmic results for the case of independent valuations and two ways of breaking ties: Vickrey tie-breaking and random tie-breaking.

KW - AAMAS proceedings

KW - economics

KW - interaction::auctions and related structures

KW - theoretical

M3 - Article in proceedings

SN - 978-0-9817381-7-8

VL - 2

SP - 1227

EP - 1228

BT - Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS'09)

A2 - S. Decker, Keith

A2 - Sichman, Jaime Simão

A2 - Sierra, Carles

A2 - Castelfranchi, Cristiano

PB - International Foundation for Autonomous Agents and Multiagent Systems

T2 - International Conference on Autonomous Agents and Multiagents Systems (AAMAS'09)

Y2 - 10 May 2009 through 15 May 2009

ER -

Escamocher G, Miltersen PB, Santillan R. Existence and computation of equilibria of first-price auctions with integral valuations and bids. In S. Decker K, Sichman JS, Sierra C, Castelfranchi C, editors, Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS'09): SESSION: Interactions. Vol. 2. International Foundation for Autonomous Agents and Multiagent Systems. 2009. p. 1227-1228

Existence and computation of equilibria of first-price auctions with integral valuations and bids

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this