On the Impact of Local Taxes in a Set Cover Game

摘要

Given a collection C of weighted subsets of a ground set ε, the SET COVER problem is to find a minimum weight subset of C which covers all elements of ε. We study a strategic game defined upon this classical optimization problem. Every element of ε 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.