LP-based Covering Games with Low Price of Anarchy

Series: 
ACO Student Seminar
Friday, March 16, 2012 - 13:00
1 hour (actually 50 minutes)
Location: 
Executive classroom, ISyE Main Building
,  
CoC, Georgia Tech
,  
I  present a new class of vertex cover and set cover games, with the price of anarchy bounds matching the best known constant factor approximation guarantees for the centralized optimization problems for linear and also for submodular costs. In particular, the price of anarchy is 2 for vertex cover. The basic intuition is that the members of the vertex cover form a Mafia that has to "protect" the graph, and may ask ransoms from their neighbors in exchange for the protection. These ransoms turn out to capture a good dual solution to the linear programming relaxation. For linear costs we also exhibit linear time best response dynamics that converge that mimic the classical greedy approximation algorithm of Bar-Yehuda and Even. This is a joint work with Georgios Piliouras and Tomas Valla.