Strategyproof Facility Location for Five Agents on a Circle using PCD
Ido Farjoun, Technion Advisor: Reshef Meir · 2025
Read Strategyproof Facility Location for Five Agents on a Circle using PCD by Ido Farjoun, Technion Advisor: Reshef Meir (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-17435.txt.
Introduction
Placing a shared facility so that no one gains by lying about where they live is a classic puzzle in game theory. Ido Farjoun and Reshef Meir study that puzzle on a circle, a setting that fits services arranged around a ring, with exactly five agents. They focus on one known truthful rule, called PCD, which picks an agent reported spot with a chance proportional to the arc of the circle ahead of it.
Farjoun and Meir shrink the space of cases step by step until standard optimisation tools can settle the worst case performance of the rule. They prove that the bound they find is tight, meaning no better guarantee is possible for that rule. They also offer a guess for how the same rule performs with any odd number of agents.
Catalog record
| CREATOR | Ido Farjoun, Technion Advisor: Reshef Meir |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-17435
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Strategyproof Facility Location for Five Agents on a Circle using PCD Ido Farjoun, Technion Advisor: Reshef Meir Abstract We consider the strategyproof facility location problem on a circle. We focus on the case of 5 agents, and find a tight bound for the PCD strategyproof mechanism, which selects the reported location of an agent in proportion to the length of the arc in front of it. We methodically ”reduce” the size of the instance space and then use standard optimization techniques to find and prove the bound is tight. Moreover we hypothesize the approximation ratio of PCD for general odd n n . 1 Introduction 1.1 Setting We consider the problem of locating a facility in a metric space. A set of n strategic agents have ideal locations for the facility x_{i} , where the cost for each agent is exactly the distance from the facility to their ideal location. Each agent prefers to be as close as possible to the facility. We are interested in placing the facility in a way that optimizes some objective function. For example minimizing the social cost - The sum of costs for all agents. A mechanism is a function that maps the reported ideal locations of all agents, to a single location for the facility. A central authority, receives the reported ideal locations of all agents, and uses a mechanism to place the facility to optimize the objective function. Since agents want to be as close as possible to the facility, there is no guarantee their reports will be truthful. Hence the central authority is interested in mechanisms that optimize a social utility function, while being strategy-proof (i.e agents cannot benefit from misreporting their preferred location). We can generalize these mechanisms to be randomized, thus mapping the agents ideal locations to a distribution over the metric space. Evidently, the mechanism that places the facility on the optimal location will not always be strategy-proof. Hence, we are interested in the cost approximation ratio of the mechanism. The facility location problem can be varied to different metric spaces (Euclidean space , circle, graphs etc.), different objective functions, ranging number of facilities, and other constraints. 1.2 Current Knowledge The most basic case of facility location is on a line, where Black 1948 showed that selecting the median agent location is both optimal and strategy proof. Moulin 1980 further extended this idea and characterized all strategy proof mechanisms on a discrete/continuous line under general single-peaked preferences. Dokow et al. 2012 characterized the class of mechanisms for discrete lines under symmetric preferences, which is richer than the general single-peaked class, since there are less ways to manipulate, and hence more strategyproof mechanisms. It is worth noting that the median mechanism can also be extended to any acyclic graph. By contrast, a circle is essentially the simplest metric space where median based mechanisms fail to work. This fact draws attention to finding the best strategyproof mechanism on a circle, which remains unknown. Schummer and Vohra 2002 showed that any deterministic (onto) strategyproof mechanism on a circle must be dictatorial, which is obviously far from optimal. Therefore, the focus has shifted to the realm of randomized strategy proof mechanisms, which remains largely unexplored. Until recently, literature doesn’t mention mechanisms that approximate the optimal social cost better than the Random Dictator mechanism, which gives an approximation ratio of 2-\frac{2}{n} for any metric space Alon et al. 2009 . Meir 2019 presented two mechanisms (PCD and q-QCD) that improve the upper bound for 3 agents on a circle, and improved the lower bound slightly by use of linear programming. Rogowski and Dziubiński 2025 improved the upper bound to 7/4 by mixing the PCD and Random Dictator mechanism for any odd n\geq 3 , and hypothesize the bound for this mechanism can be lowered to 1.5. 1.3 Contribution and Method Our contribution is lowering the upper bound for five agents on a circle by finding the approximation ratio of the Proportional Circle Distance (PCD) mechanism to be 7-4\sqrt{2}\approx 1.343 and showing that this bound is tight. This further improves the best known bound given by Random Dictator of \frac{8}{5} . Moreover we hypothesize a closed formula for the approximation ratio of PCD for any odd n (Figure 1 ) . A comparison of the known and new results can be seen in Table 1 . Mechanism n=3 n=5 odd n\geq 7 RD \frac{4}{3}\approx 1.333\vphantom{\frac{2^{2^{2}}}{2_{2_{2}}}} \frac{8}{5}=1.6 2-\frac{2}{n} ( Alon et al. 2009 ) PCD \frac{5}{4}=1.25\vphantom{\frac{2^{2^{2}}}{2_{2_{2}}}} ( Meir 2019 ) 7-4\sqrt{2}\approx 1.34 [Main result]* \geq 2-O(\frac{1}{\sqrt{n}})\vphantom{\frac{2^{2^{2}}}{2_{2_{2}}}} Meir 2019 \frac{2\big[(n^{2}-3n+4)-\sqrt{2}\,(n-1)^{3/2}\big]}{(n-3)^{2}}\vphantom{\frac{2^{2^{2}}}{2_{2_{2}}}} [Hypothesis]* PCD+RD \leq 1.75\vphantom{\frac{2^{2^{2}}}{2_{2_{2}}}} \leq 1.75 \leq 1.75\vphantom{\frac{2^{2^{2}}}{2_{2_{2}}}} ( Rogowski and Dziubiński 2025 ) \leq 1.5\vphantom{\frac{2^{2^{2}}}{2_{2_{2}}}} [Hypothesis] Best Upper Bound \frac{7}{6}\approx 1.166\vphantom{\frac{2^{2^{2}}}{2_{2_{2}}}} (QCD) Meir 2019 7-4\sqrt{2}\approx 1.34 \frac{7}{4}=1.75 Best Lower Bound 1.0456 ( Meir 2019 ) ? ? Table 1 : Known and new results for approximation of strategyproof mechanisms on a circle. New results marked with asterisk. To find the approximation ratio for PCD, we theoretically have to compute the maximum value of the ratio between the expected cost of the mechanism solution and the cost of the optimal position, for all possible instances. This of course is a very demanding task, due to the endless asymmetric instances of 5 agents on a circle, the fact that there isn’t a compact way of determining the optimal location, and the fact that this ratio isn’t a differentiable function. To overcome this, we partition our instance space, and try solving the problem regionally. By first finding bounds for cases that have 2 pairs of agents that share a location, we then attempt bounding the challenging asymmetric cases by showing the two pair cases actually give worse ratios. We thus gradually cover the instance space by using bounds we have already found, until we are left with a region where the approximation ratio for a given instance can be written explicitly, thus allowing us to use basic optimization techniques. In addition we utilize the fact that in most cases, the optimal location is on the agent facing the longest arc. To find the worst instance and observe the general PCD mechanism behavior we created an application that visualizes instances neatly: Interactive App . Figure 1 : The hypothesized approximation ratio of PCD as number of agents grows, compared to a numerical computation, and other known mechanisms. 2 Prelimineries We denote the metric space by (X,d) , where d(x,y) is the shortest distance between x and y , and we denote the ideal locations of the n strategic agents by x_{i} for 1\leq\ i\leq n . An instance will be denoted as \mathbf{x}=(x_{1},x_{2},..x_{n})\in X^{n} , and the facility location will be denoted by a\in X . The cost of placing the facility at a for agent i is exactly c_{i}(a):=d(x_{i},a) , and the social cost is given by SC(\mathbf{x},a)=\sum_{i\in N}c_{i}(a) . The mechanism will be denoted by g:X^{n}\rightarrow X . For randomized mechanisms g:X^{n}\rightarrow\Delta X , where \Delta X is the set of distributions over X . We denote the randomized outcome by h\in\Delta X and generalize the cost to c_{i}(h):=\mathbb{E}_{z\sim h}[d(x_{i},z)]. The social cost generalizes naturally due to linearity of expectation. A mechanism g is strategyproof if for any report \textbf{x}\in X^{n} , for any player i\in N