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.

Research

Research Interest: Bilevel Programming, Interdiction Problems, Integer Programming Games, Computational Complexity
Applications: Kidney Exchange Programs; Network observability with Phasor measurement unit (PMU).

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

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 de ned 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.

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.

M. Carvalho, C. Telha, M. Van Vyve, J. P. Pedroso, "Competitive uncapacitated lot-sizing game", International Journal of Production Economics, Volume 204, 148-159, October 2018.

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.

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, Volume 223, 11-23, February 2018.

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.

M. Carvalho, A. Lodi, J. P. Pedroso, A. Viana, "Nash Equilibria in the Two-Player Kidney Exchange Game", Mathematical Programming, Volume 161, Issue 1–2, 389–417, January 2017.

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.

A. Caprara, M. Carvalho, A. Lodi, G.J. Woeginger, "Bilevel knapsack with interdiction constraints", INFORMS Journal on Computing, Volume 28, Issue 2, 319-333, April 2016

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.

M. Carvalho, J. P. Pedroso, "Note on the Cournot and Stackelberg Competitions: is it worth to be the last playing?", Technical Report DCC-2015-01, DCC-FC & INESC, Universidade do Porto

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.

M. Carvalho, A. Lodi, J. P. Pedroso, A. Viana, "Two-Player Kidney Exchange Game", Poster at IPCO 2014

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.

A. Caprara, M. Carvalho, A. Lodi, G.J. Woeginger, "A Study on the Computational Complexity of the Bilevel Knapsack Problem", SIAM Journal on Optimization, Volume 24, Issue 2, 823-838, June 2014.

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.

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.

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

M. Carvalho, J.P. Pedroso, J. Saraiva, "Electricity Day-Ahead Markets: Computation of Nash Equilibria", Journal of Industrial and Management Optimization 11(3), 2015, 985-998.

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.

Follow @mxmmargarida

 

News

I am organizing the monthly seminars Comp4Med.

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

Office: 3387 pavillon André-Aisenstadt

Phone: 1-514-343-5941

 

Technical Reports

CERC

 

Affiliations

CERC in Data Science for Real-Time Decision-Making

CIRRELT

 

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

My python script to use djhero table as VJ

GitHub Repositories