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
TypeCommunication / Conférence
Conference titleSIROCCO 2010: 17th International Colloquium on Structural Information and Communication Complexity
Book titleStructural Information and Communication Complexity, 17th International Colloquium, SIROCCO 2010, Sirince, Turkey, June 7-11, 2010. Proceedings.
Book authorPatt-Shamir, Boaz; Ekim, Tinaz
Series titleLecture Notes in Computer Science
MetadataShow full item record
Abstract (EN)Given a collection C of weighted subsets of a ground set E, the set cover problem is to ﬁnd a minimum weight subset of C which covers all elements of E. We study a strategic game deﬁned 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 / KeywordsSet cover; Optimization
Showing items related by title and author.
Complexity and Approximation Results for the Connected Vertex Cover Problem in Graphs and Hypergraphs Monnot, Jérôme; Gourvès, Laurent; Escoffier, Bruno (2010) Article accepté pour publication ou publié