Group photo in front of the Three Village Inn on 17 July 2013 by Angelina Vidali
Click on a speaker name for title and abstract.
|
time |
Tuesday 16 July |
Wednesday 17 July |
Thursday 18 July |
|
|
|
|
|
|
9:00- 9:45 |
|||
|
coffee break |
|
|
|
|
10:15-11:00 |
|||
|
11:00-11:45 |
Prize lecture: Michael Ostrovsky, Michael Schwarz, and Hal Varian |
||
|
coffee break |
|
|
|
|
12:00-12:45 |
|||
|
12:45-14:00 lunch |
|
|
|
|
14:00-14:45 |
|||
|
14:45-15:30 |
|||
|
coffee break |
|
|
- finish - |
|
16:00-16:45 |
|
||
|
16:45-17:30 |
|
||
|
|
|
|
|
|
18:00-22:00 |
|
workshop reception and dinner |
|
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)
|
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.
|
|
|
The Limits of Price Discrimination |
We present
an application of "Bayes Correlated Equilibrium" using a
few nice finite, algorithmic arguments. |
|
|
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.
|
|
|
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. |
|
|
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. |
|
|
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.
|
|
|
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. |
|
|
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. |
|
|
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. |
|
|
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 |
|
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.
|
|
|
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. |
|
|
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).
|
|
|
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. |
|
|
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. |
|
|
Reflections on a Sculpture |
An elementary exposition of test sets for integer programs. |
|
|
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. |
|
|
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.
|
|
|
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.
|
|
|
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.
|