Path: SAGT 2009/ > Program

Paphos - Cyprus

October 18 - 20, 2009

Invited Speakers
Call for papers
How to submit
Camera Ready Instr.
Venue Site
Important Dates
Accepted Papers
About Cyprus
Getting to Cyprus

Supported by:

University of Cyprus


Integrated Project


European Association for Theoretical Computer Science


Limassol Co-operative Savings Bank Ltd


IBM Cyprus






The session room will have a data/video-projector, a laptop, a screen and an overhead projector.

Speakers planning an electronic presentation may either

(i) use the provided laptop


(ii) bring their own laptop. (If you plan to bring and use a mac/apple laptop, you must also bring the adaptor

required for connecting to a data/video-projector cable.)

Each contributed talk should go for 20 minutes, leaving some additional minutes for discussion.


Tentative schedule



Saturday 17 October 2009

  • 18:00-20:00 Registration

  • 20:00-22:00 Welcome Reception

Sunday 18 October 2009

  • 8:00-9:15 Registration

  • 9:15-10:15 Invited Talk by Elias Koutsoupias:

                           Approximate Price of Anarchy and Stability

                            Session Chair: Marios Mavronicolas

  • 10:15-10:45 Coffee Break

  • 10:45-12:25 Session 1 (Congestion Games)

                         Session Chair: Edith Elkind

    • Tobias Harks, Max Klimm and Rolf H. Moehring,
      Characterizing the Existence of Potential Functions in Weighted Congestion Games

    • Vittorio Bilò, Angelo Fanelli, Michele Flammini and Luca Moscardelli,
      Performances of One-Round Walks in Linear Congestion Games

    • Tanmoy Chakraborty and Sanjeev Khanna,
      Nash Dynamics in Constant Player and Bounded Jump Congestion Games

    • Andrew Byde, Maria Polukarov and Nicholas Jennings,
      Games with Congestion-Averse Utilities

  • 12:30-14:30 Lunch Break

  • 14:30-16:10 Session 2 (Potpourri)

                         Session Chair: Elias Koutsoupias

    • Yoram Bachrach, Edith Elkind, Reshef Meir, Dmitrii Pasechnik, Michael Zuckerman,

      Joerg Rothe and Jeffrey Rosenschein,
      The Cost of Stability and Its Application to Weighted Voting Games

    •  Hyunwoo Jung and Kyung-Yong Chwa,
      The Balloon Popping Problem Revisited: Lower and Upper Bounds

    • Rajiv Raman, Khaled Elbassioni, Saurabh Ray and Rene Sitters,
      On Profit-Maximizing Pricing for the Highway and Tollbooth Problems

    • Edith Elkind, Piotr Faliszewski and Arkadii Slinko,
      Swap Bribery

  • 16:10-16:40 Coffee Break

  • 16:40-18:20 Session 3 (Scheduling and Routing)

                         Session Chair: Vittorio Bilo

    • Elliot Anshelevich and Satish Ukkusuri,
      Equilibria in Dynamic Selfish Routing

    • Ronald Koch and Martin Skutella,
      Nash Equilibria and the Price of Anarchy for Flows Over Time

    • Kim Thang Nguyen and Christoph Dürr,
      Non-Clairvoyant Scheduling Games

    • Christine Chung and Evangelia Pyrga,
      Stochastic Stability in Internet Router Congestion Games

Monday 19 October 2009

  • 9:15-10:15 Invited Talk by Mihalis Yannakakis:

                           Computational Aspects of Equilibria

                            Session Chair: Paul Spirakis

  • 10:15-10:45 Coffee Break

  • 10:45-12:25 Session 4 (Solution Concepts and Complexity)

                         Session Chair: Pino Persiano  

    • Felix Brandt, Markus Brill, Felix Fischer and Jan Hoffmann,
      The Computational Complexity of Weak Saddles

    • Michal Feldman and Moshe Tennenholtz,
      Partition Equilibrium

    • Joshua Letchford, Vincent Conitzer and Kamesh Munagala,
      Learning and Approximating the Optimal Strategy to Commit To

    • Felix Brandt, Markus Brill, Felix Fischer and Paul Harrenstein,
      On the Complexity of Iterated Weak Dominance in Constant-Sum Games

  • 12:30-14:00 Lunch Break

  • 14:00 Bus departure to excursion (excursion program)

Tuesday 20 October 2009

  • 9:15-10:15 Invited Talk by Noam Nisan :

                           Google´s Auction for TV ads

                       Session Chair: Burkhard Monien 

  • 10:15-10:45 Coffee Break

  • 10:45-12:25 Session 5 (Potpourri)

                         Session Chair: Michal Feldman 

    • Elliot Anshelevich, Sanmay Das and Yonatan Naamad,
      Anarchy, Stability, and Utopia: Creating Better Matchings

    •  Leah Epstein and Asaf Levin,
      On equilibria for ADM minimization games

    • Martin Hoefer, Lars Olbrich and Alexander Skopalik,
      Doing Good with Spam is Hard

    • Elliot Anshelevich and Bugra Caskurlu,
      Price of Stability in Survivable Network Design


  • 12:30-14:30 Lunch Break

  • 14:30-16:10 Session 6 (Mechanism Design and Auctions)

                         Session Chair: Krzysztof Apt

    • Shahar Dobzinski and Noam Nisan,
      A Modular Approach to Roberts' Theorem

    • Oren Ben-Zwi, Ilan Newman and Guy Wolfovitz,
      A Perfect Auction Derandomization

    • Po-An Chen and David Kempe.
      Bayesian Auctions with Friends and Foes

    • Moshe Babaioff, Michal Feldman and Noam Nisan,
      Free-Riding and Free-Labor in Combinatorial Agency

  • 16:10-16:40 Coffee Break

  • 16:40-18:45 Session 7 (Mechanisms)

                         Session Chair: George Christodoulou 

    •  Andre Berger, Rudolf Mόller and Seyed Hossein Naeemi,
      Characterizing Incentive Compatibility for Convex Valuations

    • Clemens Thielen and Sven Krumke,
      Truthful Mechanisms for Selfish Routing and Two-Parameter Agents

    • Abraham Othman and Tuomas Sandholm,
      Better with Byzantine: Manipulation-Optimal Mechanisms

    • Jose Correa and Nicolas Figueroa,
      On the planner’s loss due to lack of information in Bayesian mechanism design

    • Krzysztof Apt and Arantza Estevez-Fernandez,
      Sequential pivotal mechanisms for public project problems





Last Change: 14 October 2009