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

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › 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.

Originalsprog	Engelsk
Titel	Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS'09) : SESSION: Interactions
Redaktører	Keith S. Decker, Jaime Simão Sichman, Carles Sierra, Cristiano Castelfranchi
Antal sider	2
Vol/bind	2
Forlag	International Foundation for Autonomous Agents and Multiagent Systems
Publikationsdato	2009
Sider	1227-1228
ISBN (Trykt)	978-0-9817381-7-8
Status	Udgivet - 2009
Begivenhed	International Conference on Autonomous Agents and Multiagents Systems (AAMAS'09) - Budapest, Ungarn Varighed: 10 maj 2009 → 15 maj 2009 Konferencens nummer: 8

Konference

Konference	International Conference on Autonomous Agents and Multiagents Systems (AAMAS'09)
Nummer	8
Land/Område	Ungarn
By	Budapest
Periode	10/05/2009 → 15/05/2009

Adgang til dokumentet

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

Citationsformater

Escamocher, G., Miltersen, P. B., & Santillan, R. (2009). Existence and computation of equilibria of first-price auctions with integral valuations and bids. I K. S. Decker, J. S. Sichman, C. Sierra, & C. Castelfranchi (red.), Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS'09): SESSION: Interactions (Bind 2, s. 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. red. / Keith S. Decker ; Jaime Simão Sichman ; Carles Sierra ; Cristiano Castelfranchi. Bind 2 International Foundation for Autonomous Agents and Multiagent Systems, 2009. s. 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. i K S. Decker, JS Sichman, C Sierra & C Castelfranchi (red), Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS'09): SESSION: Interactions. bind 2, International Foundation for Autonomous Agents and Multiagent Systems, s. 1227-1228, International Conference on Autonomous Agents and Multiagents Systems (AAMAS'09), Budapest, Ungarn, 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. red. / Keith S. Decker; Jaime Simão Sichman; Carles Sierra; Cristiano Castelfranchi. Bind 2 International Foundation for Autonomous Agents and Multiagent Systems, 2009. s. 1227-1228.

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › 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. I S. Decker K, Sichman JS, Sierra C, Castelfranchi C, red., Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS'09): SESSION: Interactions. Bind 2. International Foundation for Autonomous Agents and Multiagent Systems. 2009. s. 1227-1228

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

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater