Grant: Discovery Grants Program - Individual
Université de Montréal
$31,000.00
Game theory for decision-making
EF 2020-21
Résumé
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.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
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
2020
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:2-5
Partie
4
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.