On the Stability of Generalized Second Price Auctions with Budgets

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

doi:10.1007/s00224-015-9634-4

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: Contribution to journal › Article › peer-review

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)
Pages (from-to)	1-23
Number of pages	23
Journal	Theory of Computing Systems
Volume	59
Issue number	1
DOIs	https://doi.org/10.1007/s00224-015-9634-4
State	Published - Jul 1 2016

Keywords

Auctions
Keyword auctions
Second price
Sponsored search

ASJC Scopus subject areas

Theoretical Computer Science
Computational Theory and Mathematics

Access to Document

10.1007/s00224-015-9634-4

Cite this

@article{148d3a6a79584c9cab9ac9ab4a0ac45e,

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.",

keywords = "Auctions, Keyword auctions, Second price, Sponsored search",

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

note = "Publisher Copyright: {\textcopyright} 2015, Springer Science+Business Media New York.",

year = "2016",

month = jul,

day = "1",

doi = "10.1007/s00224-015-9634-4",

language = "English (US)",

volume = "59",

pages = "1--23",

journal = "Theory of Computing Systems",

issn = "1432-4350",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

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 - 2016/7/1

Y1 - 2016/7/1

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.

KW - Auctions

KW - Keyword auctions

KW - Second price

KW - Sponsored search

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

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

U2 - 10.1007/s00224-015-9634-4

DO - 10.1007/s00224-015-9634-4

M3 - Article

AN - SCOPUS:84931044575

SN - 1432-4350

VL - 59

SP - 1

EP - 23

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 1

ER -

On the Stability of Generalized Second Price Auctions with Budgets

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this