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.
Programme FINAL
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)
Last modified: Mon Jun 12 16:17:02 CEST 2006