Journ�ée: "Th�éorie Algorithmique des Jeux. Applications aux R�éseaux de T�él�écommunications et aux R�éseaux de Capteurs"

Mardi 16 Mai 2006, Paris II.

Lieu:

• Universit�é Panth�éon Assas, Paris II.
  Salle 12 & 13.
  12, Place du Panth�éon
  Paris 5i�ème.
  

  Participation libre.

Programme:

• 9h00 (salle 12): Daniel Lehmann (Hebrew University of Jerusalem, Israel)
  
  "Th�éorie des m�écanismes algorithmiques"
  (expos�é en anglais)
  
  
  
• 10h15 (salle 12): Berthold Voecking (RTWH Aachen, Germany)
  
  "Approximation Techniques for Utilitarian Mechanism Design" ( slides )
  (joint work with Patrick Briest and Piotr Krysta, STOC 2005)
  
  
  
• 11h30: Coffea break
  
  
  
• 12h00 (salle 12): Marios Mavronicolas (University of Cyprus, Cyprus)
  
  "A Network Security Game with Attackers and a Defender"
  
  
  
• Pause d�éjeuner.
  
  
  
• 15h00 (salle 13): Roger Wattenhofer (ETH Zurich, Switzerland)
  
  "Sensor Networks: Distributed Algorithms Reloaded -- or Revolutions?"
  
  
  
• 16h15 (salle 13): Sukumar Ghosh (University of Iowa, USA)
  
  "Altruistic Routing in P2P networks: Solutions and Problems" ( slides )
  (joint work with Alina Bejan and Amlan Bhattacharya)
  
  

R�ésum�és

• Daniel Lehmann (Hebrew University of Jerusalem, Israel) "Th�éorie des m�écanismes algorithmiques"

  
  L'expos�é d�écrira bri�èvement la probl�ématique de la th�éorie des m�écanismes et certains d�éveloppements de la th�éorie des m�écanismes algorithmiques (algorithmic mechanism design) qui int�ègre des consid�érations de complexit�é �à la th�éorie classique.

• Berthold Voecking (RTWH Aachen, Germany) "Approximation Techniques for Utilitarian Mechanism Design"
  (joint work with Patrick Briest and Piotr Krysta, STOC 2005)

  The talk is about the design of efficiently computable incentive compatible, or truthful, mechanisms for combinatorial optimization problems with multi-parameter agents. We focus on approximation algorithms for NP-hard mechanism design problems. Such algorithms need to satisfy certain monotonicity properties to ensure truthfulness. Since most of the known approximation techniques do not fulfill these properties, we study alternative techniques.
  We give a method to transform a pseudopolynomial algorithm into a monotone fully polynomial time approximation scheme (FPTAS). This method can be applied to various problems like, e.g., {\em knapsack}, {\em constrained shortest path}, or {\em job scheduling with deadlines}. The monotone FPTAS for the {\em knapsack problem} gives a very efficient mechanism for {\em multi-unit auctions}. The best previous result for such auctions was a 2-appro\-xi\-ma\-tion. We also derive a monotone polynomial time approximation scheme for the {\em generalized assignment problem\/} with any bounded number of parameters per agent.
  The most efficient way to solve packing integer programs (PIPs) is LP-based randomized rounding, which is also not monotone. We show that monotone primal-dual greedy algorithms achieve almost the same approximation ratios for PIPs as randomized rounding. This significantly improves on the known approximation ratios of truthful mechanisms for two famous mechanism design problems--{\em combinatorial auctions} and {\em unsplittable flow routing}.
  

• Marios Mavronicolas (University of Cyprus, Cyprus) "A Network Security Game with Attackers and a Defender"

  We will introduce and analyze a game on graphs that models network security problems in emerging networks like the Internet. In this game, attackers and a (single) defender choose vertices and edges on the graph via their own probability distributions on vertices and edges, respectively. The Individual Profit of each attacket is the probability it is not caught by the defender; the Individual Profit of the defender is the expected number of attackers it catches. What are the induced Nash equilibria?
  We will present some elegant connections between the structure of Nash equilibria and the structure of the graph. We use this necessary structure for defining and analyzing some very natural classes of Nash equilibria for the game. In particular, we analyze the Price of Defense for these equilibria, a new measure that we introduce for the evaluation of Nash equilibria in our game.
  

• Roger Wattenhofer (ETH Zurich, Switzerland) "Sensor Networks: Distributed Algorithms Reloaded -- or Revolutions?"

• Sukumar Ghosh (University of Iowa) "Altruistic Routing in P2P networks: Solutions and Problems"
  (joint work with Alina Bejan and Amlan Bhattacharya)