ESRC Workshop on Algorithmic Game Theory, London School of Economics

Thursday-Friday October 17-18, 2013       Organizer: Bernhard von Stengel

Speakers:

Location at LSE:

Maps of the LSE campus can be found here: http://www2.lse.ac.uk/mapsAndDirections/findingYourWayAroundLSE.aspx

Schedule

Click on a speaker name for title, abstract, and talk presentation (if available).

Speakers, Titles and Abstracts

Yakov Babichenko (Caltech)	Query Complexity of Approximate Nash Equilibria Talk slides, PDF, 1.3MB	We study the query complexity of approximate notions of Nash equilibrium in games with a large number of players n and a constant number of actions m. Our main result states that even for constant ε, the query complexity of an ε-well-supported Nash equilibrium is exponential in n.
Costis Daskalakis (MIT)	Reductions from Mechanism to Algorithm Design	Algorithmic mechanism design centers around the following question: How much harder is optimizing an objective over inputs that are furnished by rational agents compared to when the inputs are known? We present computationally efficient reductions from mechanism design (i.e. optimizing over rational inputs) to algorithm design (i.e. optimizing over known inputs) in general Bayesian settings. We also explore whether structural properties about optimal mechanisms can be inferred from these reductions. As an application, we present extensions of Myerson's celebrated single-item auction to multi-item settings.
Edith Elkind (Oxford)	A Characterization of Single-Peaked Single-Crossing Domain Talk slides, PPTX, 89kB Talk slides, PDF, 147kB	In this talk we focus on two classic domain restrictions that are often considered in social choice: single-peaked and single-crossing preferences. We characterize the preference profiles that are simultaneously single-peaked and single-crossing. We also discuss some algorithmic implications of our characterization for the problem of fully proportional representation.
Kousha Etessami (Edinburgh)	Branching Stochastic Games	Branching stochastic games are two-player zero-sum stochastic games that generalize multi-type branching processes, a classic discrete-time stochastic process. The goal of the two players is to maximizing/minimizing extinction probability, starting with a given population of objects. We first consider the 1-player setting: Branching MDPs. We give a polynomial time algorithm for approximating the maximum (and minimum) extinction probability of a BMDP, to desired precision. The algorithm is based on a Generalized Newton's Method (GNM), applied to the Bellman optimality equations for a BMDP. These are systems of max-(min-)probabilistic polynomial equations whose Least Fixed Point gives the desired optimal probabilities. Each iteration of GNM involves linear programming. By using our P-time approximation algorithm for BMDPs, and by using a static-determinacy result for Branching simple stochastic games, we show that the value of these games can be approximated in NP. (Joint work with Alistair Stewart and Mihalis Yannakakis.)
Felix Fischer (Cambridge)	(Approximately) Optimal Impartial Selection Talk slides, PDF, 77kB	We study impartial mechanisms for selecting a member of a set of agents based on nominations by agents from that set. Here, impartiality means that nominations submitted by an agent do not affect its own chances of being selected. Our main result concerns a randomized mechanism that in expectation selects an agent with at least half the maximum number of nominations. Subject to impartiality, this is optimal. (Joint work with Max Klimm.)
Martin Gairing (Liverpool)	Complexity and Approximation of the Continuous Network Design Problem Talk slides, PDF, 1.2MB	We revisit a classical problem in transportation, known as the continuous (bilevel) network design problem, CNDP for short. We are given a graph for which the latency of each edge depends on the ratio of the edge flow and the capacity installed. The goal is to find an optimal investment in edge capacities so as to minimize the sum of the routing cost of the induced Wardrop equilibrium and the investment cost. While this problem is considered as challenging in the literature, its complexity status was still unknown. We close this gap showing that CNDP is strongly NP-complete and APX-hard, even for instances with affine latencies. As for the approximation of the problem, we first provide a detailed analysis for a heuristic studied by Marcotte for the special case of monomial latency functions (Mathematical Programming, Vol. 34, 1986). Specifically, we derive a closed form expression of its approximation guarantee for arbitrary sets of allowed latency functions. Second, we propose a different approximation algorithm and show that it has the same approximation guarantee. As our final - and arguably most interesting - result regarding approximation, we show that using the better of the two approximation algorithms results in a strictly improved approximation guarantee for which we give a closed form expression. For affine latencies, e.g., this algorithm achieves a 49/41-approximation which improves on the 5/4 that has been shown before by Marcotte. (Joint work with Tobias Harks and Max Klimm.)
Paul Goldberg (Oxford)	The Complexity of Computing the Solution Obtained by a Specific Algorithm Talk slides, PDF, 3.8MB	In a recent paper, we showed that it is PSPACE-complete to compute any of the Nash equilibria that are found by the Lemke-Howson algorithm. I will give an overview of the complexity-theoretic background to that result, and discuss possible generalizations.
Elias Koutsoupias (Oxford)	Near-Optimal Multi-Unit Auctions With Ordered Bidders Talk slides, PDF, 388kB	I will discuss prior-free profit-maximizing auctions for digital goods. In particular, I will give an overview of the area and I will focus on prior-free auctions with ordered bidders and identical items. In this model, we compare the expected revenue of an auction to the monotone price benchmark: the maximum revenue that can be obtained from a bid vector using prices that are non-increasing in the bidder ordering and bounded above by the second-highest bid. I will discuss an auction with constant-factor approximation guarantee for identical items, in both unlimited and limited supply settings. Consequently, this auction is simultaneously near-optimal for essentially every Bayesian environment in which bidders' valuation distributions have non-increasing monopoly prices, or in which the distribution of each bidder stochastically dominates that of the next.
Ruta Mehta (Georgia Tech)	Equilibrium Computation in Bimatrix Games: Rank-1 and Beyond	The rank of a bimatrix game (A, B) is defined as the matrix rank of A + B. For zero-sum games, i.e., rank-0, von Neumann (1928) showed that Nash equilibrium are min-max strategies. Its existence is equivalent to the linear programming duality. We solve the open question of Kannan and Theobald (2005) of designing an efficient algorithm for rank-1 games. The main difficulty is that the set of equilibria can be disconnected. We circumvent this by moving to a space of rank-1 games which contains our game (A, B), and defining a quadratic program whose optimal solutions are Nash equilibria of all games in this space. We then isolate the Nash equilibrium of (A, B) as the fixed point of a single variable function which can be found in polynomial time via an easy binary search. An extension of this approach reduces NE computation in rank-k games to k-dimensional fixed point. However, the discrete version of 2D-fixed point is known to be PPAD-hard. We investigate consequences of this on constant rank games. (The first part of the talk is based on a joint work with Bharat Adsul, Jugal Garg and Milind Sohoni.)
Rahul Savani (Liverpool)	Learning Equilibria of Games via Payoff Queries Talk slides, PDF, 187kB	We study a computational learning model for games in which an algorithm queries the payoffs of players at pure strategy profiles. The goal of the algorithm is to find an exact or approximate Nash equilibrium of the game with as few queries as possible. We give basic results on the payoff query complexity of bimatrix and graphical games. Our focus is on symmetric network congestion games. For directed acyclic networks, we can learn the cost functions (and hence compute an equilibrium) while querying just a small fraction of pure-strategy profiles. For the special case of parallel links, we have the stronger result that an equilibrium can be identified while only learning a small fraction of the cost values.
Paul Spirakis (Liverpool)	Strong Bounds for Evolution in Networks Talk slides, PDF, 1MB	The work concerns evolutionary antagonism in undirected networks (graphs) and thus it concerns evolutionary game theory issues. Given is a network whose nodes are occupied by members of a resident population. Each member has a fitness normalized to one. A single non-resident (mutant) is then placed at a node, and has a fitness, usually bigger than one. Mutants and residents can copy themselves on neighbours, replacing the previous inhabitant. The selection of a node to copy itself on a random neighbour is based on a probabilistic experiment which gives more probability to bigger fitness. This process may result in (a) the whole net occupied by mutants (fixation) or (b) elimination of mutants (extinction). A main magnitude of interest is the probability of fixation (given the graph). Here we describe work done in ICALP 2013 (and also refer to previous works by the speaker and coauthors, in WINE 2011 and SODA 2012). In particular, having the clique as a measure net, we examine existence of "strong" amplifiers of selection (nets having fixation probability much bigger than the clique) and "strong" suppressors of selection (having fixation prob much lower than the clique). We also present our "Thermal" theorem which gives strong bounds on the fixation probability by taking into account the initial position of the mutant and the structure of the net. This work extends some results of [Lieberman et al, Nature 2005]. (Joint work with G. Mertzios.)
Tomáš Valla (Prague)	Complexity of the Guarding Game Talk slides, PDF, 1.4MB	The guarding game is a game in which several cops try to guard a region in a (directed or undirected) graph against a robber. The robber and the cops are placed on the vertices of the graph; they take turns in moving to adjacent vertices (or staying), cops inside the guarded region, the robber on the remaining vertices (the robber-region). The goal of the robber is to enter the guarded region at a vertex with no cop on it. The problem is to determine whether for a given graph and given number of cops the cops are able to prevent the robber from entering the guarded region. Fomin et al. proved that the problem is NP-complete when the robber-region is restricted to a tree. Further they prove that is it PSPACE-complete when the robber-region is restricted to a directed acyclic graph, and they ask about the problem complexity for arbitrary graphs. In this paper we prove that for arbitrary graphs (directed or undirected) the problem is E-complete. (Joint work with R. Šámal.)
László Varga (Budapest)	Algebraic Combinatorics and the Parity Argument Talk slides, PDF, 722kB	The topic of this talk is related to PPA membership of the Combinatorial Nullstellensatz and related problems. We present new generalizations of Olson's theorem and of a consequence of Alon's Combinatorial Nullstellensatz. These enable us to extend some of its combinatorial applications with conditions modulo primes to conditions modulo prime powers. We analyze computational search problems corresponding to these kinds of combinatorial questions and we prove that the problem of finding degree-constrained subgraphs modulo 2d such as 2d-divisible subgraphs and the search problem corresponding to the Combinatorial Nullstellensatz over F2 belongs to the complexity class Polynomial Parity Argument (PPA).
László Végh (LSE)	Convex Programs for Linear Arrow-Debreu Markets Talk slides, PDF, 7.6MB	We give a new, flow-type convex program for linear Arrow-Debreu markets, along with a simple proof of the existence of equilibria and some further properties. We also survey previous convex programs for the problem and investigate connections between them. (Joint work with Nikhil Devanur and Jugal Garg.)
Adrian Vetta (McGill)	How do you price a durable good?	A duropolist is a monopolist for a good that is long-lasting and can be consumed repeatedly over time. Such goods are evidently desirable but Richard Coase (1972) made the startling conjecture that a duropolist has no monopoly power at all! We discuss this issue and the various pricing mechanisms available to a duropolist. We then quantify the extent to which a duropolist can, in fact, generate higher profits than an equivalent monopolist for a perishable good. (Joint work with Peter Sloan and Gerardo Berbeglia.)