DIMACS Workshop on Computational Issues in Game Theory and Mechanism Design

October 31 - November 2, 2001
DIMACS Center, Rutgers University, Piscataway

Organizers:

Vijay Vazirani, Georgia Tech, vazirani@cc.gatech.edu

Noam Nisan, Hebrew University, Jerusalem, Israel, noam@cs.huji.ac.il

Workshop Program:

Wednesday, October 31, 2001

8:45-9:15       Breakfast and Registration

9:15-9:20       Welcome and Greeting:
                Fred S. Roberts, DIMACS Director

9:20-9:30       Welcome and Greeting:
                Noam Nisan, Hebrew University
                Vijay Vazirani, Georgia Tech

Session Chair: Vijay Vazirani, Georgia Tech

9:30-10:30      Christos Papadimitriou, University of California - Berkeley
                Algorithmic Issues in Game Theory

10:30-11:15     Jon Kleinberg Cornell University 
                Fairness Measures in Optimization

                Tal Rabin, IBM
                A Cryptographic Solution to a Game Theoretic Problem

11:15-11:45     Break

11:45-12:30     Kamal Jain, Microsoft Research
                Equitable, Group Strategyproof Cost Allocations via
                Primal-Dual-Type Algorithms            
 
                Michael Kearns, Syntek Capital
                Graphical Models for Game Theory

12:30-2:00      Lunch

Session Chair: Joan Feigenbaum, Yale University

2:00-3:00       Scott Shenker, University of California - Berkeley
                Mechanism Design and the Internet

3:00-4:15       Eric Friedman, Cornell University
                A Generic Analysis of Selfish Routing

                Peter Key, Microsoft Research, Cambridge 
                Mixing Streaming and Flow-Controlled Traffic in Networks:
                Distributed Control Incentives

                Elias Koutsoupias, UCLA
                Selfish Resource Allocation

4:15-4:45       Break

4:45-6:00       Rahul Sami, Yale University
                Approximation and Collusion in Multicast Cost Sharing

                Eva Tardos, Cornell University
                How Bad is Selfish Routing?

                Tim Roughgarden, Cornell University
                Designing Networks for Selfish Users is Hard

8:00-           Rump session - Session Chair: Noam Nisan, Hebrew University
                All participants are invited to make 5 minute presentations.
                Please send title and (optional) abstract plus URL to a paper
                or a presentation to Noam Nisan at Noam@cs.huji.ac.il.

                Vijay Vazirani, Georgia Tech
                Strategyproof profit-maximization via fixed point computations
                (work in progress) Joint work with Aranyak Mehta and 
                Scott Shenker.

                Tim Roughgarden, Cornell University
                The Price of Anarchy is Independent of the
                Network Topology

                Chris Dellarocas, MIT and NYU
                Dynamic optimization framework for designing
                effective online reputation mechanisms

                Sasa Pekec, The Fuqua School of Business, Duke University
                Data aggregation in combinatorial auction design

                Ahuva Mualem, Hebrew University
                Truthful Approximation Mechanisms for Restricted
                Combinatorial Auctions

                Ron Lavi, Hebrew University
                Competitive Analysis of Incentive Compatible Online Auctions              

                Liad Blumrosen, Hebrew University
                Auctions with bounded communication
               
                Daniel Grosu, University of Texas, San Antonio
                A Cooperative Load Balancing Game in Distributed Systems
                                
                Aaron Archer, Cornell University
                Mechanisms for One-Parameter Agents
                
                Michael Rothkopf, Rutgers University
                Designing and Analyzing Auctions: the Devil is in the details
                (and not just on Halloween) and some scary heresies

                Arvind Krishnamurty, Yale University
                Lower Bounds on Multicast Cost Sharing

                Joan Feigenbaum, Yale University
                Incentive-compatible Interdomain Routing
                (Joint work with Christos Papadimitriou, Rahul Sami
                and Scott Shenker)

                David M. Pennock, NEC
                Compact Securities Markets for Minimizing Risk and
                Maximizing Information

                Artur Czumaj, New Jersey Institute of Technology
                Tight Bounds for Worst-Case Equilibria

                                

Thursday, November 1, 2001

8:30-9:00       Breakfast and Registration

Session Chair: Michael Rothkopf, Rutgers University

9:00-10:00      Rakesh Vohra, Northwestern University
                Combinatorial Auctions

10:00-11:15     Daniel Lehmann, Hebrew University
                Combinatorial Auctions with Decreasing Marginal Utilities

                David Parkes, Harvard University
                Minimal Preference Elicitation: An Equilibrium Approach

                Tuomas Sandholm, Carnegie Mellon University
                Bidding Agents with Complex Valuation Problems in Autions

11:15-11:45     Break

11:45-1:00      Ion Mandoiu, Georgia Tech
                XOR Auctions with Buyer Preferences and Seller Priorities

                Sven de Vries, Munchen
                Linear Programming and Ascending Auctions

                Ilya Segal, Stanford University
                The Communication Complexity of Efficient Discrete Allocations

1:00-2:30       Lunch

Session Chair: Chris Dellarocas, MIT and NYU

2:30-3:30       Michael Wellman, University of Michigan
                Trading Agents

3:30-4:40       Amy Greenwald, Brown University
                Correlated Q-Learning

                Bhaskar Dutta, Indian Statistical Institute, Delhi
                Cost Momotonicity, Consistency and Minimum Cost Spanning
                Tree Games

                Rudolf Muller, Maastricht University
                On the Complexity of Auctions

4:40-5:00       Break

5:00-6:30       Panel Discussion: Computer Science and Game Theory 
                Methodological Differences and How to Overcome Them
                Moderator: Rakesh Vohra, Northwestern University

                John Nash, Princeton University
                Andrew Odlyzko, University of Minnesota
                Christos Papadimitriou, University of California, Berkeley 
                Mark Satterthwaite, Northwestern University
                Scott Shenker, University of California, Berkeley
                Micahel Wellman, University of Michigan

7:15-           Banquet (at the Holiday Inn in South Plainfield)


Friday, November 2, 2001

8:30-9:00       Breakfast and Registration

Session Chair: TBA

9:00-10:00      Mark A. Satterthwaite, Northwestern University
                Mechanism Design Under Incomplete Information:
                Uses, Limitations and the Necessity of Computational Approaches

10:00-10:45     Ilan Kremer, Stanford University
                Divisible Good Auctions - the role of allocation rules

                Amir Ronen, Stanford University
                On Approximating Optimal Auctions

10:45-11:15     Break

11:15-12:30     Andrew V. Goldberg, InterTrust STAR Lab
                Design of Competitive Mechanisms

                Jason Hartline, Washington University
                Two Results On Competitive Auctions

                Anna Karlin, Washington University
                Open Problems in Competitive Auction Design

12:30-2:00      Lunch

Session Chair: TBA

2:00-3:00       Andrew Odlyzko, University of Minnesota
                Pricing, Behavioral Economics and Mechanism Design

3:00-3:45       Michel Goemans, MIT
                Cooperative Facility Location Games

                Jeffrey MacKie-Mason, University of Michigan
                An Evolutionary Games Analysis of Bidding Strategies in a
                Scheduling Auction

Previous: Participation

Next: Registration

Workshop Index

DIMACS Homepage