Portrait of Margarida Carvalho

Margarida Carvalho

Associate Academic Member
Assistant Professor, Université de Montréal, Department of Computer Science and Operations Research
Research Topics
AI and Sustainability
Algorithmic Fairness
Combinatorial Optimization
Decision Theory
Game Theory
Optimization
Website
Google Scholar

Biography

Margarida Carvalho holds a bachelor’s and master’s degree in mathematics. She completed her PhD in computer science at the University of Porto, for which she received the 2018 EURO Doctoral Dissertation Award.

In 2018, Carvalho was appointed assistant professor in the Department of Computer Science and Operations Research at Université de Montréal, where she holds the FRQ-IVADO Research Chair in Data Science for Combinatorial Game Theory.

She is an expert in operations research, in particular, combinatorial optimization and algorithmic game theory. Her research is motivated by real-world decision-making problems that involve the interaction of multiple agents, such as kidney exchange programs, school choice and competitive markets.

Current Students

Marylou Fauchard
Master's Research - Université de Montréal
Co-supervisor :
Golnoosh Farnadi
William St-Arnaud
PhD - Université de Montréal
Principal supervisor :
Golnoosh Farnadi
Nagisa Sugishita
Postdoctorate - HEC Montréal

Publications

Fairness in Kidney Exchange Programs through Optimal Solutions Enumeration
Golnoosh Farnadi
Behrouz Babaki
Margarida Carvalho
Not all patients who need kidney transplant can find a donor with compatible characteristics. Kidney exchange programs (KEPs) seek to match … (see more)such incompatible patient-donor pairs together, usually with the objective of maximizing the total number of transplants. We propose a randomized policy for selecting an optimal solution in which patients’ equity of opportunity to receive a transplant is promoted. Our approach gives rise to the problem of enumerating all optimal solutions, which we tackle using a hybrid of constraint programming and linear programming. We empirically demonstrate the advantages of our proposed method over the common practice of using the first optimal solution obtained by a solver.
2019-12-31
(published)
www.semanticscholar.org
Nash Games Among Stackelberg Leaders
Margarida Carvalho
Gabriele Dragotto
Felipe Feijoo
Andrea Lodi
Sriram Sankaranarayanan
We analyze Nash games played among leaders of Stackelberg games (NASP). We show it is Σ p 2 - hard to decide if the game has a mixed-strate… (see more)gy Nash equilibrium (MNE), even when there are only two leaders and each leader has one follower. We provide a finite time algorithm with a running time bounded by O (2 2 n ) which computes MNEs for NASP when it exists and returns infeasibility if no MNE exists. We also provide two ways to improve the algorithm which involves constructing a series of inner approximations (alternatively, outer approximations) to the leaders’ feasible region that will provably obtain the required MNE. Finally, we test our algorithms on a range of NASPs arising out of a game in the energy market, where countries act as Stackelberg leaders who play a Nash game, and the domestic producers act as the followers.
2019-10-13
arXiv.org (preprint)
dblp.uni-trier.de
Existence of Nash Equilibria on Integer Programming Games
Margarida Carvalho
Andrea Lodi
João Pedro Pedroso
2018-02-14
Springer Proceedings in Mathematics & Statistics (published)
doi.org
Nash equilibria for integer programming games
Margarida Carvalho
Andrea Lodi
João Pedro Pedroso
In this paper, we develop algorithmic approaches for a recently defined class of games, the integer programming games. Two general methods t… (see more)o approximate an equilibrium are presented and enhanced in order to improve their practical efficiency. Their performance is analysed through computational experiments in a knapsack game and a competitive lot-sizing game. To the best of our knowledge, this is the first time that equilibria computation methods for general integer programming games are build and computationally tested.
2017-12-31
(published)
www.semanticscholar.org
A polynomial algorithm for a continuous bilevel knapsack problem.
Margarida Carvalho
Andrea Lodi
Patrice Marcotte
2017-12-31
Operations Research Letters (published)
doi.org
Nash equilibria in the two-player kidney exchange game
Margarida Carvalho
Andrea Lodi
João Pedro Pedroso
Ana Luiza D'ávila Viana
2016-04-20
Mathematical Programming (published)
doi.org