Tractable equilibria in sponsored search with endogenous budgets

Dragos Florin Ciocan, Krishnamurthy Iyer

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


We consider an ad network’s problem of allocating the auction for each individual impression to an optimal subset of advertisers with the goal of revenue maximization. This is a variant of bipartite matching except that advertisers may strategize by choosing their bidding profiles and their total budget. Because the ad network’s allocation rule affects the bidders’ strategies, equilibrium analysis is challenging. We show that this analysis is tractable when advertisers face a linear budget cost rj. In particular, we show that the strategy in which advertisers bid their valuations shaded by a factor of 1 + rj is an approximate equilibrium with the error decreasing with market size. This equilibrium can be interpreted as one in which a bidder facing an opportunity cost rj is guaranteed a return on investment of at least rj per dollar spent. Furthermore, in this equilibrium, the optimal allocation for the ad network, as determined from a linear program (LP), is greedy with high probability. This is in contrast with the exogenous budgets case, in which the LP optimization is challenging at practical scales. These results are evidence that, although in general such bipartite matching problems may be challenging to solve because of their high dimensionality, the optimal solution is remarkably simple at equilibrium.

Original languageEnglish (US)
Pages (from-to)227-244
Number of pages18
JournalOperations research
Issue number1
StatePublished - Jan 1 2021

Bibliographical note

Funding Information:
Funding: K. Iyer gratefully acknowledges support from the National Science Foundation [Grant CMMI-2002156]. Supplemental Material: The online appendix is available at

Publisher Copyright:
Copyright: © 2020 INFORMS


  • Bipartite matching
  • Endogenous budgets
  • Truthful equilibrium


Dive into the research topics of 'Tractable equilibria in sponsored search with endogenous budgets'. Together they form a unique fingerprint.

Cite this