论文标题
在二维的坐标中值机制的最佳位置的最优性
Optimality of the coordinate-wise median mechanism for strategyproof facility location in two dimensions
论文作者
论文摘要
我们考虑设施位置问题在两个维度上。特别是，我们考虑了一个设置，在该设置中，代理具有由其理想点定义的欧几里得偏好，以便将设施位于$ \ Mathbb {r}^2 $中。我们表明，对于$ p-norm $（$ p \ geq 1 $）的目标，坐标的中值机制（CM）的最差案例近似值是确定性，匿名和策略性防护机制的最差近似值。对于迷你目标和奇数代理$ n $，我们表明CM具有$ \ sqrt {2} \ frac {\ sqrt {\ sqrt {n^2+1}}} {n+1} $的最差案例近似值（AR）。对于$ p-norm $社交成本目标（$ p \ geq 2 $），我们发现CM的AR在上面以$ 2^{\ frac {\ frac {3} {2} {2} {2} - \ frac {2} {2} {p}}} $。我们认为，CM的AR实际上等于下限$ 2^{1- \ frac {1} {p}}} $（对于任何$ p = 2 $和$ p = \ infty $的情况，对于任何$ p \ geq 2 $）。
We consider the facility location problem in two dimensions. In particular, we consider a setting where agents have Euclidean preferences, defined by their ideal points, for a facility to be located in $\mathbb{R}^2$. We show that for the $p-norm$ ($p \geq 1$) objective, the coordinate-wise median mechanism (CM) has the lowest worst-case approximation ratio in the class of deterministic, anonymous, and strategyproof mechanisms. For the minisum objective and an odd number of agents $n$, we show that CM has a worst-case approximation ratio (AR) of $\sqrt{2}\frac{\sqrt{n^2+1}}{n+1}$. For the $p-norm$ social cost objective ($p\geq 2$), we find that the AR for CM is bounded above by $2^{\frac{3}{2}-\frac{2}{p}}$. We conjecture that the AR of CM actually equals the lower bound $2^{1-\frac{1}{p}}$ (as is the case for $p=2$ and $p=\infty$) for any $p\geq 2$.
