Vittorio Bilò - "The Price of Stability of Undirected Broadcast Games is Constant"

3 février 2018, 14:00-15:00 salle B102

Joint work with Michele Flammini and Luca Moscardelli.
Abstract : one of the most challenging open problems in Algorithmic Game Theory is the characterization of the price of stability in undirected network design games with fair cost sharing. In this talk, we present a breakthrough result showing that this quantity is O(1) in the special case of broadcast games, where every node aims at building a connection to a distinguished common source.