SPOC 13 "Théorie des jeux algorithmique et Optimisation Combinatoire"

Date: 
Vendredi, 25 septembre, 2015

13ème séminaire du groupe POC

Le VENDREDI 25 SEPTEMBRE 2015

Au laboratoire LIP6 de l’Université Pierre et Marie Curie - Paris 6
4 place Jussieu Paris 6 (métro Jussieu)

Rotonde 26 - 1er étage - Couloir 25-26 - Salle 105

Sur le thème

Théorie des jeux algorithmique
et Optimisation Combinatoire

 

Entrée gratuite
Merci de vous inscrire à cette journée pour faciliter l'organisation

Pour voir la liste des inscrits

Programme de la journée:


9h30-10h30  Accueil "café - viennoiserie"


 

10h30-11h30

Gianpaolo Oriolo
Università di Roma "Tor Vergata".

PROTECTION OF FLOWS UNDER ATTACKS

Due to the importance of robustness in many real-world optimization problems, the field of robust optimization has gained a lot of attention over the past decade. In this talk, we concentrate on maximum flow problems and deal with a model where the first player (“the flow-player”) moves first and chooses an s-t flow, and the second player (“the interdictor”) moves later and attacks the flow trying to minimize the amount of it that will reach the destination t. We in particular focus on the max-min problem that the flow player has to solve, i.e. that of a choosing a flow as to maximizes the amount of it that will survive the attack of the interdictor.

 


 

11h30-12h30

Sylvain Sorin
Institut de mathématiques de Jussieu - Paris Rive Gauche

FINITE COMPOSITE GAMES: EQUILIBRIA AND DYNAMICS

We introduce finite games with the following types of players:
(I) nonatomic players,
(II) atomic splittable players,
(III) atomic non splittable players.

We recall and compare the basic properties, expressed through variational inequalities, concerning equilibria, potential games and dissipative games, as well as evolutionary dynamics.
Then we consider composite games where the three types are present, a typical example being congestion games, and extend the previous properties of equilibria and dynamics.

Finally we describe an instance of composite potential game.

Joined work with Cheng Wan

 


12h30-14h15     Repas


 

14h15 - 15h15

 Jose R. Correa
Department of Industrial Engineering, Universidad de Chile

MINSUM SCHEDULING GAMES

In this talk I will review some recent results in machine scheduling problems in which the jobs are controlled by different players which want to minimize their own cost. The goal is thus to design machine processing policies (a.k.a coordination mechanisms) which are on the one hand easy to implement and work with only local information, while on the other hand the implied equilibria are near efficient. In the last part of the talk I will discuss applications to local search heuristics and open problems.

 


15h15 - 15h30     Pause


 

15h30 - 16h30

Laurent Gourvès
Laboratoire LAMSADE, Université Paris Dauphine

COUPONS DES MATROÏDES COMME DES GÂTEAUX

On s’intéresse au partage équitable de biens indivisibles et leur extension aux matroïdes. En particulier on cherche des bornes inférieures sur l’utilité de l’agent le plus pauvre, dans le pire des cas. Ces bornes peuvent être obtenues par le biais d’un algorithme centralisé ou d’un protocole décentralisé s’inspirant du fameux protocole "cut and choose".

Travail effectué avec J. Monnot et L. Tlilane.

 


 

 

 

Si vous souhaitez proposer une présentation lors de cette journée, merci de contacter les organisateurs (baiou@isima.fr)

Le Groupe POC du GDR RO