## Short Bio

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.

In August 2018, Margarida became an assistant professor in the Department of Computer Science and Operations Research at University of Montreal. She currently holds a FRQ–IVADO Research Chair in Data Science for Combinatorial Game Theory.

## Research

Research Interest: Bilevel Programming, Interdiction Problems, Integer Programming Games, Computational Complexity

Applications: Kidney Exchange Programs; Network observability with Phasor measurement unit (PMU).

M. Carvalho, X. Klimentova, K. Glorie, A. Viana, M. Constantino, "Robust Models for the Kidney Exchange Problem", working paper.

## Abstract

Kidney exchange programs enable transplants between incompatible donor-patient pairs: a set of pairs is chosen in such a way that each selected patient receives a kidney from a compatible donor from another pair in the set. Pairs involved in the exchanges are then notified and more accurate crossmatch tests are performed. These tests may reveal incompatibilities, preventing a planned exchange from proceeding. Furthermore, pairs may dropout of the program before being transplanted. In this paper we study the case in which, if incompatibilities are discovered or a pair withdraws from the program, a new set of pairs may be selected. The new set should be as close as possible to the initial set in order to minimize the material and emotional costs of the changes. Various recourse policies that determine the allowed post-matching actions are proposed. For each recourse policy, a robust model is developed. Besides the development of a novel adjustable robust optimization model, our contribution includes techniques to solve exactly the optimization problems at hand and their validation through computational experiments.## Keywords

Kidney Exchange, Robust Optimization, Integer Programming.M. Carvalho, A. Lodi, J. P. Pedroso, "Computing Nash equilibria for integer programming games", working paper.

## Abstract

In this paper we explore the recently defined class of integer programming games. Two general methods to approximate an equilibrium are presented and enhanced in order to improve their practical efficiency. The performance of our approaches is analyzed by testing them in a knapsack game and a competitive lot-sizing game.## Keywords

Keywords: Nash equilibria, Mixed integer programming game, Algorithmic game theory.A. Baggio, M. Carvalho, A. Lodi, A. Tramontani, "Multilevel Approaches for the Critical Node Problem", 2018. working paper.

## Abstract

In recent years, a lot of effort has been dedicated to develop strategies to defend networks against possible cascade failures or malicious viral attacks. In particular, many results rely on two different viewpoints. On the one hand, network safety is investigated from a preventive perspective. In this paradigm, for a given network, the goal is to modify its structure, in order to minimize the propagation of failures. On the other hand, blocking models have been proposed for scenarios where the attack has already taken place. In this case, a harmful spreading process is assumed to propagate through the network with particular dynamics, allowing some time for an effective defensive reaction. In this work, we combine these two perspectives. More precisely, following the framework Defender-Attacker-Defender, we consider a model of prevention, attack, and damage containment using a three-stage, sequential game. Thus, we assume the defender not only to be able to adopt preventive strategies but also to defend the network after an attack takes place. Assuming that the attacker will act optimally, we want to chose a defensive strategy for the first stage that would minimize the total damage to the network in the end of the third stage. Our contribution consists of considering this problem as a trilevel Mixed-Integer Program and design an exact algorithm for it based on tools developed for multilevel programming.## Keywords

Multilevel Programming, Critical Node Problem, Firefighter Problem, Mixed-Integer Programming, Defender-Attacker-Defender.## Abstract

We study the strategical behavior of firms facing a lot-sizing problem with Cournot competition. Each player is a firm with her own production facility, modeled as an uncapacitated lot-sizing problem ({\ie}, production incurs set-up and variable costs and inventories are allowed). A Cournot competition is played in each time period (market) with each player deciding the quantity of product to place on it. The market price of that product in each time period depends on the total quantity placed in the market. We show that this is a potential game with possibly multiple pure Nash equilibria. We then investigate the plausibility of these equilibria to predict the game outcome by evaluating the difficulty of computing them. If the game has a single period, we prove that an equilibrium can be found in polynomial time, but it is weakly NP-hard to find an optimal pure Nash equilibrium (with respect to a given equilibrium refinement). If the game has no variable production and inventory costs, we prove that a pure Nash equilibrium can be computed in polynomial time.## Keywords

Cournot Competition, Lot-Sizing Problem, Nash equilibria, Potential Game.## Keywords

Network observability, PMU, Combinatorial optimization, Bilevel programming, Cutting plane.## Keywords

Bilevel programming, Continuous knapsack problem, Polynomial time.## Abstract

We 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.## Keywords

Keywords: Integer programming games, Nash equilibria, Computational complexity.## Ph.D in Computer Science

Thesis - Computation of equilibria on integer programming games.

Advisor: João Pedro Pedroso; Co-Advisor: Andrea Lodi.

## Abstract

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.

## Abstract

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.

## Abstract

In 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.## Abstract

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.## Abstract

We 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).International Workshop on Lot Sizing 2014 - Competitive uncapacitated lot-sizing game

## Abstract

We 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.17th Aussois Combinatorial Optimization Workshop 2013 - Bilevel Knapsack with interdiction constraints

## Master in Mathematical Engineering

Thesis - Nash Equilibria: a Case Study in the Energy Market.

Advisor: João Pedro Pedroso; Co-Advisor: João Saraiva.

Conference ALIO EURO 2011 - Nash Equilibria in Electricity Markets

Technical Report 2012 - Equilibria on the Day-Ahead Electricity Market

## Abstract

In 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.

## News

FRQ–IVADO Research Chair in Data Science for Combinatorial Game Theory.

Interview (in french) La théorie des jeux à la rescousse des stratégies de production.

I am organizing the monthly seminars Journal Club.

I was awarded the Prémios Novos 2018: CIÊNCIA.

I was awarded the EURO Doctoral Dissertation Award 2018. See Press.

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"

## Contact

I aim at promoting an inclusive and diverse group in my research program. Thus, I invite and encourage anyone that shares the same research interests to contact me. I am looking for students.

Office: 3387 pavillon André-Aisenstadt

Phone: 1-514-343-5941

carvalho[at]iro[dot]umontreal[dot]ca

## Technical Reports

CERC

## Affiliations

CERC in Data Science for Real-Time Decision-Making

## Things that keep me busy in the spare time

Transparência Hackday: playing with names presented to Instituto dos Registos e do Notariado in 2014

My python script for Secret Santa (in portuguese Amigo Secreto)

My python script to process Italian earthquakes data