Game theory for decision-making

点击翻译按钮获取中文摘要

Many real-world decision processes involve the interaction of competing decision makers. Such situations fall in two fields: (1) Game Theory, with decision makers being called players; and (2) Mathematical Programming, with players aiming to optimize their individual outcome (payoff). Integer programming games (IPGs) is a recently defined class of games that brings together these two fields: it models situations where each player's goal is described through a mathematical optimization program whose payoff depends on the competitors. Furthermore, this framework allows one to encode discrete decisions that are inherent to practical problems. There is a striking difference between IPGs and most of the game theory literature. In general, the literature focus in games where: (1) each player's optimization problem is convex, or (2) all possible game outcomes are explicitly enumerated in the input, the so-called normal-form games. The goal of our research is to tackle non-cooperative IPGs. In specific, we aim to determine what are the most rational strategies that the players can select, the so-called equilibrium strategies. Understanding integer programming games is of crucial importance as this class enables us to properly mirror practical situations where different self-interested entities interact. For example, defender-attacker interactions in the context of homeland security, transplant programs (markets) across countries that aim to optimize the benefit of their own patients, production planning of different firms competing in the same market, to name a few. By investigating the development of algorithms to compute the games' equilibria one can: (1) classify the problem complexity and, consequently, establish hypothesis on the realism of players adopting an equilibrium; (2) generalize game theory results to this broader class of games and, simultaneously, advance on mathematical programming tools; (3) propose policy changes to repair ongoing games, by re-designing games with more "convenient equilibria". The ultimate goal of this research is to study beyond static games and move forward to dynamic and incomplete-information games. Such investigation has the potential to suggest more transparent policies, incentive progress through adequate game rules for competition, and accomplish social benefits.