Advertisement
Published in:
2010 | OriginalPaper | Chapter
On the Impact of Local Taxes in a Set Cover Game
Authors : Bruno Escoffier, Laurent Gourvès, Jérôme Monnot
Published in: Structural Information and Communication Complexity
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Given a collection
$\mathcal{C}$
of weighted subsets of a ground set
$\mathcal{E}$
, the
set cover
problem is to find a minimum weight subset of
$\mathcal{C}$
which covers all elements of
$\mathcal{E}$
. We study a strategic game defined upon this classical optimization problem. Every element of
$\mathcal{E}$
is a player which chooses one set of
$\mathcal{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.