Grant: Discovery Grants Program - Individual
Université de Montréal
$31,000.00
Game theory for decision-making
FY 2021-22
Summary
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.
Program
Discovery Grants Program - Individual
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2019-04557
Name nom
da Silva Carvalho, Maria
Department département
Department of Computer Science and Operations Research
Organization id
63
Institution établissement
Université de Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2021
Competition year année de concours
2019
Award amount
31000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1509
Committee name en
Civil, Industrial and Systems Engineering
Committee name fr
Génie civil, industriel et des systèmes
Area of application code
1100
Area of application group en
Health, education and social services
Area of application group fr
Santé publique, éducation et services sociaux
Area of application en
Health, education and social services
Area of application fr
Santé publique, éducation et services sociaux
Research subject code
1601
Research subject group en
Industrial engineering
Research subject group fr
Génie industriel
Research subject en
Operations research and management science
Research subject fr
Recherche opérationnelle et science de la gestion
Installment
inst:3
Partie
1
Nb partie
5
Application title
Game theory for decision-making
Keyword
NSERC
Application summary
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.