A Mean Field Game Analysis of Sponsored Search Auctions

Abstract

In online sponsored searches, the advertisers participate in a sequence of multi-keyword sponsored search auctions, and their bidding behaviour can be analysed as a non-cooperative stochastic differential game. Each advertiser has a two-dimensional cost and valuation state. The underlying cost dynamics are modelled by a Markovian deterministic process driven by an optimal feedback control based on an analysis of competitors' behaviour. The underlying valuation dynamics are modelled by a stationary stochastic process, which can be estimated from the users' behaviour by using statistical tools. Though the induced dynamic game is complex, we can simplify the analysis of the market using an approximation methodology known as mean-field games. The methodology assumes that advertisers optimise only with respect to the distribution of other advertisers' two-dimensional states. The problem can be broken down into two coupled PDEs, where an individual advertiser's optimal control paths are analysed by solving a Hamilton-Jacobi-Bellman equation, and the evolution of joint distribution of costs and valuations is characterised by a Fokker-Planck equation. Closed-form analytic solutions are not available, however, I apply numerical methods to compute both stationary and time-dependent distributions, as well as the optimal controls. The best response bidding strategies are then determined from the optimal controls by solving a mixed-integer nonlinear problem. I prove the existence and uniqueness of the stationary mean-field game equilibrium. It is also demonstrated that the mean-field game equilibrium is a reliable approximation of a rational advertiser's behaviour, in the sense that when the other advertisers use the mean-field game equilibrium in the finite stochastic differential game, the advertiser's best response is also to use the mean-field game equilibrium.