- Kira Goldner, Graduate Student, University of Washington
- Vangelis Markakis, Assistant Professor, Athens University of Economics and Business
- Balasubramanian Sivan, Research Scientist, Google Research, New York
- Chaitanya Swamy, Professor, University of Waterloo
Tutorial by Kira Goldner
Speaker : Kira Goldner, Graduate Student, University of Washington
Title: Mechanism Design for Social Good
The Algorithmic Game Theory community has long been interested in problems in auction theory, both due to their mathematical appeal and to their importance to industry and government. In addition, a few major efforts stand out where mechanism design has had an impact on society: kidney exchange, residency matching, and school choice.
The "Mechanism Design for Social Good" agenda is to find problems from relatively unexplored domains (1) that are mathematically interesting and (2) where tools from theoretical mechanism design have the potential for great impact. In this tutorial, we'll examine real-world problems from a wealth of domains where current market and government mechanisms are failing, and where algorithmic mechanism design can help play a role to improve social welfare. In particular, we'll discuss problems from healthcare, refugee resettlement, online labor markets, education, and more.
Kira Goldner is a fourth-year PhD student in Computer Science and Engineering at the University of Washington, advised by Anna Karlin. Her research focuses on problems in mechanism design, ranging from social good questions in healthcare and online platform design to revenue maximization problems inspired by practice. Over the past year, Kira has been pursuing an agenda of "Mechanism Design for Social Good" by co-organizing, with Rediet Abebe, an online interdisciplinary and multi-institution reading group to identify applications in this domain that give rise to interesting theoretical mechanism design questions. She also co-organized with Abebe the first workshop on Mechanism Design for Social Good at the 2017 ACM Conference on Economics and Computation. She is a 2017 recipient of the Microsoft Research PhD Fellowship and was a 2016 recipient of a Google Anita Borg Scholarship. Kira received her B.A. in Mathematics from Oberlin College and also studied at Budapest Semesters in Mathematics.
Tutorial by Vangelis Markakis
Speaker : Vangelis Markakis, Assistant Professor, Athens University of Economics and Business
Title: Fairness with indivisible goods: solution concepts and algorithms
Fair division typically involves the allocation of a set of resources to a set of agents, so that certain fairness criteria are achieved. Over the years, fair division problems have attracted the attention of various scientific disciplines including among others, mathematics, economics, computer science, and political science. A notable qualitative distinction in the models that have been used concerns the nature of the resources and whether they are divisible or indivisible. Indeed, even though most fairness notions are guaranteed to exist under divisible items, this is no longer the case in the presence of indivisibilities. To make it worse, decent approximation algorithms are also unlikely to exist for the most standard and oldest fairness notions that have been proposed, such as envy-freeness and proportionality.
The purpose of this tutorial is to give an overview of fairness concepts that have been studied in the more recent years and seem to be more appropriate for the context of indivisible items. Among others, these include maximin share fairness, envy-freeness up to one item, envy-freeness up to any item, and related variants. These concepts tend to be more amenable to efficient algorithms, than the more traditional fairness notions, and after the relevant definitions, we will discuss the currently known algorithmic results for each of them. Our focus will be on both exact and approximation algorithms, highlighting also certain special cases. Finally, the last part of the tutorial will also discuss mechanism design aspects of these problems. We will conclude with many interesting open problems that stem from this line of research.
Vangelis Markakis is currently an Assistant Professor at the Department of Informatics of the Athens University of Economics and Business (AUEB) in Athens, Greece. He received his PhD in Computer Science from the Georgia Institute of Technology, Atlanta, USA, in 2005, and after that, he also held appointments as a postdoctoral researcher at the University of Toronto and at the center for Mathematics and Computer Science (CWI, Amsterdam). His research interests lie in the areas of theoretical computer science, analysis of algorithms, algorithmic game theory, mechanism design, and their applications to the design of auctions and other e-commerce environments.
Tutorial by Balasubramanian Sivan
Speaker : Balasubramanian Sivan, Research Scientist, Google Research, New York
Title: Dynamic Mechanism Design and Learning
We survey recent results in the theory of dynamic mechanism design, particularly as it applies to buyers participating in repeated auctions with a single seller (such as an ad exchange), highlighting the main techniques and open problems therein. We discuss the role of learning in such a repeated setting, both from the buyers’ and seller’s perspective, and the trade-offs that learning (as opposed to full prior knowledge of the setting) imposes.
Balasubramanian Sivan is a research scientist at Google Research, New York. His research interests are in algorithmic game theory, mechanism design, online algorithms and online learning. He is a recipient of the ACM SIGecom doctoral dissertation award. For more information,click here
Tutorial by Chaitanya Swamy
Speaker : Chaitanya Swamy, Professor, University of Waterloo
Title: New perspectives and challenges in routing games: query models and signaling
Network routing games are a popular means of modeling settings where a collection of self-interested, uncoordinated users or agents route their traffic along an underlying network: prominent examples include communication and transportation networks. These games are typically described in terms of an underlying directed graph modeling the network, a set of commodities specified by source-sink pairs and the volume of traffic routed between them, and latency or delay functions on the edges modeling the delay experienced on an edge as a function of the volume of traffic present on it. The outcome of users' strategic behavior is described by an equilibrium traffic pattern, where no user may unilaterally deviate and reduce her total delay. The typical means of mathematically investigating network routing games assumes that one has precise, detailed information about the underlying latency functions, and in this setting, we have a reasonably good understanding of equilibria, their (in)efficiency, and algorithms for computing them. However, such precise information about the latency functions may be unavailable, or difficult to obtain.
In this tutorial, after starting out with some basic results on network routing games, we will discuss two recent, and somewhat orthogonal, perspectives on network routing games that have emerged from the above concern, and the challenges that arise in solving the underlying questions in the resulting models. In the first set of models, we examine routing games under the lens of query models: here, the routing game is viewed as a black box that can answer certain limited types of queries, such as the cost of a given strategy profile (i.e., traffic pattern), or the equilibrium flow that results under a given set of tolls. The second set of models concerns settings where there is some underlying uncertainty in the latency functions and asymmetry in the amount of knowledge possessed by the underlying parties. Specifically, there is a central authority who has perfect information about the uncertain "state of nature", while the self-interested users only know only the distribution of this state. The central authority seeks to leverage this asymmetry and wants to solve the following signaling problem: what information should it release to the users so as to obtain an efficient traffic pattern?
We will see how optimization techniques coupled with an understanding of equilibria can be utilized to obtain answers to some of these underlying questions in these models, which in turn deepen our understanding of network routing games. However, various interesting questions remain open and suggest promising directions for further research. No prior knowledge of routing games will be assumed.
Chaitanya Swamy studied computer science at the Indian Institute of Technology, Delhi, and received his PhD in computer science from Cornell University. After a postdoctoral stint at Caltech, he joined the faculty of the Department of Combinatorics & Optimization at the University of Waterloo in 2006, where he currently holds the position of professor. Swamy's research interests lie in theoretical computer science, and in particular, in the design and analysis of algorithms, combinatorial optimization and mathematical programming, and algorithmic game theory. He has published various influential papers in leading conferences and journals in his field. He is currently an Associate Editor of SIAM Journal on Computing and Discrete Optimization, and has been a program committee member of various theoretical computer science conferences.