Workshop on Algorithmic Game Theory

DIMAP, University of Warwick, UK

March 25 - 28, 2007

Follow the links to access abstracts and NEW! slides for the talks



Sunday, March 25

  9:00 - 10:00    Registration: building of the Warwick Mathematics Institute
10:00 - 10:10    Opening
10:10 - 10:40    Uri Zwick (Tel Aviv University, Israel)
    Simple Stochastic Games, Mean Payoff Games and Parity Games  [Slides]
10:40 - 11:10    Seffi Naor (Microsoft Research and Technion, Haifa, Israel)
      Best Response Dynamics in Multicast Cost Sharing  [Slides]
  Coffee break
11:40 - 12:10    Richard Cole (New York University, USA)
       Why Might Markets be Self-converging? A Local, Quickly Convergent Tatonnement Algorithm  [Slides]
12:10 - 12:40    Kamal Jain (Microsoft Research, Redmond, USA)
      On Stability of the Core  [Slides]
12:40 -   Lunch (CS building)
  2:10 -   2:40    Amin Saberi (Stanford University, USA)
      Approximation Algorithms for Max-Min Fair Allocation of Indivisible Goods  [Slides]
  2:40 -   3:10    Uri Feige (Weizmann Institute, Israel and Microsoft Research, Redmond, USA)
      On Allocations that Maximize Fairness  [Slides]
  Coffee break
  3:50 -   4:40    Keynote Speaker: V.V. Vazirani (Georgia Tech)
      Markets and the Primal-Dual Paradigm  [Slides, paper 1 and paper 2]
  4:40 -   5:10    Yossi Azar (Tel Aviv University, Israel and Microsoft Research, Redmond, USA)
      (Almost) Optimal Coordination Mechanisms for Unrelated Machine Scheduling  [Slides]
  5:10 -   5:40    Elias Koutsoupias (University of Athens, Greece)
      Lower Bounds of Mechanisms for Scheduling Unrelated Machines  [Slides]
  6:30 - Dinner at Radcliffe House (on the campus)

Monday, March 26

  9:00 -   9:50    Keynote Speaker: É. Tardos (Cornell)
      Pricing Games in Networks  [Slides]
  9:50 - 10:20    David M. Pennock (Yahoo! Research, New York, USA)
      Computational Aspects of Prediction Markets  [Slides]
  Coffee break
11:00 - 11:30    Bernhard von Stengel (London School of Economics, United Kingdom)
    Finding all Nash Equilibria of a Bimatrix Game  [Slides]
11:30 - 12:00    Kousha Etessami (University of Edinburgh, UK)
    On the Complexity of Approximating Exact Fixed Points:
     Nash Equilibria, Stochastic Games, and Recursive Markov Chains  [Slides]
12:05 - Lunch (CS building)
  2:00 -   2:50    Keynote Speaker: C. H. Papadimitriou (Berkeley)
      Equilibria and Complexity: What now?  [Slides]
  2:50 -   3:20    Vincent Conitzer (Duke University, USA)
      Preprocessing Techniques for Computing Nash Equilibria  [Slides; paper 1 and paper 2]
  Coffee break
  3:50 -   4:20    Paul Spirakis (University of Patras, Greece, and CTI Patras, Greece)
      Well-Supported Approximate Nash Equilibria  [Slides]
  4:20 -   4:50    Adrian Vetta (McGill University, Canada)
      Finding Nash Equilibria in Certain Classes of 2-Player Game  [Slides]
  5:00 -   6:00    Reception/launch of DIMAP
  6:00 - Panel Discussion:
     »Algorithmic Game Theory - Where Does it Stand and Where Can it Go?«
     Panelist: F. Kelly, N. Nisan, C. Papadimitriou, D.M. Pennock, T. Roughgarden, E. Tardos, V. Vazirani (lead)

Tuesday, March 27

  9:00 -   9:50    Keynote Speaker: T. Roughgarden (Stanford)
      Quantifying Inefficiency in Mechanism and Protocol Design  [Slides]
  9:50 - 10:20    Amir Ronen (Technion, Haifa, Israel)
      The Local and Global Price of Anarchy of Graphical Games  [Slides]
  Coffee break
11:00 - 11:30    Stefano Leonardi (Universita' di Roma "La Sapienza", Roma, Italy)
      Efficient Cost Sharing Mechanisms for Prize-collecting Steiner Forest  [Slides]
11:30 - 12:00 Burkhard Monien (University of Paderborn, Germany)
      The Power of Two-Prices: Beyond Cross-Monotonicity  [Slides]
12:05 - Lunch (CS building)
  1:30 -   2:00    Berthold Vöcking (RWTH Aachen, Germany)
      Inapproximability of Congestion Games  [Slides]
  2:00 -   2:30    Frank Kelly (Cambridge University, UK)
      Congestion Control Algorithms  [Slides]
  2:30 -   3:00    Amos Fiat (Tel Aviv University, Israel)
      Efficient Contention Resolution Protocols for Selfish Agents  [Slides]
  3:05 - Excursion to Kenilworth Castle
  6:30 - Conference Dinner, Cross Restaurant, Kenilworth

Wednesday, March 28

  9:00 -   9:50    Keynote Speaker: N. Nisan (Hebrew University)
    Approximation Mechanisms and Characterization of Implementable Social Choice Rules  [Slides]
  9:50 - 10:20    Jason D. Hartline (Microsoft Research, Mountain View, USA)
    The Simple Mathematics of Optimal Auctions  [Slides]
Coffee break
11:00 - 11:30    Shahar Dobzinski (Hebrew University, Israel)
    Truthful Mechanisms for Combinatorial Auctions with Subadditive Bidders  [Slides]
11:30 - 12:00    Piotr Krysta (University of Liverpool, UK)
    Approximability of Pricing Problems  [Slides]
12:05 - Lunch (CS building)