Decision, Algorithms and Geometry

Joint seminar of the Optimization team of CERMICS (Ecole des Ponts
Paristech) and the Tropical team (INRIA Saclay & CMAP, Ecole

Forthcoming sessions

Kazuo Murota (The Institute of Statistical Mathematics, Tokyo)

May 20th, 10:00, Online

Multiple exchange property of gross substitutes valuations
with a proof by discrete convex analysis

Discrete convex analysis (DCA) offers a general framework of discrete optimization,
combining the ideas from matroid theory and convex analysis.  It has found applications
in many different areas including operations research, mathematical economics, and game
theory. The interaction between DCA and mathematical economics was initiated by
Danilov, Koshevoy, and Murota (2001), and accelerated by the crucial observation of Fujishige
and Yang (2003) that M-natural-concavity is equivalent to the gross substitutes (GS) property
of Kelso and Crawford (1982).

In this talk we show how an old question in economics was settled with
the DCA machinery. More concretely, we explain how the equivalence of the gross substitutes
condition to the strong no complementarities (SNC) condition of Gul and Stacchetti
(1999) can be proved with the use of the Fenchel-type duality theorem and the conjugacy
theorem in DCA.
The SNC condition means the multiple exchange property of a set function
f, saying that, for two subsets X and Y and a subset I of X-Y, there exists a subset J
of Y-X such that  f((X-I)+J) +f((Y-J)+I) is not smaller than f(X) + f(Y).

This talk is intended to offer a glimpse at a technical interaction
between DCA and economics.
No preliminary knowledge of DCA is required.


Past 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

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.