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.

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

M. Carvalho, A. Lodi, J. P. Pedroso, "Existence of Nash equilibria on integer programming games", IO2018 - Springer Proceedings in Mathematics and Statistics series, accepted.

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: Nash equilibria, Mixed integer programming game, Algorithmic game theory.

M. Carvalho, A. Lodi, P. Marcotte, "A polynomial algorithm for a continuous bilevel knapsack problem", submitted.

Keywords

Bilevel programming, Continuous knapsack problem, Polynomial time.

M. Carvalho, X. Klimentova, A. Viana, "Observability of power systems with optimal PMU placement", Computers & Operations Research, 2017.

Keywords

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

M. Carvalho, C. Telha, M. Van Vyve, J. P. Pedroso, "Competitive uncapacitated lot-sizing game", submitted.

Keywords

Cournot 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

Keywords

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

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

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"

International Workshop on Optimization Challenges in the Evolution of Energy Networks to Smart Grids, Coimbra, Oct 27, 2016: "Robust PMU Placement"

EURO 2016 Poznan, Poland, July 5th: "Nash equilibria in the kidney exchange game"

INESC TEC, CEGI, March 17th, I'll give a tutorial about "Bilevel programming"

GERAD, Montreal, Canada: "Bilevel and simultaneous integer programming games"

International Symposium on Mathematical Programming - ISMP2015 : "Bilevel Optimization in Game Theory"

Euro Mini Conference 2015: "Robust Kidney Exchange Program"

 

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