Skip to main content
  • Conference proceedings
  • © 2008

Algorithmic Game Theory

First International Symposium, SAGT 2008, Paderborn, Germany, April 30 - May 2, 2008, Proceedings

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 4997)

Part of the book sub series: Information Systems and Applications, incl. Internet/Web, and HCI (LNISA)

Conference series link(s): SAGT: International Symposium on Algorithmic Game Theory

Conference proceedings info: SAGT 2008.

Buy it now

Buying options

eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

This is a preview of subscription content, log in via an institution to check for access.

Table of contents (32 papers)

  1. Front Matter

  2. Session 1: Routing and Scheduling I

    1. The Influence of Link Restrictions on (Random) Selfish Routing

      • Martin Hoefer, Alexander Souza
      Pages 22-32
    2. The Price of Anarchy on Uniformly Related Machines Revisited

      • Leah Epstein, Rob van Stee
      Pages 46-57
    3. Approximate Strong Equilibrium in Job Scheduling Games

      • Michal Feldman, Tami Tamir
      Pages 58-69
  3. Session 2: Markets

    1. Bertrand Competition in Networks

      • Shuchi Chawla, Tim Roughgarden
      Pages 70-82
    2. On the Approximability of Combinatorial Exchange Problems

      • Moshe Babaioff, Patrick Briest, Piotr Krysta
      Pages 83-94
    3. Window-Games between TCP Flows

      • Pavlos S. Efraimidis, Lazaros Tsavlidis
      Pages 95-108
  4. Session 3: Routing and Scheduling II

    1. Atomic Congestion Games: Fast, Myopic and Concurrent

      • Dimitris Fotakis, Alexis C. Kaporis, Paul G. Spirakis
      Pages 121-132
    2. Frugal Routing on Wireless Ad-Hoc Networks

      • Gunes Ercal, Rafit Izhak-Ratzin, Rupak Majumdar, Adam Meyerson
      Pages 133-144
    3. Facets of the Fully Mixed Nash Equilibrium Conjecture

      • Rainer Feldmann, Marios Mavronicolas, Andreas Pieris
      Pages 145-157
    4. Sensitivity of Wardrop Equilibria

      • Matthias Englert, Thomas Franke, Lars Olbrich
      Pages 158-169
  5. Session 4: Mechanism Design

    1. Prompt Mechanisms for Online Auctions

      • Richard Cole, Shahar Dobzinski, Lisa Fleischer
      Pages 170-181
    2. A Truthful Mechanism for Offline Ad Slot Scheduling

      • Jon Feldman, S. Muthukrishnan, Evdokia Nikolova, Martin Pál
      Pages 182-193
    3. Alternatives to Truthfulness Are Hard to Recognize

      • Vincenzo Auletta, Paolo Penna, Giuseppe Persiano, Carmine Ventre
      Pages 194-205

Other Volumes

  1. Algorithmic Game Theory

About this book

This book constitutes the refereed proceedings of the First International Symposium on Algorithmic Game Theory, SAGT 2008, held in Paderborn, Germany, in April/May 2008. 

The 28 revised full papes presented together with 3 invited lectures were carefully reviewed and selected from 60 submissions. The papers are organized in topical sections on routing and scheduling, markets, mechanism design, potpourri of games, solution concepts, and cost sharing.

Editors and Affiliations

  • Institut für Informatik, Universität Paderborn, Paderborn, Germany

    Burkhard Monien, Ulf-Peter Schroeder

Bibliographic Information

Buy it now

Buying options

eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access