Cost Sharing and Strategyproof Mechanisms for Set Cover 
Zheng Sun
HK Baptist U


Date: Friday November 19, 2004
Time 11-12
Venue: Room 3501, HKUST


Abstract
We develop for set cover games several general cost-sharing methods that are
approximately budget-balanced, core, and/or group-strategyproof. We first
study the cost sharing for a single set cover game, which does not have a
budget-balanced core. We show that there is no cost allocation method that
can always recover more than $\frac{1}{\ln n}$ of the total cost if we
require that the total shared cost of any subset of players is no more than
the total cost of serving them only, i.e., core. Here $n$ is the number of
all players to be served. We give an efficient cost allocation method that
always recovers $\frac{1}{\ln d_{max}}$ of the total cost, where $d_{max}$
is the maximum size of all sets. We then study the cost allocation scheme
for all induced subgames. It is known that no cost sharing scheme can always
recover more than $\frac{1}{n}$ of the total cost for every subset of
players. We give an efficient cost sharing scheme that always recovers at
least $\frac{1}{2n}$ of the total cost for every subset of players and
furthermore, our scheme is cross-monotone. When the elements to be covered
are selfish agents with privately known valuations, we present a
strategyproof charging mechanism such that each element maximizes its profit
when it reports its valuation truthfully; further, the total cost of the set
cover is no more than $\ln d_{max}$ times that of an optimal solution.
When the sets are selfish agents with privately known costs, we present a
strategyproof payment mechanism in which each set maximizes its profit when
it reports its cost truthfully. We also show how to \emph{fairly} share the
payments to all sets among the elements.