Abstract

In this work, we concentrate on the problem of finding a set of neurons in a trained neural network whose pruning leads to a marginal loss in accuracy. To this end, we introduce Optimizing ANN Architectures using Mixed-Integer Programming (OAMIP) to identify critical neurons and prune non-critical ones. The proposed OAMIP uses a Mixed-Integer Program (MIP) to assign importance scores to each neuron in deep neural network architectures. The impact of simultaneous neuron pruning on the main learning tasks guides the neurons' scores. By carefully devising the objective function of the MIP, we drive the solver to minimize the number of critical neurons (i.e., with high importance score) that maintain the overall accuracy of the trained neural network. Our formulation identifies optimized sub-network architectures that generalize across different datasets, a phenomenon known as lottery ticket optimization. This optimized architecture not only performs well on a single dataset but also generalizes across multiple ones upon retraining of network weights. Additionally, we present a scalable implementation of our pruning methodology by decoupling the importance scores across layers using auxiliary networks. Finally, we validate our approach experimentally, showing its ability to generalize on different datasets and architectures.

Abstract

The recent promotion of sustainable urban planning combined with a growing need for public interventions to improve well-being and health have led to an increased collective interest for green spaces in and around cities. In particular, parks have proven a wide range of benefits in urban areas. This also means inequities in park accessibility may contribute to health inequities. In this work, we showcase the application of classic tools from Operations Research to assist decision-makers to improve parks' accessibility, distribution and design. Given the context of public decision-making, we are particularly concerned with equity and environmental justice, and are focused on an advanced assessment of users' behavior through a spatial interaction model. We present a two-stage fair facility location and design model, which serves as a template model to assist public decision-makers at the city-level for the planning of urban green spaces. The first-stage of the optimization model is about the optimal city-budget allocation to neighborhoods based on a data exposing inequality attributes. The second-stage seeks the optimal location and design of parks for each neighborhood, and the objective consists of maximizing the total expected probability of individuals visiting parks. We show how to reformulate the latter as a mixed-integer linear program. We further introduce a clustering method to reduce the size of the problem and determine a close to optimal solution within reasonable time. The model is tested using the case study of the city of Montreal and comparative results are discussed in detail to justify the performance of the model.

Abstract

A main aim of kidney exchange programs (KEPs) is to maximize the number of transplants within a pool of incompatible patient-donor pairs by exchanging donors. A KEP involving pairs from pools of several hospitals, regions, or countries has the potential to increase the number of transplants. These entities may behave strategically and strive to maximize the transplant benefit for their patients. Recently, a decentralized non-cooperative game was formulated to model this situation, and the game solutions (equilibria) for the 2-player case were characterized when each player's utility is the number of her patients receiving a kidney and exchanges are restricted to pairwise.

In this paper, we generalize the result on the existence of social welfare equilibra for $N$-players and discuss the impact in the game solutions when transplant information quality is introduced, changing the players' utilities. Furthermore, the game theory model is analyzed through computational experiments on instances generated by leveraging data of the Canadian Kidney Paired Donation Program. These experiments highlight the importance of using the concept of Nash equilibrium, as well as, the need of further research to assist policy makers once measures on transplant quality are available.

Abstract

The network pricing problem (NPP) is a bilevel problem, where the leader optimizes its revenue by deciding on the prices of certain arcs in a graph, while expecting the followers (also known as the commodities) to choose a shortest path based on those prices. In this paper, we investigate the complexity of the NPP with respect to two parameters: the number of tolled arcs, and the number of commodities. We devise a simple algorithm showing that if the number of tolled arcs is fixed, then the problem can be solved in polynomial time with respect to the number of commodities. In contrast, even if there is only one commodity, once the number of tolled arcs is not fixed, the problem becomes NP-hard. We characterize this asymmetry in the complexity with a novel property named strong bilevel feasibility. Finally, we describe an algorithm to generate valid inequalities to the NPP based on this property, accommodated with numerical results to demonstrate its effectiveness in solving the NPP with a high number of commodities.

Abstract

The recently-defined class of integer programming games (IPG) models situations where multiple self-interested decision makers interact with their strategy sets represented by a finite set of linear constraints together with integer requirements. Many real-world problems can suitably be cast in this way, hence anticipating IPG outcomes is of crucial value for policy makers. Nash equilibria have been widely accepted as the solution concept of a game. Thus, their computation provides a reasonable prediction of games outcome. In this paper, we start by showing the computational complexity of deciding the existence of a Nash equilibrium for an IPG. Then, using sufficient conditions for their existence, we develop a general algorithmic approach that is guaranteed to return a Nash equilibrium when the game is finite and to approximate an equilibrium when payoff functions are Lipschitz continuous. We also showcase how our methodology can be changed to determine other types of equilibria. The performance of our methods is analysed through computational experiments on knapsack, kidney exchange and a competitive lot-sizing games. To the best of our knowledge, this is the first time that equilibria computation methods for general IPGs have been designed and computationally tested.

Abstract

Nowadays, reaching a high level of employee satisfaction in efficient schedules is an important and difficult task faced by companies. We tackle a new variant of the personnel scheduling problem under unknown demand by considering employee satisfaction via endogenous uncertainty depending on the combination of their preferred and received schedules. We address this problem in the context of reserve staff scheduling, an unstudied operational problem from the transit industry. To handle the challenges brought by the two uncertainty sources, regular employee and reserve employee absences, we formulate this problem as a two-stage stochastic integer program with mixed-integer recourse. The first-stage decisions consist in finding the days off of the reserve employees. After the unknown regular employee absences are revealed, the second-stage decisions are to schedule the reserve staff duties. We incorporate reserve employees' days-off preferences into the model to examine how employee satisfaction may affect their own absence rates.

Abstract

In this work, we introduce the problem of jointly allocating a school capacity expansion (given a fixed budget) and finding the best allocation for the students in the expanded market. Given the computational complexity of the problem, we provide an integer quadratically-constrained programming formulation and study its linear reformulations. We also propose two heuristics: A greedy algorithm and an LP-based method. We empirically evaluate the performance of our approaches in a detailed computational study. We observe the practical superiority of the linearized model in comparison with its quadratic counterpart and we outline their computational limits. Finally, we use the Chilean school choice system data to empirically demonstrate the impact of capacity planning under stability conditions. Our results show that each additional school seat can benefit multiple students. In addition, depending on the decision-maker, our methodology can prioritize the assignment of previously unassigned students or improve the assignment of several students through improvement chains.

Abstract

Product recalls are often consequences of quality failures. While such failures are related to a manufacturer's or supplier's design quality, the perceived quality of products may be severely damaged when a product harm crisis occurs. However, most often, such a crisis will not last forever, and a firm at fault eventually recovers. Considering an optimal control model, we investigate the optimal pricing decisions, advertising and quality efforts of a firm while it anticipates a product recall and a subsequent recovery. We show that the decisions and profits of the manufacturer vary widely with the stochastic parameters: crisis likelihood, recovery likelihood, crisis impact and recovery intensity. We illustrate that myopic firms are more severely affected by a product recall than farsighted firms when the impact of recall is high. However, it might not be so detrimental to take myopic decisions for low impact recalls. In the absence of recovery, a product recall can lead to bankruptcy. High initial perceived quality may not insulate a firm against bankruptcy.

Abstract

Motivated by a real-world application, we present a multi-container loading problem with 3-open dimensions. We formulate it as a biobjective mixed-integer nonlinear program with lexicographic objectives in order to reflect the decision maker's optimization priorities. The first objective is to minimize the number of containers, while the second objective is to minimize the volume of those containers. Besides showing the NP-hardness of this sequential optimization problem, we provide bounds for it which are used in the three proposed algorithms, as well as, on their evaluation when a certificate of optimality is not available. The first is an exact parametric-based approach to tackle the lexicographic optimization through the second objective of the problem. Nevertheless, given that the parametric programs correspond to large nonlinear mixed-integer optimizations, we present a heuristic that is entirely mathematical-programming based. The third algorithm enhances the solution quality of the heuristic. These algorithms are specifically tailored for the real-world application. The effectiveness and efficiency of the devised heuristics is demonstrated with numerical experiments.

Abstract

Physiological signals are often corrupted by noisy sources. Usually, artificial intelligence algorithms analyze the whole signal, regardless of its varying quality. Instead, experienced cardiologists search for a high-quality signal segment, where more accurate conclusions can be draw. We propose a methodology that simultaneously selects the optimal processing region of a physiological signal and determines its decoding into a state sequence of physiologically meaningful events. Our approach comprises two phases. First, the training of a neural network that then enables the estimation of the state probability distribution of a signal sample. Second, the use of the neural network output within an integer program. The latter models the problem of finding a time window by maximizing a likelihood function defined by the user. Our method was tested and validated in two types of signals, the phonocardiogram and the electrocardiogram. In phonocardiogram and electrocardiogram segmentation tasks, the system's sensitivity increased on average from 95.1% to 97.5% and from 78.9% to 83.8%, respectively, when compared to standard approaches found in the literature.

Abstract

In this work, we analyze a sequential game played in a graph called the Multilevel Critical Node problem (MCN). A defender and an attacker are the players of this game. The defender starts by preventively interdicting vertices (vaccination) from being attacked. Then, the attacker infects a subset of non-vaccinated vertices and, finally, the defender reacts with a protection strategy. We provide the first computational complexity results associated with MCN and its subgames. Moreover, by considering unitary, weighted, undirected and directed graphs, we clarify how the theoretical tractability or intractability of those problems vary. Our findings contribute with new NP-complete, Σp2-complete and Σp3-complete problems.

Abstract

The privileged treatment for patients suffering from end-stage renal disease is transplantation. In Kidney Exchange Programs (KEPs), each participating patient is registered together with an incompatible donor. Then, KEPs maximize overall patient benefit through donor exchanges. Compatibility requirements can severely restrict these programs, with certain patients waiting long to be selected for an exchange. Thus, the policy governing the selection of exchanges requires a careful balance between fairness in terms of individual access to transplantation and utilitarian criteria (e.g., total number of transplants). In this work, we review several fairness schemes, interpret them in the context of KEPs and describe their weaknesses. To overcome those drawbacks, we propose a novel scheme based on the Nash Social Welfare Program that simultaneously optimizes the fairness and the utilitarian objectives. Because the application of fairness schemes and a utilitarian objective implies solving conic programs of exponential size, we design a decomposition methodology to efficiently run them on KEP instances. Finally, we make an extensive comparison of the different schemes and validate the scalability of our methodology for benchmark instances from the literature.

Abstract

We present a new model for finding the optimal placement of electric vehicle charging stations across a multi-period time frame so as to maximise electric vehicle adoption. Via the use of advanced discrete choice models and user classes, this work allows for a granular modelling of user attributes and their preferences in regard to charging station characteristics. Instead of embedding an analytical probability model in the formulation, we adopt a simulation approach and pre-compute error terms for each option available to users for a given number of scenarios. This results in a bilevel optimisation model that is, however, intractable for all but the simplest instances. Using the pre-computed error terms to calculate the users covered by each charging station allows for a maximum covering model, for which solutions can be found more efficiently than for the bilevel formulation. The maximum covering formulation remains intractable in some instances, so we propose rolling horizon, greedy, and GRASP heuristics to obtain good quality solutions more efficiently. Extensive computational results are provided, which compare the maximum covering formulation with the current state-of-the-art, both for exact solutions and the heuristic methods.

Abstract

The many-to-one stable matching problem provides the fundamental abstraction of several real-world matching markets such as school choice and hospital-resident allocation. The agents on both sides are often referred to as residents and hospitals. The classical setup assumes that the agents rank the opposite side and that the capacities of the hospitals are fixed. It is known that increasing the capacity of a single hospital improves the residents' final allocation. On the other hand, reducing the capacity of a single hospital deteriorates the residents' allocation. In this work, we study the computational complexity of finding the optimal variation of hospitals' capacities that leads to the best outcome for the residents, subject to stability and a capacity variation constraint. First, we show that the decision problem of finding the optimal capacity expansion is NP-complete and the corresponding optimization problem is inapproximable within a certain factor. This result holds under strict and complete preferences, and even if we allocate extra capacities to disjoint sets of hospitals. Second, we obtain analogous computational complexity results for the problem of capacity reduction. Finally, we study the variants of these problems when the goal is to maximize the size of the final matching under incomplete preference lists.

Abstract

We study the network pricing problem where the leader maximizes their revenue by determining the optimal amounts of tolls to charge on a set of arcs, under the assumption that the followers will react rationally and choose the shortest paths to travel. Many distinct single-level reformulations of this bilevel optimization program have been proposed, however, their relationship has not been established. In this paper, we aim to build a connection between those reformulations and explore the combination of the path representation with various modeling options, allowing us to generate 12 different reformulations of the problem. Moreover, we propose a new path enumeration scheme, path-based preprocessing, and hybrid framework to further improve performance and robustness when solving the final model. We provide numerical results, comparing all the derived reformulations and confirming the efficiency of the novel dimensionality reduction procedures.

Abstract

Sustainability goals are becoming a priority in many societies. An important element in this context is the success of environmentally friendly products. Hence, we consider a manufacturer-retailer vertical supply chain model, managing a green product and its conventional counterpart, designated by brown product. We analyze three kinds of dynamic market scenarios: no market leadership, the manufacturer as the market leader, and the retailer as the market leader. Under each scenario, we determine the equilibrium decisions for pricing and greening investments as well as their dependence on a cost-sharing proportion agreement between the firms. We find that generally both firms have similar pricing trends, where the gap between the two product prices increases with the share of cost carried by the retailer. Moreover, we analyze how these decisions affect the consumer surplus and the performance of the firms. The absence of a market leader leads to higher consumer surplus with the manufacturer investing more in greening. However, cost-sharing may fail if there is no market leader. The retailer has incentive to share the highest proportion of greening costs when it is the leader. When the manufacturer is the leader, the retailer may have incentive to change the cost-sharing proportion over time. Finally, we compare the greening level and learning trajectories for the different scenarios. We provide essential managerial insights on how decisions should be operated, enabling green products to successfully gain a stable market share.

Abstract

We present ZERO, a modular and extensible C++ library interfacing Mathematical Programming and Game Theory. ZERO provides a comprehensive toolkit of modeling interfaces for designing games, helper tools, and algorithms to find Nash equilibria. Specifically, the software supports Reciprocally Bilinear Games (RBGs), i.e., simultaneous non-cooperative games where each player solves a mathematical program with a linear objective in the player's variable and bilinear in its opponents' variables. This class of games generalizes to a multi-agent setting the classical problems of Operations Research. ZERO provides extended support for integer non-convexities, linear bilevel problems, and linear equilibrium problems with equilibrium constraints. Its modular structure provides users with all the elementary ingredients to devise new models and algorithms for RBGs, aiming to boost methodological advancement in the field. We provide an overview of the software's key components and showcase a Knapsack Game, i.e., each player solves a binary knapsack problem. Code, documentation and examples are available at www.getzero.one .

Abstract

The concept of Nash equilibrium enlightens the structure of rational behavior in multi-agent settings. However, the concept is as helpful as one may compute it efficiently. We introduce the Cut-and-Play, an algorithm to compute Nash equilibria for non-cooperative simultaneous games where each player's objective is linear in their variables and bilinear in the other players' variables. Using the rich theory of integer programming, we alternate between constructing (i.) increasingly tighter outer approximations of the convex hull of each player's feasible set -- by using branching and cutting plane methods -- and (ii.) increasingly better inner approximations of these hulls -- by finding extreme points and rays of the convex hulls. In particular, we prove the correctness of our algorithm when these convex hulls are polyhedra. Our algorithm allows us to leverage the mixed integer programming technology to compute equilibria for a large class of games. Further, we integrate existing cutting plane families inside the algorithm, significantly speeding up equilibria computation. We showcase a set of extensive computational results for Integer Programming Games and simultaneous games among bilevel leaders. In both cases, our framework outperforms the state-of-the-art in computing time and solution quality.

Abstract

The college admission problem plays a fundamental role in several real-world allocation mechanisms such as school choice and supply chain stability. The classical framework assumes that the capacity of each college is known and fixed in advance. However, increasing the quota of even a single college would improve the overall cost of the students. In this work, we study the problem of finding the college capacity expansion that achieves the best cost of the students, subject to a cardinality constraint. First, we show that this problem is NP-hard to solve, even under complete and strict preference lists. We provide an integer quadratically constrained programming formulation and study its linear reformulation. We also propose two natural heuristics: A greedy algorithm and an LP-based method. We empirically evaluate the performance of our approaches in a detailed computational study. We observe the practical superiority of the linearized model in comparison with its quadratic counterpart and we outline their computational limits. In terms of solution quality, we note that the allocation of a few extra spots can significantly impact the overall student satisfaction.

Abstract

Kidney exchange programs aim at matching end-stage renal disease patients who have a willing but incompatible kidney donor with another donor. The programs comprise a pool of such incompatible patient-donor pairs and, whenever a donor from one pair is compatible with the patient of another pair, and vice versa, the pairs may be matched and exchange kidneys. This is typically a two-step process in which, first, a set of pairs is matched based on preliminary compatibility tests and, second, the matched pairs are notified and more accurate compatibility tests are performed to verify that actual transplantation can take place. These additional tests may reveal incompatibilities not previously detected. When that happens, the planned exchange will not proceed. Furthermore, pairs may drop out before the transplant, and thus the planned exchange is canceled. In this paper, we study the case in which a new set of pairs may be matched if incompatibilities are discovered or a pair withdraws from the program. 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 admissible second-stage actions are investigated. For each recourse policy, we propose a novel adjustable robust integer programming model. We also propose solution approaches to solve this model exactly. The approaches are validated through thorough computational experiments.

Abstract

Two-sided markets have become increasingly more important during the last years, mostly because of their numerous applications in housing, labor and dating. Consumer-supplier matching platforms pose several technical challenges, specially due to the tradeoff between recommending suitable suppliers to consumers and avoiding collisions among consumers' preferences.

In this work, we study a general version of the two-sided sequential matching model introduced by Ashlagi et al. (2019). The setting is the following: we (the platform) offer a menu of suppliers to each consumer. Then, every consumer selects, simultaneously and independently, to match with a supplier or to remain unmatched. Suppliers observe the subset of consumers that selected them, and choose either to match a consumer or leave the system. Finally, a match takes place if both the consumer and the supplier sequentially select each other. Each agent's behavior is probabilistic and determined by a regular discrete choice model. Our objective is to choose an assortment family that maximizes the expected revenue of the matching. Given the computational complexity of the problem, we show several constant factor guarantees for the general model that, in particular, significantly improve the approximation factors previously obtained. Furthermore, we obtain the first constant approximation guarantees when the problem is subject to cardinality constraints. Our approach relies on submodular optimization techniques and appropriate linear programming relaxations. Finally, we provide a computational study on different settings that supports our technical results.

Abstract

Kidney transplant is the preferred method of treatment for patients suffering from kidney failure. However, not all patients can find a donor which matches their physiological characteristics. Kidney exchange programs~(KEPs) seek to match such incompatible patient-donor pairs together, usually with the main objective of maximizing the total number of transplants. Since selecting one optimal solution translates to a decision on who receives a transplant, it has a major effect on the lives of patients. The current practice in selecting an optimal solution does not necessarily ensure fairness in the selection process. In this paper, the existence of multiple optimal plans for a KEP is explored as a mean to achieve individual fairness. We propose the use of randomized policies for selecting an optimal solution in which patients' equal opportunity to receive a transplant is promoted. Our approach gives rise to the problem of enumerating all optimal solutions, which we tackle using a hybrid of constraint programming and linear programming. The advantages of our proposed method over the common practice of using the optimal solution obtained by a solver are stressed through computational experiments. Our methodology enables decision makers to fully control KEP outcomes, overcoming any potential bias or vulnerability intrinsic to a deterministic solver.

Abstract

The integration of the outbound and the inbound logistics of a company leads to a large transportation network, allowing to detect backhauling opportunities to increase the efficiency of the transportation. In collaborative networks, backhauling is used to find profitable services in the return trip to the depot and to reduce empty running of vehicles. This work investigates the vertical collaboration between a shipper and a carrier for the planning of integrated inbound and outbound transportation. Based on the hierarchical nature of the relation between the shipper and the carrier and their different goals, the problem is formulated as a bilevel Vehicle Routing Problem with Selective Backhauls (VRPSB). At the upper level, the shipper decides the minimum cost delivery routes and the set of incentives offered to the carrier to perform integrated routes. At the lower level, the carrier decides which incentives are accepted and on which routes the backhaul customers are visited. We devise a mathematical programming formulation for the bilevel VRPSB, where the routing and the pricing problems are optimized simultaneously, and propose an equivalent reformulation to reduce the problem to a single-level VRPSB. The impact of collaboration is evaluated against non-collaborative approaches and two different side payment schemes. The results suggest that our bilevel approach leads to solutions with higher synergy values than the approaches with side payments.

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.

Abstract

Learning heuristics for combinatorial optimization problems through graph neural networks have recently shown promising results on some classic NP-hard problems. These are single-level optimization problems with only one player. Multilevel combinatorial optimization problems are their generalization, encompassing situations with multiple players taking decisions sequentially. By framing them in a multi-agent reinforcement learning setting, we devise a value-based method to learn to solve multilevel budgeted combinatorial problems involving two players in a zero-sum game over a graph. Our framework is based on a simple curriculum: if an agent knows how to estimate the value of instances with budgets up to B, then solving instances with budget B+1 can be done in polynomial time regardless of the direction of the optimization by checking the value of every possible afterstate. Thus, in a bottom-up approach, we generate datasets of heuristically solved instances with increasingly larger budgets to train our agent. We report results close to optimality on graphs up to 100 nodes and a 185× speedup on average compared to the quickest exact solver known for the Multilevel Critical Node problem, a max-min-max trilevel problem that has been shown to be at least Σp2-hard.

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.

Abstract

Sustainable Supply Chain Management (SSCM) has assumed a position of prominence for academics and industry over the last two decades. The sustainability literature shows that typically manufacturers aim to optimize their pricing and greening level decisions in a mixed (green and brown) consumer market. In this work, we capture a manufacturer’s classic dilemma on the pricing of green and brown products, and greening investments, while subject to budget constraint. We compute and analyze the variations of optimal decisions over time. Our findings underscore the importance of investing in greening technologies and learning for the survival of green products. Furthermore, we show that a manufacturer’s optimal pricing strategy is to enter the market with a lower price for the green product and to increase it over time, eventually, surpassing the price for the brown product. Our analysis reveals that the greening level attraction can nullify the effect of a high price on the green product, resulting in higher green demand than brown. Higher green product demand is a win-win situation for both the manufacturer and the environment.

Abstract

We analyze Nash games played among leaders of Stackelberg games (NASP). We show it is Σ^p₂-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(n^2^2) 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.

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.

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.

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.

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

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.