Game Theory Discussion Group - Fall 2006

Given a graph G, consider the problem of finding a distribution over maximum matchings of G, in which, as much as possible, the probability of each vertex being matched is as equal as possible.

This problem has been studied in a sequence of recent papers in the Economics community, culminating in the following results:

1) there exists a Lorenz dominant distribution, i.e. one in which the sum of the lowest k vertex probabilities is at least as great as in any other distribution, for any k.

2) this distribution can be found in polynomial time for bipartite graphs

In this presentation, we will see a greatly simplified existence proof, and also a polynomial-time algorithm for general graphs.

This talk will discuss recent work involving emerging empirical methodologies in the field of computational game theory. We will discuss three papers, published this year by members of the AI Lab at the University of Michigan, which provide a first look at the techniques and challenges involved in applying game theory in a complex empirical (rather than abstract) setting. The first two papers deal with estimating a simplified version of a complex game's normal form through experimentation, then applying normative game-theoretic analysis to the learned game (Wellman et. al., 2006a, Wellman et. al. 2006b). The third paper approaches mechanism design with a framework that integrates game-theoretic models of self-interested agent behavior with statistical models learned empirically (Vorobeychik et. al., 2006). We will conclude with a discussion about the potential impact of this trend towards empiricism on our work.

[Wellman et. al. 2006a] Wellman, Jordan, Kiekintveld, Miller, and Reeves. Empirical game-theoretic analysis of the TAC market games. AAMAS.06 Workshop on Game-Theoretic and Decision-Theoretic Agents, 2006.

[Wellman et. al. 2006b] Wellman, Reeves, Lochner, and Suri. Searching for Walverine 2005. in Han La Poutre, Norman Sadeh and Sverker Janson (eds.), Agent-Mediated Electronic Commerce: Designing Trading Agents and Mechanisms, LNAI 3937, Springer Verlag, 2006.

[Vorobeychick et. al. 2006] Vorobeychik, Kiekintveld, and Wellman. Empirical mechanism design: Methods, with application to a supply chain scenario. ACM Electronic Commerce, 2006.

In this talk I will give a brief introduction to equilibrium refinements and how one can compute equilibria with these added properties. The talk will focus on two papers, published earlier this year, and some work yet to be published.

[1] P. B. Miltersen and T. B. Sørensen, Computing sequential equilibria for two-player games, SODA'06

[2] P. B. Miltersen and T. B. Sørensen, Computing Proper Equilibria of Zero-Sum Games, CG'06

Column generation is a classical technique for solving large linear programs. In this talk, we will cover column generation, as well as its extension for integer programs, namely branch-and-price. Throughout, we will be using the following problem as an example.

Kidney-exchange problem [Directed cycle cover with small cycles]: Given a directed weighted graph, find a maximum weight collection of disjoint cycles such that no cycle has length more than some given K.