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

Maxine Dussault
Maîtrise recherche - UdeM
Superviseur⋅e principal⋅e :
Guy Wolf
Github
LinkedIn
Marylou Fauchard
Maîtrise recherche - UdeM
Co-superviseur⋅e :
Golnoosh Farnadi
Francesco Morri
Postdoctorat - Polytechnique
Co-superviseur⋅e :
Quentin Cappart
Site web
Github
Google Scholar
William St-Arnaud
Doctorat - UdeM
Superviseur⋅e principal⋅e :
Golnoosh Farnadi
Nagisa Sugishita
Postdoctorat - HEC

Publications

Penalties and Rewards for Fair Learning in Paired Kidney Exchange Programs
Margarida Carvalho
Alison Caulfield
Yi Lin
Adrian Vetta
A kidney exchange program, also called a kidney paired donation program, can be viewed as a repeated, dynamic trading and allocation mechani… (voir plus)sm. This suggests that a dynamic algorithm for transplant exchange selection may have superior performance in comparison to the repeated use of a static algorithm. We confirm this hypothesis using a full scale simulation of the Canadian Kidney Paired Donation Program: learning algorithms, that attempt to learn optimal patient-donor weights in advance via dynamic simulations, do lead to improved outcomes. Specifically, our learning algorithms, designed with the objective of fairness (that is, equity in terms of transplant accessibility across cPRA groups), also lead to an increased number of transplants and shorter average waiting times. Indeed, our highest performing learning algorithm improves egalitarian fairness by 10% whilst also increasing the number of transplants by 6% and decreasing waiting times by 24%. However, our main result is much more surprising. We find that the most critical factor in determining the performance of a kidney exchange program is not the judicious assignment of positive weights (rewards) to patient-donor pairs. Rather, the key factor in increasing the number of transplants, decreasing waiting times and improving group fairness is the judicious assignment of a negative weight (penalty) to the small number of non-directed donors in the kidney exchange program.
2023-12-30
Web and Internet Economics (publié)
doi.org
arxiv.org
When Nash Meets Stackelberg
Margarida Carvalho
Gabriele Dragotto
Felipe Feijoo
Andrea Lodi
Sriram Sankaranarayanan
2023-12-21
Management Science (publié)
doi.org
arxiv.org
Capacity Planning in Stable Matching: An Application to School Choice
Federico Bobbio
Margarida Carvalho
Andrea Lodi
Ignacio Rios
Alfredo Torrico
Centralized mechanisms are becoming the standard approach to solve several assignment problems. Examples include the allocation of students … (voir plus)to schools (school choice), high-school graduates to colleges, residents to hospitals and refugees to cities. In most of these markets, a desirable property of the assignment is stability, which guarantees that no pair of agents has incentive to circumvent the matching. Using school choice as our matching market application, we introduce the problem of jointly allocating a school capacity expansion and finding the best stable matching for the students in the expanded market. We analyze theoretically the problem, focusing on the trade-off behind the multiplicity of student-optimal assignments, and the problem complexity. Since the theoretical intractability of the problem precludes the adaptation of classical approaches to solve it efficiently, we generalize existent mathematical programming formulations of stability constraints to our setting. These generalizations result in integer quadratically-constrained programs, which are computationally hard to solve. In addition, we propose a novel mixed-integer linear programming formulation that is exponentially-large on the problem size. We show that the stability constraints can be separated in linear time, leading to an effective cutting-plane method. We evaluate the performance of our approaches in a detailed computational study, and we find that our cutting-plane method outperforms mixed-integer programming solvers applied to existent formulations extended to our problem setting. We also propose two heuristics that are effective for large instances of the problem. Finally, we use the Chilean school choice system data to demonstrate the impact of capacity planning under stability conditions. Our results show that each additional school seat can benefit multiple students. On the one hand, we can focus on access by prioritizing extra seats that benefit previously unassigned students; on the other hand, we can focus on merit by allocating extra seats that benefit several students via chains of improvement. These insights empower the decision-maker in tuning the matching algorithm to provide a fair application-oriented solution.
2023-07-06
Proceedings of the 24th ACM Conference on Economics and Computation (publié)
doi.org
Identifying Critical Neurons in ANN Architectures using Mixed Integer Programming
Mostafa Elaraby
Guy Wolf
Margarida Carvalho
2023-05-22
Integration of Constraint Programming, Artificial Intelligence, and Operations Research (publié)
doi.org
arxiv.org
Optimization of the location and design of urban green spaces
Caroline Leboeuf
Margarida Carvalho
Yan Kestens
Benoit Thierry
2023-03-12
ArXiv (prépublication)
doi.org
arxiv.org
A theoretical and computational equilibria analysis of a multi-player kidney exchange program
Margarida Carvalho
Andrea Lodi
2023-01-31
European Journal of Operational Research (publié)
doi.org
arxiv.org
Optimising Electric Vehicle Charging Station Placement using Advanced Discrete Choice Models
Steven Lamontagne
Margarida Carvalho
Emma Frejinger
Bernard Gendron
Miguel F. Anjos
Ribal Atallah
D'epartement d'informatique et de recherche op'erationnelle
U. Montr'eal
S. O. Mathematics
U. Edinburgh
Institut de Recherche d'Hydro-Qu'ebec
We present a new model for finding the optimal placement of electric vehicle charging stations across a multi-period time frame so as to max… (voir plus)imise electric vehicle adoption. Via the use of advanced discrete choice models and user classes, this work allows for a granular modelling of user attributes and their preferences in regard to charging station characteristics. Instead of embedding an analytical probability model in the formulation, we adopt a simulation approach and pre-compute error terms for each option available to users for a given number of scenarios. This results in a bilevel optimisation model that is, however, intractable for all but the simplest instances. Using the pre-computed error terms to calculate the users covered by each charging station allows for a maximum covering model, for which solutions can be found more efficiently than for the bilevel formulation. The maximum covering formulation remains intractable in some instances, so we propose rolling horizon, greedy, and GRASP heuristics to obtain good quality solutions more efficiently. Extensive computational results are provided, which compare the maximum covering formulation with the current state-of-the-art, both for exact solutions and the heuristic methods. Keywords: Electric vehicle charging stations, facility location, integer programming, discrete choice models, maximum covering
2022-12-31
INFORMS J. Comput. (publié)
doi.org
arxiv.org
Capacity Variation in the Many-to-one Stable Matching
Federico Bobbio
Margarida Carvalho
Andrea Lodi
Alfredo Torrico
2022-05-02
ArXiv (prépublication)
doi.org
arxiv.org
Computing Nash Equilibria for Integer Programming Games
Margarida Carvalho
Andrea Lodi
João Pedro Pedroso
The recently defined class of integer programming games (IPG) models situations where multiple self-interested decision makers interact, wit… (voir plus)h their strategy sets represented by a finite set of linear constraints together with integer requirements. Many real-world problems can suitably be fit in this class, and hence anticipating IPG outcomes is of crucial value for policy makers and regulators. Nash equilibria have been widely accepted as the solution concept of a game. Consequently, their computation provides a reasonable prediction of the games outcome. In this paper, we start by showing the computational complexity of deciding the existence of a Nash equilibrium for an IPG. Then, using sufficient conditions for their existence, we develop two general algorithmic approaches that are guaranteed to approximate an equilibrium under mild conditions. We also showcase how our methodology can be changed to determine other equilibria definitions. The performance of our methods is analyzed through computational experiments in a knapsack game, a competitive lot-sizing game, and a kidney exchange game. To the best of our knowledge, this is the first time that equilibria computation methods for general integer programming games have been designed and computationally tested.
2021-12-31
European Journal of Operational Research (publié)
doi.org
arxiv.org
ZERO: Playing Mathematical Programming Games
Gabriele Dragotto
S. Sankaranarayanan
Margarida Carvalho
Andrea Lodi
2021-11-14
ArXiv (prépublication)
arxiv.org
arxiv.org
The Cut and Play Algorithm: Computing Nash Equilibria via Outer Approximations
Margarida Carvalho
Gabriele Dragotto
Andrea Lodi
Sriram Sankaranarayanan
We introduce the Cut-and-Play, an efficient algorithm for computing equilibria in simultaneous non-cooperative games where players solve non… (voir plus)convex and possibly unbounded optimization problems. Our algorithm exploits an intrinsic relationship between the equilibria of the original nonconvex game and the ones of a convexified counterpart. In practice, Cut-and-Play formulates a series of convex approximations of the original game and refines them with techniques from integer programming, for instance, cutting planes and branching operations. We test our algorithm on two families of challenging nonconvex games involving discrete decisions and bilevel programs, and we empirically demonstrate that it efficiently computes equilibria and outperforms existing game-specific algorithms.
2021-11-09
ArXiv (prépublication)
arxiv.org
arxiv.org
Individual Fairness in Kidney Exchange Programs
Golnoosh Farnadi
William St-Arnaud
Behrouz Babaki
Margarida Carvalho
Kidney transplant is the preferred method of treatment for patients suffering from kidney failure. However, not all patients can find a dono… (voir plus)r which matches their physiological characteristics. Kidney exchange programs (KEPs) seek to match such incompatible patient-donor pairs together, usually with the main objective of maximizing the total number of transplants. Since selecting one optimal solution translates to a decision on who receives a transplant, it has a major effect on the lives of patients. The current practice in selecting an optimal solution does not necessarily ensure fairness in the selection process. In this paper, the existence of multiple optimal plans for a KEP is explored as a mean to achieve individual fairness. We propose the use of randomized policies for selecting an optimal solution in which patients' equal 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. The advantages of our proposed method over the common practice of using the optimal solution obtained by a solver are stressed through computational experiments. Our methodology enables decision makers to fully control KEP outcomes, overcoming any potential bias or vulnerability intrinsic to a deterministic solver.
2021-05-17
AAAI Conference on Artificial Intelligence (publié)
doi.org