Journ
Forum 'Annonces' - Sujet créé le 2006-05-02
Appel à Participation.
================================================
Journée
"Théorie Algorithmique des Jeux.
Applications aux Réseaux de Télécommunications et aux Réseaux de Capteurs"
Mardi 16 Mai, Paris.
================================================
Lieu: Université Panthéon Assas, Paris II.
Salles 12 & 13.
12, Place du Panthéon
Paris 5ième.
Objectifs: Mardi 16 mai, nous aurons plusieurs orateurs invités de
qualité spécialistes de la théorie algorithmique des jeux, en lien
avec ses applications à l'algorithmique pour les réseaux de
télécommunications et les réseaux de capteurs.
Participation libre.
=======
Programme provisoire / Invités confirmés:
10h00-11h00: (salle 12)
** Daniel Lehmann (Hebrew University of Jerusalem, Israel)
"Théorie des mécanismes algorithmiques"
11h00-12h00: (salle 12)
** Berthold Voecking (RTWH Aachen, Germany)
"Approximation Techniques for Utilitarian Mechanism Design"
(joint work with Patrick Briest and Piotr Krysta, STOC 2005)
12h00-13h00: (salle 12)
*** Marios Mavronicolas (University of Cyprus, Cyprus)
"A Network Security Game with Attackers and a Defender"
15h00-16h00: (salle 13)
*** Roger Wattenhofer (ETH Zurich, Switzerland)
"Sensor Networks: Distributed Algorithms Reloaded -- or Revolutions?"
=====
Résumés de quelques exposés:
* Daniel Lehmann (Hebrew University of Jerusalem, Israel)
"Théorie des mécanismes algorithmiques"
(exposé en anglais)
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., knapsack,
constrained shortest path, or job scheduling with
deadlines. The monotone FPTAS for the knapsack problem gives a
very efficient mechanism for multi-unit auctions. The best
previous result for such auctions was a 2-approximation. We
also derive a monotone polynomial time approximation scheme for the 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--
combinatorial auctions and 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.
======
Détails: http://sogea.loria.fr/journee-Mai-2006.html
================================================
Journée
"Théorie Algorithmique des Jeux.
Applications aux Réseaux de Télécommunications et aux Réseaux de Capteurs"
Mardi 16 Mai, Paris.
================================================
Lieu: Université Panthéon Assas, Paris II.
Salles 12 & 13.
12, Place du Panthéon
Paris 5ième.
Objectifs: Mardi 16 mai, nous aurons plusieurs orateurs invités de
qualité spécialistes de la théorie algorithmique des jeux, en lien
avec ses applications à l'algorithmique pour les réseaux de
télécommunications et les réseaux de capteurs.
Participation libre.
=======
Programme provisoire / Invités confirmés:
10h00-11h00: (salle 12)
** Daniel Lehmann (Hebrew University of Jerusalem, Israel)
"Théorie des mécanismes algorithmiques"
11h00-12h00: (salle 12)
** Berthold Voecking (RTWH Aachen, Germany)
"Approximation Techniques for Utilitarian Mechanism Design"
(joint work with Patrick Briest and Piotr Krysta, STOC 2005)
12h00-13h00: (salle 12)
*** Marios Mavronicolas (University of Cyprus, Cyprus)
"A Network Security Game with Attackers and a Defender"
15h00-16h00: (salle 13)
*** Roger Wattenhofer (ETH Zurich, Switzerland)
"Sensor Networks: Distributed Algorithms Reloaded -- or Revolutions?"
=====
Résumés de quelques exposés:
* Daniel Lehmann (Hebrew University of Jerusalem, Israel)
"Théorie des mécanismes algorithmiques"
(exposé en anglais)
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., knapsack,
constrained shortest path, or job scheduling with
deadlines. The monotone FPTAS for the knapsack problem gives a
very efficient mechanism for multi-unit auctions. The best
previous result for such auctions was a 2-approximation. We
also derive a monotone polynomial time approximation scheme for the 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--
combinatorial auctions and 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.
======
Détails: http://sogea.loria.fr/journee-Mai-2006.html