SPOC 13 "Théorie des jeux algorithmique et Optimisation Combinatoire"
Date:
Friday, 25 September, 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.