Nir Andelman

Tel Aviv University

  Friday, July 22, 3:15

Testing Truthfulness for Single Parameter Agents    [pdf]

(joint work with Yishay Mansour)


We consider the task of designing truthful mechanisms for single parameter agents. We prove a general sufficient condition for truthfulness when the valuation function of the agents of any outcome is one dimensional and continuous. For certain types of natural valuation functions, our condition is also necessary. One of the main advantages of our characterization is that it provides a computationally efficient method for testing whether a given algorithm admits a truthful payment scheme.

We then demonstrate the simplicity of testing our condition by showing that classical criteria for truthfulness in combinatorial problems such as auctions and machine scheduling can be derived from our condition. In addition, we use our condition to derive results for new single parameter problems, which have not been previously analyzed.

We also consider combinatorial problems where the true types of agents affect the valuation of each other, such as in load balancing. In such cases there are no efficient dominant strategy mechanisms. We show that the same condition can be used to design mechanisms which are ex-post truthful, meaning that the outcome where all agents cooperate and report their true type is a Nash equilibrium. We demonstrate the power of this condition by applying it on the problem of machine scheduling with strategic job owners, which was not addressed before. We prove upper and lower bounds for ex-post truthful mechanisms for this problem.

Richard Cole

New York University

  Thursday, July 21, 5:00

Toward Discrete Distributed Tatonnement Algorithms for Market Equilibria, part I

Vincent Conitzer

Carnegie Mellon University

  Wednesday, July 20, 3:30

Complexity of (Iterated) Dominance and Other Solution Concepts

(joint work with Tuomas Sandholm)

Parijat Dube

IBM T. J. Watson Research Center

  Friday, July 22, 2:45

Capacity Planning, Quality of Service and Price Wars

Lisa K. Fleischer


  Thursday, July 21, 5:30

Toward Discrete Distributed Tatonnement Algorithms for Market Equilibria, part II

Andrew G. Gilpin

Carnegie Mellon University

  Wednesday, July 20, 4:00

Finding equilibria in large sequential games of incomplete information    [pdf]

(joint work with Andrew Gilpin and Tuomas Sandholm)


Computing an equilibrium of an extensive form game of incomplete
information is a fundamental problem in computational game theory, but
current techniques do not scale to large games. To address this, we
introduce the ordered game isomorphism and the related ordered game
isomorphic abstraction transformation. For an n-player sequential game
of incomplete information with observable actions and an ordered
signal space, we prove that any Nash equilibrium in an abstracted
smaller game, obtained by one or more applications of the
transformation, can be easily converted into a Nash equilibrium in the
original game. We present an efficient algorithm, GameShrink, which
automatically and exhaustively abstracts the game. Using GameShrink,
we find an equilibrium to a poker game that is over four orders of
magnitude larger than the largest poker game solved previously. To
address even larger games, we introduce approximation methods that do
not preserve equilibrium, but nevertheless yield (ex post) provably
close-to-optimal strategies.

Amy Greenwald

Brown University

  Thursday, July 21, 4:00

Multiagent Value Iteration in Markov Games

Sergiu Hart

Hebrew University of Jerusalem

  Wednesday, July 20, 11:00

Uncoupled Dynamics and Nash Equilibrium    [pdf]

(joint work with Andreu Mas-Colell)


We call a dynamical system "uncoupled" if the dynamic for each player does not depend on the payoff functions of the other players. This is a natural informational restriction. We study convergence of uncoupled dynamics to Nash equilibria, and present a number of possibility and impossibility results.

Kamal Jain

Microsoft Research

  Thursday, July 21, 3:30


Ramesh Johari

Stanford University

  Friday, July 22, 11:30

A Contract-Based Model for Directed Network Formation

(joint work with Shie Mannor (McGill) and John N. Tsitsiklis (MIT))


We consider a network game where the nodes of the network wish to form a graph to route traffic between themselves. We present a model where costs are incurred for routing traffic, as well as for a lack of network connectivity. We focus on directed links and the link stability equilibrium concept, and characterize connected link stable
equilibria. The structure of connected link stable networks is analyzed for several special cases.

Hisao Kameda

University of Tsukuba

  Friday, July 22, 1:30

The Degree of a Braess-like Paradox in a Symmetric Network Can Increase without Bound


We first mention noncooperative networks and distinguish between those with non-atomic (infinitely many infinitesimal) users and those with atomic (a finite number of) users. Next, we characterize the concept of Braess-like paradoxes in noncooperative optimization exemplified by the Braess paradox, i.e., after adding means to a network (so that each user has extra freedom in decision) the state of a network is at times Pareto inferior to the state before doing so. We give a measure of the degree of a Braess-like paradox. Then, we present the analysis of a very simple symmetric network with atomic users where the Braess-like paradox is apparently counter-intuitive and where the degree of a Braess-like paradox can increase without bound. In contrast, it seems that there have been seen no networks with non-atomic users where the degree of the Braess-like paradox can increase without bound.

Matt Lepinski

Massachusetts Institute of Technology

  Wednesday, July 20, 6:00

Collusion-Free Protocols

Shie Mannor

McGill University

  Friday, July 22, 11:00

Calibrated Forecasts: Efficiency versus Universality

Silvio Micali

Massachusetts Institute of Technology

  Wednesday, July 20, 9:00

Universal Mechanism Design    [pdf]

(joint work with Sergei Izmalkov and Matt Lepinski)

Peter Bro Miltersen

University of Aarhus

  Thursday, July 21, 3:00

Computing Equilibrium Refinements for Zero-sum Games

(joint work with Troels Bjerre Sorensen)


The linear-programming based algorithm by Koller, Megiddo and von Stengel for computing minimax strategies for extensive-form zero-sum games has been used by the AI community for computing prescriptive strategies for games with hidden information such as poker. We observe that the computation of equilibrium refinements is strongly motivated by such applications. We show that computing sequential equilibria for two-player zero-sum extensive-form games with perfect recall can be done in polynomial time. We discuss whether extensive-form perfect and normal-form proper equilibria for such games can also be found in polynomial time.

Vahab S. Mirrokni

Massachusetts Institute of Technology

  Thursday, July 21, 6:00

Sink Equilibria and Convergence

Ariel Orda


  Friday, July 22, 9:00

Over Two Decades of Research on Networking Games


The application of game theoretic models and tools in the area of networking has been gaining increasing attention in recent years. From what was a rather "esoteric" area of research not many years ago, it has grown to be well within the mainstream of the networking research agenda.

In this talk we shall overview the major stages in the evolution of this area. First, we shall move back 4-5 decades and examine some of the early (game theoretic) advances in related fields such as queuing systems and transportation networks. Then, we shall move on to about 2 decades ago, and examine the early steps of game theory in communication networks. We will consider the early motivation, contrast it with current motivation, and overview some of the (early) fundamental results in flow-control and routing games. Moving on to more recent studies, we shall observe the main issues at stake, namely characterization of the network properties and performance in a noncooperative environment, and an attempt to improve the inherent inefficiency that stems from unregulated behavior, via proper design and management (in particular, pricing) tools. We shall conclude by outlining several current challenges and opportunities for future work.

Tuomas Sandholm

Carnegie Mellon University

  Wednesday, July 20, 3:00

Approximating Revenue-Maximizing Combinatorial Auctions    [pdf]

(joint work with Anton Likhodedov and Tuomas Sandholm)


Designing revenue-maximizing combinatorial auctions (CAs)
is a recognized open problem in mechanism design. It is unsolved
even for two bidders and two items for sale. Rather than
attempting to characterize the optimal auction, we focus on
designing approximations (suboptimal auction mechanisms which
yield high revenue).

Our approximations belong to the family of virtual valuations
combinatorial auctions (VVCA), which we introduced in AAAI-04.
VVCA is a Vickrey-Clarke-Groves (VCG) mechanism run on virtual
valuations that are linear transformations of the bidders' real valuations.

We pursue two approaches to constructing approximately optimal
CAs. The first is to construct a VVCA with worst-case and
average-case performance guarantees. We give a logarithmic
approximation auction for basic important special cases of the
problem: 1) limited supply of items on sale with additive
valuations and 2) unlimited supply. The second approach is to
search the parameter space of VVCAs in order to obtain
high-revenue mechanisms for the general problem. We introduce a
series of increasingly sophisticated algorithms that use economic
insights to guide the search and thus reduce the computational
complexity. Our experiments demonstrate that in many cases these
algorithms perform almost as well as the optimal VVCA, yield a
substantial increase in revenue over the VCG mechanism and
drastically outperform the straightforward algorithms in run-time.

Rahul Savani

London School of Economics

  Thursday, July 21, 10:00

Hard-to-solve Bimatrix Games

Abhi Shelat

Massachusetts Institute of Technology

  Wednesday, July 20, 5:30


Nahum Shimkin


  Friday, July 22, 10:00

Topological Conditions for Uniqueness of the Nash Equilibrium in Competitive Routing

Éva Tardos

Cornell University

  Wednesday, July 20, 10:00

Price of Anarchy for a Network Pricing Game for Selfish Traffic    [pdf]

(joint work with Ara Hayrapetyan and Tom Wexler)


The success of the Internet is remarkable in light of the decentralized manner in which it is designed and operated. Unlike small scale networks, the Internet is built and controlled by a large number of disperate service providers who are not interested in any global optimization. Instead, providers simply seek to maximize their own profit by charging users for access to their service. Users themselves also behave selfishly, optimizing over price and quality of service. Game theory provides a natural framework for the study of such a situation. However, recent work in this area tends to focus on either the service providers or the network users, but not both. This paper introduces a new model for exploring the interaction of these two elements, in which network managers compete for users via prices and the quality of service provided. We study the extent to which competition between service providers hurts the overall social utility of the system.

Paul Valiant

Massachusetts Institute of Technology

  Wednesday, July 20, 5:00


Bernhard Von Stengel

London School of Economics

  Thursday, July 21, 9:00

Geometric Views of Linear Complementarity Algorithms and Their Complexity

Laura Wynter

IBM Research

  Friday, July 22, 2:00


Yinyu Ye

Stanford University

  Thursday, July 21, 11:00

On Exchange Market Equilibria with Leontief's Utilities: Hardness Results and Hopeful Algorithms