Margarida Carvalho was born in 1988 in Oporto.
Since her early years science has ignited her curiosity, particularly in the field of Mathematics.
She earned a degree in this field by the Faculty of Sciences of the University of Porto (FCUP).
At the beginning of 2009, she started her collaboration with the Department of Computer Science in the Neurosciences division.
Alongside the creative component that this research activity introduced in her curriculum, she developed her skills by enrolling in 2009 the Mathematical Engineering MA.
To accomplish her master thesis, she made research in applied game theory in the electricity market.
Since 2010 Margarida is working for INESC TEC.
In 2012, her first PhD year, Margarida visits the University of Bologna, hosted by DEI and supported by an FCT grant, where she investigated bilevel programming.
The first semester of 2014, Margarida visited CORE, Université catholique de Louvain, Belgium. She studied the generalization of the classic lot-sizing problem to the case with several decision-makers.
In April 2016, Margarida finished with distinction her Ph.D. in Computer Sciences and started a postdoctoral research position in the Center for Industrial Engineering and Management at INESC TEC, Porto.
In March 2017, Margarida started an IVADO Fellowship within the Canada Excellence Research Chair in Data Science for Real-Time Decision-Making in the Department of Mathematical and Industrial Engineering of the Polytechnique Montréal.
Research Interest: Bilevel Programming, Interdiction Problems, Integer Programming Games, Computational Complexity
Applications: Kidney Exchange Programs; Network observability with Phasor measurement unit (PMU).
M. Carvalho, A. Lodi, J. P. Pedroso, "Computing Nash equilibria for integer programming games", working paper.
AbstractIn this paper we explore the recently dened class of integer programming games. Two general methods to approximate an equilibrium are presented and enhanced in order to improve their practical eciency. The performance of our approaches is analyzed by testing them in a knapsack game and a competitive lot-sizing game.
KeywordsKeywords: Nash equilibria, Mixed integer programming game, Algorithmic game theory.
M. Carvalho, A. Lodi, J. P. Pedroso, "Existence of Nash equilibria on integer programming games", In: Vaz A., Almeida J., Oliveira J., Pinto A. (eds) Operational Research. APDIO 2017. Springer Proceedings in Mathematics & Statistics, 2018.
AbstractWe aim to investigate a new class of games, where each player’s set of strategies is a union of polyhedra. These are called integer programming games. Examples suitable to be modeled by an integer programming game are described motivating our work. We prove that it is a \Sigma_^2-complete problem to decide the existence of Nash equilibria and we provide sufficient conditions for an equilibrium to exist.
KeywordsKeywords: Integer programming games, Nash equilibria, Computational complexity.
KeywordsBilevel programming, Continuous knapsack problem, Polynomial time.
KeywordsNetwork observability, PMU, Combinatorial optimization, Bilevel programming, Cutting plane.
M. Carvalho, C. Telha, M. Van Vyve, J. P. Pedroso, "Competitive uncapacitated lot-sizing game", submitted.
KeywordsCournot Competition, Lot-Sizing Problem, Nash equilibria, Potential Game.
K. Glorie, M. Carvalho, M. Constantino, P. Bouman, A. Viana, "Robust Models for the Kidney Exchange Problem", working paper
KeywordsKidney Exchange, Robust Optimization, Integer Programming.
Ph.D in Computer Science
Thesis - Computation of equilibria on integer programming games.
Advisor: João Pedro Pedroso; Co-Advisor: Andrea Lodi.
Kidney exchange programs have been set in several countries within national, regional or hospital frameworks, to increase the possibility of kidney patients being transplanted. For the case of hospital programs, it has been claimed that hospitals would benefit if they collaborated with each other, sharing their internal pools and allowing transplants involving patients of different hospitals. This claim led to the study of multi-hospital exchange markets. We propose a novel direction in this setting by modeling the exchange market as an integer programming game. The analysis of the strategic behavior of the entities participating in the kidney exchange game allowed us to prove that the most rational game outcome maximizes the social welfare and that it can be computed in polynomial time.
We consider a Bilevel Integer Programming model that extends the classic 0--1 knapsack problem in a very natural way. The model describes a Stackelberg game where the leader's decision interdicts a subset of the knapsack items for the follower. As this interdiction of items substantially increases the difficulty of the problem, it prevents the application of the classical methods for bilevel programming and of the specialized approaches that are tailored to other bilevel knapsack variants. Motivated by the simple description of the model, by its complexity, by its economic applications, and by the lack of algorithms to solve it, we design a novel viable way for computing optimal solutions. Finally, we present extensive computational results that show the effectiveness of the new algorithm on instances from the literature and on randomly generated instances.
AbstractIn this brief note, a competition on a new product produced by two firms sharing a market is analyzed both from a Cournot and Stackelberg point of view. In contrast with classical models, setup costs are considered in the firms’ production costs, leading to ambiguities in their best response strategies. Our aim is to establish the different equilibria strategies that may arise from these two competition versions. Moreover, our goal is to open the discussion of whether it might be worth for a player to wait for the opponents to move, forcing a Stackelberg equilibrium to be played.
AbstractKidney exchange programs have been set in several countries within national, regional or hospital frameworks, to increase the possibility of kidney patients being transplanted. For the case of hospital programs, it has been claimed that hospitals would benefit if they collaborated with each other, sharing their internal pools and allowing transplants involving patients of different hospitals. This claim led to the study of multi-hospital exchange markets. We propose a novel direction in this setting by modeling the exchange market as an integer programming game. The analysis of the strategic behavior of the entities participating in the kidney exchange game allowed us to prove that the most rational game outcome maximizes the social welfare and that it can be computed in polynomial time.
AbstractWe analyze the computational complexity of three fundamental variants of the bilevel knapsack problem. All three variants are shown to be complete for the second level of the polynomial hierarchy. We also discuss the somewhat easier situation where the weight and profit coefficients in the knapsack problem are encoded in unary: two of the considered bilevel variants become solvable in polynomial time, whereas the third becomes NP-complete. Furthermore, we design a polynomial time approximation scheme for this third variant, whereas the other two variants cannot be approximated in polynomial time within any constant factor (assuming P≠NP).
AbstractWe consider a game where there is a separate market (for a single product) in each of a given set of discrete time periods. Each player can decide the quantity of product to place in each time period (market). Each player has her own production facility which is represented as an uncapacitated lot-sizing model (i.e. production incurs fixed cost and inventories are allowed). We show that this game is potential and always admits at least one pure Nash Equilib- rium. There are in general several such equilibria. When there are no variable production and inventory cost, we can compute one pure Nash Equilibrium in polynomial time. When there is only one period, it is NP-Hard to find an optimal pure Nash equilibrium (i.e. with respect ot a given objective function), but one can compute such an optimal equilibrium in pseudo-polynomial time.
A. Caprara, M. Carvalho, A. Lodi, G.J. Woeginger, "A Complexity and Approximability Study of the Bilevel Knapsack Problem", in M. Goemans, J. Correa, Eds., Integer Programming and Combinatorial Optimization - IPCO 2013, Lecture Notes in Computer Science 7801, Springer-Verlag, Berlin Heidelberg, 2013, 98-109.
Master in Mathematical Engineering
Thesis - Nash Equilibria: a Case Study in the Energy Market.
Advisor: João Pedro Pedroso; Co-Advisor: João Saraiva.
AbstractIn a restructured electricity sector, day-ahead markets can be modeled as a game where some players - the producers - submit their proposals. To analyze the companies' behavior we have used the concept of Nash equilibrium as a solution in these multi-agent interaction problems. In this paper, we present new and crucial adaptations of two well-known mechanisms, the adjustment process and the relaxation algorithm, in order to achieve the goal of computing Nash equilibria. The advantages of these approaches are highlighted and compared with those available in the literature.
Interview (in portuguese) Cadê Você?
My Ph.D. thesis was awarded the APDIO/ IO 2017 prize
I am a speaker in the 2017 Mixed Integer Programming Workshop: "An Integer Programming Game in Health-care"