A Group-Strategyproof Mechanism for Steiner Forests

game:

Suppose a service provider owns a communication network represented as undirected
graph $G = (V,E)$ with non-negative edge costs $c_e$ for all edges $e \in E$.
We have a set of $k$ atonomous agents $R = \{ (s_1, t_1), \dots, (s_k, t_k) \}
\subseteq V \times V$ and the aim of each agent $j$ is to establish communication
between its terminal nodes $s_j$ and $t_j$.
Each agent $j$ also holds a private utility $u_j$ that represents the maximum
price $j$ is willing to pay for establishing communication between $s_j$ and $t_j$.

A cost-sharing mechanism is an algorithm that collects a bid $b_j$ from each agent
and based on these bids (i) determines a subset $R' \subseteq R$ of agents whose
communication requests are going to be satisfied, (ii) computes a forest $F$ that
contains an $s_j, t_j$-path for each agent $j \in R'$, and (iii) fixes a price $x_j$
for each agent $j \in R$ that he has to pay for the establishing of his communication
request. Agent $j$ enjoys a benefit of $u_j - x_j$ if $j \in R'$ and of zero
otherwise. We assume that each agent $j$ is selfish and thus may misreport his
utility so as to maximize his benefit.
The goal is to design a mechanism that assures group-strategyproofness, i.e., the
dominant strategy of each agent $j$ is to bid his true utility $u_j$ and the same
holds even if collaboration between the agents is allowed.

We present a group-strategyproof cost-sharing mechanism for this game that is
$2$-approximate budget-balanced. That is, the sum of the prices collected from the
agents in $R'$ is at least the cost of $F$ and is no more than $2$ times the optimum
cost to satisfy the communication requests of agents in $R'$.
Previously, Jain and Vazirani gave a $2$-approximate budget-balanced cost-sharing
mechanism for the Steiner tree game --- a special case of the game considered here.

Our algorithm is an original extension of the known primal-dual algorithm of
Agrawal, Klein and Ravi and of Goemans and Williamson and is also interesting
independently of the game-theoretic setting that we consider here.
The novel idea of our algorithm is that we also raise dual variables of non-violated
cuts, thereby still achieving the approximation guarantee of $2 - 2/k$ of the
standard primal-dual algorithm mentioned above. On some critical instances, our
algorithm therefore produces a lower bound that is significantly stronger than
the one obtained by the standard algorithm.


Joint work with:
* Jochen K\"onemann (University of Waterloo, Canada)
* Stefano Leonardi (University of Rome "La Sapienza", Italy)