Thursday 14:05 Keynote: Optimal Kidney Exchange with Immunosuppressants Ágnes Cseh Hungarian Academy of Sciences
The deployment of centralized matching algorithms for efficient exchange of donated kidneys is a major success story of market design. In the standard kidney exchange problem, blood- or tissue-type incompatibility between a patient and a donor makes a transplant impossible. However, novel technological advances on potent immunosuppressant drugs can lift this barrier.
We present a general computational framework to study kidney exchange with immunosuppressants. In contrast to the standard kidney exchange problem, our problem also involves the decision about which patients get immunosuppressants to make them compatible with originally incompatible kidneys. Our main contribution is a set of general algorithms that provide flexibility in terms satisfying meaningful purposes.
Joint work with Haris Aziz.
Thursday 15:10 On the price of anarchy for flows over time Tim Oosterwijk Maastricht University
Dynamic network flows, or network flows over time, constitute an important model for real-world situations where steady states are unusual, such as urban traffic and the Internet. In order to describe the temporal evolution of such systems one has to consider the propagation of flow across the network by tracking the position of each particle along time. These applications immediately raise the issue of analyzing dynamic network flows from a game-theoretic perspective.
In this talk I will discuss dynamic equilibria in the deterministic fluid queuing model in single-source single-sink networks, arguably the most basic model for flows over time. I will then present the main ideas behind the result that if we could reduce the inflow of the network in a dynamic equilibrium, then the Price of Anarchy is bounded by a factor, parameterized by the longest path length, that converges to e/(e-1) = 1.582. I will mention some other results we found and finish with some intriguing open questions.
This is joint work with José Correa and Andrés Cristi from the Universidad de Chile.
Thursday 15:35 Flow-Based Network Creation Games Anna Melnichenko Hasso Plattner Institute, University of Potsdam
Network Creation Games are a well-known approach for explaining and analyzing the structure, quality and dynamics of real-world networks like the Internet and other infrastructure networks which evolved via the interaction of selfish agents without a central authority. In this game selfish agents that correspond to nodes in a network strategically buy incident edges to improve their centrality. In the last three decades, many strategic models have been proposed and analyzed, but most of them have in common that the central metric for network quality is based on the distance to other agents. This implies an optimized latency, which is an appropriate approach for a lot of network-use cases. Nevertheless, with the rising demand for cloud storage, high-quality video streaming and also in physical networks like the power grid, bandwidth/throughput is a crucial metric. Based on the maximum flow problem we present a novel kind of Network Creation Game that regards the throughput between pairs of agents in a graph as the crucial metric for network quality. We analyze the quality and structural properties of equilibria and social optimum for two natural versions of the game which we then use for establishing bounds on the Price of Anarchy. Moreover, we investigate the game dynamics of both models.
16:00 Capacity and Price Competition in Markets with Congestion Effects Anja Schedel University of Augsburg "We study oligopolistic competition in service markets where firms offer a service to customers. The service quality of a firm - from the perspective of a customer - depends on the level of congestion and the charged price. A firm can set a price for the service offered and additionally decides on the service capacity in order to mitigate congestion. The total profit of a firm is derived from the gained revenue minus the capacity investment cost. Firms simultaneously set capacities and prices in order to maximize their profit and customers subsequently choose the services with lowest combined cost (congestion and price). For this basic model, Johari, Weintraub and Van Roy (2010) derived the first existence and uniqueness results of pure Nash equilibria (PNE) assuming mild conditions on congestion functions. Their existence proof relies on Kakutani's fixed-point theorem and a key assumption for the theorem to work is that demand for service is elastic, that is, there is a smooth inverse demand function determining the volume of customers given the effective customers' costs.
We consider the case of perfectly inelastic demand. This scenario applies to realistic cases where customers are not willing to drop out of the market, e.g., if prices are regulated by reasonable price caps. We investigate existence, uniqueness and quality of PNE for models with inelastic demand and price caps. We show that for linear congestion cost functions, there exists a PNE. This result requires a completely new proof approach compared to previous approaches, since the best response correspondences of firms may be empty, thus standard fixed-point arguments are not directly applicable. We show that the game is C-secure (see Reny (1999), and McLennan, Monteiro and Tourky (2011)), which leads to the existence of PNE. We furthermore show that the PNE is unique, and that the efficiency compared to a social optimum is unbounded in general.
(Joint work with Tobias Harks.)
Thursday 17:00 Topological Influence and Locality in Swap Schelling Games Louise Molitor Hasso Plattner Institute
Residential segregation is a wide-spread phenomenon that can be observed in almost every major city. In these urban areas residents with different racial or socioeconomic background tend to form homogeneous clusters. Schelling’s famous agent-based model for residential segregation explains how such clusters can form even if all agents are tolerant, i.e., if they agree to live in mixed neighborhoods.For segregation to occur, all it needs is a slight bias towards agents preferring similar neighbors. Very recently, Schelling’s model has been investigated from a game-theoretic point of view with selfish agents that strategically select their residential location. In these games, agents can improve on their current location by performing a location swap with another agent who is willing to swap. We significantly deepen these investigations by studying the influence of the underlying topology modeling the residential area on the existence of equilibria, the Price of Anarchy and on the dynamic properties of the resulting strategic multi-agent system. Moreover, as a new conceptual contribution, we also consider the influence of locality, i.e., if the location swaps are restricted to swaps by neighboring agents. We give improved almost tight bounds on the Price of Anarchy for arbitrary underlying graphs and we present tight bounds for regular graphs, paths and cycles. Moreover, we give almost tight bounds for grids, which are the most commonly used underlying topology in empirical studies. For grids we also show that locality has a severe impact on the game dynamics.
Thursday 17:25 Generalized Matching Games for International Kidney Exchange Walter Kern University of Twente
We introduce generalized matching games defined on a graph $G=(V,E)$ with an edge weighting $w$ and a partition $V=V_1 \cup \dots \cup V_n$ of~$V$. The player set is $N = \{ 1, \dots, n\}$, and player $p \in N$ owns the vertices in $V_p$. The value $v(S)$ of coalition $S \subseteq N$ is the maximum weight of a matching in the subgraph of $G$ induced by the vertices owned by players in $S$. If $|V_p|=1$ for every player~$p$ we obtain the classical matching game. We prove that checking core non-emptiness is polynomial-time solvable if $|V_p|\leq 2$ for each $p$ and co-\NP-hard if $|V_p|\leq 3$ for each $p$. We do so via pinpointing a relationship with $b$-matching games and also settle the complexity classification on testing core non-emptiness for $b$-matching games. We propose generalized matching games as a suitable model for international kidney exchange programs, where the vertices in $V$ correspond to patient-donor pairs and each $V_p$ represents one country. For this setting we prove a number of complexity results.
Friday 09:30 Keynote Maria Polukarov King's College London .
Friday 10:40 An irrational solution concept for one-shot games Thomas Boehme TU Ilmenau
Friday 11:05 Prophet Inequalities for Bayesian Persuasion Niklas Hahn Goethe-University Frankfurt
We study an information-structure design problem (i.e., a Bayesian persuasion problem) in an online scenario. Inspired by the classic gambler’s problem, consider a set of candidates who arrive sequentially and are evaluated by one agent (the sender). This agent learns the value from hiring the candidate to herself as well as the value to another agent, the receiver. The sender provides a signal to the receiver who, in turn, makes an irrevocable decision on whether or not to hire the candidate. A-priori, for each agent the distribution of valuation is independent across candidates but may not be identical. We design good online signaling schemes for the sender. To assess the performance, we compare the expected utility to that of an optimal offline scheme by a prophet sender who knows all candidate realizations in advance.
We show an optimal prophet inequality for online Bayesian persuasion, with a 1/2-approximation when the instance satisfies a “satisfactory-status-quo” assumption. Without this assumption there are instances without any finite approximation factor. We extend the results to combinatorial domains and obtain prophet inequalities for matching with multiple hires and multiple receivers.
Friday 11:35 Electricity Pricing Mechanism Based on Losses Using Electricity Network Topology Victor Reijnders University of Twente
Pricing mechanisms for electricity network costs currently used for consumers do not provide incentives to decrease the stress on the electricity network. In this talk, we present a novel pricing mechanism for the network costs based on the losses caused by the transport of electricity in the low voltage (LV) network. This mechanism is based on the Shapley value. Firstly, we derive an explicit formulation of the Shapley value based on the given location of households in the LV network. Secondly, since the location of the households heavily influences the prices, we present a pricing mechanism that averages the Shapley value over all permutations of households on the different locations in the network. This results in a cost per household as if the household is on an average location in the network. This cost can be calculated efficiently if the households are connected to a single cable. Thirdly, an approximation of this value is presented which could be useful or even necessary for extensions to LV networks of different topology. Lastly, we show some considerations for the actual implementation of these pricing mechanisms.
12:00 Strategic Payments in Financial Networks Daniel Schmand Goethe University Frankfurt In their seminal work on systemic risk in financial markets, Eisenberg and Noe proposed and studied a model with n firms embedded into a network of debt relations. We analyze this model from a game-theoretic point of view. Every firm is a rational agent in a directed graph that has an incentive to allocate payments in order to clear as much of its debt as possible. Each edge is weighted and describes a liability between the firms. We consider several variants of the game that differ in the permissible payment strategies. We study the existence and computational complexity of pure Nash and strong equilibria, and we provide bounds on the (strong) prices of anarchy and stability for a natural notion of social welfare. Our results highlight the power of financial regulation.
Friday 13:30 Keynote: Mechanisms for Two-Sided Markets Bart de Keijzer King's College London
In this talk, I will give an introduction to mechanism design for two-sided markets. Such markets find applications in the sharing/access economy, internet advertising, and more generally e-commerce. Compared to the better-known "classical" mechanism design scenarios where the items are being sold by a single non-strategic entity that can be thought of as the mechanism itself, in the case of two-sided markets it is assumed that the items are sold by one or more self-interested agents. These selling agents strategically interact with the mechanism so as to optimize their utility, similar to what the buying agents are attempting to do. The presence of strategically acting sellers brings new challenges to designing an satisfactory mechanism, as there are now multiple types of agent who can potentially manipulate the mechanism, and the mechanism must furthermore specify, and make sure to balance out, potential monetary payments between the sellers and buyers. A mechanism in the two-sided market setting thus takes the role of an intermediator between the buyers and sellers that makes sure that trade happens in an optimal way.
Mechanisms in this setting must satisfy various economically motivated properties, such as individual rationality, strategy-proofness, and budget-balance. Simultaneously, we want them to run fast (i.e. in polynomial time), and achieve a good outcome quality (usually measured as an approximation factor with respect to an optimal allocation of the items). Various mechanisms have been proposed in the literature that attempt to satisfy these properties or trade them off in the best possible way. I will give an overview of this area of research and discuss some recent results and open challenges.
Friday 14:20 Convergence of Large Atomic Congestion Games Marc Schröder RWTH Aachen University
We study the convergence of sequences of atomic unsplittable congestion games with an increasing number of players. We consider two situations. In the first setting, each player has a weight that tends to zero, in which case the mixed equilibria of the finite games converge to the set of Wardrop equilibria of the corresponding nonatomic limit game. In the second case, players have unit weights, but participate in the game with a probability that tends to zero. In this case, the mixed equilibria converge to the set of Wardrop equilibria of
another nonatomic game with suitably defined costs, which can be seen as a Poisson game in the sense of Myerson (1998). In both settings we show that the price of anarchy of the sequence of games converges to the price of anarchy of the nonatomic limit.