Tractable Equilibria in Sponsored Search with Endogenous Budgets

Dragos Florin Ciocan () and Krishnamurthy Iyer
Additional contact information
Dragos Florin Ciocan: INSEAD, Technology and Operations Management, Fontainebleau 77300, France

Operations Research, 2021, vol. 69, issue 1, 227-244

Abstract: 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 r j . In particular, we show that the strategy in which advertisers bid their valuations shaded by a factor of 1 + r j 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 r j is guaranteed a return on investment of at least r j 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.

Keywords: bipartite matching; endogenous budgets; truthful equilibrium (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/opre.2020.2052 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:69:y:2021:i:1:p:227-244

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().