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.
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)\).
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:
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\).
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.
The interrogatives I find interesting about MPGs can be distilled in 6 bullet points:
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 π