Show simple item record

dc.contributor.authorMonnot, Jérôme
dc.contributor.authorGourvès, Laurent
dc.contributor.authorEscoffier, Bruno
dc.date.accessioned2010-04-27T10:07:15Z
dc.date.available2010-04-27T10:07:15Z
dc.date.issued2010
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/4011
dc.language.isoenen
dc.subjectSet coveren
dc.subjectOptimizationen
dc.subject.ddc003en
dc.titleOn the impact of local taxes in a set cover gameen
dc.typeCommunication / Conférence
dc.description.abstractenGiven 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.en
dc.identifier.citationpages2-13
dc.identifier.citationpages15en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber6058
dc.relation.ispartoftitleStructural Information and Communication Complexity, 17th International Colloquium, SIROCCO 2010, Sirince, Turkey, June 7-11, 2010. Proceedings.
dc.relation.ispartofeditorPatt-Shamir, Boaz
dc.relation.ispartofeditorEkim, Tinaz
dc.relation.ispartofpublnameSpringer
dc.relation.ispartofpublcityBerlin
dc.relation.ispartofdate2010
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/978-3-642-13284-1
dc.relation.isversionofdoihttp://dx.doi.org/10.1007/978-3-642-13284-1_2
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-642-13283-4
dc.relation.conftitleSIROCCO 2010: 17th International Colloquium on Structural Information and Communication Complexityen
dc.relation.confdate2010-06
dc.relation.confcitySirinceen
dc.relation.confcountryTurquieen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record