Portrait de Margarida Carvalho

Margarida Carvalho

Membre académique associé
Professeure adjointe, Université de Montréal, Département d'informatique et de recherche opérationnelle
Sujets de recherche
Équité algorithmique
IA et durabilité
Optimisation
Optimisation combinatoire
Théorie de la décision
Théorie des jeux
Site web
Google Scholar

Biographie

Margarida Carvalho est titulaire d'un baccalauréat et d'une maîtrise en mathématiques. Elle a obtenu un doctorat en informatique à l'Université de Porto, pour lequel elle a reçu le prix de la thèse EURO en 2018. La même année, elle est devenue professeure adjointe au Département d'informatique et de recherche opérationnelle de l'Université de Montréal, où elle occupe la Chaire de recherche FRQ-IVADO en science des données pour la théorie des jeux combinatoires.

Elle est une experte en recherche opérationnelle, notamment en optimisation combinatoire et en théorie algorithmique des jeux. Ses recherches sont motivées par des problèmes de prise de décision du monde réel impliquant l'interaction de plusieurs agents, tels que les programmes d'échange de reins, le choix des écoles et les marchés concurrentiels.

Étudiants actuels

Marylou Fauchard
Maîtrise recherche - UdeM
Co-superviseur⋅e :
Golnoosh Farnadi
marylou.fauchard@mila.quebec
William St-Arnaud
Doctorat - UdeM
Superviseur⋅e principal⋅e :
Golnoosh Farnadi
Nagisa Sugishita
Postdoctorat - UdeM

Publications

Capacity Expansion in the College Admission Problem
Federico Bobbio
Margarida Carvalho
Andrea Lodi
Alfredo Torrico
2021-01-01
arXiv.org (prépublication)
dblp.uni-trier.de
Multilevel Approaches for the Critical Node Problem
Andrea Baggio
Margarida Carvalho
Andrea Lodi
Andrea Tramontani
2021-01-01
Operational Research (publié)
doi.org
Multi-agent Assortment Optimization in Sequential Matching Markets
Alfredo Torrico
Margarida Carvalho
Andrea Lodi
2020-06-08
ArXiv (prépublication)
arxiv.org
arxiv.org
Provable Guarantees for General Two-sided Sequential Matching Markets
Alfredo Torrico
Margarida Carvalho
Andrea Lodi
Two-sided markets have become increasingly more important during the last years, mostly because of their numerous applications in housing, l… (voir plus)abor and dating. Consumer-supplier matching platforms pose several technical challenges, specially due to the trade-off between recommending suitable suppliers to consumers and avoiding collisions among consumers' preferences. In this work, we study a general version of the two-sided sequential matching model introduced by Ashlagi et al. (2019). The setting is the following: we (the platform) offer a menu of suppliers to each consumer. Then, every consumer selects, simultaneously and independently, to match with a supplier or to remain unmatched. Suppliers observe the subset of consumers that selected them, and choose either to match a consumer or leave the system. Finally, a match takes place if both the consumer and the supplier sequentially select each other. Each agent's behavior is probabilistic and determined by a regular discrete choice model. Our objective is to choose an assortment family that maximizes the expected cardinality of the matching. Given the computational complexity of the problem, we show several provable guarantees for the general model, which in particular, significantly improve the approximation factors previously obtained.
2020-06-08
arXiv.org (prépublication)
dblp.uni-trier.de
Electric Vehicles Equilibrium Model that Considers Queue Delay and Mixed Traffic
Nurit Oliker
Miguel F. Anjos
Margarida Carvalho
Emma Frejinger
Bernard Gendron
This study develops an equilibrium model for electric vehicles (EVs) that considers both queue delays in charging stations and flow dependen… (voir plus)t travel times. This is a user equilibrium model that accounts for travel, charging and queuing time in the path choice modelling of EVs and the complementary traffic. Waiting and service times in charging stations are represented by an m/m/k queuing system. The model considers multiple vehicle and driver classes, expressing different battery capacity, initial charge state and range anxiety level. Feasible paths are found for multiple classes given their limited travel range. A numerical application exemplifies the limitations of EVs assignment and their impact on flow distribution.
2020-01-01
(publié)
www.semanticscholar.org
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 … (voir plus)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.
2020-01-01
(publié)
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… (voir plus)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-14
arXiv.org (prépublication)
dblp.uni-trier.de
A polynomial algorithm for a continuous bilevel knapsack problem
Margarida Carvalho
Andrea Lodi
Patrice Marcotte
2018-03-01
Operations Research Letters (publié)
doi.org
Existence of Nash Equilibria on Integer Programming Games
Margarida Carvalho
Andrea Lodi
João Pedro Pedroso
2018-02-15
Springer Proceedings in Mathematics & Statistics (publié)
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… (voir plus)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.
2018-01-01
(publié)
www.semanticscholar.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-21
Mathematical Programming (publié)
doi.org