Text

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

Ketersediaan

Informasi Detail

Judul Seri

OPERATIONS RESEARCH; Vol.69 No.1 January-February 2021

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 227 - 244

Bahasa

English

ISBN/ISSN

-

Klasifikasi

-

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

BIPARTITE MATCHING
ENDOGENOUS BUDGETS
TRUTHFUL EQUILIBRIUM

Info Detail Spesifik

https://doi.org/10.1287/opre.2020.2052

Pernyataan Tanggungjawab

Dragos Florin Ciocan, Krishnamurthy Iyer

Versi lain/terkait

Lampiran Berkas

Komentar