Groupe d’études et de recherche en analyse des décisions

G-2014-07

The return function: A new computable perspective on Bayesian-Nash equilibria

et

In this paper, we suggest a new approach called the return function to deal with the determination of Bayesian-Nash equilibria in games of incomplete information. Whereas in the traditional approach players reply to each others' strategies, here each player replies to his own return function. In short, given a player's choice of action and the other players' strategies, the return function of that given player is the probability distribution of the outcome. Interestingly, we show that the dynamics of best-reply strategies, which are hard to compute in practice, are mapped to an observable and easy-to-compute dynamics of return functions. We propose a new algorithm for computing Bayesian-Nash equilibria, and illustrate its implementation on a cake-cutting problem. Finally, we prove the convergence of the dynamics of return functions to the Bayesian-Nash equilibrium under fairly general topological assumptions.

, 28 pages