On the Stability of Generalized Second Price Auctions with Budgets

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

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Pages (from-to)1-23
Number of pages23
JournalTheory of Computing Systems
Issue number1
StatePublished - Jul 1 2016


  • Auctions
  • Keyword auctions
  • Second price
  • Sponsored search

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics


Dive into the research topics of 'On the Stability of Generalized Second Price Auctions with Budgets'. Together they form a unique fingerprint.

Cite this