
On the impact of local taxes in a set cover game
Monnot, Jérôme; Gourvès, Laurent; Escoffier, Bruno (2010), On the impact of local taxes in a set cover game, in Patt-Shamir, Boaz; Ekim, Tinaz, Structural Information and Communication Complexity, 17th International Colloquium, SIROCCO 2010, Sirince, Turkey, June 7-11, 2010. Proceedings., Springer : Berlin, p. 2-13
View/ Open
Type
Communication / ConférenceDate
2010Conference title
SIROCCO 2010: 17th International Colloquium on Structural Information and Communication ComplexityConference date
2010-06Conference city
SirinceConference country
TurquieBook title
Structural Information and Communication Complexity, 17th International Colloquium, SIROCCO 2010, Sirince, Turkey, June 7-11, 2010. Proceedings.Book author
Patt-Shamir, Boaz; Ekim, TinazPublisher
Springer
Series title
Lecture Notes in Computer ScienceSeries number
6058Published in
Berlin
ISBN
978-3-642-13283-4
Pages
2-13; 15
Publication identifier
Metadata
Show full item recordAbstract (EN)
Given a collection C of weighted subsets of a ground set E, the set cover problem is to find a minimum weight subset of C which covers all elements of E. We study a strategic game defined upon this classical optimization problem. Every element of E is a player which chooses one set of C where it appears. Following a public tax function, every player is charged a fraction of the weight of the set that it has selected. Our motivation is to design a tax function having the following features: it can be implemented in a distributed manner, existence of an equilibrium is guaranteed and the social cost for these equilibria is minimized.Subjects / Keywords
Set cover; OptimizationRelated items
Showing items related by title and author.
-
Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2011) Communication / Conférence
-
Monnot, Jérôme; Gourvès, Laurent; Escoffier, Bruno (2010) Article accepté pour publication ou publié
-
Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2007) Document de travail / Working paper
-
Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2017) Article accepté pour publication ou publié
-
Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2007) Communication / Conférence