Stony Brook Workshop on Computational Game Theory

Tuesday - Thursday July 16-18, 2013       Organizer: Bernhard von Stengel

group photo

Group photo in front of the Three Village Inn on 17 July 2013 by Angelina Vidali

Schedule

Click on a speaker name for title and abstract.

time

Tuesday 16 July

Wednesday 17 July

Thursday 18 July





9:00- 9:45

Ilan Adler

Aviezri Fraenkel

Éva Tardos

coffee break




10:15-11:00

Herbert Scarf

Tim Roughgarden

Urban Larsson

11:00-11:45

Ruta Mehta

Prize lecture: Michael Ostrovsky, Michael Schwarz, and Hal Varian

Carlos Santos

coffee break



12:00-12:45

Richard Cole

Richard Nowakowski

12:45-14:00 lunch




14:00-14:45

Angelina Vidali

Eran Shmaya

Adam Landsberg

14:45-15:30

Rahul Savani

Dirk Bergemann

Sam Payne

coffee break



- finish -

16:00-16:45

Jochen Koenemann

Thane Plambeck


16:45-17:30

Bernhard von Stengel

Costis Daskalakis






18:00-22:00


workshop reception and dinner


Speakers, Titles and Abstracts

Further confirmed participants:
Bob Aumann (Hebrew University, Jerusalem), Sandro Brusco (Stony Brook), Pradeep Dubey (Stony Brook), Ehud Kalai (Northwestern), John Nash (Princeton), Abraham Neyman (Hebrew University, Jerusalem), Michael Todd (Cornell)

Ilan Adler (Berkeley)

The Central Role of Bimatrix Games in the Computational Analysis of PPAD LCP's

It is well known that the problem of finding a Nash equilibrium for a bimatrix game (2-NASH) can be formulated as a linear complementarity problem (LCP). In addition, 2-NASH is known to be complete in the complexity class PPAD. However, the ingeniously constructed reduction (designed for any PPAD problem) is very complicated, so while of great theoretical significance, it is not practical for actually solving an LCP via 2-NASH, and it may not provide the potential insight that can be gained from studying the game obtained when formulated as an LCP. In this talk we'll show that for any LCP and a positive covering vector d (associated with Lemke's algorithm) satisfying a nondegeneracy assumption, we can directly construct a symmetric 2-NASH problem whose equilibria correspond one-to-one to the end points of the Lemke's graph induced by the LCP and d. This construction leads to direct reductions of PPAD LCP's to 2-NASH problems of similar sizes. We'll conclude with a couple of examples where the reductions lead to answers to hitherto open questions.
Joint work with Sushil Verma.

Dirk Bergemann (Yale)

The Limits of Price Discrimination

We present an application of "Bayes Correlated Equilibrium" using a few nice finite, algorithmic arguments.
We analyze the welfare consequences of a monopolist having additional information about consumers' tastes, beyond the prior distribution; the additional information can be used to charge different prices to different segments of the market, i.e., carry out "third degree price discrimination". We show that the segmentation and pricing induced by the additional information can achieve every combination of consumer and producer surplus such that: (i) consumer surplus is non-negative, (ii) producer surplus is at least as high as profits under the uniform monopoly price, and (iii) total surplus does not exceed the efficient gains from trade. As well as characterizing the welfare impact of price discrimination, we examine the limits of how prices and quantities can change under price discrimination. We also examine the limits of price discrimination in richer environments with quantity discrimination and limited ability to segment the market.

Richard Cole (NYU)

Tatonnement Beyond Gross Substitutes

Tatonnement is a natural and simple distributed price adjustment rule for markets of goods. It can be viewed as an algorithmic process or as a natural real-world heuristic for price updates. However, it will not converge in all markets, which raises the question of when it does converge.
We show that for a substantial class of markets tatonnement amounts to gradient descent on a suitable convex function of the prices. We also show, using a localized form of strong convexity, that rapid convergence holds for many of these markets.
Joint work with Yun Kuen Cheung and Nikhil Devanur.

Costis Daskalakis (MIT)

Reductions from Mechanism to Algorithm Design

Algorithmic mechanism design centers around the following question: How much harder is optimizing an objective function over inputs that are furnished by rational agents compared to when the inputs are known? We provide a computationally efficient, black-box reduction from mechanism design (i.e. optimizing over rational inputs) to algorithm design (i.e. optimizing over known inputs) in general Bayesian settings. As an application of our reduction, we extend Myerson's celebrated auction to the multi-item setting.

Aviezri Fraenkel (Weizmann Institute)

The Exciting Story of Combinatorial Game Theory

AIM: To present a systematic development of the theory of combinatorial games from the ground up. APPROACH: Computational complexity. Combinatorial games are completely determined; the questions of interest are efficiencies of strategies. METHODOLOGY: Divide and conquer. Ascend from Nim to Chess in small strides at a gradient that's not too steep. PRESENTATION: Largely informal; examples of combinatorial games sampled from various strategic viewing points along scenic mountain trails illustrate the theory.

Jochen Koenemann (Waterloo)

Network Bargaining with General Capacities

We study balanced solutions for network bargaining games with general capacities, where agents can participate in a fixed but arbitrary number of contracts. We provide the first polynomial time algorithm for computing balanced solutions for these games. In addition, we prove that an instance has a balanced solution if and only if it has a stable one. Our methods use a new idea of reducing an instance with general capacities to a network bargaining game with unit capacities defined on an auxiliary graph. This represents a departure from previous approaches, which rely on computing an allocation in the intersection of the core and prekernel of a corresponding cooperative game, and then proving that the solution corresponding to this allocation is balanced. In fact, we show that such cooperative game methods do not extend to general capacity games.
Joint work with Linda Farczadi and Konstantinos Georgiou

Adam Landsberg (Claremont)

Renormalization Analysis of Combinatorial Games

Renormalization is a technique used widely in physics to analyze problems involving self-similar geometric structures. This talk will provide an overview of how renormalization methods can be adapted to address issues in combinatorial game theory. Although renormalization methods are not fully mathematically rigorous, they nonetheless can provide interesting insights into the behavior of various games. Applications to combinatorial games such as Chomp and Nim-with-a-pass will be discussed.

Urban Larsson (Chalmers)

Imitation Nim

We study a variation of the normal play combinatorial game of 2-pile Nim. Move as in 2-pile Nim but with the following move-size dynamic constraint: Suppose the previous player has just removed say x>0 tokens from the shorter pile (either pile in case they have the same height). If the next player now removes x tokens from the larger pile, then he imitates his opponent. For a predetermined nonnegative integer p, by the rules of the game, neither player is allowed to imitate his opponent on more than p consecutive moves. We demonstrate that (regarded as starting positions) the P-positions of this game are the same as a variant of Wythoff Nim with a certain blocking maneuver on p diagonal positions.

Ruta Mehta (Georgia Tech)

A Polynomial Time Algorithm for Rank-1 Bimatrix Games (Despite Disconnected Solutions)

The rank of a bimatrix game (A, B) is defined as the rank of (AB). For zero-sum games, i.e., rank 0, von Neumann (1928) showed that Nash equilibrium are min-max strategies, which 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. Based on joint work with Bharat Adsul, Jugal Garg and Milind Sohoni.

Richard Nowakowski (Dalhousie)

Two Approximations in Combinatorial Game Theory

It is not always necessary to have all the information about a game to be able to play well. The Atomic weight and the reduced canonical form are two that strip away much detail revealing a core of information that often is enough to win.

Michael Ostrovsky (Stanford), Michael Schwarz (Google), Hal Varian (Berkeley and Google)

Sponsored Search Auctions

Prize in Game Theory and Computer Science of the Game Theory Society in Honor of Ehud Kalai
This talk will summarize the results from "Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords" by Edelman, Ostrovsky, and Schwarz and "Position Auctions" by Varian. We will also discuss some historical background behind these papers, as well as the subsequent developments in the theory and practice of sponsored search auctions.

Sam Payne (Yale)

Bidding Games

I will discuss variations on traditional two-player games, such as tic-tac-toe, hex, and chess, in which players do not alternate moves, but instead bid for the right to determine who moves next. For instance, both players might start with 100 chips. If Alice bids 15 for the first move and Bob bids 17, then Bob gives Alice 17 chips and makes a move on the board. Now Alice has 117 chips, Bob has 83, and they bid for the next move.
I will present the basics of bidding games, including solutions of bidding tic-tac-toe and bidding hex. As time permits, I will also discuss further challenges posed as the complexity of the underlying game increases, heuristics for effective bidding play in games where neither play can accurately determine the true mathematical value of the next move, and ongoing efforts to develop artificial intelligence for bidding chess.

Thane Plambeck (Counterwave, Inc)

Advances in Losing

We will give an overview of recent advances in the theory of impartial combinatorial games in misère play, including an introduction to "misère quotients", which are commutative monoids that generalize the nim-heaps and nim-sums that arise in the normal-play Sprague-Grundy theory. Along the way, we'll show how to play X-only Tic-Tac-Toe in misère play and describe some pesky fundamental open problems in the current misère theory.

Tim Roughgarden (Stanford)

The Price of Anarchy in Games of Incomplete Information

Pure-strategy Nash equilibria --- where each player deterministically picks a single action --- are often easier to analyze than their more general cousins like mixed-strategy Nash equilibria (where players can randomize) and Bayes-Nash equilibria (where players don't even know with certainty what game they're playing in).
For this reason, the price of anarchy of a game --- the worst-case ratio between the objective function value of an equilibrium and of an optimal outcome --- is often analyzed, at least initially, only for the game's pure-strategy Nash equilibria. But as much as he or she might want to, the conscientious researcher cannot stop there. For example, the Nash equilibrium concept fundamentally assumes that all players' preferences are common knowledge, which is inappropriate for most auction and mechanism design contexts, where participants have private information.
Can we obtain price of anarchy bounds for more general equilibrium concepts without working any harder than we already do to analyze pure-strategy Nash equilibria? Ideal would be an "extension theorem" that could be used in the following ``black-box'' way: (1) prove a bound on the price of anarchy of pure-strategy Nash equilibria of a game; (2) invoke the extension theorem to conclude immediately that the exact same approximation bound applies to some more general equilibrium concept. Such an extension theorem would dodge the obvious deterrents from generalizing price of anarchy bounds beyond pure Nash equilibria --- no extra work, and no loss in the approximation guarantee.
In this talk, I'll describe an extension theorem for games of incomplete information, along with some applications.

Carlos Santos (Lisbon)

Scoring Combinatorial Game Theory

Combinatorial games originally allowed only winning and losing (and perhaps a draw) as possible outcomes. Scoring combinatorial games also allow for accumulating scores in the course of play. They have been independently studied by John Milnor, Mark Ettinger, Fraser Stewart and Will Johnson. Reminiscent of what was done in Misère Theory, these researchers considered different universes that define play. In these works we cannot observe a clear concern with the relation between the structure of the short Conway's group (the group of short Conway's combinatorial games such that the sets of options are finite) and the proposed scoring structure, which we bridge with our approach. Also, and this is the fundamental result, we propose a well-chosen scoring universe U in such a way that it is possible to establish a natural order-preserving embedding from the short Conway's group into U and it is possible to use Ettinger's ideas with a slightly different definition of stop.

Rahul Savani (Liverpool)

Learning Equilibria of Games via Payoff Queries

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.

Herbert Scarf (Yale)

Reflections on a Sculpture

An elementary exposition of test sets for integer programs.

Eran Shmaya (Northwestern)

Anonymous Games

We first prove that in anonymous games with m actions and with payoff functions that are Lipschitz continuous with constant δ (assumed to be small) there is a pure (approximate) (δm)-equilibrium. This improves on a previous result of Daskalakis and Papadimitriou with m2 instead of m. We also show that our bound is tight. The implications for the complexity of finding the pure equilibrium are rather straightforward and are the same as in their paper. Second, we relate the result to the problem of finding envy-free allocation of resources, which is a problem that has also beeen studied before. Again, our main focus is existence, and the computational implications are straightforward.

Éva Tardos (Cornell)

What Mechanisms are Composable and Efficient?

E-commerce applications require simple and well-designed systems, and systems that work well even if users participate in multiple mechanisms (and the value of each player overall is a complex function of their outcomes). Traditional mechanism design has considered such mechanisms only in isolation, and the mechanisms it proposes tend to be complex and impractical. In contrast, players typically participate in various mechanisms, mechanisms that are run by different principals (e.g. different sellers on eBay or different ad-exchange platforms) and coordinating them to run a single combined mechanism is infeasible or impractical. Even the simple and elegant Vickrey auction loses some of its appeal when not in isolation: when the overall value of each player is a complex function of their outcomes, the global mechanism is no longer truthful.
In this talk we initiate the study of efficient mechanism design with guaranteed good properties even when players participate in multiple different mechanisms either simultaneously or sequentially. Over the last decade, computer scientists and game theorists have developed good understanding of the impact of strategic user behavior on system performance in environments that include selfish traffic routing, service location, and bandwidth sharing. We will consider simple mechanisms from this perspective. We define smooth mechanisms (that can be thought of as mechanisms that generate approximately market clearing prices), and show that smooth mechanisms are approximately efficient, and the efficiency guarantees for smooth mechanisms (when studied in isolation) carry over to the same or approximately the same guarantees for a market composed of such mechanisms.
Joint work with Vasilis Syrgkanis.

Angelina Vidali (Duke)

Mechanism Design for Scheduling with Uncertain Execution Time

We study the problem where a task must be executed. There are multiple machines/agents that can potentially perform the task, and our objective is to minimize the expected sum of the agents' processing times. Each agent does not know exactly how long it will take him to finish the task; he only knows the distribution from which this time is drawn. These times are independent across agents and the distributions fulfill the monotone hazard rate condition. Agents are selfish and will lie about their distributions if this increases their expected utility.
We construct a mechanism that takes as input the agents' reported distributions and that outputs a schedule that minimizes the expected sum of processing times, as well as payments that make it an ex-post equilibrium for the agents to both truthfully report their distributions and exert full effort to complete the task.
Joint work with Vincent Conitzer.

Bernhard von Stengel (LSE)

Computing an Extensive-Form Correlated Equilibrium in Polynomial Time

We present a polynomial-time algorithm for finding one extensive form correlated equilibrium (EFCE) for multiplayer extensive games with perfect recall. This is the first such algorithm for an equilibrium notion for games of this generality. The EFCE concept has been defined by von Stengel and Forges (2008). Our algorithm extends the constructive existence proof by Hart and Schmeidler (1989) and the polynomial-time algorithm for finding a correlated equilibrium in succinctly representable games by Papadimitriou and Roughgarden (2008). The crucial generalization is to allow for games that have exponentially many alternative actions per player and are therefore not of ``polynomial type'', as it is the case for extensive games.
Joint work with Wan Huang.