Thursday, the 17th of February 2022, I defended my doctoral research on Mathematical Programming Games at Polytechnique. While my thesis is available here, I will try to condense in a few lines what are Mathematical Programming Games and why we should care for them.

In many decision-making settings, a selfish agent seeks to optimize its benefit given some situational constraints. Mathematically, the decision-maker’s task is often formulated as an optimization problem whose solution provides a prescriptive recommendation on the best decision. However, decision-making is rarely an individual task: each selfish decision-maker often interacts with other similarly self-interested decision-makers. This thesis discusses and proposes a novel perspective to capture the dynamics of multi-agent strategic decision-making involving multiple agents solving optimization problems. We explore the opportunities offered by the interplay of Mathematical Optimization – specifically Mixed-Integer Programming (MIP) – and Algorithmic Game Theory (AGT) by analyzing them through the lenses of a unified framework capable of integrating elements of the two disciplines. We introduce the taxonomy of Mathematical Programming Games (MPGs), simultaneous non-cooperative games where each agent decision problem is an optimization problem expressing a heteroge- neous and possibly complex set of constraints.

What is an MPG?

An MPG is essentially a simultaneous game among \(n\) players, where each of them solves the optimization problem:

\(\max_{x^i} \{ f^i(x^i,x^{-i}) : x^i \in \mathcal{X}^i \}\),

where \(f^i\) and \(\mathcal{X}^i\) are the payoff (objective function) and the set of moves of \(i\), respectively. With the notation \(x^i\) we denote the variables belonging to \(i\), while \(x^{-i}\) are the ones of the other \(n-1\) players, i.e., \((x^1,x^2,\dots,x^{i-1},x^{i+1},\dots,x^n)\).

Why?

The taxonomy of MPGs provides a bridge between Optimizers and (Algorithmic) Game Theorists by providing a unified framework to frame the strategic interaction.

The reasons behind this new taxonomy -- which can be similar to the one of "Nash Equilibrium Problems" -- are mainly 3:

• Actions representation. We implicitly represent each player's action space with a set \(\mathcal{X}^i\). The action space may be unbounded and contain infinitely or finitely many elements. This representation enables the understanding of the game even from a geometrical perspective. For instance, when for any \(i\) the set \(\mathcal{X}^i\) is a polyhedron and \(f(x^i,x^{-i})\) is a linear function in \(x^i\) (given the parameters \(x^{-i})\), each player is solving a (parametrized) linear program. As the vertices of \(\mathcal{X}^i\) are geometrically relevant for the simplex method, they are also relevant for the game: no rational player \(i\) would adopt a strategy in the interior of its polyhedron \(\mathcal{X}^i\) as no optimal solution to the \(i\)-th linear program lies in the interior of \(\mathcal{X}^i\).
• Intersecting objectives with Game Theory. We aim to build a language intersecting both game theory and mathematical programming elements. In this sense, our MPG definition is as broad as possible. We aim to extend the theoretical analysis on the efficiency of equilibria performed on standard Algorithmic Game Theory games (i.e., the price of stability and anarchy) to the realm of MPGs. Concurrently, we aim at providing theoretical and algorithmic frameworks to select equilibria in MPGs.
• Modeling requirements. Algorithmic Game Theory and mechanism design often change the game's structure or incentives to ensure one can efficiently compute equilibria with guaranteed efficiency properties (i.e., prices). However, this may not be the case in applications requiring an explicit optimization problem that captures the application's complexity. Representing the decision-makers' complex set of operational requirements through constraints of MPGs increases modelization fidelity: it may be the case that the application's requirements do not allow to simplify the model. Furthermore, the complexity associated with the model itself often translates into equivalently rich insights stemming from the game's equilibria.

How is this taxonomy different from the one of Nash Equilibrium Problems?

Most of the methods developed in Equilibrium Programming methods often assume \(\mathcal{X}^i\) has a specific structure, i.e., the players' feasible regions are continuous. In the broad definition of MPGs, we do not assume that computing equilibria should require any specific method or structure on any \(\mathcal{X}^i\).

Can you give some examples of MPGs?

My favorite example is an Integer Programming Game -- a game among players solving integer programs -- involving the two characters of Fairy 🧚🏼 and Wizard 🧙🏽‍♂️. The two want to open a convenience store in Magicville, where they live.

In order to decide which items to sell -- either \(x^1_1\) or \(x^1_2\) for Wizard and either \(x^2_1\) or \(x^2_2\) for Fairy -- they both solve a binary Knapsack problem. However, since their convenience store would be one in front of the other, strange things may happen when they both sell one item. For instance, the residents of Magicville may prefer to go to Wizard over Fairy for the first item, and vice versa. Thus, there are some interaction terms -- products of variables involving both players -- in their objective functions.

One possible solution to this game is the so-called Nash Equilibrium. In this case, Fairy and Wizard would both sell the first item -- i.e., \(x^1_1=x^2_1=1\) and \(x^1_2=x^2_2=0\) -- and live happy together.

Some open questions

The interrogatives I find interesting about MPGs can be distilled in 6 bullet points:

1. Can MPGs accurately model real-world problems?
2. How do different Nash equilibria compare in terms of efficiency (i.e., quality)?
3. How do we build efficient algorithms to compute and select (i.e., optimize!) such equilibria?
4. What are the theoretical properties of these algorithms?
5. What are the prescriptive insights that equilibria provide in real-world applications?
6. Can MPGs’ equilibria promote socially beneficial outcomes?

While we answer some of these questions in my thesis, that is just the tip of the iceberg. If at this point you are at least intrigued by MPGs, then I would suggest you browse through some slides here. And if you are motivated, skim through my thesis 👀