Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location Mechanism
Authors: Haris Aziz
Alexander Lam
Mashbat Suzuki
Toby Walsh
Venue: NeurIPS 2022 Accept (2022)
Keywords: Facility location
Randomized Social Choice
Fairness in Collective Decision Problems
Voting

Abstract: Proportionality is an attractive fairness concept that has been applied to a range of problems including the facility location problem, a classic problem in social choice. In our work, we propose a concept called Strong Proportionality, which ensures that when there are two groups of agents at different locations, both groups incur the same total cost. We show that although Strong Proportionality is a well-motivated and basic axiom, there is no deterministic strategyproof mechanism satisfying the property. We then identify a randomized mechanism called Random Rank (which uniformly selects a number $k$ between $1$ to $n$ and locates the facility at the $k$'th highest agent location) which satisfies Strong Proportionality in expectation. Our main theorem characterizes  Random Rank as the unique mechanism that achieves universal truthfulness, universal anonymity, and Strong Proportionality in expectation among all randomized mechanisms. Finally, we show via the AverageOrRandomRank mechanism that even stronger ex-post fairness guarantees can be achieved by weakening universal truthfulness to strategyproofness in expectation. 

Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location Mechanism
Haris Aziz
Alexander Lam
Computer Science and Engineering UNSW Sydney
Computer Science and Engineering
UNSW Sydney
Sydney NSW 2052, Australia haris. azizounsw. edu. au
Sydney NSW 2052, Australia alexander 1am1 1uun sw edu. au
Mashbat Suzuki
Toby Walsh
Computer Science and Engineering
Computer Science and Engineering
UNSW Sydney
UNSW Sydney
Sydney NSW 2052, Australia mashbat suzuki @unsw. edu. au
Sydney NSW 2052, Australia t. walshuussw edu.
Abstract
Proportionality is attractive fairness concept that has been applied to range problems including the facility location problem, a classic problem in social choice. In our work, propose concept called Strong Proportionality, which ensures that when there are two groups of agents at different locations, both groups incur the same total cost. We show that although Strong Proportionality is well- motivated and basic axiom, there no deterministic strategyproof mechanism satisfying the property. We then identify a randomized mechanism called Random Rank (which uniformly selects a number k between 1 to n and locates the facility the k'th highest agent location) which satisfies Strong Proportionality in expecta- tion. Our main theorem characterizes Random Rank as the unique mechanism that achieves universal truthfulness, universal anonymity, and Strong Proportionality expectation among all randomized mechanisms. Finally, we show via the Avera- geOrRandomRant mechanism that even stronger ex ex-post fairness guarantees can be achieved by weakening universal truthfulness to strategyproofness in expectation.
Introduction
The facility location problem has been widely studied in various literatures. the classic setting, we given set of agent locations the unit interval, and tasked with finding 'ideal' location on the interval to place a facility. Each agent incurs a cost equal to its distance from the facility, and therefore wants the facility be placed as close possible to its own location. The problem applies to many real-world scenarios, such as the geographical placement of public facilities (Schummer and Vohral 2002 Miyagawa, 2001], the choice of political representative [Moulin] 1980, Feldman al. 2016]. The problem can be similarly applied to aggregate votes on what proportion budget is dedicated certain project [Freeman et al. 2021], and the ID-metric can be extended graph to model router placement on network [Hakimi] 1965].
In this paper, explore the space of facility location mechanisms that have desirable fairness and strategic properties. In particular, a mechanism should satisfy anonymity, which requires that the outcome of the mechanism should not depend the names of the agents. Secondly, seek
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

universal
universal truthfulness
universal strong proportionality
anonymity
anonymity
strategyproofness in expectation
strong proportionality in expectation
in expectation
Logical relations between fairness and efficiency concepts. An arrow from (A) to (B) denotes that (A) implies (B). The properties in green are simultaneously satisfied by some algorithms. The properties in the dotted pink shapes are impossible to simultaneously satisfy.
Figure 1:
mechanisms that are strategyproof and hence cannot be manipulated by agents misreporting their truthful private information (which in our case is the agents' location). Thirdly, we require that the mechanisms should be fair. We focus on a fairness concept called Strong Proportionality that has deep foundation in the theory of fair collective decision making. It is based the idea that when there are two groups of agents at different locations, both groups incur the same total cost. As consequence, the facility is placed such that the ratio of distances between each group and the facility is inversely proportional to the ratio of their group sizes. In other words, the facility is placed "proportionally" closer to the larger group of agents. Our primary focus on identifying mechanisms which satisfy all three properties discussed above.
In addition to the faireess axiom of Strong Proportionality, focus universal versions of and and anonymity as desirable properties. These universal versions can be viewed as more robust variants of their counterpart axioms when considering randomized mechanisms. Universal truthful mechanisms randomize over deterministic strategyproof mechanisms, and do not incentivize agent misreport even when the random outcome is known (see e.g., [Nisan and Ronen 2001) ) Similarly, universally anonymous mechanisms randomize over deterministic anonymous mechanisms, and are robust to agent changing its labelling to achieve better outcome even if they know the random outcome.
truthfulness!
In paper, focus on randomized mechanisms we show that no deterministic mechanism satisfies truthfulness along with Strong Proportionality. For this reason, we target Strong Proportion- ality in expectation and explore the space of mechanisms that satisfy universal anonymity, universal truthfulness and Strong Proportionality in expectation. Figure describes the relationships between the fairness and efficiency concepts that study.
Contributions Our paper makes several contributions the facility location literature in particular and the social choice literature in general. Firstly, we adopt the fairness axiom of Proportionality from the participatory budgeting literature and formulate the axiom of Strong Proportionality. which enforces the basic and natural requirement that when there are two groups of agents at different locations, the facility should be placed closer the larger group of agents. We show that deterministic and strategyproof mechanism can satisfy Strong Proportionality. and hence we turn randomized mechanisms. Our main contribution is the characterization of the Random Rank mechanism as the unique mechanism satisfying universal truthfulness, universal anonymity and Strong Proportionality in expectation. When universal truthfulness is weakened to strategyproofnes: in expectation, we find that there is a family of mechanisms that achieve a fairer ex- ex-post distribution of outcomes. Finally, we show that our main characterization still holds when Strong Proportionality is strengthened to Strong Proportional Fairness, a property which captures fairness guarantees for more general groups of agents with similar locations. Table summarizes the properties satisfied by the mechanisms we discuss in the paper. Statements and results lacking proofs are proven in the appendix.
We use truthfulness and strategyproofness interchangeably.

---

Table I: Summary of properties satisfied by the mechanisms we study. We show that in the space of all randomized mechanisms, only the Random Rank mechanism satisfies each property specified below. "The AverageOrRR p mechanism is strategyproof in expectation if and only if p E [0, 21.
Mechanism
Universal Truthfulness
Strafegyyroofnes expectation
Universal Anonymity
Proportionality expectation
Strong Pruportionality in expectation
Random Rank
Yes
Yes
Yes Yes
Yes
Random Diclatorship
Yes
No
Yes
Yes
Random Phantom
Yes
Yes
Yes
Yes
No
AverageOrRR
No
Yes"
Yes
Yes
Yes
Median
Yes
Yes
Yes
No
No
Uniform Phantom
Yes
Yes
Yes
Yes
No
2 Related Work
Randomized social choice functions. Randomized schemes have been proposed for a variety
of social choice contexts to circumvent impossibility results (e.g. see [Brandi] 2017 Aziz
2019]).
For instance, the famous impossibility result of the SatthardwSttteewatteee theorem Gibbard 1973
Satterthwaite/ 19755 can be overcome by using random dictatorship that chooses outcome uniformly at random, which was first studied by [iibbard [1977 1978]. The random dictatorship is similar to the 'Random Rank' mechanism we propose in main characterization result. A generalization of random dictatorship is applied to the k- facility location problem by Fotakis and Tzamos 2010)) achieving strategyproofness in expectation and a constant approximation for optimal total cost. Other recent studies on randomized mechanisms in the facility location problem have investigated the tradeoff between a mechanism's approximation ratio and its variance (Procaccia el
al. 2018), and proposed strategyproof mechanisms which minimize the maximum agent envy [Cai el
al. 2016]. Finally, we note that our results differ from the existing characterizations of randomized
facility location mechanisms by Ehlers et al. [2002) and Peters et al. [2014), as their definitions of strategyproofness revolve around stochastic dominance, whilst our main characterization uses stronger axiom of universal truthfulness. Furthermore, the mechanisms we discuss are additionally constrained to be proportionally fair and thus our characterizations are more succinct.
Facility location problems. Facility location problems have been widely studied in the fields of computer science, economies and operations research. We take a mechanism design approach, finding mechanisms which do not incentivize agents to misreport their locations. The origins of this approach can be traced to the seminal work by Moulin [1980), which provides a characterization of strategyproof mechanisms when agent preferences are single-peaked. He also provides further characterizations when the axioms of anonymity and Pareto efficiency are imposed. There have since been many extensions of facility location mechanism design that build off these results, such as the placement multiple facilities by Miyagawa [1998] 2001] and Fotakis and Tzamos [2013) as well as when agents have fractional or optional preferences Fong et al. [2018] Chen et al. 2020]. For further related work, we refer the reader to survey by Chan el al. [021] A connection between voting and facility location problems is drawn by Feldman el al. 2016). in which mechanisms minimizing social cost are formulated for the problem where there is a fixed, limited set of candidates on the real line.
Fairness in collective decision problems. Fairness constraints and measures have been formulated in a wide variety of different collective decision problems [Steinhaus] 1948 Dummett 1997| Aziz et al. 2019]. Our paper draws from the area of participatory budgeting. in which various axioms have been proposed to represent proportional fairness concerns for groups of agents with similar preferences [Azzz et al. 2019. Pierezyński et al. [2021). Specifically, the axiom of "Proportionality" we use is drawn from the work on participatory budgeting by Freeman et al. [2021], and our new axiom of "Strong Proportionality" is, as the name suggests, a stronger version of the axiom. Our paper is most closely related to the work by Aziz et al. [2021], providing a characterization of strategyproof and proportionally fair mechanisms, but in much more general randomized setting which introduces new conceptual and technical challenges as we see in later sections. Another related paper by Zhou ei al. [2022) has similar underlying motivations, exploring group fairness cost objectives and proposing strategyproof mechanisms that approximate these objectives. We note that the notions of proportional
AA randomized mechanism satisfies universal Strong Proportionality if it is distribution over deterministic mechanisms satisfying Strong Proportionality.
3

---

fairness explored in our paper differ from the fairness objective of egalitarian welfare explored widely in the facility location literature. For a comprehensive comparison between proportional and egalitarian fairness in the facility location problem, we refer the reader to the discussion by Aziz et al. [202T]
3 Preliminaries
Let .N- = [1....,,]] n be a set of agents with n 2 2, and let X := [0, 1] be the domain of locations. The unit interval can be scaled and shifted to represent any closed and bounded interval on R. As will explain, our characterization results hold even when the domain is the real line. However, we restrict to X = 10. 1 to remain consistent with the related literature [Mssóó and Moreno De Barreda
2011 Aziz et al. 2020 2021 Freeman et al. 2021] Agent i's location is denoted by 2; E X; the
profile of agent locations denoted by (I1,-... Fen E X"
deterministic mechanism is a mapping f X + from the agent location profile to a facility location. Given location profile X", agent i's cost is d(xi, (z)) := [x; (xx)
randomized mechanism probability distribution over deterministic mechanisms
common requirement in mechanism design is that the mechanism's 's output should not depend on the agents' labels. That is, the mechanism outcome is invariant under permutation of agent labels. Formally:
Definition (Anonymous), A mechanism f is anonymous if. for every location profile x E X and every bijection a N + N,
f(xa) = f(x),
where == (I) (2). ...))...........................
Fa(n)) ;...)))))))
When considering randomized mechanisms, the notion of anonymity extends as follows:
A randomized mechanism is universally anonymous if it is distribution over deterministic anonymous mechanisms. If mechanism is not universally anonymous, an agent that knows the random outcome may change its labelling to achieve a better outcome.
A randomized mechanism is anonymous in expectation the expected facility location does not change when the agents are relabelled.
Another normative property seek in paper is truthfulness, which incentivizes agents to report their locations truthfully. Definition (Strategyproof), A mechanism f is strategyproof if. for every agent E N, we have for every z and for every -_1
d(x,, f x)))) I d(x;, f(
In the context of randomized mechanisms, the following are the two main notions of strategyproolness (truthfulness):
A randomized mechanism is universally truthful if it is a distribution over deterministic strategyproof mechanisms. Under a universally truthful mechanism, an agent will not have incentive to misreport its location even if it knows the random outcome.
A randomized mechanism is truthful in expectation if no agent can improve its expected distance from the facility by misreporting its own location.
Given a location profile x, a facility location is said to be Pareto optimal if there exists no other facility location y' such that d(z,, y²) < d(I;, y) for all i, and d(æ,, v/) < d(x;, y) for at least one agent. A mechanism f said to be (Pareto) efficient if, for every location profile x, the facility location f(x) is Pareto optimal. In our setting, Pareto optimality is equivalent to requiring that f(x) E [minGen F,, max zz).
A mechanism is ex-post efficient if it only gives positive support to Pareto efficient deterministic mechanisms.
TThis definition of randomized mechanisms commonly used in the literature Dobzinski and Dughmi
2013
Assadi and Singla 2019)
Here =- denotes the location profile of all agents except

---

Deterministic Anonymous and Strategyproof Mechanisms
When agents have of anonymous, strategyproof deterministic mechanisms as the class of 'Phantom' mechanisms, which place the facility the median the n reported agent locations and 1 fixed 'phantom' locations. A similar characterization for the unit interval with symmetric single peaked preferences has been shown by Massó and Moreno De Barreda [20TT..
preferences on the real line, Moulin 1980 has characterized the set
Definition (Phantom Mechanism). Given 1 fixed real numbers 0 S yı S ... S yn-1 S 1 annd
a location profile I, a Phantom mechanism f locates the facility at
f(x)= med((1..... ,.1...,,,,,, .
Theorem (Massó and Moreno De Barreda (0111). A (deterministic) facility location mechanism is anonymous and strategyproof if and only if it a Phantom mechanism.
Setting of the phantoms 0 and 1 also provides characterization of anonymous, strategyproof and efficient mechanisms.
Theorem (Massó and Moreno De Barreda (011]) A (deterministic) location mechanism is anonymous, strategyproof and efficient if and only if it is Phantom mechanism with phantoms y1 = and fn+1
Such mechanism also be interpreted Phantom mechanism with 1 phantom locations.
4 Proportional Fairmess Axioms
In this section, we describe and motivate our axioms of proportional fairness used throughout the paper. We first state the fairness property Proportionality which was defined in the context of the facility location problem by Aziz et al. (2021).
Definition 4 (Proportionality). A mechanism f satisfies Proportionality if for any location profile {0, 1 and set S of agents the same location,
[x), 1- ViES.
Remark 1. Proportionality is equivalent to requiring that if all agents are located at the interval endpoints, the facility is placed the average of the agents' locations.
We consider strengthening of Proportionality to allow for more general location profiles
3
Definition 5 (Strong Proportionality). A mechanism J satisfies Strong Proportionality if for any location profile x {a, 3}" with 0 S a < and set S of agents at the same location.
|5| (3
d(ri, (x))
a)) V.
n1
Strong Proportionality is equivalent requiring that agents are most different locations, the facility is placed at the average of the agents' locations.
Remark 2.
Strong Proportionality captures number of basic fairness properties.
Unanimity: all agents are unanimous in their reported locations, then the facility is located at this same location.
Equitable treatment of groups: When there are at most two groups of agents at different locations, both groups incur the same total cost.
While Strong Proportionality is very basic and modest property, applying only to small subset of possible location profiles, it cannot be satisfied by a deterministic, strategyproof mechanism.
Proposition No deterministic and strategyproof mechanism satisfies Strong Proportionality.
*Strong Proportionality is applicable to settings lacking information on the endpoints of the domain, or when the domain has endpoints (i.e. the interval is unbounded).
5

---

1
9
Strong Proportionality
Figure 2: Facility location problem with agents and location profile x (0, 0, }). For this profile, Strong Proportionality requires that the facility is placed location 5 which is achieved in expectation by the Random Rank mechanism.
As result, we turn to the larger, more general space of randomized mechanisms. However, Propo- sition implies no universally truthful mechanism can guarantee an output that achieves Strong Proportionality. Consequently, we attempt to find universally truthful mechanisms that instead achieve Strong Proportionality expectation.
When considering randomized mechanisms, our proportional fairnsss axioms are adapted as follows: Definition (Proportionality in expectation). A mechanism f satisfies Proportionality in expectation for any location profile E {0, 1)" and set S of agents at the same location,
Bid(z, f()))
Vi
n1
Definition (Strong Proportionality in expectation), A mechanism I satisfies Strong Proportionality expectation if for any location profile x {a,8)* with 0 S a < < and S of agents the same location,
Eid(a;, f(x)) n-151 (B a) Vi
n
5 Characterization of Universal Truthfulness and Strong Proportionality
In this section, we present the main result of the paper: unique characterization of facility location mechanisms satisfying universal truthfulness, universal anonymity and Strong Proportionality in expectation. First, we define mechanism which satisfies the aforementioned properties.
Definition 8. The Random Rank mechanism fAR chooses a number k at uniformly random from (1...., n and outputs rank (a)) == med(O,....)
11 II....,Tn).
k-1
The Random Rank mechanism can also be interpreted as simply choosing number is at uniformly at random from {1, {1....,,I n. and outputting the kih largest agent location.
Remark 3.
As we will show, Random Rank is the only mechanism in the space of randomized mechanisms to satisfy universal truthfulness, universal anonymity and Strong Proportionality in expectation.
Theorem 3. A mechanism is universally anonymous, universally truthful and Strong Proportional in expectation if and only if it is the Random Rank mechanism.
Proof. (=) ) The Random Rank mechanism is universally anonymous and universally truthful as each realization of the mechanism, rank strategyproof and anonymous by Theorem Consider any location profile E {o,, 33" denote S. as the set of agents located at a and S3 N S, as the set of agents located at B.. For all Sa, we have E[|(E,, (allxs;fnnn [nn())) [8al (33 a) n-15a| a) since Random Rank places the facility
n with probability [Sa] and 3 with probability [8al By similar and symmetric argument, for all j E Sy, we have E(d(z,, [n]())) a-15al (88 -x). Thus Random Rank satisfies Strong Proportionality expectation along with universal anonymity and universal truthfulness.

---

(=) Let f be a mechanism satisfying universal anonymity, universal truthfulness, and Strong Proportionality expectation. By Lemma [] (which we will show later), f also satisfies ex-post efficiency as Strong Proportionality in expectation implies Proportionality in expectation. Hence f a distribution over deterministic truthful, anonymous and efficient mechanisms. Furthermore, by Theorem 2 each of the deterministic mechanisms are Phantom mechanisms with phantom locations. Consequently we see that can be written as
f()) = med(Y "M Yn-1,,
where the Yi's are random variables corresponding to the locations of the n 1 Phantoms. Denote Y(a) as the random variable corresponding to the i'th order statistic, defined by sorting the values of Y1,'.. - in increasing order. We first show that the order statistics must satisfy very restrictive set of properties.
Claim 1: Pr(Y()) = 1] i and Pr((()) = 0] = -ي for each i E ,,,-..,--- 1}.
Proof of Claim 1. Fix i (1,... ,n). Consider the following family of location profiles (a,
xa 0
< B.
n1-
Let S = -[1, , - 1). Due to Strong Proportionality, we have
O(d(z1,(xx01/) n (n i)
(3 a)
n
- (3 a).
On the other hand, we see that
Bid(a1, ((x
202000 Pr(Vo S Sa] + Sa]+
a)) Pr[V 2 $ = (3 - Pr(y 2 3)
Combining the two equations above, we see that Pr(Y() ()) 2 3] S 4. Similarly we may take S' {n- 1...... nJ. Strong Proportionality then implies
Eid(an, f( n
(B a).
However, we also see that
Bid(an, fa 1]] -3 Pr({) _ al +0 Pr(Y() 2 3
= (B - a) Pr\Y Sa.
-3
Combining the two equations above, we have Pr(Y S al < n-i distribution Y(s) must satisfy
Thus we see that the probability
Pr s <al s Pr[Y
m
for any 0 05a<
(I)
2
B < n
Letting 3 = 1, we see that Pr[Y() = 1] < and for any a < we have Pr(y()) > o 2 i by
condition 1 Taking the limit + 1 shows Pr(Y()) = 1|
By similar argument, by setting = 0 we see that Pr[Y (1) 0] < n-i and for any 3 > 0 we have
Pr(Y < B > n-i T.aiinng the limit + implies Pr(Y()) 0] n as desired.
a
By Claim 1, we know that V, (0, 1) for each i E (1,... n 1}. Thus the mechanism output is distribution over T1,""" Zn. Since is a Phantom mechanism with Y()) (0, 10. we see that for
7

---

any k E [1,.,,mh
Pr(f(z) rank rank Pr(f(z) med 0.1. ب. æ1 21. ... [nm]
Pr[y(n-H) 0, ((nn++1) =
(r|Y (n- (n-k) 0] Pr[y (n k+1) = 0]
(n k) (n k 1)
n
n
n
Here the third equality follows from the fact that for any E {1,... ,n). we have Pr(Y())
Y(+1) 1] + (r(Y() 0, ((+1)) 0] Pr|y() 0] and Pr(Y() 0, (((1)) 0 (r((()+1) 0]. The fourth equality follows by Claim 1.
Thus we see that f is equivalent to running the rank mechanism for each (1...,, nn with probability ,, Hence f is the Random Rank mechanism.
We remark that the Random Rank mechanism satisfies Strong Proportionality only in expectation, and that the guarantee does not hold for each individual deterministic mechanism in the ex-post sense. However, this is unavoidable since no deterministic mechanism satisfies strategyproofness along with Strong Proportionality by Proposition]] 1
We now introduce the auxiliary lemma which was used the proof Theorem
Lemma If a mechanism is universally anonymous, universally truthful and Proportional in expectation, then it is also ex-post efficient.
Proof. Let f be an arbitrary mechanism that satisfies universal anonymity, universal truthfulness, and Proportionality expectation. By Theorem []] we know that deterministic anonymous and strategyproof mechanisms are Phantom mechanisms. Therefore f must be a probability distribution Phantom mechanisms. Thus I can be written (xx) med(Yi.... Iii ,.n), where Yt's are random variables corresponding to the phantom locations. We also denote the order statistics (()) mYn .1) and ((++)) = max(Yi, ... .Y411).
Claim 2: Pr[Y(n41) 1] and Pr(Y() 0] = 1.
We defer the proof of this claim the appendix.
By Claim and the property of the median, we have that
f(x)
mod(Y()) .(n+)), 21, Fn) med(0, Y()) ... M(n) 1, ,n.) med(Y ... (i,) (.,)
almost surely. Thus f can be written randomized mechanism over Phantom mechanisms with n Phantoms. Since we know from Theorem 2 that Phantom mechanisms with n 1 Phantoms efficient, see that is ex-post efficient.
We find that Theorem also extends to the setting where the domain is X R. As shown in the appendix, the extension requires few modifications to the proof.
Theorem A mechanism on the domain X is universally anonymous, universally truthful and Strong Proportional in expectation if and only if it is the Random Rank mechanism.
We remark that the requirements of Theorem 3 are tight in the sense that any requirement is weakened or removed, the result fails to hold. As we show in the appendix, if Strong Proportionality expectation is weakened to Proportionality in expectation, the fairness property can be satisfied by the 'Random Phantom' mechanism, which sets phantoms = 0 and yo+1 1 and draws the remaining phantoms I.L.. from ([0, 1)). This mechanism also satisfies universal truthfulness, ex-post efficiency and universal anonymity.

---

If universal anonymity is weakened to anonymity in expectation, we have the Random Dictator mechanism, which satisfies universal truthfulness and Strong Proportionality in expectation is effectively the same as the Random Rank mechanism.
Definition 9 (Random Dictator). The Random Dictator mechanism chooses an agent uniformly at random be the dictator and runs the Dictator mechanism i.e. places the facility at the dictator's location.
Random Dictator is not universally anonymous as it is a distribution over dictatorial mechanisms which are not anonymous, but it is anonymous in expectation as each agent's reported location has an equal probability of being selected. Hence an agent that knows the realization of the random coin under Random Dictator may change its labelling achieve a better outcome this is not possible under the universally anonymous Random Rank mechanism.
If universal truthfulness is weakened to strategyproofness in expectation, there is a class of mecha- nisms that have better ex xx-post fairness guarantees, as we will discuss in the next section.
Improving Ex-post Fairness
In the previous section, we identified Random Rank as the only mechanism satisfying certain desirable properties. One possible drawback of Random Rank is that while it satisfies Strong Proportionality ex-ante, it does not have good ex-post fairness guarantees. We consider class of mechanisms called AverageOrRandon
that satisfies Strong Proportionality expectation
Mechanism). The Avereg@OrRandoRRakk- mechanism places the facility at the average agent location with probability, and places the facility at the output of the Random Rank mechanism with probability.
Definition 10 (AverageO
When p [0, 11, the class of mechanisms additionally satisfy strategyproofinss in expectation.
Theorem 5. The FarrrgeOORanddRRaakkk mechanism satisfies Strong Proportionality in expecta- tion and is strategyproof in expectation if and only if E [0, 2-
Remark This result additionally holds when the domain X TR, as the proof does not involve the interval endpoints.
To motivate this class of mechanisms, we refer to the example in Figure 2 When we run Random Rank, the facility is placed 0 with probability unfair for the group agents that do not have the facility at their location. In comparison, the AverageOrRandooRRakk
at 3 with probability 3 either solution is
mechanism halves the respective probabilities that the facility is placed 1. and gives 1/ probability of placing the facility at the average location of 1 which is fair solution for both groups of agents. To summarize, the AverageOrRandomRaiie has 50% chance of giving proportionally fair outcome in the ex-post sense, whilst retaining strategyproofness in expectation.
mechanism
7 Achieving Stronger Ex-ante Fairness
The fairness axiom of Strong Proportionality is weaker variant Strong Proportional Fairness, an axiom proposed by Aziz et al. [2021]. Strong Proportional Fairnsss is defined as follows.
Definition 11 (Strong Proportional Fairness (SPF)). A mechanism J satisfies Strong Proportional
Fairness (SPF) if for any location profile within range R and subset of agents S N within range
S
d(I;, f(x)) R
V.
n1
This axiom captures faimess concerns between cohesive groups of agents that near each other but not necessarily at the same location. The motivation behind this axiom is similar to that of proportional representation axioms in social choice which guarantee appropriate level of representation for sufficienlly large group of agents with "similar" preferences [Sánchez-Fernández et al.) 2017 Aziz
Feldman and Wilf 2013 look at similar mechanism, but their focus is welfare rather than faimess.

---

et al. 2017]. Incidentally, the Random Rank mechanism satisfies the notion of Strong Proportional Fairness in expectation leading the following characterization.
Theorem 6. mechanism is universally anonymous, universally truthful and SPF in expectation if and only if it is the Random Rank mechanism.
8 Conclusion and Future Directions
In this work, we have proposed a new axiom of proportional fairness for the facility location problem called Strong Proportionality and identified mechanisms that satisfy Strong Proportionality in expectation along with universal anonymity and either universal truthfulness or strategyproofness expectation.
Our results have many natural extensions. The problem could be extended to multiple dimensions. would also be interesting characterize mechanisms that satisfy Strong Proportionality in expectation along with definition of strategyproofnes based on stochastic dominance. Other directions for our work include computing approximation ratios for social cost for mechanisms satisfying proportional fairness properties, extending the problem to multiple facilities and discussing facilities with capacity limits.
Acknowledgements
This work was partially supported by the ARC Laureate Project F1.200100204 on "Trustworthy AI". The authors also thank Barton Lee for valuable comments.
References
S. Assadi and S. Singla. Improved truthful mechanisms for combinatorial auctions with submodular bidders. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 233-248. IEEE, 2019.
H. Aziz, M. Brill, V. Conitzer, E. Elkind, R. Freeman, and T. Walsh. Justified representation in approval-based committee voting. Social Choice and Welfare, pages 461-485, 2017.
H. Aziz, A. Bogomolnaia, and H. Moulin. Fair mixing: the case of dichotomous preferences. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 753-781, 2019.
H. Aziz, H. Chan, B. Lee, and D. Parkes. The capacity constrained facility location problem. Games and Economic Behavior, 124:478-490 -90, 2020.
H. Aziz, A. Lam, B. E. Lee, and T. Walsh. Strategyproof and proportionally fair facility location. 2021.
CoRR,
H. Aziz. A probabilistic approach to voting, allocation, matching, and coalition formation. In The Future of Economic Design, pages 45-50. Springer, 2019.
F. Brandt. Rolling the dice: Recent results in probabilistic social choice. Trends in computational social choice, pages 3-26, 2017.
Q Cai, A. Filos-Ratsikas, and P. Tang. Facility location with minimax envy. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, pages 137-143, 2016.
H. Chan, A. Patss-Rassikas, B. Li, M. Li, and C. Wang. Mechanism design for facility location problems: A survey. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), 2021.
7. Chen, K. C. K. Fong, Li, K. Wang. H. Yuan, and Y. Zhang. Facility location games with optional preference. Theoretical Computer Science, 847:185-197, 197, 2020.
"Stonn Proportional Fairness in expectation is defined similarly Strong Proportionality in expectation.
10

---

S. Dobzinski and S. Dughmi. On the power of randomization in algorithmic mechanism design. SIAM Journal on Computing, 4266)2227722044 2013.
M. Dummett. Principles of Electoral Reform. Oxford University Press, 1997.
L. Ehlers, H. Peters, and T. Storcken. Strategy-prood probabilistic decision schemes for one- dimensional single-peaked preferences. Journal of Economic Theory, 105(2)4008-334 2002.
M. Feldman and Y. Wilf. Strategyproof facility location and the least squares objective. In Proceedings of the fourteenth ACM Conference on Electronic Commerce, EC 2013, Philadelphia, PA, USA, June 16-20, 2013, pages 873-890. ACM, 2013.
M. Feldman, A. Fiat, and Golomb. voting and facility location. In Proceedings of the 17th ACM Conference on Electronic Commerce (ACM-EC), pages 269-286, 2016.
K. C. K. Fong, M. Li, Lu, T. Todo, and M. Yokoo. Facility location games with fractional preferences. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
D. Fotakis and C. Tzamos. Winner-imposing strategyproof mechanisms for multiple facility location games. In Internet and Network Economics, pages 234-245, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg.
D. Fotakis and C. Tzamos.
On the power of deterministic mechanisms for facility location games. In Automata, Languages, and Programming, volume 7965 of Lecture Notes Computer Science. Springer, Berlin, Heidelberg, 2013.
R. Freeman, D. M. Pennock, D. Peters, and J.W. Vaughan. Truthful aggregation of budget proposals. Journal of Economic T'heory, 105234,,,, 2021.
A. Gibbard. Manipulation of voting schemes: A general result. Econometrica, 41(4)5587-601, 1973.
A. Gibbard. Manipulation of schemes that mix voting with chance. Econometrica, 55(3):665-68) 1977.
A. Gibbard. Straightforwardness of game forms with lotteries as outcomes. Econometrica: Journal of the Econometric Society, pages 595-614, 1978.
S. L. Hakimi. Optimum distribution of switching centers in communication network and some related graph theoretic problems. Operations Research, 13(3):662-475, 1965.
J. Massó and I. Moreno De Barreda. On caautcyy-proffness and symmetric single-peakednne peakedness. Games and Economic Behavior, 72(2):467-484. 2011.
E. Miyagawa. Mechanisms for providing a menu of public goods. PhD dissertation, University of Rochester, 1998.
E. Miyagawa. Locating libraries street. Social Choice and Welfare, 18:527-541, 2001.
H. Moulin. On strategy strategy-proofness and single peakedness. Public Choice, 45(4):437-455, 1980.
N. Nisan and A. Ronen. Algorithmic mechanism design. Games and Economic Behavior, 35(1- 2):166-196 2001.
H. Peters, S. Roy, A. Sen, and T. Storcken. Probabilistic strategy-proof rules over single-peaked domains. Journal of Mathematical Economics, 52:123-127, 2014.
G. Pierczyński, Skowron, and D. Peters. Proportional participatory budgeting with additive utilities. Advances in Neural Information Processing Systems, 34, 2021.
A. Procaccia. D. Waje, and H. Zhang. Approximation--varaate tradeoffs in facility location games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
L. Férénnz--ermández, E. Elkind, M. Lackner, N. Fernández. J. A. Fisteus, P. Basanta Val, and Skowron. Proportional justified Artificial Intelligence (AAAI). AAAI Press, 2017.
justifffe representation. In Proceedings of the 31 AAAI Conference on

---

M. A. Satterthwaite. Strategy-proue proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory. 10:187- 217, 1975.
J. Schummer and R. V. Vohra. Strategy-proof location network. Journal of Economic Theory, 104:405 428, 2002.
H. Steinhaus. The problem of fair division. Econometrica, 16:101-104, 1948.
H. Zhou, M. Li, and H. Chan. Strategyproof mechanisms for group-fair facility location problems. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, pages 613-619, 2022.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Sections 5 and X
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Results lacking proof's in the main text are proven in the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/relcasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "TWBtqUzR0_9", "reviewer": "Reviewer_HQVm", "summary": "In this paper, the author proposes a new concept called Strong Proportionality as a new fairness measurement. The author shows that Strong Proportionality is not achievable using deterministic and strategyproof mechanisms and proposes a randomized mechanism called Random Rank which can achieve not only Strong Proportionality but also other efficiency concepts like universal truthfulness etc. ", "questions": "I have a few questions:\n\n- In the actual deployment, will the decision-maker picks and fix a deterministic mechanism (choose from the randomized mechanisms?) If that's the case, the theoretical guarantee holds only in expectation over the choice of the deterministic mechanism, which does not hold for every single mechanism. The paper could be stronger if the author could say something like \"w.h.p. over the choice of the mechanisms, the deployed mechanism also satisfies strong proportionality\" etc.\n\n- Can the authors comment on how the mechanism scales up to a higher dimensional setting? Will there be any curse of dimensionality problem?", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, the paper contributes useful concepts, and the definitions and mathematical arguments are clearly written. The impossibility results show us the limitation of deterministic mechanisms and thus the randomized mechanisms are naturally motivated. The paper gaps between the economic and machine learning literature and is a valuable contribution to the community.\n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PzYxN79gGj", "reviewer": "Reviewer_BKnC", "summary": "The paper studies mechanisms for facility location games that are both truthful and fair.  In particular, the authors consider a fairness notion called Strong Proportionality, which roughly says when there are two groups of agents where each group are located at the same location, the total costs of the two groups should be the same in expectation.  The main result is that the only mechanism that is anonymous (meaning symmetric across agents), truthful, and strongly proportional is Random  Rank, which picks an integer k uniformly at random between 1 and n and outputs the k-th largest location.", "questions": "(Also putting some detailed comments here.)\n\nLine 70, \"k-facility: the \"-\" looks like a minus sign.\n\n\"AverageOrRandomRank-p\": again the \"-\" looks like a minus sign.\n\nSec 6: I'm a bit confused by the logical flow here.  Random Rank is only fair in expectation, and the fix is another mechanism that is also only fair in expectation?  Is the idea that the new mechanism is \"more fair\" (although still not \"exactly fair\") in the ex-post sense?", "limitations": "Overall I'm satisfied (see detailed comments above for some minor suggestions).", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\nThe paper is well written and polished.  Fairness in facility location games is a meaningful problem.  The main result of the paper is clean and nice, and the proof is cute and nontrivial.  Conceptually, I mostly view the result as a negative message saying proportionality is hard to achieve in facilitty location games, which is of course a meaningful message.\n\n\nWeaknesses\n\nMy biggest concern is regarding the proportionality axiom itself.  While the axiom definitely makes sense, it's not clear to me it is the only reasonable notion of fairness in the context of facility location games.  To this end, I'd appreciate more discussion on other notions of fairness (if they exist) and why they are not as suitable for the purposes of this paper.  A less important thing is I'm curious about the possibility of a characterization for truthful-in-expectation mechanisms.  There presumably one would need some new techniques, since the characterization by Massó and Moreno De Barreda no longer applies.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CW9X2bkxUyg", "reviewer": "Reviewer_EUGM", "summary": "This paper proposes a new concept Strong Proportionality, which means in the case that there are only two groups of agents at two locations, then both groups incur the same total cost. This is a stronger version of the Proportionality property in the participatory budgeting literature. The authors show that there is no deterministic strategyproof mechanism satisfying this property, and designed an algorithm, Random Rank, that satisfies Strong Proportionality in expectation. They also show that Random Rank is the only randomized mechanism that achieves universal truthfulness, universal anonymity, and Strong Proportionality in expectation. Finally, they show that if universal truthfulness could be weakened to truthfulness in expectation, then there is a mechanism that could have a fairer ex-post fairness guarantee.\n", "questions": "Have you considered generalizing the setting to multiple groups in 1 dimension? What makes it much more difficult than the two groups case?", "limitations": "The authors mentioned that one future direction would be to extend the problem to multiple dimensions, but even in the one dimension case, it would be nice to have a more general case than only two groups of agents.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* Originality: This paper is closely related to research on facility location and fairness in collective decision making, especially the Proportionality concept in participatory budgeting. The Strong Proportionality concept is naturally motivated. The proofs are nicely built on previous results about the Phantom mechanism. Related work is properly cited.\n* Quality: The notations are well defined. The theorems / lemmas are cleanly presented and proved.\n* Clarity: This paper is well written and organized. A minor comment: Figure 1 and Table 1 are not referred to in the main paper. \n* Significance: The authors have a nice summary of randomized social choice and facility location mechanisms in Table 1, and show how Random Rank is the only algorithm that satisfies all the properties listed. This result is interesting and could inspire new research directions in this area. However, I feel the setting that there are only two groups of agents at two locations is limited. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AxCOjnX_5uT", "reviewer": "Reviewer_vt86", "summary": "This work considers the classical facility location problem with a new fairness constraint, \"strong proportionality.\" The authors show that no deterministic strategy can be both strategyproof and fair, and further leverage known characterizations of strategyproof mechanisms in this setting to identify ``Random Rank\" as the unique (randomized) mechanism that is both strategyproof and fair.", "questions": "---Again, I would like the thank the authors for the clear and respectful exposition.\n\n---To elaborate on the ``weaknesses\" above, how surprising is the main result? While I am not an expert on this literature, the strong characterization of strategyproof mechanisms seems to make the result somewhat unsurprising, at least naively. This rigidity further manifests in the limited setting of the problem to $[0,1]$ or $\\mathbb{R}$.\n    \n---One could even argue that the main takeaway of the main result is that it shows that strong proportionality is itself not a sufficiently interesting fairness notion, especially given that it seems to have been first introduced in the present paper.\n    \n---That said, I do wish to emphasize that the arguments in this work are quite nice in their own right. However, it seems to me that the results in the present paper would be a great complement to a more thorough investigation of strong proportionality or other related fairness notions, as seems to have been done for proportionality in Aziz, et al (2021).\n    \n---The definition of randomized mechanism (Footnote 3) seems slightly ambiguous; it seems like the probability distribution over deterministic algorithms should itself be a function of the input to accommodate the example in the footnote, but this isn't clear in the definition.", "limitations": "There do not appear to be obvious negative societal impacts. The authors do discuss several possible avenues for improving the current results.", "rating": 4, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: This paper succeeds in providing a complete characterization of strategyproof mechanisms that satisfy their notion of strong proportionality. The paper is quite well-written and respectful to the reader.\n\nWeaknesses: My overall impression is that the results and techniques in this work may be somewhat limited in scope; a more thorough investigation of the ramifications of strong proportionality would make for a very strong paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept