Home  Issues  Aims and Scope  Instructions for Authors 
Special Issue on Selected Papers from the Tenth International Workshop on Algorithms and Computation (WALCOM 2016)
DOI: 10.7155/jgaa.00415
Parameterization of StrategyProof Mechanisms in the Obnoxious Facility Game
Vol. 21, no. 3, pp. 247263, 2017. Regular paper.
Abstract In the obnoxious facility game, a location for an undesirable facility
is to be determined based on votes cast by selfish agents.
The design of group strategy proof mechanisms has been extensively studied, and it is known
that choosing a facility location that maximizes the social benefit (i.e., the sum of individual benefits) may not be a strategyproof decision, and viceversa, the social benefit obtainable by a strategyproof mechanism does not maximize the social benefit over all choices of facility locations;
their ratio, called the benefit ratio, can be up to 3 in the line metric space.
In this paper, we investigate a tradeoff between the benefit ratio and a possible relaxation of group strategy proofness,
taking $2$candidate mechanisms for the obnoxious facility game in the line metric as an example.
Given a real $\lambda \geq 1$ as a parameter,
we introduce a new concept of strategy proofness, called "$\lambda$group strategyproofness,"
so that each coalition of agents has no incentive to lie unless every agent in the group
can increase her benefit by strictly more than $\lambda$ times by doing so,
where $1$group strategyproofness
reduces to the standard concept of
group strategyproofness.
We next introduce "masking zone mechanisms," a new notion on the structure of mechanisms,
and prove that every $\lambda$ strategyproof ($\lambda$SP) mechanism is a masking zone mechanism.
We then show that, for any $\lambda \geq 1$, there exists a $\lambda$GSP mechanism
whose benefit ratio is at most $1+\frac{2}{\lambda}$,
which converges to 1 as $\lambda$ becomes infinitely large.
Finally we prove that the bound is nearly tight: given $n \geq 1$ selfish agents, the benefit ratio of $\lambda$GSP mechanisms cannot be better than
$1+\frac{2}{\lambda}$ when $n$ is even, and $1 + \frac{2n2}{\lambda n + 1}$ when $n$ is odd.

Submitted: May 2016.
Reviewed: November 2016.
Revised: November 2016.
Accepted: November 2016.
Final: January 2017.
Published: February 2017.
