nach oben

Autonomous Agents and Multi-Agent Systems

Erschienen in:

Open Access 20.03.2017

Facility location with double-peaked preferences

verfasst von: Aris Filos-Ratsikas, Minming Li, Jie Zhang, Qiang Zhang

Erschienen in: Autonomous Agents and Multi-Agent Systems | Ausgabe 6/2017

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Patentsuche

Aus

Abstract

We study the problem of locating a single facility on a real line based on the reports of self-interested agents, when agents have double-peaked preferences, with the peaks being on opposite sides of their locations. We observe that double-peaked preferences capture real-life scenarios and thus complement the well-studied notion of single-peaked preferences. As a motivating example, assume that the government plans to build a primary school along a street; an agent with single-peaked preferences would prefer having the school built exactly next to her house. However, while that would make it very easy for her children to go to school, it would also introduce several problems, such as noise or parking congestion in the morning. A 5-min walking distance would be sufficiently far for such problems to no longer be much of a factor and at the same time sufficiently close for the school to be easily accessible by the children on foot. There are two positions (symmetrically) in each direction and those would be the agent’s two peaks of her double-peaked preference. Motivated by natural scenarios like the one described above, we mainly focus on the case where peaks are equidistant from the agents’ locations and discuss how our results extend to more general settings. We show that most of the results for single-peaked preferences do not directly apply to this setting, which makes the problem more challenging. As our main contribution, we present a simple truthful-in-expectation mechanism that achieves an approximation ratio of $1+b/c$ for both the social and the maximum cost, where b is the distance of the agent from the peak and c is the minimum cost of an agent. For the latter case, we provide a 3 / 2 lower bound on the approximation ratio of any truthful-in-expectation mechanism. We also study deterministic mechanisms under some natural conditions, proving lower bounds and approximation guarantees. We prove that among a large class of reasonable strategyproof mechanisms, there is no deterministic mechanism that outperforms our truthful-in-expectation mechanism. In order to obtain this result, we first characterize mechanisms for two agents that satisfy two simple properties; we use the same characterization to prove that no mechanism in this class can be group-strategyproof.

Aris Filos-Ratsikas and Jie Zhang were supported by the ERC Advanced Grant 321171 (ALGAME) and the Sino-Danish Center for the Theory of Interactive Computation, funded by the Danish National Research Foundation and the National Science Foundation of China (under the Grant 61061130540), and by the Center for research in the Foundations of Electronic Markets (CFEM), supported by the Danish Strategic Research Council. Minming Li was partly supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China [Project No. CityU 117913]. Qiang Zhang was supported by FET IP Project MULTIPEX 317532.

1 Introduction

We study the problem of locating a single facility on a real line, based on the input provided by selfish agents who wish to minimize their costs. Each agent has a location $x_i \in \mathbb {R}$ which is her private information and is asked to report it to some central authority, which then decides where to locate the facility, aiming to optimize some function of the agents’ reported locations. This model corresponds to problems such as finding the ideal location for building a primary school or a bus stop along a street, so that the total distance of all agents’ houses from the location is minimized, or so that no agent’s house will lie too far away from that location.

In our setting, we assume that agents have double-peaked preferences, i.e. we assume that each agent i has two unique most preferred points or peaks, located at some distances from $x_i$ on opposite sides, where her cost is minimum. Traditionally, preferences in facility location problems are assumed to be single-peaked, i.e. each agent’s location is her most preferred point on the line and furthermore the cost is assumed to be linear, i.e. it increases linearly (at the same rate) to the left and the right of that peak. Sometimes however, single-peaked preferences do not model real-life scenarios accurately. Take for instance the example mentioned above, where the government plans to build a primary school on a street. An agent with single-peaked preferences would definitely want the school built next to her house, so that she wouldn’t have to drive her children there everyday. However, it is quite possible that she is also not very keen on the inevitable drawbacks of having a primary school next to her house either, like unpleasant noise or trouble with parking. On the other hand, a 5-min walking distance is sufficiently far for those problems to no longer be a factor but also sufficiently close for her children to be able to walk to school. There are two such positions, (symmetrically) in each direction, and those would be her two peaks.

Our primary objective is to explore double-peaked preferences in facility location settings similar to the ones studied extensively for single-peaked preferences throughout the years [1, 11, 14, 18, 20, 23, 26, 27, 30, 32]. For that reason, following the literature we assume that the cost functions are the same for all agents and that the cost increases linearly, at the same rate, as the output moves away from the peaks. The straightforward extension to the double-peaked case is piecewise-linear cost functions, with the same slope in all intervals, which gives rise to the natural model of symmetric agents, i.e. the peaks are equidistant from the agent’s location. Note that this symmetry is completely analogous to the single-peaked case (for facility location problems, e.g. see [30]), where agents have exactly the same cost on two points equidistant from their peaks. Our lower bounds and impossibility results naturally extend to non-symmetric settings, but some of our mechanisms do not. We discuss those extensions in Sect. 6.

Our model also applies to more general spaces, beyond the real line. One can imagine for instance that the goal is to build a facility on the plane where for the same reasons, agents would like the facility to be built at some distance from their location, in every direction. This translates to an agent having infinitely many peaks, located on a circle centered around her location. In that case of course, we would no longer refer to agents’ preferences as double-peaked but the underyling idea is similar to the one presented in this paper. We do not explore such extensions here; we leave that for future work.

Agents are self-interested entities that wish to minimize their costs. We are interested in mechanisms that ensure that agents are not incentivized to report anything but their actual locations, namely strategyproof mechanisms. We are also interested in group strategyproof mechanisms, i.e. mechanisms that are resistant to manipulation by coalitions of agents. Moreover, we want those mechanisms to achieve some good performance guarantees, with respect to our goals. If our objective is to minimize the sum of the agent’s costs, known as the social cost, then we are looking for strategyproof mechanisms that achieve a social cost as close as possible to that of the optimal mechanism, which need not be strategyproof. The prominent measure of performance for mechanisms in computer science literature is the approximation ratio [2, 6, 12, 24], i.e. the worst possible ratio of the social cost achieved by the mechanism over the minimum social cost over all instances of the problem. The same holds if our objective is to minimize the maximum cost of any agent. In the case of randomized mechanisms, i.e. mechanisms that output a probability distribution over points in $\mathbb {R}$, instead of a single point, as a weaker strategyproofness constraint, we require truthfulness-in-expectation, i.e. a guarantee that no agent can reduce her expected cost from misreporting.

1.1 Our results

Our main contribution is a truthful-in-expectation mechanism (M1) that achieves an approximation ratio of $1+b/c$ for the social cost and $\max \{1+b/c,2\}$ for the maximum cost, where b is the distance between an agent’s location and her peak and c is her minimum cost. We also prove that no truthful-in-expectation mechanism can do better than a 3 / 2 approximation for the maximum cost proving that at least for the natural special case where $b=c$, Mechanism M1 is not far from the best possible. For deterministic mechanisms, we prove that no mechanism in a wide natural class of strategyproof mechanisms can achieve an approximation ratio better than $1+b/c$ for the social cost and $1+2b/c$ for the maximum cost and hence cannot outperform mechanism M1. To prove this, we first characterize the class of strategyproof, anonymous and position invariant mechanisms for two agents, showing that it consists only of a single Mechanism (M2). Intuitively, anonymity requires that all agents are handled equally (irrespectively of their names) by the mechanism while position invariance essentially requires that if we shift an instance by some amount, the location of the facility should be shifted by the same amount as well. This is a quite natural condition and can be interpreted as a guarantee that the facility will be located relatively to the reports of the agents and independently of the underlying network (e.g. the street).

We prove that the approximation ratio of Mechanism M2 for the social cost is $\max \{n-1,1+2b/c\}$, where n is the number of agents and conjecture that no deterministic strategyproof mechanism can achieve an o(n) approximation ratio in this case. For the maximum cost, the ratio of Mechanism M2 is $\max \{1+2b/c,3\}$ which means that the mechanism is actually the best in the natural class of anonymous and position invariant mechanisms. For any deterministic strategyproof mechanism, we prove a lower bound of 2 on the approximation ratio, proving that at least for the natural case of $b=c$, Mechanism M2 is also not far from optimal. Finally, we prove an impossibility result; there is no (strongly) group strategyproof, anonymous and position invariant mechanism for the problem. This is in constrast with the single-peaked preference setting, where there is a large class of (strongly) group strategyproof mechanisms that satisfy those properties. Our results are summarized in Table 1.

Table 1

Summary of our results

	Double-peaked		Single-peaked
	Upper	Lower	Upper	Lower
Social cost
Deterministic	$n-1$	$1+ \frac{b}{c}$	1	1
Randomized	$1+\frac{b}{c}$	–	1	1
Maximum cost
Deterministic$^*$	$1+\frac{2b}{c}$	$1+ \frac{2b}{c}$	2	2
Randomized	$1+\frac{b}{c}$	3 / 2	3 / 2	3 / 2

The lower bounds for deterministic mechanisms hold for anonymous and position invariant strategyproof mechanisms

For $\mathbf {(^*)}$, an additional lower bound of 2 holds under no conditions

Fields indicated by (−) are not proven yet. For the social cost, the deterministic upper bound is actually $\max \{n-1,1+2b/c\}$

For the maximum cost, the approximation ratios are actually $\max \{1+2b/c,3\}$ and $\max \{1+b/c,2\}$ respectively

The results for single-peaked preferences are also noted for comparison

The strategic version of the facility location problem in computer science was first studied by Proccacia and Tennenholtz [30] in a seminal paper, where the authors coined the term approximate mechanism design without money to study problems where, in the absence of monetary terms, strategyproof mechanisms can only achieve the desired objectives within some approximation factor. The main goal of [30] is the location of a single facility on the real line when agents have single-peaked preferences, and the corresponding bounds shown in Table 1 are from that paper. A series of papers have studied generalizations of the problem to more general metric spaces [1, 11, 32], multiple facilities [14, 23, 26, 27] or even enhancing strategyproof mechanisms with additional capabilities [21, 22]. Most of the related work actually considers the same objectives that we do here, namely the social cost or the maximum cost, with the notable exceptions of the least-squares objective [18], the $L_p$ norm of costs [17] or the minimax envy [5]. In a recent paper, Procaccia et al. [29] use the facility location problem to explore the trade-offs between the approximation guarantees and the variance of truthful-in-expectation mechanisms.

In the literature of artificial intelligence and multi-agent systems, in recent years, several variations of the basic model have emerged, capturing different situations that may arise in practice. A series of papers [7, 8, 16] study the obnoxious facility location problem over an interval, where agents declare their least preferred point and their utility increases linearly in both directions away from that point. Preference relations that give rise to such utility structures are referred to as single-dipped or single-caved preferences [25]. Serafino and Ventre [33, 34] introduced and studied the setting with heterogeneous facilities, in which agents’ locations are known and they declare their interests in different facilities. Building on the idea of heterogeneous facilities, a recent literature [16, 39] considers a single facility location setting where the agents report their most preferred positions, along with a binary variable, indicating whether the facility is desirable or obnoxious. Preference profiles in such a setting can be seen as being a combination of single-peaked and single-dipped preference orderings. In a different direction, Todo et al. [37] and Sonoda et al. [35] study the capabilities of false-name proof mechanisms, which are strategyproof mechanisms that are also impervious to agents assuming false identities.

In light of these recent developments, the current paper (the conference version of which preceded many of the aforementioned papers) can be seen as a different generalization of the basic facility location model, capturing different real-life scenarios and building on the vastly growing literature on such extensions.

Single-peaked preferences were introduced in [4] as a way to avoid Condorcet cycles in majority elections. Moulin [28] characterized the class of strategyproof mechanisms in this setting, proving that median voter schemes are essentially the only strategyproof mechanisms for agents with single-peaked preferences. Double-peaked preferences have been mentioned in social choice literature, to describe settings where preferences are not single-peaked, voting cycles do exist and majority elections are not possible. For example, Cooter ([10], pages 39–42) argues that when the decisions involve multi-dimensional choices, preferences are more likely to be double-peaked rather than single-peaked and the intransitivity of the preferences disallows for majority winners. As a motivating example, he uses the choice of the level of expenditure in public schools in the U.S. and the example of “yuppies”, i.e. young urban professionals that would prefer either a high expenditure level or a low expenditure level rather than a moderate level, as in the first case they could send their children to public school whereas in the second case they would send them to a private school without being burdened by large taxes for the support of public education. A simpler example of the same principle can be the choice of temperature in a room; both $15^\circ $ with a lightweight jacket and $25^\circ $ with just a regular shirt might be preferable to a moderate choice of $20^\circ $.

More broadly, in social choice settings similar to the example of [10], double-peaked preferences can be used to model situations where e.g. a left-wing party might prefer a more conservative but quite effective policy to a more liberal but ineffective one on a left-to-right political axis. In fact, Egan [13] provides a detailed discussion on double-peaked preferences in political decisions. He uses a 1964–1970 survey about which course of action the United States should take with regard to the Vietnam war as an example where the status quo (keep U.S. troops in Vietnam but try to terminate the war) was ranked last by a considerable fraction of the population when compared to a left-wing policy (pull out entirely) or a right-wing policy (take a stronger stand). This demonstrates that in a scenario where the standard approach would be to assume that preferences are single-peaked, preferences can instead be double-peaked. Egan provides additional evidence for the occurrence of double-peaked preferences supported by experimental results based on surveys on the U.S. population, for many different problems (education, health care, illegal immigration treatment, foreign oil treatment etc).

More examples of double-peaked preferences in real-life scenarios are presented in [31]. The related work demonstrates that although they might not be as popular as their single-peaked counterpart, double-peaked preferences do have applications in settings more general than the street example described earlier. On the other hand, the primary focus of this paper is to study double-peaked preferences on facility location settings and therefore the modeling assumptions follow the ones of the facility location literature.

In the literature of multi-agent systems, Yang and Guo [38] consider $\kappa $-peaked preferences (a straightforward generalization of double-peaked preferences) and the problem of controlling elections for such preference profiles for several well-known voting rules, proving several hardness and parametrized complexity results.

2 Preliminaries

Let $N=\{1,2,\ldots ,n\}$ be a set of agents. We consider the case where agents are located on a line, i.e. each agent $i \in N$ has a location $x_i \in \mathbb {R}$. We will occasionally use $x_i$ to refer to both the position of agent i and the agent herself. We will call the collection ${\mathbf {x}} = \langle x_1, \ldots , x_n\rangle $ a location profile or an instance.

A deterministic mechanism is a function $f: \mathbb {R}^n \mapsto \mathbb {R}$ that maps a given location profile to a point in $\mathbb {R}$, the location of the facility. We assume that agents have double-peaked preferences, symmetric with respect to the origin. We discuss how our results extend to non-symmetric agents in Sect. 6. Given any instance ${\mathbf {x}}$ and a location $y \in \mathbb {R}$, the cost of agent i is

$$\begin{aligned} {\mathrm {cost}}(y, x_i) = {\left\{ \begin{array}{ll} c+\left| x_i - b - y\right| &{} \text {if}\ y \le x_i \\ c+\left| x_i + b - y\right| &{} \text {if}\ y > x_i \end{array}\right. } \end{aligned}$$

where c and b are positive constants. We will say that y admits a cost of ${\mathrm {cost}}(y, x_i)$ for agent i on instance $\mathbf {x}$. For a mechanism that outputs $f(\mathbf {x})$ on instance $\mathbf {x}$, the cost of agent i is ${\mathrm {cost}}(f(\mathbf {x}),x_i)$. Intuitively, each agent has two most favorable locations, i.e. $x_i - b$ and $x_i + b$, which we refer to as the peaks of agent i. Note that these peaks are actually the troughs of the curve of the cost function, but much like most related work, we refer to them as peaks. The parameter $c>0$ is the minimum cost incurred to an agent when the facility is built on one of her peaks.¹ Note that the special case, where $b=c$ corresponds to the natural setting where the incurred minimum cost of an agent is interpreted as the distance she needs to cover to actually reach the facility. This case is particularly appealing, since the bounds we obtain are clean numbers, independent of b and c. The bounds for the natural case can be obtained directly by letting $b=c$ in all of our results.

A randomized mechanism is a function $f: \mathbb {R}^n \mapsto \varDelta (\mathbb {R})$, where $\varDelta (\mathbb {R})$ is the set of probability distributions over $\mathbb {R}$. It maps a given location profile to probabilistically selected locations of the facility. The expected cost of agent i is $\mathbb {E}_{y \sim {\mathcal {D}}} \left[ {\mathrm {cost}}(y, x_i) \right] $, where ${\mathcal {D}}$ is the probability distribution of the mechanism outputs.

We will call a deterministic mechanism f strategyproof if no agent would benefit by misreporting her location, regardless of the locations of the other agents. This means that for every ${\mathbf {x}}\in \mathbb {R}^n$, every $i\in N$ and every $x'_i\in \mathbb {R}$, ${\mathrm {cost}}(f({\mathbf {x}}),x_i)\le {\mathrm {cost}} (f(x'_i, \mathbf {x}_{-i}), x_i)$, where $\mathbf {x}_{-i}=\langle x_1,\ldots ,x_{i-1}, x_{i+1},\ldots ,x_n \rangle $. A mechanism is truthful-in-expectation if it guarantees that every agent always minimizes her expected cost by reporting her location truthfully. Throughout the paper we will use the term strategyproofness when refering to deterministic mechanisms and the term truthfulness when refering to randomized mechanisms.

A mechanism is (strongly) group strategyproof if there is no coalition of agents, who by jointly misreporting their locations, affect the outcome in a way such that the cost of none of them increases and the cost of at least one of them strictly decreases. In other words, there is no $S \subseteq N$ such that for some misreports $x_S$ of agents in S and some reports $\mathbf {x}_{-S}$ of agents in $N\backslash S$, ${\mathrm {cost}} (f(x_S', \mathbf {x}_{-S}), x_i) \le {\mathrm {cost}} (f({\mathbf {x}}), x_i)$ for all $i \in S$, and ${\mathrm {cost}} (f(x_S', \mathbf {x}_{-S}), x_j) < {\mathrm {cost}} (f({\mathbf {x}}), x_j)$ for at least one $j \in S$.

We note here that the definition above is often referred in the literature as strong group strategyproofness, to distinguish it from weak group strategyproofness, where for a group deviation to be possible, it should be the case that the cost of all agents of the deviating coalition strictly decreases. Throughout the paper, when referring to group strategyproofness, we will assume that the notion follows the strong definition.

Given an instance ${\mathbf {x}}$ and a location $y \in \mathbb {R}$, the social cost and the maximum cost of y are defined respectively as:

$$\begin{aligned} SC_y(\mathbf {x}) = \sum ^n_{i=1} {\mathrm {cost}} (y, x_i), \ \ \ MC_y(\mathbf {x}) = \max _{i \in N} {\mathrm {cost}} (y, x_i). \end{aligned}$$

We will say that y admits a social cost of $SC_y(\mathbf {x})$ or a maximum cost of $MC_y(\mathbf {x})$. We will call $y \in \mathbb {R}$ an optimal location (for the social cost), if $y \in \arg \min _y SC_y(\mathbf {x})$. The definition for the maximum cost is analogous. Let $SC_{{\mathrm {opt}}}({\mathbf {x}})$ and $MC_{{\mathrm {opt}}}({\mathbf {x}})$ denote the social cost and the maximum cost of an optimal location respectively, on instance $\mathbf {x}$. For a mechanism f that outputs $f(\mathbf {x})$ on instance $\mathbf {x}$, we will call $SC_\mathrm {f}(\mathbf {x})({\mathbf {x}})$ the social cost of the mechanism and we will denote it by $SC_\mathrm {f}({\mathbf {x}})$; and analogously for the maximum cost.

We are interested in strategyproof mechanisms that perform well with respect to the goal of minimizing either the social cost or the maximum cost. We measure the performance of the mechanism by comparing the social/maximum cost it achieves with the optimal social/maximum cost, on any instance ${\mathbf {x}}$.

The approximation ratio of mechanism f, with respect to the social cost, is given by

$$\begin{aligned} r=\sup _{\mathbf {x}} \frac{SC_\mathrm {f}(\mathbf {x})}{SC_{{\mathrm {opt}}}(\mathbf {x})}. \end{aligned}$$

The approximation ratio of mechanism f, with respect to maximum cost, is defined similarly.

For randomized mechanisms, the definitions are similar and the approximation ratio is calculated with respect to the expected social or maximum cost, i.e. the expected sum of costs of all agents and expected maximum cost of any agent, respectively.

Finally we consider some properties which are quite natural and are satisfied by many mechanisms (including the optimal mechanism). A mechanism f is anonymous, if for every location profile ${\mathbf {x}}$ and every permutation $\pi $ of the agents, $f(x_1, \ldots , x_n) = f(x_{\pi (1)}, \ldots , x_{\pi (n)})$. We say that a mechanism f is onto, if for every point $y \in \mathbb {R}$ on the line, there exists a location profile ${\mathbf {x}}$ such that $f({\mathbf {x}}) = y $. Without loss of generality, for anonymous mechanisms, we can assume $x_1\le \cdots \le x_n$.

A property that requires special mention is that of position invariance, which is a very natural property as discussed in the introduction. This property was independently defined by [17] where it was referred to as shift invariance. One can view position invariance as an analogue to neutrality in problems like the one studied here, where there is a continuum of outcomes instead of a finite set.

Definition 1

A mechanism f satisfies position invariance, if for all location profiles $\mathbf {x}=\langle x_1,\ldots ,x_n \rangle $ and $t \in \mathbb {R}$, it holds $f(x_1+t, x_2+t, \ldots , x_n+t) = f({\mathbf {x}}) + t$. In this case, we will call such a mechanism position invariant. We will refer to instances ${\mathbf {x}}$ and $\langle x_1+t, x_2+t, \ldots , x_n+t \rangle $ as position equivalent.

Note that position invariance implies the onto condition. Indeed, for any location profile $\mathbf {x}$, with $f(\mathbf {x})=y$, we have $f(x_1+t, x_2+t, \ldots , x_n+t)=y'=y+t$ for any $t \in \mathbb {R}$, so every point $y' \in \mathbb {R}$ is a potential output of the mechanism.

3 A truthful-in-expectation mechanism

We start the exposition of our results with our main contribution, a truthful-in-expectation mechanism that achieves an approximation ratio of $1+b/c$ for the social cost and $\max \{1+b/c,2\}$ for the maximum cost.

Mechanism M1

Given any instance $\mathbf {x}=\langle x_1,\ldots ,x_n\rangle $, find the median agent $x_{m}={\mathrm {median}}(x_1,\ldots ,x_n)$, breaking ties in favor of the agent with the smallest index. Output $f(\mathbf {x})=x_m-b$ with probability $\frac{1}{2}$ and $f(\mathbf {x})=x_m+b$ with probability $\frac{1}{2}$.

Theorem 1

Mechanism M1 is truthful-in-expectation.

Proof

First, note that the median agent does not have an incentive to deviate, since her expected cost is already minimum, neither does any agent i for which $x_i=x_m$. Hence, for the deviating agent i it must be either $x_i < x_m$ or $x_i> x_m$. We consider three cases when $x_i<x_m$. The proof for the case $x_i>x_m$ is symmetric. Observe that for agent i to be able to move the position of the facility, she has to report $x_i'\ge x_m$ and change the identity of the median agent. Let $x'_m$ be the median agent in the new instance $\langle x'_i,x_{-i} \rangle $, after agent i’s deviation. If $x'_m=x_m$, then obviously agent $x_i$ does not gain from deviating, so we will assume that $x'_m>x_m$.

Case 1 $x_i + b \le x_m-b$ (symmetrically $x_i-b \ge x_m+b$).

Case 2 $x_m-b < x_i + b \le x_m$ (symmetrically $x_m \le x_i-b < x_m+b$).

Case 3 $x_m < x_i+b \le x_m+b$ (symmetrically $x_m-b \le x_i-b < x_m$).

The cost of agent i before misreporting is calculated with respect to $x_i-b$ when the outcome is $x_m-b$ and with respect to $x_i+b$ when the outcome is $x_m+b$. For any misreport $x'_i < x_i+b$, this is still the case (for $x'_m-b$ and $x'_m+b$ respectively) and since $(x'_m-b)-(x_m-b)=(x'_m+b)-(x_m+b)$, her expected cost is not smaller than before. For any misreport $x'_i > x_i+b$, her cost is calculated with respect to $x_i+b$ for both possible outcomes of the mechanism and for the same reason as in Case 2, her expected cost is at least as much as it was before misreporting. $\square $

Next, we will calculate the approximation ratio of the mechanism for the social cost. In order to do that, we will need the following lemma.

Lemma 1

Let $\mathbf {x}=\langle x_1,\ldots ,x_m,\ldots ,x_n\rangle $, where $x_{m}={\mathrm {median}}\,(x_1,\ldots ,x_n)$, breaking ties in favor of the smallest index. There exists an optimal location for the social cost in $[x_m-b,x_m+b]$.

Proof

Assume by contradiction that there exists a point $y<x_m-b$ or $y>x_m+b$ with a strictly smaller social cost than all the points in $[x_m-b,x_m+b]$.

Assume first that $y<x_m-b$. Since $x_m$ is the median agent, it holds that for at least $\lceil n/2 \rceil $ agents, $x_i-b \ge x_m-b$, that is $x_m-b$ admits a smaller cost for at least $\lceil n/2 \rceil $ agents when compared to y. Let $X_1$ be the set of those agents. On the other hand, for each agent $x_i<x_m$, $x_m-b$ may admit a smaller or larger cost than y, depending on her position with respect to y. In the worst case, the cost is larger for every one of those agents, which happens when $x_i+b \le y$ for every agent with $x_i < x_m$. Let $X_2$ be the set of those agents. Now observe that for any two agents $x_\alpha \in X_1$ and $x_\beta \in X_2$, it holds that ${\mathrm {cost}}(x_\alpha ,y)-{\mathrm {cost}}(x_a,x_m-b) = {\mathrm {cost}}(x_\beta ,x_m-b)-{\mathrm {cost}}(x_\beta ,y)$. Since $|X_1| \ge |X_2|$, it holds that that $SC_{x_m-b}({\mathbf {x}}) \le SC_{y}({\mathbf {x}})$. Since it holds that $SC_{x_m-b}({\mathbf {x}}) > SC_{y}({\mathbf {x}})$, $x_m-b$ is an optimal location and we get a contradiction.

Now assume $y> x_m+b$. If the number of agents is odd, then we can use an exactly symmetric argument to prove that $SC_{x_m+b} \le SC_{y}$. If the number of agents is even, the argument can still be used, since our tie-breaking rule selects agent $x_{n/2}$ as the median. Specifically, $x_m+b$ admits a smaller cost for exactly n / 2 of the agents (including agent $x_{n/2}$) and in the worst case, y admits a smaller cost for n / 2 agents as well. If $X_1$ and $X_2$ are the sets of those agents respectively, then again it holds that ${\mathrm {cost}}(x_\alpha ,y)-{\mathrm {cost}}(x_\alpha ,x_m+b) = {\mathrm {cost}}(x_\beta ,x_m+b)-{\mathrm {cost}}(x_\beta ,y)$ for $x_\alpha \in X_1$ and $x_\beta \in X_2$ and we get a contradiction as before. $\square $

We now proceed to proving the approximation ratio of Mechanism M1.

Theorem 2

Mechanism M1 has an approximation ratio of $1+\frac{b}{c}$ for the social cost.

Proof

Consider an arbitrary instance $\mathbf {x}=\langle x_1,\ldots ,x_n\rangle $ and let $x_m$ be the median agent. By Lemma 1, there exists an optimal location $y \in [x_m-b,x_m+b]$. Let $\delta =y-(x_m-b)$. For every agent i, it holds that $\text {cost}(x_i,x_m-b) \le \text {cost}(x_i,y)+\delta $. To see this, first observe that $|(x_i-b)-(x_m-b)| \le |(x_i-b)-y|+\delta $ and that $|(x_i+b)-(x_m-b)| \le |(x_i+b)-y|+\delta $. If the cost of an agent admitted by y and $x_m-b$ is calculated with respect to the same peak, then $\min (|(x_i-b)-(x_m-b)|,|(x_i+b)-(x_m-b)|) \le \min (|(x_i-b)-y|,|(x_i+b)-y|)+\delta $ and the inequality holds. If the cost is calculated with respect to different peaks for y and $x_m-b$, it must be that $\text {cost}(x_i,x_m-b)=c+|(x_i-b)-(x_m-b)|$ and $\text {cost}(x_i,y)=c+|x_i+b-y|$, because $x_m-b < y$. Since $|(x_i-b)-(x_m-b)| \le |(x_i+b)-(x_m-b)| \le |(x_i+b)-y|+\delta $, the inequality holds. Similarily, we can prove that $\text {cost}(x_i,x_m+b) \le \text {cost}(x_i,y)+(2b-\delta )$ for every agent i. Hence, we can upper bound the cost of Mechanism M1 by $\frac{1}{2}\sum _{i=1}^{n}\text {cost}(x_i,x_m-b) +$ $\frac{1}{2}\sum _{i=1}^{n}\text {cost}(x_i,x_m+b)$ $\le \frac{1}{2} \sum _{i=1}^{n} \left( \text {cost}(x_i,y)+\delta \right) +\frac{1}{2} \sum _{i=1}^{n} \left( \text {cost}(x_i,y) + 2b-\delta \right) = SC_y(\mathbf {x}) +nb = SC_{{\mathrm {opt}}}(\mathbf {x}) + nb$. The approximation ratio then becomes $1+\frac{nb}{SC_{{\mathrm {opt}}}(\mathbf {x})}$, which is at most $1+\frac{b}{c}$, since $SC_{{\mathrm {opt}}}(\mathbf {x})$ is at least nc.

For the lower bound, consider the location profile $\mathbf {x}=\langle x_1,\ldots ,x_n\rangle $ with $x_1=\cdots =x_{k-1}=x_k-b=x_{k+1}-2b=\cdots =x_n-2b$. Note that the argument works both when $n=2k$ and when $n=2k+1$ because Mechanism M1 selects agent $x_k$ as the median agent in each case. The optimal location is $x_1+b$ whereas Mechanism M1 equiprobably outputs $f_{{\mathrm{M1}}}(\mathbf {x})=x_{k}-b$ or $f_{{\mathrm{M1}}}(\mathbf {x})=x_{k}+b$. The cost of the optimal location is $SC_{\mathrm {opt}}(\mathbf {x}) = nc + b$ whereas the cost of Mechanism M1 is $SC_{\mathrm{M1}}(\mathbf {x})=nc + (1/2)(n-1)b +(1/2)(n-1)b=nc+(n-1)b$. The approximation ratio then becomes $\frac{nc+(n-1)b}{nc+b}$ $= 1 \frac{b}{c}\cdot \frac{n-2}{n+(b/c)}$. As the number of agents grows to infinity, the approximation ratio of the mechanism on this instance approaches $1+b/c$. This completes the proof. $\square $

3.2 Maximum cost

We also consider the maximum cost and prove the approximation ratio of Mechanism M1 as well as a lower bound on the approximation ratio of any truthful-in-expectation mechanism. The results are summarized in Table 1.

Theorem 3

Mechanism M1 has an approximation ratio of $\max \{1+b/c,2\}$ for the maximum cost.

Proof

Let $\mathbf {x}=\langle x_1,\ldots ,x_n\rangle $ be an arbitrary instance and let $x_m$ be the median agent. We will consider two cases, based on the location of $f_{\mathrm {opt}}(\mathbf {x})$ with respect to $x_m-b$ (or symmetrically $x_m+b$).

Case 1 $f_{\mathrm {opt}}(\mathbf {x}) < x_m-b$ (or $f_{\mathrm {opt}}(\mathbf {x}) > x_m+b$).

Let $\delta = (x_m-b)-f_{\mathrm {opt}}(\mathbf {x})$. For the same reason as in the proof of Theorem 2, for every agent i, it holds that $\text {cost}(x_i,x_m-b) \le \text {cost}(x_i,f_{\mathrm {opt}}(\mathbf {x}))+\delta $ and also that $\text {cost}(x_i,x_m+b) \le \text {cost}(x_i,f_{\mathrm {opt}}(\mathbf {x}))+(2b+\delta )$.

The maximum cost of Mechanism M1 is

$$\begin{aligned} MC_{{\mathrm{M1}}}(\mathbf {x})= & {} \frac{1}{2}\max _{i \in N}\text {cost}\left( x_i,x_m-b\right) + \frac{1}{2}\max _{i \in N}\text {cost}\left( x_i,x_m+b\right) \\\le & {} \frac{1}{2}\left( \max _{i \in N}\text {cost}\left( x_i,f_{\mathrm {opt}}(\mathbf {x})\right) +\delta \right) + \frac{1}{2}\left( \max _{i \in N}\text {cost}\left( x_i,f_{\mathrm {opt}}(\mathbf {x})\right) +(2b+\delta )\right) \\= & {} MC_{\mathrm {opt}}(\mathbf {x}) + b + \delta \le 2MC_{\mathrm {opt}}(\mathbf {x}) +b-c \end{aligned}$$

since $MC_{\mathrm {opt}}(\mathbf {x}) \ge c+\delta $. The approximation is at most $2+\frac{b-c}{MC_{\mathrm {opt}}(\mathbf {x})}$, which is at most $1+\frac{b}{c}$ if $b\ge c$ (since $MC_{\mathrm {opt}}(\mathbf {x}) \ge c$) and at most 2 if $b<c$ (since $MC_{\mathrm {opt}}(\mathbf {x}) > 0$).

Case 2 $x_m-b \le f_{\mathrm {opt}}(\mathbf {x}) \le x_m+b$.

Now, let $\delta =f_{\mathrm {opt}}(\mathbf {x})-(x_m-b)$. Again, it holds that $\text {cost}(x_i,x_m-b) \le \text {cost}(x_i,f_{\mathrm {opt}}(\mathbf {x}))+\delta $ and also that $\text {cost}(x_i,x_m+b) \le \text {cost}(x_i,f_{\mathrm {opt}}(\mathbf {x}))+(2b-\delta )$.

The maximum cost of Mechanism M1 is

$$\begin{aligned} MC_{{\mathrm{M1}}}(\mathbf {x})= & {} \frac{1}{2}\max _{i \in N}\text {cost}\left( x_i,x_m-b\right) + \frac{1}{2}\max _{i \in N}\text {cost}\left( x_i,x_m+b\right) \\\le & {} \frac{1}{2}\left( \max _{i \in N}\text {cost}\left( x_i,f_{\mathrm {opt}}(\mathbf {x})\right) +\delta \right) + \frac{1}{2}\left( \max _{i \in N}\text {cost}\left( x_i,f_{\mathrm {opt}}(\mathbf {x})\right) +(2b-\delta )\right) \\= & {} MC_{\mathrm {opt}}(\mathbf {x}) + b \end{aligned}$$

and the approximation ratio is at most $1+\frac{b}{c}$ (since $MC_{\mathrm {opt}}(\mathbf {x}) \ge c$).

For the matching lower bound, consider an instance $\mathbf {x}=\langle x_1,\ldots ,x_n\rangle $ on which $x_1+b < x_2-b$ and $x_i=x_2$ for all $i \notin \{1,2\}$. It is $f_{\mathrm {opt}}(\mathbf {x})= \frac{x_1+x_2}{2}$, i.e. the middle of the interval between $x_1$ and $x_2$, whereas Mechanism M1 selects equiprobably among $x_2-b$ and $x_2+b$. Let $d = f_{\mathrm {opt}}(\mathbf {x}) - (x_1+b)$. Then $MC_{\mathrm {opt}}(\mathbf {x}) = c+d$, whereas $MC_{{\mathrm{M1}}}(\mathbf {x}) = c + \frac{1}{2}2d + \frac{1}{2}(2d+2b)= b+c+2d$. The approximation ratio is $1+\frac{b+d}{c+d}$ which is $1+\frac{b}{c}$ as d goes to 0 and 2 as d goes to infinity. $\square $

Next, we provide a lower bound on the approximation ratio of any truthful-in-expectation mechanism.

Theorem 4

For any values of c and b, no truthful-in-expectation mechanism can achieve an approximation lower than $\frac{3}{2}$ for the maximum cost.

First, we state a couple of lemmas which are in essence very similar to those used in the proof of the single-peaked preferences case in [30]. Let $\mathbf {x}=\langle x_1,x_2 \rangle $ be an instance such that $x_1+b<x_2-b$ and let $\lambda = (x_2-b)-(x_1+b)$. Let f be a truthful-in-expectation mechanism and let $\mathcal {D}$ be the distribution that $y=f(\mathbf {x})$ follows on instance $\mathbf {x}$.

Lemma 2

On instance $\mathbf {x}$, at least one of $\mathbb {E}_{y \sim {\mathcal {D}}}\left[ \text {cost}(x_1,y)\right] \ge c+\frac{\lambda }{2}$ and $\mathbb {E}_{y \sim \mathcal {D}}\left[ \text {cost}(x_2,y)\right] \ge c+\frac{\lambda }{2}$ holds.

Proof

Obviously, $\text {cost}(x_1,y) + \text {cost}(x_2,y) \ge 2c+\lambda $ for any choice of y, hence $\mathbb {E}_{y \sim {\mathcal {D}}}\left[ \sum _{i=1}^{2}\text {cost}(x_i,y)\right] = \sum _{i=1}^{2}\mathbb {E}_{y \sim {\mathcal {D}}}[\text {cost}(x_i,y)] \ge 2c+\lambda $. Therefore, it must be that $\mathbb {E}_{y \sim {\mathcal {D}}}[\text {cost}(x_i,y)] \ge c+\frac{\lambda }{2}$ for at least one of $i=1$ or $i=2$. $\square $

Lemma 3

Let $f_{\mathrm {opt}}(\mathbf {x})$ be the outcome of the optimal mechanism on instance $\mathbf {x}$. If $\mathbb {E}_{y \sim {\mathcal {D}}}[|y-f_{\mathrm {opt}}(\mathbf {x})|] = \varDelta $, then the maximum cost of the mechanism on this instance is $\mathbb {E}[MC_f(\mathbf {x})] = c+ \frac{\lambda }{2} + \varDelta $.

Proof

Since $\forall y$, $MC_f(\mathbf {x}) = c + |y-f_{\mathrm {opt}}(\mathbf {x})| + \lambda /2$, it holds

$$\begin{aligned} \mathbb {E}_{y \sim \mathcal {D}}\left[ MC_f(\mathbf {x})\right]&= \mathbb {E}_{y \sim {\mathcal {D}}}\left[ c+\frac{\lambda }{2}+\left| y-f_{\mathrm {opt}} (\mathbf {x})\right| \right] =c+\frac{\lambda }{2}+\mathbb {E}_{y \sim {\mathcal {D}}}\left[ \left| y-f_{\mathrm {opt}}(\mathbf {x})\right| \right] \\&=c+\frac{\lambda }{2}+\varDelta . \end{aligned}$$

$\square $

We can now prove the theorem.

Proof

Consider an instance with two agents on which $x_1+b < x_2-b$ and $(x_2-b)-(x_1+b)=\lambda $. It holds that $f_{\mathrm {opt}}(\mathbf {x})=\frac{x_1+x_2}{2}$. Assume there is a truthful-in-expectation mechanism M on which $y=f(x_1,x_2)$ follows a distribution ${\mathcal {D}}$ on this instance. According to Lemma 2, at least one of $\mathbb {E}_{y \sim \mathcal {D}}[\text {cost}(y,x_1)] \ge c+\lambda /2$ and $\mathbb {E}_{y \sim \mathcal {D}}[\text {cost}(y,x_2)] \ge c+\lambda /2$ holds. W.l.o.g., assume the second inequality is true (if the first inequality is true then we can make a symmetric argument with agent $x_1$ deviating).

Next, consider the instance $\mathbf {x'}=\langle x'_1,x'_2 \rangle $ with $x'_1 = x_1$ and $x'_2 = x_2+\lambda $. Let $f_{\mathrm {opt}}(\mathbf {x'}) = (x'_1 + x'_2)/2 = x_2-b$. Let ${\mathcal {D}}'$ be the distribution that $y'$ follows on instance $\mathbf {x'}$. By strategyproofness, $\mathbb {E}_{y' \sim {\mathcal {D}}'} \left[ \text {cost}(y',x_2)\right] \ge \mathbb {E}_{y \sim {\mathcal {D}}}[\text {cost}(y,x_2)] \ge c + \lambda /2$, since $x'_2$ could be a deviation of agent 2 on instance $\mathbf {x}$. This implies $\mathbb {E}_{y' \sim {\mathcal {D}}'} \left[ |y'-(x_2-b)| \right] \ge \frac{\lambda }{2}$. To see this, assume otherwise for contradiction, we would have

$$\begin{aligned} \mathbb {E}_{y' \sim {\mathcal {D}}'} \left[ \text {cost}(y',x_2)\right]= & {} \mathbb {E}_{y' \sim {\mathcal {D}}'} \left[ c+\min \left\{ \left| y'-(x_2-b)\right| , \left| y'-(x_2+b)\right| \right\} \right] \\\le & {} c+\min \left\{ \mathbb {E}_{y' \sim {\mathcal {D}}'} \left[ \left| y'-(x_2-b)\right| \right] , \mathbb {E}_{y' \sim \mathcal {D}'} \left[ \left| y'-(x_2+b)\right| \right] \right\} \\< & {} c+\frac{\lambda }{2} . \end{aligned}$$

Equivalently, we have $\mathbb {E}_{y' \sim {\mathcal {D}}'} \left[ |y'-f_\mathrm {opt}(\mathbf {x'})| \right] \ge \frac{\lambda }{2}$. Hence, by applying Lemma 3, we know that the maximum cost of the mechanism on the second instance is $\mathbb {E}_{y' \sim {\mathcal {D}}'}\left[ MC_M(\mathbf {x'}) \right] \ge c+\lambda +\frac{\lambda }{2}=c+\frac{3\lambda }{2}$. Since the optimal mechanism locates the facility on $f_{\mathrm {opt}}(\mathbf {x'})$, its maximum cost is $c+\lambda $. Therefore, the approximation ratio is at least $\frac{c+3\lambda /2}{c+\lambda }$. As $\lambda $ grows to infinity, the approximation ratio approaches $\frac{3}{2}$. To generalize the proof to more than two agents, place every other agent on $f_{\mathrm {opt}}(\mathbf {x})+b$ on instance $\mathbf {x}$. Since $\lambda $ is large enough, the maximum cost is still calculated with respect to $x_2$ and all the arguments still hold. $\square $

4 Deterministic mechanisms

We now turn our attention to deterministic mechanisms. We will start by stating and proving the following lemma, which will be very useful throughout the paper. Variations of the instances used here will appear in several of our proofs. When $n=2$, we define the following family of instances, called primary instances.

Primary instance We will say that an instance is a primary instance, if it holds that ${\mathbf {x}}=\langle x_1,x_2 \rangle $ with $x_1+2b+\epsilon = x_2-b$, where $\epsilon $ is a positive real number. In the following we will fix such an $\epsilon >0$ (e.g. $\epsilon = b/2$) and refer to the resulting instance as the primary instance.

Lemma 4

On the primary instance, there is no anonymous, position invariant and strategyproof mechanism such that $f({\mathbf {x}}) \in [x_1+b,x_2-b]$.

Proof

For contradiction, suppose there exists an anonymous, position invariant strategyproof mechanism M that ouputs $f({\mathbf {x}})\in [x_1+b,x_2-b]$. Let’s denote $\delta _1 = f(\mathbf {x}) - (x_1+b)$, $\delta _2=(x_2-b)-f(\mathbf {x})$. Throughout the proof we start with the primary instance and construct some other instances to prove the lemma. There are 2 cases to be considered.

Case 1 $0<\delta _1 \le \frac{1}{2} (b+\epsilon )$, i.e. $x_1+b<f(\mathbf {x}) \le \frac{x_1+x_2}{2}$ (symmetrically, for the case $0<\delta _2 \le \frac{1}{2} (b+\epsilon )$). See Fig. 1.

Instance $\mathrm {I}$ : $\mathbf {x^{\mathrm {I}}}=\langle x^{\mathrm {I}}_1,x^{\mathrm {I}}_2 \rangle $, where $x^{\mathrm {I}}_1=x_1+\delta _1, x^{\mathrm {I}}_2=x_2$.
Instance $\mathrm {II}$ : $\mathbf {x^{\mathrm {II}}}=\langle x^{\mathrm {II}}_1,x^{\mathrm {II}}_2 \rangle $, where $x^{\mathrm {II}}_1=x_1+\delta _1, x^{\mathrm {II}}_2=x_2+\delta _1$.

First, we know that on instance $\mathrm {I}$, strategyproofness requires that $f(\mathbf {x^{\mathrm {I}}})=x_1^{\mathrm {I}}-b$ or $x_1^{\mathrm {I}}+b$, otherwise agent $x^{\mathrm {I}}_1$ could misreport $x_1$ and move the facility to position $x_1^{\mathrm {I}}+b$, minimizing her cost. Second, since instance $\mathrm {II}$ and the primary instance are position equivalent ($\mathrm {II}$ is a shifted version of the primary instance to the right by $\delta _1$), by position invariance we know $f(\mathbf {x^{\mathrm {II}}})=x_1^{\mathrm {II}}+b+\delta _1 =x_1^{\mathrm {I}}+b+\delta _1$. Now let’s consider agent $x_2^{\mathrm {I}}$ in instance $\mathrm {I}$. If agent $x_2^{\mathrm {I}}$ misreports $x_2^{\mathrm {II}}$, she can move the facility from $x_1^{\mathrm {I}}-b$ or $x_1^{\mathrm {I}}+b$ to $x_1^{\mathrm {I}}+b+\delta _1 \le x^{\mathrm {I}}_2-b$; in either case the facility is closer to her left peak. Therefore $x_2^{\mathrm {I}}$ can manipulate the mechanism, which violates strategyproofness. Hence $f(\mathbf {x}) \not \in (x_1+b,\frac{x_1+x_2}{2}]$.

Case 2 $\delta _1=0$, i.e. $f(\mathbf {x})=x_1+b$ (symmetrically, for the case $\delta _2=0$). See Fig. 2.

Instance $\mathrm {III}$ : $\mathbf {x^{\mathrm {III}}}=\langle x^{\mathrm {III}}_1,x^{\mathrm {III}}_2 \rangle $, where $x^{\mathrm {III}}_1=x_1+2b, x^{\mathrm {III}}_2=x_2$.

First, we know that on instance $\mathrm {III}$, strategyproofness requires either that $f(\mathbf {x^{\mathrm {III}}})=x_1^{\mathrm {III}}-b$ or $f(\mathbf {x^{\mathrm {III}}})=x_1^{\mathrm {III}}+b$, otherwise agent $x^{\mathrm {III}}_1$ could misreport $x_1$ and move the facility to position $x_1^{\mathrm {III}}-b$, minimizing her cost. Now, there are two subcases.

(a)

$f(\mathbf {x^{\mathrm {III}}})=x_{1}^{\mathrm {III}}-b$. See left hand side of Fig. 2, where we have instance $\mathrm {IVa}$: $x_1^{\mathrm {IVa}}=x_1+2b, x_2^{\mathrm {IVa}}=x_2+2b$.

Obviously, instance $\mathrm {IVa}$ is position equivalent to the primary instance, so $f(x_1^{\mathrm {IVa}},x_2^{\mathrm {IVa}})=x_1^{\mathrm {IVa}}+b$. Note that the cost of agent $x_2^{\mathrm {III}}$ is $b+c+\epsilon $. If agent $x_2^{\mathrm {III}}$ misreports $x_2^{\mathrm {IVa}}$, then her cost becomes $b+c-\epsilon $, which is smaller than when reporting truthfully. So $f(\mathbf {x^{\mathrm {III}}})\not =x_1^{\mathrm {III}}-b$ if Mechanism M is strategyproof.

(b)

$f(\mathbf {x^{\mathrm {III}}})=x_1^{\mathrm {III}}+b$. See right hand side of Fig. 2, where we have instance $\mathrm {IVb}$: $x_1^{\mathrm {IVb}}=x_1^{\mathrm {III}}, x_2^{\mathrm {IVb}}=x_1^{\mathrm {III}}-(b+\epsilon )$.

Obviously, instance $\mathrm {IVb}$ is position equivalent to instance $\mathrm {III}$, so it holds that $f(x_1^{\mathrm {IVb}},x_2^{\mathrm {IVb}})=x_2^{\mathrm {IVb}}+b$ as implied by anonymity and position invariance. Note that on instance $\mathrm {III}$, the cost of agent $x_2^{\mathrm {III}}$ is $b+c-\epsilon $. If agent $x_2^{\mathrm {III}}$ misreports $x_2^{\mathrm {IVb}}$, then her cost becomes $c+2\epsilon $, which is smaller than when reporting truthfully (since $\epsilon $ is arbitrarily small). So $f(\mathbf {x^{\mathrm {III}}})\not =x_1^{\mathrm {III}}+b$ if Mechanism M is strategyproof.

Hence, in order for mechanism M to be strategyproof, it must be $f(\mathbf {x}) \not = x_1+b$.

In all, there is no anonymous, position invariant and strategyproof mechanism such that $f({\mathbf {x}}) \in [x_1+b,x_2-b]$. $\square $

It is well known [28] that when agents have single-peaked preferences, outputting the location of the kth agent (kth order statistic), results in a strategyproof mechanism. This is not the case however, for double-peaked preferences and any choice of k.

Lemma 5

Given any instance $\mathbf {x}=\langle x_1,\ldots ,x_n \rangle $, any mechanism that outputs $f({\mathbf {x}})=x_i-b$, for $i=2,\ldots ,n$ or any mechanism that outputs $f({\mathbf {x}})=x_i+b$, for $i=1,\ldots ,n-1$, is not strategyproof.

Proof

We prove the case when $f({\mathbf {x}})=x_1+b$. The arguments for the other cases are similar. Consider any instance where $x_2=x_1+b$ and $x_i-b > x_2+b$ for $i=3,\ldots ,n$. Since $f(\mathbf {x})=f(x_1,x_2,x_3,\ldots ,x_n)=x_1+b$, the cost of agent 2 is $\mathrm {cost}(f(\mathbf {x}),x_2)=b+c$. If agent 2 misreports $x_2'=x_1-b$, the outcome will be $f(\mathbf {x'})=f(x_1,x_2',x_3,\ldots ,x_n)=x_2'+c=x_1$, and $\mathrm {cost}(f(\mathbf {x'}),x_2)=c<b+c=\mathrm {cost}(f(\mathbf {x}),x_2)$. Agent 2 has an incentive to misreport, therefore the mechanism is not strategyproof. $\square $

This only leaves two potential choices among kth order statistics, either $f({\mathbf {x}})=x_{1}-b$ or $f({\mathbf {x}})=x_{n}+b$. Consider the following mechanism.

Mechanism M2

Given any instance $\mathbf {x}=\langle x_1,\ldots ,x_n \rangle $, locate the facility always on the left peak of agent 1, i.e. $f({\mathbf {x}})=x_{1}-b$ or always on the right peak of agent n, i.e. $f(\mathbf {x})=x_n+b$.

From now on, we will assume that M2 locates the facility on $x_1-b$ on any instance $\mathbf {x}$. The analysis for the other case is similar.

Theorem 5

Mechanism M2 is strategyproof.

Proof

Obviously, agent 1 has no incentive to misreport, since her cost is already minimum. For any other agent $i, i=2,\ldots ,n$, the cost is $\mathrm {cost}(f({\mathbf {x}}),x_{i}) = c+x_i-x_1$. For any misreport $x'_{i} \ge x_1$, the facility is still located on $x_1-b$ and every agent’s cost is the same as before. For some misreport $x'_{i} < x_{1}$, the facility moves to $f(x_1,\ldots ,x_i',\ldots ,x_n)=x'_{i}-b<x_1-b$, i.e. further away from any of agent i’s peaks and hence this choice admits a larger cost for her. $\square $

In the following, we prove that for the case of two agents, Mechanism M2 is actually the only strategyproof mechanism that satisfies anonymity and position invariance. We start with the following lemma.

Lemma 6

For any instance ${\mathbf {x}}= \langle x_1,x_2 \rangle $, where $x_1+b<x_2-b$, if an anonymous, position invariant and strategyproof mechanism outputs $f(x_1,x_2)=x_1-b$, then it must output $f(x'_1,x'_2)=x_1'-b$ for any instance $\mathbf {x'}=\langle x_1',x_2'\rangle $ with $x_1' \le x_2'$.

Proof

Let $(x_2-b) - (x_1+b) = \gamma $. For any other instance $\mathbf {x'}=\langle x'_1,x'_2\rangle $ with $x_1' \le x_2'$, we assume $x'_1=x_1$ without loss of generality due to position invariance. In particular, we will first prove that on any instance $\mathbf {x'}$ with $x'_1=x_1$ and $x'_2 > x_1$, the position of the facility has to be $x'_1-b$ and we will establish that by only considering potential deviations of agent 2 on instance ${\mathbf {x}}$ such that $x_2'\ge x_1$. If it holds for this set of deviations, then it certainly holds even if agent 2 can deviate anywhere on the real line. Let S be the set of those instances. But then, any instance ${\tilde{\mathbf {x}}} \notin S$ is position equivalent to some instance $\mathbf {x} \in S$ and therefore it has to be that $f({\tilde{\mathbf {x}}})=\tilde{x}_1-b$ and the lemma will follow.

On instance $\mathbf {x}$, the cost of agent 2 is $2b+c+\gamma $, so for any deviation of $x_2$, her cost must be at least $2b+c+\gamma $, as required by strategyproofness. This implies that if agent 2 misreports $x'_2$, then on the resulting instance it must be either $f(x_1,x'_2) \in (-\infty ,x_1-b]$ or $f(x_1,x'_2)\in [x_2+3b+\gamma ,+\infty )$.

First, assume $f(x_1,x_2')\in [x_2+3b+\gamma ,\infty )$. Let instance $\mathrm {I}$ be $\mathbf {x^I}=\langle x^\mathrm {I}_1,x^\mathrm {I}_2\rangle $, where $x^\mathrm {I}_1=x_1, x^\mathrm {I}_2=f(x_1,x_2')+b$. On instance $\mathrm {I}$ it must be either $f(x^\mathrm {I}_1,x^\mathrm {I}_2)=f(x_1,x_2')$ or $f(x^\mathrm {I}_1,x^\mathrm {I}_2)=f(x_1,x_2')+2b$, otherwise agent 2 can deviate from $x^\mathrm {I}_2$ to $x_2'$ and move the facility to $x_2^{\mathrm {I}}-b$, minimizing her cost and violating strategyproofness. However then, on instance $\mathrm {I}$, agent 1 can misreport $\bar{x}_1^{\mathrm {I}}=x^\mathrm {I}_2-2b-\gamma $ and move the facility to $x^{\mathrm {I}}_2-3b-\gamma $, reducing her cost and violating strategyproofness. This follows from the fact that the resulting instance $\langle \bar{x}_1^\mathrm {I},x_2^\mathrm {I}\rangle $ and instance $\mathbf {x}$ are position equivalent and that $f(x_1,x_2)=x_1-b$ on instance $\mathbf {x}$. Hence, it can not be that $f(x_1,x_2') \in [x_2+3b+\gamma ,\infty )$ on instance $\mathbf {x'}$.

Second, assume $f(x_1,x_2')\in (-\infty ,x_1-b)$. Then, since $x_2' > x_1$, agent 2 can deviate from $x_2'$ to $x_2$ and move the facility to $x_1-b$, i.e. closer to her actual position. Hence, it can’t be that $f(x_1,x_2') \in (-\infty ,x_1-b)$ on instance $\mathbf {x'}$ either.

In conclusion, it must be $f(x_1,x_2')=f(x_1',x_2')=x_1'-b$ for any instance $\mathbf {x'}=(x_1',x_2')$ with $x_1' \le x_2'$. $\square $

Theorem 6

When $n=2$, the only strategyproof mechanism that satisfies position invariance and anonymity is Mechanism M2.

Proof

For contradiction, suppose there exists an anonymous, position invariant strategyproof mechanism M which is different from Mechanism M2 and consider the primary instance used in Lemma 4.

We first argue that it must be that $f(x_1,x_2) \in [x_1+b,x_2-b]$. Assume on the contrary that $f(x_1,x_2) < x_1+b$ (the argument for $f(x_1,x_2)>x_2-b$ is symmetric). Then, consider the instance $\langle x'_1,x'_2 \rangle $, where $x_2'=x_2$ and $x_1'=f(x_1,x_2)-b$. On this instance, it must be that $f(x_1',x_2') = x_1'-b$ or $f(x_1',x_2') = x_1'+b$, otherwise agent 1 can deviate from $x_1'$ to $x_1$ and move the facility to $x_1'+b$, minimizing her cost. In addition, if $f(x_1',x_2') = x_1'-b$, then according to Lemma 6, the unique strategyproof mechanism that satisfies position invariance and anonymity is Mechanism M2, and thus our assumption is violated. So let’s assume $f(x_1',x_2')=x_1'+b$. Then, on the primary instance, agent 2 could report $\hat{x}_2 =x_2+(x_1+b-f(x_1,x_2))$ and by position invariance (since instances $\langle x_1',x_2'\rangle $ and $\langle x_1,\hat{x}_2\rangle $ are position equivalent), it should be $f(x_1,\hat{x}_2)=x_1+b$. This would give agent 2 an incentive to misreport, violating strategyproofness. Hence, on the primary instance it must be that $f(x_1,x_2) \in [x_1+b,x_2-b]$.

However, according to Lemma 4, it is impossible for a strategyproof mechanism to output $f(x_1,x_2) \in [x_1+b,x_2-b]$ on the primary instance. In conclusion, no mechanism other than Mechanism M2 is strategyproof, anonymous and position invariant. $\square $

We have seen that Mechanism M2 is strategyproof, but how well does it perform with respect to our goals, namely minimizing the social cost or the maximum cost? In other words, what is the approximation ratio that Mechanism M2 achieves against the optimal choice? First, we observe that the optimal mechanism, which minimizes the social cost, is not strategyproof.

Theorem 7

The optimal mechanism with respect to the social cost, $f_{\mathrm {opt}}(\mathbf {x}) = \arg \min \limits _y \sum \limits _{i=1}^{n} \mathrm {cost}(y,x_i)$, is not strategyproof.

Proof

Consider an instance ${\mathbf {x}}=\langle x_1,x_2,x_3\rangle $, such that $x_2+b<x_3-b$, $x_2-b< x_1 + b < x_2$ and $(x_1+b)-(x_2-b) = \epsilon $, where $\epsilon $ is an arbitrarily small positive quantity. On this instance, the optimal facility location is $x_2+b$ and the cost of agent $x_1$ is $c+2b-\epsilon $. Suppose now that agent $x_1$ reports $x'_1 < x_2-2b$. Moreover, suppose that when there are two locations $y_1$ and $y_2$, with $y_1 < y_2$ that admit the same social cost, the optimal mechanism outputs $y_1$. If the mechanism outputs $y_2$ instead, we can use a symmetric argument on the instance $\mathbf {x'}=\langle x'_1,x'_2,x'_3 \rangle =\langle x'_1,x_2,x_2+2b-\epsilon \rangle $ with agent 3 misreporting $x_3$.² By this tie-breaking rule, on instance $\mathbf {x}=\langle x_1',x_2,x_3\rangle $, the location of the facility is $x_2-b$ and the cost of agent $x_1$ is $c+\epsilon $, i.e. smaller than before. Hence, the optimal mechanism is not strategyproof. To extend this to an arbitrary number of agents, let $x_j=x_2$ for every other agent $x_j$. $\square $

Unfortunately, when considering the social cost, in the extremal case, the approximation ratio of Mechanism M2 is dependent on the number of agents. The approximation ratio is given by the following theorem.

Theorem 8

For $n > 3$ agents, the approximation ratio of Mechanism M2 for the social cost is

$$\begin{aligned} \max \left\{ n-1,1+\frac{2b}{c}\right\} . \end{aligned}$$

Proof

Consider any instance $\mathbf {x'}=\langle x'_1,\ldots ,x'_n\rangle $ and let $y=f_{\mathrm {opt}}(\mathbf {x'})$. It also holds that $f_{\mathrm{M2}}(\mathbf {x'})=x'_1-b$. Denote the social costs of the optimal mechanism and Mechanism M2 on instance $\mathbf {x'}$ by $SC_{\mathrm {opt}}(\mathbf {x'})$ and $SC_{\mathrm{M2}}(\mathbf {x'})$, respectively. Let $\mathbf {x}$ be the instance obtained by instance $\mathbf {x'}$ as follows. For every agent $i, i \ne 1$, if $x'_i+b \le y$, let $x_i=2y-x'_i$; if $x'_i< y< x'_i + b$, let $x_i =x'_i+2b$; if $x'_i-b<y<x'_i$, let $x_i =2y-x'_i+2b$; otherwise let $x_i=x'_i$. Observe that $|x_i-b-y|=\min \left( |x'_i-b-y|,|x'_i+b-y|\right) $ and hence $\text {cost}(x_i,y)=\text {cost}(x'_i,y)$ for every agent i. Similarily, it holds that $(x_i-b)-(x_1-b)\ge (x'_i-b)-(x'_1-b)$ and hence (since $x_1=x'_1$), $\text {cost}(x_i-b,x_1-b)\ge \text {cost}(x'_i-b,x'_1-b)$ for all agents i.

We will calculate an upper bound on the approximation ratio on instance $x'$. To do that, we will calculate an upper bound on the value of the ratio $SC_{\mathrm{M2}}(\mathbf {x})/SC_{y}(\mathbf {x})$ on instance $\mathbf {x}$, where $SC_{\mathrm{M2}}(\mathbf {x})$ is the social cost of Mechanism M2 on instance $\mathbf {x}$ and $SC_{y}(\mathbf {x})$ is the social cost admitted by y on instance $\mathbf {x}$. By the way the instance was constructed, it holds that $SC_{\mathrm{M2}}(\mathbf {x}) \ge SC_{\mathrm{M2}}(\mathbf {x'})$ and $SC_{y}(\mathbf {x})=SC_{y}(\mathbf {x'})=SC_{\mathrm {opt}}(\mathbf {x'})$ and hence $SC_{\mathrm{M2}}(\mathbf {x})/SC_{y}(\mathbf {x})$ is an upper bound on $SC_{\mathrm{M2}}(\mathbf {x'})/SC_{\mathrm {opt}}(\mathbf {x'})$.

Let $d_i=(x_i-b)-y$, for $i=2,\ldots ,n$ and let $k = \sum _{i\ne 1}d_i$. Finally let $d = |y - (x_1+b)|$. We consider three cases. (See Fig. 3).

Case 1 $x_1+b < y$.

In this case, the social cost admitted by y is $SC_{y}(\mathbf {x}) = nc+ k + d$, and the cost of Mechanism M2 is $SC_{\mathrm{M2}}(\mathbf {x})= nc + k + (n-1)(d+2b)$. The ratio is

$$\begin{aligned} \frac{SC_{\mathrm{M2}}(\mathbf {x})}{SC_{y}(\mathbf {x})} = g(k,d,n) = \frac{k+(n-1)(d+2b)+nc}{k+d+nc}. \end{aligned}$$

By calculating the partial derivative of the ratio with respect to k, we have

$$\begin{aligned} \frac{\partial g(k,d,n)}{\partial k}= & {} \frac{k+d+nc-k-(n-1)(d+2b)-nc}{(k+d+nc)^2} = \frac{d - (n-1)(d+2b)}{(k+d+nc)^2} < 0. \end{aligned}$$

When $k=0$, i.e. $x_i=y+b$ for all agents $i=2,\ldots ,n$, the ratio achieves the maximum value with respect to k. We plug in $k=0$ to the above formula and get

$$\begin{aligned} \frac{SC_{\mathrm{M2}} (\mathbf {x})}{SC_{y}(\mathbf {x})} = g(d,n)= & {} \frac{(n-1)(d+2b)+nc}{d+nc} = \frac{(n-1)d + 2(n-1)b+nc}{d+nc}. \end{aligned}$$

Again, we calculate the partial derivative of g(d, n) with respect to d,

$$\begin{aligned} \frac{\partial g(d,n)}{\partial d}= & {} \frac{(n-1)(d+nc) - (n-1)d - 2(n-1)b-nc}{(d+nc)^2} = \frac{c(n^2-4n+2)}{(d+nc)^2}. \end{aligned}$$

For sufficiently large n ($n\ge 4$), the above value is positive, so the ratio is maximized when d approaches to infinity, which means that agent $x_1$ is positioned very far away from the rest of the agents coinciding on position $x_i$. Therefore the ratio goes to $n-1$.

Case 2 $x_1 < y \le x_1+b$, which means $0\le d<b$.

In this case, the social cost admitted by y is $SC_{y}(\mathbf {x}) = k + d +nc$, and the cost of Mechanism M2 is $SC_{\mathrm{M2}}(\mathbf {x})=k+(n-1)(2b-d)+nc$. So the ratio is

$$\begin{aligned} \frac{SC_{\mathrm{M2}}(\mathbf {x})}{SC_{y}(\mathbf {x})} = g(k,d,n) = \frac{k+(n-1)(2b-d)+nc}{k+d+nc}. \end{aligned}$$

Again, we calculate the partial derivative of g(k, d, n) with respect to k,

$$\begin{aligned} \frac{\partial g(k,d,n)}{\partial k}= & {} \frac{k+d+nc-k-(n-1)(2b-d)-nc}{(k+d+nc)^2} = \frac{d-(n-1)(2b-d)}{(k+d+nc)^2} . \end{aligned}$$

Since $0\le d<b$, $d < 2b-d$ and the above value is negative. To get the maximum value of the ratio, we plug in $k=0$ and the approximation ratio becomes

$$\begin{aligned} \frac{SC_{\mathrm{M2}}(\mathbf {x})}{SC_{y}(\mathbf {x})} = g(d,n) = \frac{(n-1)(2b-d)+nc}{d+nc}. \end{aligned}$$

By calculating the partial derivative with respect to d, we get

$$\begin{aligned} \frac{\partial g(d,n)}{\partial d}= & {} \frac{-(n-1)(d+nc)-(n-1)(2b-d)-nc}{(d+nc)^2}\\ {}= & {} \frac{-(n-2)nc-(n-1)2b}{(d+nc)^2} < 0. \end{aligned}$$

So the ratio is maximized when $d=0$, and the ratio is $\frac{2b(n-1)+nc}{nc} < 1+\frac{2b}{c}$.

Case 3 $x_1-b<y \le x_1$, which means $b \le d <2b$.

In this case, the social cost admitted by y is $SC_{y}(\mathbf {x}) = k + 2b-d + nc$, and cost of Mechanism M2 is $SC_{{\mathrm{M2}}}(\mathbf {x})=k+(n-1)(2b-d)+nc$. So the ratio is

$$\begin{aligned} \frac{SC_{\mathrm{M2}}(\mathbf {x})}{SC_{y}(\mathbf {x})} = g(k,d,n) = \frac{k+(n-1)(2b-d)+nc}{k+2b-d+nc}. \end{aligned}$$

We first calculate partial derivative of the function g with respect to k,

$$\begin{aligned} \frac{\partial g(k,d,n)}{\partial k}= & {} \frac{k+2b-d+nc-k-(n-1)(2b-d)-nc}{(k+2b-d+nc)^2} \\= & {} \frac{(2-n)(2b-d)}{(k+2b-d+nc)^2} < 0. \end{aligned}$$

The function is decreasing in k so let’s set $k=0$. The function f becomes

$$\begin{aligned} \frac{SC_{\mathrm{M2}} (\mathbf {x})}{SC_{y}(\mathbf {x})} = g(d,n) = \frac{(n-1)(2b-d)+nc}{2b-d+nc}. \end{aligned}$$

Now, we calculate partial derivative of g with respect to d and get

$$\begin{aligned} \frac{\partial g(d,n)}{\partial d}= & {} \frac{-(n-1)(2b-d)-n(n-1)c +(n-1)(2b-d) +nc}{(2b-d+nc)^2} \le 0. \end{aligned}$$

So function g(d, n) is decreasing in d. Let’s set $d=b$, and the ratio goes to $\frac{(n-1)b+nc}{b+nc}$, which is always smaller than $n-1$.

In all, since $SC_{\mathrm{M2}}(\mathbf {x})/SC_{y}(\mathbf {x}) \le n-1$ the approximation ratio of Mechanism M2 is at most $\max \{n-1,1+\frac{2b}{c}\}$. The approximation ratio is exactly $n-1$ on any instance $\mathbf {x}=\langle x_1,x_2,\ldots ,x_n\rangle $ with $x_2=\cdots =x_n$ and $x_1 \ll x_2$, i.e. when agent 1 lies on the left, really far away from the other $n-1$ agents. We note that by our analysis, it follows that the other upper bound of the ratio of the mechanism is actually $1+\frac{(n-1)2b}{nc}$ but we instead wrote a larger bound of $1+\frac{2b}{c}$ for ease of exposition. The ratio is exactly $1+\frac{(n-1)2b}{nc}$ on any instance $\mathbf {x}=\langle x_1,x_2,\ldots ,x_n\rangle $ with $x_1+b=x_2-b=\cdots =x_n-b$ and goes to $1+\frac{2b}{c}$ as n goes to infinity. $\square $

Next, we will prove a lower bound of $1+b/c$ on the approximation ratio of any anonymous, position invariant, and strategyproof mechanism, when the number of agents is even. We will start with the following lemma. The main intuition behind the proof of the lemma is that we will simulate profiles with two agents with profiles with n agents, where two groups of n / 2 agents coincide on two different positions. The two-agent mechanism will then output the same location that the n-agent mechanism outputs on the respective location profile. Similar ideas have been used before in the literature, e.g. see [19, 36].

Lemma 7

Let $M^n$ be a strategyproof, anonymous and position invariant mechanism for n agents, where n is even. Then, for any location profile $\mathbf {x}=\langle x_1=\cdots =x_{n/2}, x_{n/2+1}=\cdots =x_n\rangle $, it holds that $M^n(\mathbf {x})= x_1-b$.

Proof

Let $M^2$ be the following mechanism for two agents: On input location profile $\langle x_1,x_2\rangle $, output $M^n(\mathbf {x'})$, where $\mathbf {x'}=\langle x'_1=\cdots =x'_{n/2}, x'_{n/2+1}=\cdots =x'_n \rangle $, and $x'_1=x_1$ and $x'_{n/2+1}=x_2$. First, we claim that $M^2$ is strategyproof, anonymous and position invariant. If that is true, then by Theorem 6, $M^2$ is Mechanism M2 and the lemma follows.

First let $\mathbf {x}=\langle x_1,x_2 \rangle $, ${\hat{\mathbf {x}}}=\langle \hat{x}_1, \hat{x}_2 \rangle $ be any two position equivalent location profiles. Observe that the corresponding n-agent profiles $\mathbf {x'}$ and ${\hat{\mathbf {x}}'}$ obtained by placing n / 2 agents on $x_1$ and $\hat{x_1}$ and n / 2 agents on $x_2$ and $\hat{x_2}$ respectively are also position equivalent. Since $M^n$ is position invariant, it must hold that $M^n(\mathbf {x'})=M^n({\hat{\mathbf {x}}'})$ and hence by construction of $M^2$, $M^2(\mathbf {x})=M^2({\hat{\mathbf {x}}})$. Since $\mathbf {x}$ and ${\hat{\mathbf {x}}}$ where arbitrary, Mechanism $M^2$ is position invariant.

Similarly, let $\mathbf {x}=\langle x_1,x_2 \rangle $, ${\hat{\mathbf {x}}}=\langle \hat{x}_1, \hat{x}_2 \rangle $ be any two location profiles, such that ${\hat{\mathbf {x}}}$ is obtained by $\mathbf {x}$ by a permutation of the agents. The outcome of $M^n$ on the corresponding n-agent location profiles (since the number of agents placed on $x_1$ and $x_2$ is the same) is the same and by construction of $M^2$, $M^2(\mathbf {x})=M^2({\hat{\mathbf {x}}})$ and since the profiles where arbitrary, the mechanism is anonymous.

Finally, for strategyproofness, start with a location profile ${\hat{\mathbf {x}}'}=\langle \hat{x}'_1,\hat{x}'_2 \rangle $ and let $\mathbf {x'}=\langle x'_1=\cdots =x'_{n/2}, x'_{n/2+1}=\cdots =x'_n \rangle $ be the corresponding n-agent location profile. Let $y=M^n(\mathbf {x'})$ and let $\text {cost}(x',y)$ be the cost of agents $x'_1,\ldots ,x'_{n/2}$ on $\mathbf {x'}$. For any $x_1$, let $\langle x_1, x'_2=\cdots =x'_{n/2}, x'_{n/2+1}=\cdots =x'_n \rangle $ be the resulting location profile. By strategyproofness of $M^n$, agent $x'_1$ can not decrease her cost by misreporting $x_1$ on profile $\mathbf {x'}$ and hence her cost on the new profile is at least $\text {cost}(x',y)$. Next, consider the location profile $\langle x_1=x_2,x'_3=\cdots =x'_{n/2}, x'_{n/2+1}=\cdots =x'_n \rangle $ and observe that by the same argument, the cost of agent $x'_2$ is not smaller on the new profile when compared to $\langle x_1, x'_2=\cdots =x'_{n/2}, x'_{n/2+1}=\cdots =x'_n \rangle $ and hence her cost is at least $\text {cost}(x',y)$. Continuing like this, we obtain the profile $\langle x_1=\cdots =x_{n/2},x'_{n/2+1}=\cdots =x'_n \rangle $ and by the same argument, the cost of agent $x'_{n/2}$ on this profile is at least $\text {cost}(x',y)$. The location profile $\langle x_1=\cdots =x_{n/2},x'_{n/2+1}=\cdots =x'_n \rangle $ corresponds to the 2-agent location profile ${\hat{\mathbf {x}}}=\langle \hat{x}_1,\hat{x}'_2 \rangle $ and by construction of $M^2$, $\text {cost}(\hat{x}'_1,M^2({\hat{\mathbf {x}}'})) \le \text {cost}(\hat{x}'_1,M^2({\hat{\mathbf {x}}}))$ and since the choice of $x_1$ (and hence the choice of $\hat{x_1}$) was arbitrary, Mechanism $M^2$ is strategyproof. $\square $

Theorem 9

When the number of agents is even, no strategyproof mechanism that satisfies position invariance and anonymity can achieve an approximation ratio lower than $1+(b/c)$ for the social cost.

Proof

Let $M^n$ be a strategyproof, anonymous and position invariant mechanism and consider any location profile $\mathbf {x}=\langle x_1=\cdots =x_{n/2},x_{n/2}+1=\cdots =x_n$ with $x_{n/2+1}=x_1+2b$. By Lemma 7, $M^n(\mathbf {x})= x_1-b$ and the social cost of $M^n$ is $nc+(n/2)\cdot 2b$ while the social cost of the optimal allocation is only nc. The lower bound follows. $\square $

4.2 Maximum cost

First, it is easy to see that the mechanism that outputs the location that minimizes the maximum cost is not strategyproof. On any instance $\langle x_1,x_2 \rangle $ with $x_1+b < x_2-b$ the optimal location of the facility is $(x_1+x_2)/2$. If agent $x_2$ misreports $x_2'=2x_2-2b-x_1$ then the location moves to $x_2-b$, minimizing her cost.

While the approximation ratio of Mechanism M2 for the social cost is not constant, for the maximum cost that is indeed the case. In fact, as we will prove, when the number of agents is even, Mechanism M2 actually achieves the best possible approximation ratio amongst strategyproof mechanisms. We start with the theorem about the approximation ratio of Mechanism M2.

Theorem 10

For $n \ge 3$, Mechanism M2 achieves an approximation ratio of $1+\frac{2b}{c}$ for the maximum cost.

Proof

Let $\mathbf {x}=\langle x_1,\ldots ,x_n\rangle $ be any instance. We consider three cases, depending on the distance between agents $x_1$ and $x_n$.

Case 1 $x_1+b \le x_n-b \Rightarrow x_n-x_1 \ge 2b$.

In this case, the cost of the optimal mechanism is $MC_{\mathrm {opt}}(\mathbf {x}) = (x_n -b) - \frac{x_1+x_n}{2} + c = \frac{x_n-x_1}{2}-b+c$, whereas the cost of Mechanism M2 is $MC_{\mathrm{M2}}(\mathbf {x}) = x_n-x_1+c$. The approximation ratio is

$$\begin{aligned} \frac{MC_{\mathrm{M2}} (\mathbf {x})}{MC_{\mathrm {opt}}(\mathbf {x})} = \frac{2(x_n-x_1+c)}{x_n-x_1-2b+2c} = 2+ \frac{4b-2c}{x_n-x_1-2b+2c} \le 1+\frac{2b}{c}. \end{aligned}$$

Hence, in this case, the approximation ratio is at most $1+\frac{2b}{c}$. For $x_n-b=x_1+b$ (the instance on which the right peak of the first agent and the left peak of the last agent coincide), the approximation ratio is exactly $1+\frac{2b}{c}$.

Case 2 $x_1< x_n-b< x_1+b \Rightarrow c< x_n-x_1 < 2b$.

The cost of Mechanism M2 in this case is $MC_{\mathrm{M2}}(\mathbf {x}) = x_n-b - (x_1-b)+c = x_n-x_1+c$, while the cost of the optimal mechanism is at least c. The approximation ratio is

$$\begin{aligned} \frac{MC_{\mathrm{M2}} (\mathbf {x})}{MC_{\mathrm {opt}}(\mathbf {x})} \le \frac{(x_n-x_1+c)}{c} < 1+\frac{2b}{c} \end{aligned}$$

Case 3 $x_1-b \le x_n-b \le x_1 \Rightarrow x_n-x_1 \le b$.

The cost of Mechanism M2 is $MC_{\mathrm{M2}}(\mathbf {x}) = x_n-x_1+c$ while the cost of the optimal mechanism is at least c. The approximation ratio is

$$\begin{aligned} \frac{MC_{\mathrm{M2}} (\mathbf {x})}{MC_{\mathrm {opt}}(\mathbf {x})} \le \frac{(x_n-x_1+c)}{c} \le 1+\frac{b}{c}. \end{aligned}$$

Over the three cases, the worst approximation ratio is at most $1+\frac{2b}{c}$ and there is actually an instance of the problem with approximation ratio exactly $1+\frac{2b}{c}$, ensuring that the bound is tight. $\square $

The lower bound for the case when the number of agents is even follows.

Corollary 1

When the number of agents is even, no deterministic strategyproof mechanism that satisfies position invariance and anonymity can achieve an approximation ratio lower than $1+\frac{2b}{c}$ for the maximum cost.

Proof

On instance ${\hat{\mathbf {x}}}$ of the proof of Theorem 9, there are agents whose cost for any strategyproof, anonymous and position invariant mechanism is $2b+c$, while under the optimal mechanism it is only c. The lower bound on the approximation ratio follows. $\square $

A different lower bound that holds for any number of agents (and without using the position invariance property) is proved in the next theorem.

Theorem 11

No deterministic strategyproof mechanism can achieve an approximation ratio lower than 2 for the maximum cost.

Proof

Consider an instance $\mathbf {x}=\langle x_1,x_2 \rangle $ with $x_1+b < x_2-b$ (the instance can be extended to arbitrarily many agents by placing agents on positions $x_1$ and $x_2$ and all the arguments will still hold). The optimal location of the facility is $f_{\mathrm {opt}}(\mathbf {x}) = \frac{x_1+x_2}{2}$. Assume for contradiction that M is a deterministic strategyproof mechanism with approximation ratio smaller than 2.

First, we argue that it can not be that $f_\mathrm {M}(\mathbf {x}) \in [x_2-b,\infty )$. Let $d = x_2-b-f_{\mathrm {opt}}(\mathbf {x})$. It holds that $MC_{\mathrm {opt}}(\mathbf {x})=c+d$. If it was $f_\mathrm {M}(\mathbf {x}) \in [x_2-b,\infty )$, then it would be that $MC_{\mathrm {M}}(\mathbf {x})\ge c+2d$ and the approximation ratio would be at least $2-\frac{c}{d+c}$ which goes to 2 as d grows to infinity (i.e. the agents are placed very far away from each other). Now, for Mechanism M to achieve an approximation ratio smaller than 2, it must be $f_{\mathrm {M}}(\mathbf {x}) \in [f_{\mathrm {opt}}(\mathbf {x}),x_2-b)$ (or symmetrically $f_{\mathrm {M}}(\mathbf {x}) \in (x_1+b,f_{\mathrm {opt}}(\mathbf {x})]$).

Now consider the instance $\mathbf {x'}=\langle x_1',x_2'\rangle $ with $x_1'=x_1$ and $x_2' = f_{\mathrm {M}}(\mathbf {x})+b$. On this instance, it must be either $f_{\mathrm {M}}(\mathbf {x'})=f_{\mathrm {M}}(\mathbf {x})$ or $f_{\mathrm {M}}(\mathbf {x'})=f_{\mathrm {M}}(\mathbf {x})+2b$ (the left or the right peak of agent $x_2'$), otherwise agent $x_2'$ could report $x_2$ and move the facility to $x_2'-b$, minimizing her cost and violating strategyproofness. For calculating the lower bound, we need the choice that admits the smaller of the two costs, i.e. $f_{\mathrm {M}}(\mathbf {x'})=f_{\mathrm {M}}(\mathbf {x})$. We calculate the approximation ratio on instance $\mathbf {x'}$.

The optimal choice for the facility is again $f_{\mathrm {opt}}(\mathbf {x'})=(x_1+x_2')/2$. Let $\lambda = (x_2'-b) - f_{\mathrm {opt}}(\mathbf {x'})$. The approximation ratio then is $2-\frac{c}{\lambda +c}$. We know that $\lambda \ge d/2$, so when d grows to infinity as before, $\lambda $ also grows to infinity and the approximation ratio goes to 2. This means that there exists an instance for which the approximation ratio of the mechanism is 2, which gives us the lower bound. $\square $

5 Group strategyproofness

As we mentioned in the introduction, under the reasonable conditions of position invariance and anonymity, there is no group strategyproof mechanism for the problem. We will prove this claim by using Lemma 4 and the following lemma.

Recall the definition of the primary instance from Sect. 4. When $n=2k+1, k\in \mathbb {Z}^+$, let P be the instance obtained by locating $k+1$ agents on $x_1$ and k agents on $x_2$ on the primary instance. Similarly, let S be the instance obtained by locating k agents on $x_1$ and $k+1$ agents on $x_2$ on the primary instance. Formally, let ${\mathbf {x}}^P=\langle x_1^P, \ldots ,x_n^P \rangle $, where $x_1^P=\cdots =x_{k+1}^P$, $x_{k+2}^P=\cdots =x_{n}^P$, and $(x_{n}^P-b)-(x_{1}^P+b)=b+\epsilon $ and ${\mathbf {x}}^S=\langle x_1^S, \ldots ,x_n^S \rangle $, where $x_1^S=\cdots =x_{k}^S$, $x_{k+1}^S=\cdots =x_{n}^S$, and $(x_{n}^S-b)-(x_{1}^S+b)=b+\epsilon $, where $\epsilon $ is the same quantity as in the primary instance.

Lemma 8

When $n=2k+1$, any position invariant and group strategyproof mechanism that outputs $f(\mathbf {x^P})=x_{1}^{{\mathrm {P}}}+b$ on instance ${\mathrm {P}}$, must output $f(\mathbf {x})=x_1+b$ on any instance $\mathbf {x}=\langle x_1,\ldots ,x_n \rangle $, where $x_1=\cdots =x_{k+1}$, $x_{k+2}=\cdots =x_{n}$ and $(x_{n}-b)-(x_{1}+b)=2b$. Similarly, any position invariant and group strategyproof mechanism that outputs $f(\mathbf {x^S})=x_{n}^{\mathrm {S}}-b$ on instance ${\mathrm {S}}$, must output $f(\mathbf {x})=x_n-b$ on any instance $\mathbf {x}=\langle x_1,\ldots ,x_n \rangle $, where $x_1=\cdots =x_{k}$, $x_{k+1}=\cdots =x_{n}$ and $(x_{n}-b)-(x_{1}+b)=2b$.

Proof

We prove the first part of the lemma. The proof of the second part is symmetric. Note that the difference between instances ${\mathbf {x}}^{{\mathrm {P}}}$ and ${\mathbf {x}}$ is that the distance between the two groups of agents is $3b+\epsilon $ in ${\mathbf {x}}^{{\mathrm {P}}}$ while it is 4b in ${\mathbf {x}}$. First, we argue that $f({\mathbf {x}})\in [x_1+b,x_n-b]$. Indeed, if that was not the case, if $f({\mathbf {x}})<x_1+b$, by the onto condition implied by position invariance, all agents could jointly misreport some different positions and move the facility to $x_1+b$. This point admits a smaller cost for all agents; specifically the cost of agents $x_1,\ldots ,x_{k+1}$ is minimized while the cost of agents $x_{k+2},\ldots ,x_{n}$ is reduced and group strategyproofness is violated. Using a symmetric argument, we conclude that it can’t be $f({\mathbf {x}})>x_n-b$ either.

Secondly, we argue that $f({\mathbf {x}}) \not \in (x_1+b,x_n-b]$. Indeed, assume that was not the case. Then agents $x^{{\mathrm {P}}}_{k+2},\ldots ,x^{{\mathrm {P}}}_{n}$ on instance ${\mathbf {x}}^{{\mathrm {P}}}$ could jointly misreport $x_{k+2},\ldots ,x_{n}$ and move the facility from $f(\mathbf {x^P})=x_{1}^{{\mathrm {P}}}+b$ to $f({\mathbf {x}})$. Since by assumption $f({\mathbf {x}}) \in (x_1+b,x_n-b]$, the cost of each deviating agent is smaller than her cost before deviating. Group strategyproofness is then violated and hence it must be that $f(\mathbf {x})=x_1+b$. By position invariance, it must be that $f({\bar{\mathbf {x}}})=\bar{x}_1+b$ on any instance ${\bar{\mathbf {x}}}$ which is position equivalent to instance $\mathbf {x}$. $\square $

Theorem 12

There is no group strategyproof mechanism that is anonymous and position invariant.

Proof

When $n=2$, on the primary instance, according to Lemma 4, there is no anonymous, position invariant and strategyproof mechanism such that $f({\mathbf {x}}) \in [x_1+b,x_2-b]$. In addition, if the facility was placed on some point $f(\mathbf {x}) < x_1+b$ (the argument for $f(\mathbf {x})>x_2-b$ is symmetric), for any mechanism that satisfies position invariance which implies onto, agents 1 and 2 could jointly misreport some positions $\hat{x}_1$ and $\hat{x}_2$ such that $f(\hat{x}_1,\hat{x}_2)=x_1+b$. Obviously, this deviation admits the minimum possible cost for agent 1 and a reduced cost for agent 2, violating group strategyproofness.

The proof can easily be extended to the case when n is even. On the primary instance, simply place $\frac{n}{2}$ agents on $x_1$ and $\frac{n}{2}$ agents on $x_2$. By considering deviations of coalitions of agents coinciding on $x_1$ or $x_2$ instead of deviations of agents $x_1$ and $x_2$ respectively, all the arguments still hold. However, additional care must be taken when n is odd.

When $n=2k+1, k\in \mathbb {Z^+}$, we denote by $P_{\mathrm {J}}$ the instance after placing $k+1$ agents on $x_{1}^{\mathrm {J}}$ and k agents on $x_{2}^{\mathrm {J}}$ on instance $\mathrm {J}$, where $\mathrm {J}$ is either instance $\mathrm {I}$, $\mathrm {II}$, $\mathrm {III}$, $\mathrm {IVa}$ or $\mathrm {IVb}$ of the proof of Lemma 4. Similarly, let $S_{\mathrm {J}}$ be the instance after placing k agents on $x_{1}^{\mathrm {J}}$ and $k+1$ agents on $x_{2}^{\mathrm {J}}$ on instance $\mathrm {J}$. Finally, let ${X_{1}^{\mathrm {K}}}$ be the group of agents i for which $x_{i}^{{\mathrm {K}}}=x_{1}^{\mathrm {K}}$ on instance K, where K is either $P,P_{\mathrm {I}},P_{\mathrm {II}},P_{\mathrm {III}}, P_{\mathrm {IVa}},P_{\mathrm {IVb}}, S,S_{\mathrm {I}},S_{\mathrm {II}},S_{\mathrm {III}}, S_{\mathrm {IVa}}$ or $S_{\mathrm {IVb}}$, and let ${X_{2}^{\mathrm {K}}}$ be the group of agents i for which $x_{i}^{{\mathrm {K}}}=x_{n}^{\mathrm {K}}$ on instance $\mathrm {K}$.

For contradiction, assume that there exists an anonymous, position invariant, and group strategyproof mechanism. On instance P, by group strategyproofness, it must be $f(\mathbf {x^{P}}) \in [x_1^{P}+b,x_n^{P}-b]$ and by the same arguments used in case 1 of Lemma 4 (with instances $P_{\mathrm {I}},P_{\mathrm {II}}$ instead of $\mathrm {I},\mathrm {II}$ and with $X_{1}^{P}$ and $X_{2}^{P}$ instead of $x_1$ and $x_2$)³, it must be $f(\mathbf {x^P}) \notin (x_1^{P}+b,x_n^{P}-b)$. Hence, it must be that either $f(\mathbf {x^P})=x_1^{P}+b$ or $f(\mathbf {x^P})=x_n^{P}-b$. Assume w.l.o.g. that $f(\mathbf {x^P})=x_1^{P}+b$; the other case can be handled symmetrically.

Following the arguments of case 2 of Lemma 4 (using instance $P_{\mathrm {III}}$ instead of $\mathrm {III}$), group strategyproofness and position invariance imply that $f(\mathbf {x^{P_{\mathrm {III}}}}) = x_{1}^{P_{\mathrm {III}}}-b$ or $f(\mathbf {x^{P_{\mathrm {III}}}}) = x_{1}^{P_{\mathrm {III}}}+b$ on instance $P_{\mathrm {III}}$. By the arguments of subcase (a) (using instance $P_{\mathrm {IVa}}$ instead of $\mathrm {IVa}$), it can’t be that $f(\mathbf {x^{P_{\mathrm {III}}}}) = x_{1}^{P_{\mathrm {III}}}-b$, so it must be that $f(\mathbf {x^{P_{\mathrm {III}}}}) = x_{1}^{P_{\mathrm {III}}}+b$. However, we can not simply apply the argument used in subcase (b) to get a contradiction, because since there is a different number of agents on $x_{1}^P$ and $x_{2}^P$, instances P and $P_{\mathrm {IVa}}$ are no longer position equivalent.

Next, consider instance S and observe that $f(\mathbf {x^S}) \notin (x_{1}^{S}+b,x_{n}^{S}-b)$ by the same arguments as above and $f(\mathbf {x^S}) \in [x_{1}^{S}+b,x_{n}^{S}-b]$ by group strategyproofness and position invariance. Hence it is either $f(\mathbf {x^S})= x_{1}^{S}+b$ or $f(\mathbf {x^S})= x_{n}^{S}-b$. Assume first that $f(\mathbf {x^S})=x_{1}^{S}+b$. By the same arguments as above (using instances $S_{\mathrm {III}}$ and $S_{\mathrm {IVa}}$), on instance $S_{\mathrm {III}}$, it must be that $f(\mathbf {x^{S_{\mathrm {III}}}}) = x_{1}^{S_{\mathrm {III}}}+b$. Now, observe that if $X_{2}^{P_{\mathrm {III}}}$ misreport $\bar{x}_{i}^{P_{\mathrm {III}}}=x_{i}^{P_{\mathrm {III}}}-2b-2\epsilon $, then we get instance $P_{\mathrm {IVb}}$ which is position equivalent to instance $S_{\mathrm {III}}$ and hence it must be that $f(\mathbf {x^{P_{\mathrm {IVb}}}})=x_n^{P_{\mathrm {IVb}}}+b$. The cost of $X_{2}^{P_{\mathrm {III}}}$ before misreporting was $b+c-\epsilon $ while it becomes $c+2\epsilon $ after misreporting. This violates strategyproofness, which means that on instance S, it must be $f(\mathbf {x^S})=x_{n}^{S}-b$.

Let’s denote instance $\mathrm {T}$ by $\mathbf {x^T}=\langle x_1^{\mathrm {T}},\ldots ,x_n^{\mathrm {T}} \rangle $, where $x_1^{\mathrm {T}}=\cdots =x_{k}^{\mathrm {T}}=x_{k+1}^{\mathrm {T}}-2b=x_{k+2}^{\mathrm {T}}-4b=\cdots =x_{n}^{\mathrm {T}}-4b$. Let $X_{1}^{\mathrm {T}}$ be the set of agents i for which $x_i^{\mathrm {T}}=x_1^{\mathrm {T}}$, and let $X_{2}^{T}$ be the set of agents j for which $x_j^{\mathrm {T}}=x_n^{\mathrm {T}}$, and let $x_{t}$ be agent $x_{k+1}^{\mathrm {T}}$. On instance $\mathrm {T}$, it must be either $f(\mathbf {x}^{T})=x_{1}^{\mathrm {T}}+b$ or $f(\mathbf {x}^{T})=x_{n}^{\mathrm {T}}-b$, otherwise agent $x_{t}$ could misreport $x_{t}'=x_{1}^{\mathrm {T}}$ and then by Lemma 8 and the fact that on instance P it is $f(\mathbf {x^P})=x_1^{P}+b$, it should be $f(x_1^{\mathrm {T}},\ldots ,x_{t}',\ldots ,x_n^{\mathrm {T}})=x_t-b$, which admits a cost of c for agent $x_t$. Similarily, by Lemma 8 and the fact that on instance S, it is $f(\mathbf {x^S})=x_n^{S}-b$, if agent $x_t$ misreports $x_{t}''= x_{n}^{\mathrm {T}}$, then it should be $f(x_1^{\mathrm {T}},\ldots ,x_{t}'',\ldots ,x_n^{\mathrm {T}})=x_t+b$. If $f(\mathbf {x^{T}})=x_{n}^{\mathrm {T}}-b$, agent $x_t$ could form a coalition with agents $X_{1}^{\mathrm {T}}$ and by misreporting $x_{t}'$, move the facility to $x_{t}-b$, a choice that would admit the same cost for her, but a strictly smaller cost for every other member of the coalition. If $f(\mathbf {x^{T}})=x_{1}^{\mathrm {T}}+b$ then agent $x_t$ could form a coalition with agents $X_{2}^{\mathrm {T}}$ and by misreporting $x_{t}''$, move the facility to $x_t+b$, a choice that would admit the same cost for her, but a strictly smaller cost for every other member of the coalition. In each case, there is a coalition of agents that can benefit from misreporting and group strategyproofness is violated. This completes the proof. $\square $

6 Conclusion and discussion

In this paper, we studied a natural variant of a well-known problem, that of truthful facility location, when agents have double-peaked linear preferences over the set of possible locations. As we saw, the fact that double-peaked preferences are not as well-behaved as their well-studied single-peaked counterpart makes the problem of designing good truthful mechanisms quite more challenging. Given the standard interpretation of the median agent as a majority outcome in the single-peaked domain, our results seem to indicate that even slightly more complicated preference structures (that do not admit such majorities) might necessarily have very bad performance guarantees in the absence of such a consensus and that some sort of randomization is in fact essential.

Our work can be placed directly in the middle of the extensive literature on truthful facility location that comprises of many interesting settings, modelling different situations. The original model [1, 30] assumes single-peaked preferences, the obnoxious facility model [7, 8, 16] assumes singled-dipped (also known as single-caved preferences) whereas the dual preference model [33, 34, 39] assumes a combination of single-peaked and single-dipped preferences. Each preference structure in these works is motivated by corresponding real-life scenarios; in this light, our model can also be seen as another interesting preference structure, motivated by a different realistic scenario, which immediately places it in tight connection to the related work in artificial intelligence and theoretical computer science. Furthermore, as we mentioned in the introduction, the interest in these types of problems is expanding with works considering different objectives or more complicated cost structures.

Given that double-peaked preferences are a natural preference structure for some scenarios, as also advocated by some of the related work in economics, one could consider their use in other problems, beyond facility location. We have already mentioned their use in [38] for the problem of controlling elections; one could think of other uses in computational aspects of social choice, an important subfield of artificial intelligence. For example, one could ask the questions of whether efficient algorithms for deciding whether a given incomplete preference structure can be extended to a double-peaked profile, similarly to the corresponding questions for single-peaked preferences [3, 15]. Another question is whether it is possible to efficiently elicit double-peaked preference orderings using some kind of query operation, e.g. comparison queries, like for instance in [9] for the single-peaked case.

7 Future work and extensions

Starting from randomized mechanisms, we would like to obtain lower bounds that are functions of b and c, to see how well Mechanism M1 fares in the general setting. For deterministic mechanisms, we would like to get a result that would clear up the picture. Characterizing strategyproof, anonymous and position invariant mechanisms would be ideal, but proving a lower bound that depends on n on the ratio of such mechanisms (for the social cost) would also be quite helpful. The techniques used in our characterization for two agents and our lower bounds seem to convey promising intuition for achieving such a task.

The problem could be extended to the case of multiple peaks, instead of two peaks, while at the same time moving to more general metric spaces. Perhaps the most natural extension would be a setting where each agent is associated with a position on a metric space, a “center” and her most preferred locations lie on a sphere centered around this position. Equivalently, one could think of each agent being associated with all the points on the sphere centered around her location and her cost would be the distance between the location of the facility and the closest such point on the sphere. Crucially though, the agent can only manipulate the position of these points throught misreporting the position of the center of the sphere. This extension is interesting becauses it models precisely the same motivating example we used in the introduction, in an even more realistic setting. For example, case of the two-dimensional space corresponds to a scenario where the government is planning to build a primary school at some spot in a neighbourhood or a city block, instead of simply a street; a city block is much better modelled as a plane, instead of a real line. This extension is also in accordance with the usual questions posed in the literature of facility location, where the investigations usually start from the case of one facility and the line metric and extend to multiple facilities on general metric spaces. The extension to multiple facilities, even for the line metric is of course also meaningful for our model of double-peaked preferences.

Table 2

The results for the case when peaks are not required to be symmetric

	Non-symmetric
	Ratio	Lower
Social cost
Deterministic	$n-1$	$1+\frac{b_1+b_2}{c}$
Randomized	$n-1$	−
Maximum cost
Deterministic	$1+\frac{b_1+b_2}{c}$	$1+\frac{b_1+b_2}{c}$
Randomized	$1+\frac{b_1+b_2}{c}$	3 / 2

A different extension could be in terms of the cost functions used in the model. Although the symmetric case is arguably the best analogue of the single-peaked preference setting, it could certainly make sense to consider a more general model, where the cost functions do not have the same slope in every interval and hence the peaks are not equidistant from the location of an agent. Let $b_1$ and $b_2$ be the distances from the left and the right peaks respectively. Clearly, all our lower bounds still hold, although one could potentially prove even stronger bounds by taking advantage of the more general setting. The main observation is that Mechanism M1 is no longer truthful-in-expectation, because its truthfulness depends heavily on the peaks being equidistant. On the other hand, mechanism M2 is still strategyproof and the approximation ratio bounds extend naturally. A summary of the results for the non-symmetric setting is depicted in Table 2.

Future work could also consider a different choice for the objective function. Here, we studied the objective functions of the social cost and the maximum cost, following the original literature on the problem with single-peaked preferences [30]. Since then, several other objectives functions have been considered in the literature such as the least-squares objective, [18], the $L_p$ norm of costs[17] or the minimax envy [5]; it would make sense to consider the same or at least similar objectives for the case of double-peaked preferences as well. Finally, it would be meaningful to consider the problem under the verification framework [21, 22], especially if it turns out that strong inapproximability bounds apply, at least for the case of deterministic strategyproof mechanisms.

Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Nächster Artikel Detection and resolution of normative conflicts in multi-agent systems: a literature survey

It is not hard to see by our results that if we let an agent’s cost be zero on her peaks, then in very general settings, no determnistic strategyproof mechanism can guarantee a finite approximation ratio.

In fact, even if the optimal mechanism outputs a distribution over points that all admit the minimum social cost, the argument still works.

Here we assume for convenience that any mechanism outputs the same location in $[x_1^{P}+c,x_n^{P}-c]$ on the primary instance and instance P. This is without loss of generality because the argument for any output in $[x_1^{P}+b,x_n^{P}-b]$ is exactly the same.

Alon, N., Feldman, M., Procaccia, A. D., & Tennenholtz, M. (2010). Strategyproof approximation of the minimax on networks. Mathematics of Operations Research, 35(3), 513–526.MathSciNetCrossRefMATH

Ashlagi, I., Fischer, F., Kash, I., & Procaccia, A. D. (2010). Mix and match. In Proceedings of the 11th ACM conference on Electronic commerce (ACM-EC) (pp. 305–314). ACM.

Bartholdi, J., & Trick, M. A. (1986). Stable matching with preferences derived from a psychological model. Operations Research Letters, 5(4), 165–169.MathSciNetCrossRefMATH

Black, D. (1957). The theory of committees and elections. Dordrecht: Kluwer Academic Publishers. (reprint at 1986).MATH

Cai, Q., Filos-Ratsikas, A., Filos, A., & Tang, P. (2016). Facility location with minimax envy. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI) (pp. 137–143).

Caragiannis, I., Filos-Ratsikas, A., & Procaccia, A. D. (2011). An improved 2-agent kidney exchange mechanism. In Proceedings of the 7th Workshop of Internet and Network Economics (WINE) (pp. 37–48). Springer.

Cheng, Y., Wei, Y., & Zhang, G. (2013). Strategy-proof approximation mechanisms for an obnoxious facility game on networks. Theoretical Computer Science, 497, 154–163.MathSciNetCrossRefMATH

Cheng, Y., Yu, W., & Zhang, G. (2011). Mechanisms for obnoxious facility game on a path. In International Conference on Combinatorial Optimization and Applications (pp. 262–271). Springer.

Conitzer, V. (2007). Eliciting single-peaked preferences using comparison queries. In Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems (p. 65). ACM.

10.

Cooter, R. D. (2002). The strategic constitution. Princeton: Princeton University Press.

11.

Dokow, E., Feldman, M., Meir, R., & Nehama, I. (2012). Mechanism design on discrete lines and cycles. In Proceedings of the 13th ACM Conference on Electronic Commerce (ACM-EC) (pp. 423–440).

12.

Dughmi, S., & Gosh, A. (2010). Truthful assignment without money. In Proceedings of the 11th ACM conference on Electronic commerce (ACM-EC) (pp. 325–334).

13.

Egan, P. J. (2013). “Do something” politics and double-peaked policy preferences. Journal of Politics, 76(2), 333–349.CrossRef

14.

Escoffier, B., Gourvès, L., Thang, N. K., Pascual, F., & Spanjaard, O. (2011). Strategy-proof mechanisms for facility location games with many facilities. In The 2nd International Conference on Algorithmic Decision Theory, (pp. 67–81). Berlin, Heidelberg: Springer.

15.

Escoffier, B., Lang, J., & Öztürk, M. (2008). Single-peaked consistency and its complexity. In The 18th European Conference on Artificial Intelligence (ECAI), 8, (pp. 366–370).

16.

Feigenbaum, I., & Sethuraman, J. (2014). Strategyproof mechanisms for one-dimensional hybrid and obnoxious facility location. arXiv preprint arXiv:1412.3414.

17.

Feigenbaum, I., Sethuraman, J., & Ye, C. (2013). Approximately optimal mechanisms for strategyproof facility location: Minimizing $l_p $ norm of costs. arXiv preprint arXiv:1305.2446.

18.

Feldman, M., & Wilf, Y. (2013). Strategyproof facility location and the least squares objective. In Proceedings of the 14th ACM conference on Electronic Commerce (ACM-EC) (pp. 873–890).

19.

Filos-Ratsikas, A., & Miltersen, P. B. (2014). Truthful approximations to range voting. In International Conference on Web and Internet Economics (pp. 175–188). Springer.

20.

Fotakis, D., & Tzamos, C. (2010). Winner-imposing strategyproof mechanisms for multiple facility location games. In Proceeding of the 5th International Workshop of Internet and Network Economics (WINE) (pp. 234–245).

21.

Fotakis, D., Tzamos, C., & Zampetakis, E. (2015). Who to trust for truthfully maximizing welfare? arXiv preprint arXiv:1507.02301.

22.

Fotakis, D., & Tzamos, C. (2013). Winner-imposing strategyproof mechanisms for multiple facility location games. Theoretical Computer Science, 472, 90–103.MathSciNetCrossRefMATH

23.

Fotakis, D., & Tzamos, C. (2014). On the power of deterministic mechanisms for facility location games. ACM Transactions on Economics and Computation, 2(4), 15.CrossRefMATH

24.

Guo, M., & Conitzer, V. (2010). Strategy-proof allocation of multiple items between two agents without payments or priors. In Ninth International Joint Conference on Autonomous Agents and Multi Agent Systems (AAMAS), Vol. 10, pp. 881–888.

25.

Inada, K. I. (1964). A note on the simple majority decision rule. Econometrica: Journal of the Econometric Society, 8, 525–531.MathSciNetCrossRef

26.

Lu, P., Sun, X., Wang, Y., & Zhu, Z. A. (2010). Asymptotically optimal strategy-proof mechanisms for two-facility games. In Proceedings of the 11th ACM Conference on Electronic Commerce (ACM-EC) (pp. 315–324).

27.

Lu, P., Wang, Y., & Zhou, Y. (2009). Tighter bounds for facility games. In Proceeding of the 5th International Workshop of Internet and Network Economics (WINE), (pp. 137–148).

28.

Moulin, H. (1980). On strategy-proofness and single peakedness. Public Choice, 35(4), 437–455.CrossRef

29.

Procaccia, A. D., Wajc, D., & Zhang, H. (2016). Approximation-Variance Tradeoffs in Mechanism Design. working paper.

30.

Procaccia, A. D., & Tennenholtz, M. (2013). Approximate mechanism design without money. ACM Transactions on Economics and Computation, 1(4), 18.CrossRef

31.

Rosen, H. S. (2005). Public Finance (7th ed.). McGraw-Hill Irwin.

32.

Schummer, J., & Vohra, R. V. (2002). Strategy-proof location on a network. Journal of Economic Theory, 104(2), 405–428.MathSciNetCrossRefMATH

33.

Serafino, P., & Ventre, C. (2015). Truthful mechanisms without money for non-utilitarian heterogeneous facility location. In AAAI (pp. 1029–1035).

34.

Serafino, P., & Ventre, C. (2016). Heterogeneous facility location without money. Theoretical Computer Science, 636, 27–46.MathSciNetCrossRefMATH

35.

Sonoda, A., Todo, T., & Yokoo, M. (2016). False-name-proof locations of two facilities: Economic and algorithmic approaches. In Proceedings of the 30th AAAI Conference on Artificial Intelligence, (pp. 615–621). AAAI Press.

36.

Svensson, L.-G., & Reffgen, A. (2014). The proof of the Gibbard–Satterthwaite theorem revisited. Journal of Mathematical Economics, 55, 11–14.MathSciNetCrossRefMATH

37.

Todo, T., Iwasaki, A., & Yokoo, M. (2011). False-name-proof mechanism design without money. In The 10th International Conference on Autonomous Agents and Multiagent Systems-Volume 2, (pp. 651–658). International Foundation for Autonomous Agents and Multiagent Systems.

38.

Yang, Y., & Guo, J. (2015). How hard is control in multi-peaked elections: A parameterized study. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, (pp. 1729–1730). International Foundation for Autonomous Agents and Multiagent Systems.

39.

Zou, S., & Li, M. (2015). Facility location games with dual preference. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, (pp. 615–623). International Foundation for Autonomous Agents and Multiagent Systems.

Titel: Facility location with double-peaked preferences
verfasst von: Aris Filos-Ratsikas
Minming Li
Jie Zhang
Qiang Zhang
Publikationsdatum: 20.03.2017
Verlag: Springer US
Erschienen in: Autonomous Agents and Multi-Agent Systems / Ausgabe 6/2017
Print ISSN: 1387-2532
Elektronische ISSN: 1573-7454
DOI: https://doi.org/10.1007/s10458-017-9361-0

Springer Professional

Abstract

1 Introduction

1.1 Our results

1.2 Related work on facility location

1.3 Related work on double-peaked preferences

2 Preliminaries

3 A truthful-in-expectation mechanism

3.1 Social cost

3.2 Maximum cost

4 Deterministic mechanisms

4.1 Social cost

4.2 Maximum cost

5 Group strategyproofness

6 Conclusion and discussion

7 Future work and extensions

Weitere Artikel der Ausgabe 6/2017

On the hierarchical nature of partial preferences over lotteries

Computational aspects of strategic behaviour in elections with top-truncated ballots

Establishing norms with metanorms over interaction topologies

Automated multi-level governance compliance checking

When do agents outperform centralized algorithms?

Towards Circular Economy implementation: an agent-based simulation approach for business model changes