Invited Session Thu.1.MA 043

Thursday, 10:30 - 12:00 h, Room: MA 043

Cluster 8: Game theory [...]

Mean-field approaches to large scale dynamic auctions and mechanisms


Chair: Gabriel Weintraub and Santiago Balseiro



Thursday, 10:30 - 10:55 h, Room: MA 043, Talk 1

Krishnamurthy Iyer
Mean field equilibria of dynamic auctions with learning

Coauthors: Ramesh Johari, Mukund Sundararajan


We study learning in a dynamic setting where identical copies of a good are sold over time through a sequence of second
price auctions. Each agent in the market has an unknown independent private valuation which determines the distribution
of the reward she obtains from the good; for example, in sponsored search settings, advertisers may initially be unsure of the
value of a click. Though the induced dynamic game is complex, we simplify analysis of the market using an approximation methodology
known as mean field equilibrium (MFE). The methodology assumes that agents optimize only with respect to long run average
estimates of the distribution of other players' bids. We show a remarkable fact: in a mean field equilibrium, the agent has an
optimal strategy where she bids truthfully according to a conjoint valuation. The conjoint valuation is the sum of her
current expected valuation, together with an overbid amount that is exactly the expected marginal benefit to one additional
observation about her true private valuation. We conclude by establishing a dynamic version of the revenue equivalence theorem.



Thursday, 11:00 - 11:25 h, Room: MA 043, Talk 2

Santiago Balseiro
Auctions for online display advertising exchanges: Approximations and design

Coauthors: Omar Besbes, Gabriel Weintraub


We study the competitive landscape that arises in Ad Exchanges and the implications for publishers' decisions. Advertisers join these markets with a pre-specified budget and participate in multiple auctions over the length of a campaign. They bid on online ad placements based on specific viewer information. We introduce the notion of a Fluid Mean Field Equilibrium (FMFE) to study the advertisers' dynamic bidding strategies. This concept is based on a mean field approximation to relax the informational requirements of advertisers, together with a fluid approximation to approximate the complex dynamics of the advertisers' stochastic control problems. We derive a closed-form characterization of the bidding strategies under a FMFE, and of the resulting landscape. Using this characterization, we study the auction design problem from the publisher's perspective, and analyze the impact of three design levers: (1) the reserve price; (2) the supply of impressions to the Exchange versus an alternative channel; and (3) the disclosure of viewers' information. Our results provide novel insights with regard to the description and design of such markets.



Thursday, 11:30 - 11:55 h, Room: MA 043, Talk 3

Alexandre Proutiere
Optimal bidding strategies and equilibria in repeated auctions with budget constraints

Coauthors: Ramki Gummadi, Peter Key


How should agents bid in repeated sequential auctions when they are budget constrained? A motivating
example is that of sponsored search auctions, where advertisers bid in a sequence of generalized second
price (GSP) auctions. These auctions have many idiosyncratic
features that distinguish them from other models of sequential auctions. (1) Each bidder competes in a large
number of auctions, where each auction is worth very little. (2) The total bidder population is large, which
means it is unrealistic to assume that the bidders could possibly optimize their strategy by modeling specific
opponents. (3) The presence of a virtually unlimited supply of these auctions means bidders are necessarily
expense constrained.
Motivated by these three factors, we first frame the generic problem as a discounted Markov Decision Process and provide a structural characterization of the associated value function and the optimal bidding strategy, which specifies the extent to which agents underbid from their true valuation due to budget constraints. We then show the existence of Mean Field Equilibria for both the repeated second price and GSP auctions with a large number of bidders.


  There are three major facts that should be watched out for in all payday loans in the United States. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Buy Cialis is the one that definitely differs from all other products.