Research Interests

  • Nash equilibria
  • Algorithmic Game Theory
  • Bilevel Programming
  • Interdiction Problems
  • Integer Programming Games
  • Computational Complexity
  • Policy Making
  • Robust Optimization
  • Matchings on graphs

Applications

  • Kidney Exchange Programs
  • Cyber Security
  • Economic managerial insights
  • Network observability with Phasor measurement unit (PMU)

Publications

M. Carvalho, G. Dragotto, F. Feijoo, A. Lodi, S. Sankaranarayanan, When Nash Meets Stackelberg

Working paper, .

﹀ Show more

Abstract

We analyze Nash games played among leaders of Stackelberg games (NASP). We show it is Σp2-hard to decide if the game has a mixed-strategy Nash equilibrium (MNE), even when there are only two leaders and each leader has one follower. We provide a finite time algorithm with a running time bounded by O(22n) which computes MNEs for NASP when it exists and returns infeasibility if no MNE exists. We also provide two ways to improve the algorithm which involves constructing a series of inner approximations (alternatively, outer approximations) to the leaders' feasible region that will provably obtain the required MNE. Finally, we test our algorithms on a range of NASPs arising out of a game in the energy market, where countries act as Stackelberg leaders who play a Nash game, and the domestic producers act as the followers.

Keywords

  • Nash Equilibria
  • Stackelberge Games
  • Algorithmic Game Theory
  • Computational Complexity.

J. Oliveira, M. Carvalho, D. M. Nogueira, M. Coimbra, Segmentation and Optimal Region Selection of Physiological Signals using Deep Neural Networks and Combinatorial Optimization

Working paper,

﹀ Show more

Abstract

Physiological signals, such as the electrocardiogram and the phonocardiogram are very often corrupted by noisy sources. Usually, artificial intelligent algorithms analyze the signal regardless of its quality. On the other hand, physicians use a completely orthogonal strategy. They do not assess the entire recording, instead they search for a segment where the fundamental and abnormal waves are easily detected, and only then a prognostic is attempted.

Inspired by this fact, a new algorithm that automatically selects an optimal segment for a post-processing stage, according to a criteria defined by the user is proposed. In the process, a Neural Network is used to compute the output state probability distribution for each sample. Using the aforementioned quantities, a graph is designed, whereas state transition constraints are physically imposed into the graph and a set of constraints are used to retrieve a subset of the recording that maximizes the likelihood function, proposed by the user.

The developed framework is tested and validated in two applications. In both cases, the system performance is boosted significantly, e.g in heart sound segmentation, sensitivity increases 2.4% when compared to the standard approaches in the literature.

Keywords

  • Biosignals
  • Deep Neural Network
  • Integer programming
  • Longest path problem

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

INFORMS Journal on Computing, . Accepted paper.

﹀ Show more

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

A. Baggio, M. Carvalho, A. Lodi, A. Tramontani, Multilevel Approaches for the Critical Node Problem

Operations Research, . Accepted paper.

﹀ Show more

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. ElAraby, G. Wolf, M. Carvalho, Identifying Critical Neurons in ANN Architectures using Mixed Integer Programming

Working paper,

﹀ Show more

Abstract

We introduce a novel approach to optimize the architecture of deep neural networks by identifying critical neurons and removing non-critical ones. The proposed approach utilizes a mixed integer programming (MIP) formulation of neural models which includes a continuous importance score computed for each neuron in the network. The optimization in MIP solver minimizes the number of critical neurons (i.e., with high importance score) that need to be kept for maintaining the overall accuracy of the model. Further, the proposed formulation generalizes the recently considered lottery ticket optimization by identifying multiple "lucky" sub-networks resulting in optimized architecture that not only perform well on a single dataset, but also generalize across multiple ones upon retraining of network weights. Finally, the proposed framework provides significant improvement in scalability of automatic sparsification of deep network architectures compared to previous attempts. We validate the performance and generalizability of our approach on MNIST, Fashion-MNIST, and CIFAR-10 datasets, using three different neural networks: LeNet 5 and two ReLU fully connected models.

Keywords

  • Mixed Integer Programming
  • Neural Networks
  • Critical Neuron

M. Carvalho, A. Lodi, Game theoretical analysis of Kidney Exchange Programs

Working paper,

﹀ Show more

Abstract

The goal of a kidney exchange program (KEP) is to maximize number of transplants within a pool of incompatible patient-donor pairs by exchanging donors. A KEP can be modelled as a maximum matching problem in a graph. A KEP between incompatible patient-donor from pools of several hospitals, regions or countries has the potential to increase the number of transplants. These entities aim is to maximize the transplant benefit for their patients, which can lead to strategic behaviours. Recently, this was formulated as a non-cooperative two-player game and the game solutions (equilibria) were characterized when the entities objective function is the number of their patients receiving a kidney.

In this paper, we generalize these results for N-players and discuss the impact in the game solutions when transplant information quality is introduced. Furthermore, the game theory model is analyzed through computational experiments on instances generated through the Canada Kidney Paired Donation Program. These experiments highlighting the importance of using the concept of Nash equilibrium, as well as, the anticipation of the necessity to further research for supporting police makers once measures on transplant quality are available.

Keywords

  • Kidney exchange program
  • Non-cooperativem Nash Equilibria
  • Social Welfare
  • Maximum Matching
  • Graft survival

G. Farnadi, B. Babaki, M. Carvalho, Enhancing Fairness in Kidney Exchange Program by Ranking Solutions

Fair ML for Health, NeurIPS 2019 Workshop,

﹀ Show more

Abstract

Algorithmic decision making is being used with increasing frequency in domains that affect peoples’ lives. In the health-care domain, kidney exchange programs are a notable example of such applications. These programs aim to match incompatible patient-donor pairs and thereby allow some of them to receive a kidney transplant. Since it is often impossible to have everyone receive a transplant, usually a solution that maximizes the overall benefit of patients is selected. When the objective is to maximize the number of transplants, there can be several optimal solutions. Since the way that one of these solutions is selected has a major effect on the lives of the patients who are declined a transplant, special care must be taken to ensure fairness in this process.

We propose a selection method based on enumeration of all optimal solutions. We formulate this enumeration task as a constraint satisfaction problem. We also investigate the differences between the optimal solutions and introduce ranking methods to select a solution that satisfies certain fairness criteria. Preliminary experiments on synthetic graphs show that some patient groups having certain physiological traits are underrepresented in the solutions. The experiments also suggest that our fairness criteria can increase the chances of such patients for receiving a transplant.

M. Carvalho, A. Lodi, J. P. Pedroso, Computing Nash equilibria for integer programming games

Working paper, .

﹀ Show more

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

  • Nash equilibria
  • Mixed integer programming game
  • Algorithmic game theory

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

International Journal of Production Economics, Volume 204, 148-159, .

﹀ Show more

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, X. Klimentova, A. Viana Observability of power systems with optimal PMU placement

Computers & Operations Research, Volume 96, 330-349, .

﹀ Show more

Keywords

  • Network observability
  • PMU
  • Combinatorial optimization
  • Bilevel programming
  • Cutting plane

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

Operations Research Letters, Volume 46, Issue 2, 185-188, .

﹀ Show more

Keywords

  • Bilevel programming
  • Continuous knapsack problem
  • Polynomial time

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, . See complementary note

﹀ Show more

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

  • Integer programming games
  • Nash equilibria
  • Computational complexity

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

﹀ Show more

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

﹀ Show more

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 .

﹀ Show more

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

﹀ Show more

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

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

17th Aussois Combinatorial Optimization Workshop 2013 - Bilevel Knapsack with interdiction constraints

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), , 985-998.

﹀ Show more

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.

Ph.D in Computer Science

Computation of equilibria on integer programming games

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

Master in Mathematical Engineering

Nash Equilibria: a Case Study in the Energy Market.

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