On the impact of local taxes in a set cover game

Monnot, Jérôme; Gourvès, Laurent; Escoffier, Bruno

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

sirocco.pdf (188.2Kb)

Type

Communication / Conférence

Date

2010

Conference title

SIROCCO 2010: 17th International Colloquium on Structural Information and Communication Complexity

Conference date

2010-06

Conference city

Sirince

Conference country

Turquie

Book title

Structural Information and Communication Complexity, 17th International Colloquium, SIROCCO 2010, Sirince, Turkey, June 7-11, 2010. Proceedings.

Book author

Patt-Shamir, Boaz; Ekim, Tinaz

Publisher

Springer

Series title

Lecture Notes in Computer Science

Series number

6058

Published in

Berlin

ISBN

978-3-642-13283-4

Pages

2-13; 15

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 / Keywords

Set cover; Optimization