Dagstuhl Seminar 03291
Algorithmic Game Theory and the Internet
( Jul 13 – Jul 18, 2003 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/03291
Organizers
- Marek Karpinski (Universität Bonn, DE)
- Christos H. Papadimitriou (University of California - Berkeley, US)
- Vijay V. Vazirani (Georgia Institute of Technology - Atlanta, US)
Contact
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:
- design of efficient algorithms for game theoretic problems connected to the Internet,
- inherent complexity of game theoretic problems,
- resource allocation and stability,
- Nash equilibria,
- market equilibria,
- mechanism design,
- economic aspects of the Internet,
- combinatorial auctions and
- cost allocations, network design.
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!
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 |
- Aaron Archer (Cornell University, US)
- Petra Berenbrink (Simon Fraser University - Burnaby, CA) [dblp]
- Meir Bing (The Hebrew University of Jerusalem, IL)
- Norbert Blum (Universität Bonn, DE)
- Artur Czumaj (NJIT - Newark, US) [dblp]
- Michel de Rougemont (Université Paris Sud, FR)
- Sven de Vries (TU München, DE)
- Nikhil Devanur Rangarajan (Georgia Institute of Technology - Atlanta, US) [dblp]
- Martin Dyer (University of Leeds, GB) [dblp]
- Lisa K. Fleischer (IBM TJ Watson Research Center, US) [dblp]
- Eric Friedman (Cornell University, US)
- Rica Gonen (The Hebrew University of Jerusalem, IL)
- Anupam Gupta (Carnegie Mellon University, US) [dblp]
- Jason Hartline (Microsoft Corp. - Mountain View, US) [dblp]
- Mathias Hauptmann (Universität Bonn, DE)
- Mark R. Jerrum (University of Edinburgh, GB) [dblp]
- Marek Karpinski (Universität Bonn, DE) [dblp]
- Elias Koutsoupias (University of Athens, GR) [dblp]
- Piotr Krysta (TU Dortmund, DE) [dblp]
- Ron Lavi (Hebrew University - Jerusalem, IL) [dblp]
- Daniel Lehmann (The Hebrew University of Jerusalem, IL) [dblp]
- Steven Low (CalTech - Pasadena, US)
- Milena Mihail (Georgia Institute of Technology - Atlanta, US) [dblp]
- Ahuva Mu'alem (Hebrew University - Jerusalem, IL)
- Rudolf Müller (Maastricht University, NL) [dblp]
- Yakov Nekrich (Universität Bonn, DE) [dblp]
- Noam Nisan (The Hebrew University of Jerusalem, IL) [dblp]
- Christos H. Papadimitriou (University of California - Berkeley, US) [dblp]
- Mike S. Paterson (University of Warwick - Coventry, GB) [dblp]
- Amir Ronen (Technion - Haifa, IL)
- Tim Roughgarden (Stanford University, US) [dblp]
- Rahul Sami (Yale University, US)
- Miklos Santha (Université Paris Sud, FR) [dblp]
- Leonard J. Schulman (Caltech - Pasadena, US) [dblp]
- Yoav Shoham (Stanford University, US) [dblp]
- Amitabh Sinha (Carnegie Mellon University, US)
- Subhash Suri (University of California - Santa Barbara, US) [dblp]
- Éva Tardos (Cornell University, US) [dblp]
- Vijay V. Vazirani (Georgia Institute of Technology - Atlanta, US) [dblp]
- Berthold Vöcking (RWTH Aachen, DE) [dblp]
- Bernhard von Stengel (London School of Economics, GB) [dblp]
- Peter Wegner (Universität Bonn, DE)
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
