Joint seminar of the Optimization team of CERMICS (Ecole des Ponts

Paristech) and the Tropical team (INRIA Saclay & CMAP, Ecole

Polytechnique)

## Forthcoming sessions

## Guillaume Vigeral (Ceremade, Paris Dauphine)

### April 8th, 10:30, Online

## Structure of the sets of Nash equilibria of finite games; applications

to the complexity of some decision problems in game theory

Abstract:

The set of Nash equilibrium payoffs of a finite game is always non

empty, compact and semialgebraic. We show that, for 3 players or more,

the reverse also holds: given E a subset of R^N that is non empty,

compact and semialgebraic, one constructs a finite N player game such

that E is its set of equilibrium payoffs. Related results also holds

when one consider only games with integral payoffs, or when the focus is

on equilibria instead of equilibrium payoffs.

We apply this result to understand the complexity class of some natural

decision problems on finite games.