13.07.03 - 18.07.03, Seminar 03291
Algorithmic Game Theory and the Internet
Organizers
M. Karpinski (Univ. Bonn, D), C. Papadimitriou (UC Berkeley, US), V. Vazirani (Georgia Tech, Atlanta, US)
Documents
Summary
The seminar was devoted to the most important recent developments in the area of the Algorithmic Game Theory connected to the problems arising from, and motivated by, the Internet and other decentralized computer networks. The most defining characteristic of the Internet is that it was not designed by a single central entity, but emerged from the complex interaction of many economic agents, such as network operators, service providers, designers, users, etc., in varying degrees of collaboration and competition. The major questions that arise in that context are in analysis of its performance and in evaluation of its long term equilibria. They include all sorts of completely new questions that lie on the interface of the fields of networks, algorithms and game theory.
The focus of the workshop was on the following specific topics:
and
Some new broadly applicable techniques have emerged recently in the above areas and the workshop has addressed those developments and new fundamental insights. The workshop has also addressed and formulated important open problems of the area and identified most challenging research directions for the future.
The 47 participants of the workshop came from various research areas connected to the main topic of the workshop. The 31 lectures delivered at the workshop covered wide body of recent research in the area. In addition, a special evening session was devoted to presentation of open problems.
The meeting was held in a very pleasant and stimulating atmosphere. Thanks to everyone who made it a very interesting and enjoyable event!
Program
Monday, July 14th, 2003
| 09:00 - 09:10 | Opening |
| Chair: | Marek Karpinski |
| 9:10 - 9:40 | Nikhil R. Devanur (Georgia Institute of Technology) Market Equilibrium: Algorithms for the Linear Case |
| 9:40 - 10:10 | Vijay Vazirani (Georgia Institute of Technology) Market Equilibrium when Buyers have Spending Constraints |
| 10:10 - 10:40 | Steven Low (CalTech - Pasadena) Duality and Stability Models of Internet Congestion Control |
| Chair: | Vijay Vazirani |
| 11:00 - 11:30 | Daniel Lehmann (University of Jerusalem) Equilibria in Exchange Economies |
| 11:30 - 12:00 | Rudolf Müller (Maastricht University) On the Complexity of Auctions |
| Chair: | Daniel Lehmann |
| 15:00 - 15:30 | Yoav Shoham (Stanford) On the non-comparable paranoias of game theory and cryptography |
| 15:30 - 16:00 | Subhash Suri (University of California at Santa Barbara) Nash Equilibrium Load Balancing |
| Chair: | Mark Jerrum |
| 16:30 - 17:00 | Rahul Sami (Yale University) Computation in a Distributed Information Market |
| 17:00 - 17:30 | Artur Czumaj (New Jersey Inst. of Technology) Worst-Case Equilibria for Server Farms |
Tuesday, July 15th, 2003
| Chair: | Martin Dyer |
| 09:00 - 09:30 | Christos Papadimitriou (Berkeley) Nash Equilibria and Complexity |
| 09:30 - 10:00 | Milena Mihail (Georgia Institute of Technology) Algorithmic Performance on Power Law Graphs |
| 10:00 - 10:30 | Elias Koutsoupias (University of California at Los Angeles) Coordination Mechanisms |
| Chair: | Michael Paterson |
| 11:00 - 11:30 | Rica Gonen (University of Jerusalem) Incentive Compatible Multi-Unit Combinatorial Auctions |
| 11:30 - 12:00 | Piotr Krysta (MPI für Informatik) Computing Equilibria for Congestion Games |
| Chair: | Elias Koutsoupias |
| 15:00 - 15:30 | Jason Hartline Profit Maximizing Envy-Free Auctions |
| 15:30 - 16:00 | Bernhard von Stengel (London School of Economics) Hard-To-Solve Bimatrix Games |
| Chair: | Leonard J. Schulman |
| 16:30 - 17:00 | Amitabh Sinha (CMU - Pittsburgh) Min-max Payoffs of a Location Game |
| 17:00 - 17:30 | Aaron Archer (Cornell University) Approximate Truthful Mechanisms fo a Combinatorial Auction |
Wednesday July 16th, 2003
| Chair: | Noam Nisan |
| 09:00 - 09:30 | Eva Tardos (Cornell University) Network Design Games |
| 09:30 - 10:00 | Amir Ronen (Technion - Haifa) Optimal Auctions - A Theorectical Computer Science-based Approach |
| 10:00 - 10:30 | Tim Roughgarden (Cornell University) Pricing Networks with Selfish Routing |
| Chair: | Eva Tardos |
| 11:30 - 12:00 | Sven de Vries (TU München) On Ascending Vickrey Auctions for Heterogeneous Objects |
| 20:00 | Evening Session |
| Chair: | Vijay Vazirani |
Thursday July 17th, 2003
| Chair: | Christos Papadimitriou |
| 09:00 - 09:30 | Noam Nisan (University of Jerusalem) Characterization of truthful combinatorial auctions I : Are there non-VCG mechanisms ? |
| 09:30 - 10:00 | Ahuva Mu'alem (University of Jerusalem) Characterization of truthful combinatorial auctions II: Truthfullnes, monotonicity, and IIA |
| 10:00 - 10:30 | Ron Lavi (University of Jerusalem) Characterization of truthful combinatorial auctions III: Proof of main theorem |
| Chair: | Rica Gonen |
| 11:00 - 11:30 | Leonard J. Schulman (Caltech) Router Congestion Control |
| 11:30 - 12:00 | Eric Friedman (Cornell University) Fairness and Stability of Sharing Protocols for the Unlicensed Bands |
| Chair: | Sven de Vries |
| 15:00 - 15:30 | Meir Bing (University of Jerusalem) Representing Substitutes Valuation |
| 15:30 - 16:00 | Anupam Gupta (Carnegie Mellon University) Approximation Algorithms via Cost Sharing |
Friday July 18th, 2003
| Chair: | Miklos Santha |
| 09:00 - 09:30 | Michel de Rougemont (Universite Paris Sud) Definable Strategies in Games |
| 09:30 - 10:00 | Petra Berenbrink (Simon Fraser University) Utilitarian Resource Assignment |
Keywords
- Algorithmic Game Theory
- Internet
- Approximation Algorithms
- Inherent Complexity
- Resource Allocation
- Stability
- Nash Equilibria
- Mechanism Design
- Combinatorial Auctions
- Cost Allocations
- Cryptography
- Congestion Fairness
- Stability
- Routing
- Load Balancing
- Network Design
