Tractable Equilibria in Sponsored Search With Endogenous Budgets

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. Since 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 where 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 where a bidder facing an opportunity cost r_j is guaranteed an ROI of at least r_j per dollar spent. Furthermore, in this equilibrium, the optimal allocation for the ad network, as determined from an LP, is greedy with high probability. This is in contrast with the exogenous budgets case, where the LP optimization is challenging at practical scales. These results are evidence that, while in general such bipartite matching problems may be challenging to solve due to their high dimensionality, the optimal solution is remarkably simple at equilibrium.