**
Speakers**

Stanford, Google and Berkeley
Prize in Game Theory and Computer Science of the Game Theory Society in Honor of Ehud Kalai |

UC Berkeley
(Joint work with Sushil Verma) 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. |

Yale University
We present an application of "Bayes Correlated Equilibrium" using a few nice finite, algorithmic arguments. |

New York University
(Joint work with Yun Kuen and Nikhil Devanur) 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. |

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

Weizmann Institute of Science
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. |

University of Waterloo
(Joint work with Linda Farczadi and Konstantinos Georgiou) 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. |

Claremont McKenna College, Pitzer College, Scripps College
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. |

Chalmers, Goteborgs Universitet
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. |

Georgia Institute of Technology
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. |

Dalhousie University
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. |

Yale University
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. |

Counterwave, Inc
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. |

Stanford University
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. |

University of Lisbon
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. |

University of Liverpool
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. |

Yale University
An elementary exposition of test sets for integer programs. |

Northwestern University
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. |

Cornell University
(Joint work with Vasilis Syrgkanis)
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. |

Duke University
(Joint work with Vincent Conitzer) 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. |

London School of Economics
(Joint work with Wan Huang) 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. |