On the stability of generalized second price auctions with budgets

Josep Díaz; Ioannis Giotis; Lefteris Kirousis; Evangelos Markakis; Maria Serna

doi:10.1007/978-3-642-54423-1_60

On the stability of generalized second price auctions with budgets

Josep Díaz, Ioannis Giotis, Lefteris Kirousis, Evangelos Markakis, Maria Serna

Computer Science

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

Abstract

The Generalized Second Price (GSP) auction used typically to model sponsored search auctions does not include the notion of budget constraints, which is present in practice. Motivated by this, we introduce the different variants of GSP auctions that take budgets into account in natural ways. We examine their stability by focusing on the existence of Nash equilibria and envy-free assignments. We highlight the differences between these mechanisms and find that only some of them exhibit both notions of stability. This shows the importance of carefully picking the right mechanism to ensure stable outcomes in the presence of budgets.

Original language	English (US)
Title of host publication	LATIN 2014
Subtitle of host publication	Theoretical Informatics - 11th Latin American Symposium, Proceedings
Publisher	Springer Verlag
Pages	695-706
Number of pages	12
ISBN (Print)	9783642544224
DOIs	https://doi.org/10.1007/978-3-642-54423-1_60
State	Published - 2014
Event	11th Latin American Theoretical Informatics Symposium, LATIN 2014 - Montevideo, Uruguay Duration: Mar 31 2014 → Apr 4 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8392 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	11th Latin American Theoretical Informatics Symposium, LATIN 2014
Country/Territory	Uruguay
City	Montevideo
Period	3/31/14 → 4/4/14

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-54423-1_60

Cite this

Díaz, J., Giotis, I., Kirousis, L., Markakis, E., & Serna, M. (2014). On the stability of generalized second price auctions with budgets. In LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Proceedings (pp. 695-706). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8392 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-54423-1_60

On the stability of generalized second price auctions with budgets. / Díaz, Josep; Giotis, Ioannis; Kirousis, Lefteris et al.
LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Proceedings. Springer Verlag, 2014. p. 695-706 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8392 LNCS).

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

Díaz, J, Giotis, I, Kirousis, L, Markakis, E & Serna, M 2014, On the stability of generalized second price auctions with budgets. in LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8392 LNCS, Springer Verlag, pp. 695-706, 11th Latin American Theoretical Informatics Symposium, LATIN 2014, Montevideo, Uruguay, 3/31/14. https://doi.org/10.1007/978-3-642-54423-1_60

Díaz J, Giotis I, Kirousis L, Markakis E, Serna M. On the stability of generalized second price auctions with budgets. In LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Proceedings. Springer Verlag. 2014. p. 695-706. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-54423-1_60

Díaz, Josep ; Giotis, Ioannis ; Kirousis, Lefteris et al. / On the stability of generalized second price auctions with budgets. LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Proceedings. Springer Verlag, 2014. pp. 695-706 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d31a15310b6e40b8b5c1c4a63f45f182,

title = "On the stability of generalized second price auctions with budgets",

abstract = "The Generalized Second Price (GSP) auction used typically to model sponsored search auctions does not include the notion of budget constraints, which is present in practice. Motivated by this, we introduce the different variants of GSP auctions that take budgets into account in natural ways. We examine their stability by focusing on the existence of Nash equilibria and envy-free assignments. We highlight the differences between these mechanisms and find that only some of them exhibit both notions of stability. This shows the importance of carefully picking the right mechanism to ensure stable outcomes in the presence of budgets.",

author = "Josep D{\'i}az and Ioannis Giotis and Lefteris Kirousis and Evangelos Markakis and Maria Serna",

year = "2014",

doi = "10.1007/978-3-642-54423-1_60",

language = "English (US)",

isbn = "9783642544224",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "695--706",

booktitle = "LATIN 2014",

note = "11th Latin American Theoretical Informatics Symposium, LATIN 2014 ; Conference date: 31-03-2014 Through 04-04-2014",

}

TY - GEN

T1 - On the stability of generalized second price auctions with budgets

AU - Díaz, Josep

AU - Giotis, Ioannis

AU - Kirousis, Lefteris

AU - Markakis, Evangelos

AU - Serna, Maria

PY - 2014

Y1 - 2014

N2 - The Generalized Second Price (GSP) auction used typically to model sponsored search auctions does not include the notion of budget constraints, which is present in practice. Motivated by this, we introduce the different variants of GSP auctions that take budgets into account in natural ways. We examine their stability by focusing on the existence of Nash equilibria and envy-free assignments. We highlight the differences between these mechanisms and find that only some of them exhibit both notions of stability. This shows the importance of carefully picking the right mechanism to ensure stable outcomes in the presence of budgets.

AB - The Generalized Second Price (GSP) auction used typically to model sponsored search auctions does not include the notion of budget constraints, which is present in practice. Motivated by this, we introduce the different variants of GSP auctions that take budgets into account in natural ways. We examine their stability by focusing on the existence of Nash equilibria and envy-free assignments. We highlight the differences between these mechanisms and find that only some of them exhibit both notions of stability. This shows the importance of carefully picking the right mechanism to ensure stable outcomes in the presence of budgets.

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

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

U2 - 10.1007/978-3-642-54423-1_60

DO - 10.1007/978-3-642-54423-1_60

M3 - Conference contribution

AN - SCOPUS:84899977133

SN - 9783642544224

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 695

EP - 706

BT - LATIN 2014

PB - Springer Verlag

T2 - 11th Latin American Theoretical Informatics Symposium, LATIN 2014

Y2 - 31 March 2014 through 4 April 2014

ER -

On the stability of generalized second price auctions with budgets

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this