The distortion of distributed metric social choice (Q5918690)

\noindent The authors consider a distributed social choice setting with a set \(N\) of agents and a set \(A\) of alternatives, all of whom are located in a metric space, containing points representing the agents and the alternatives. \(\delta\) defines a distance \(\delta(i, j)\) between any \(i, j \in N \cup A\), such that \(\delta(i, j) \leq \delta(i, x) + \delta(x, j)\) for every \(i, j, x \in N \cup A\). The agents are supposed to be partitioned into a given set \(D\) of \(k\) districts of possibly different sizes. By definition, a distributed mechanism \(M\) selects an alternative based on the preferences of the agents in two steps: first, each district selects a representative alternative using some local aggregation rule and next the mechanism uses only information about the representatives to select the final winning alternative. The goal is to choose the alternative that optimizes some aggregate objective that is a function of the distances between agents and alternatives. In the main part of their paper, given a tuple \(I = (N; A, D; \delta)\), the authors consider the following four cost minimization objectives, which can be defined as compositions of objectives applied over and within the districts: \(\bullet\) The average of the average agent-distance in each district, denoted by AVG \(\circ\) AVG. That is, the average of average cost of an alternative \(j\) is defined by (AVG \(\circ\) AVG)\((j | I)\) = \(\frac{1}{k}\sum_{d \in D} (\frac{1}{n_d} \sum_{i \in N_d} \delta(i, j))\). Here \(N_d\) is the set of agents that belong to district \(d \in D\) and \(n_d\) is the size of \(d\). \(\bullet\) Similarly, the max of max cost of an alternative \(j \in A\) is defined by (MAX \(\circ\) MAX)\((j | I)\) = max\(_{d \in D}\) (max\(_{i \in N_d} \delta(i, j)\)) = max\(_{i \in N} \delta(i, j)\). \(\bullet\) The average of max cost of an alternative \(j \in A\) is defined by (AVG \(\circ\) MAX)\((j | I) = \frac{1}{k} \sum_{d \in D}\max_{i \in N_d} \delta(i, j)\). AVG \(\circ\) MAX guarantees that the average district cost is small, where the cost of a district is now defined as the egalitarian (maximum) cost of any of its members. \(\bullet\) The max of average cost of an alternative \(j \in A\) is defined by (MAX \(\circ\) AVG)\((j | I)\) = max\(_{d \in D}\) ( \(\frac{1}{n_d} \sum_{i \in N_d} \delta(i, j)\)). MAX \(\circ\) AVG can be thought of as a fairness-inspired objective guaranteeing that no district has a very large cost, where the cost of a district is the average cost of its members. The performance of a distributed mechanism \(M\) is measured by its distortion, defined as the worst-case ratio (over all instances of the problem) between the objective value of the alternative chosen by \(M\) and the minmum possible objective value achieved over all alternatives. Given \(F, G \in \{\)AVG, MAX\(\}\), the (F \(\circ\) G)-distortion of a distributed mechanism \(M\) is defined by dist\(_{F \circ G}(M)\) = sup\(_{I = (N, A, D, \delta)} \frac{(F \circ G) (M(I) | I)}{min_{j \in A} (F \circ G)(j | I)}\), where \(M(I)\) is the alternative chosen by \(M\) when given as input an instance \(I = (N, A, D, \delta)\). The distortion of any mechanism \(M\) is at least 1. The authors distinguish between cardinal mechanisms and ordinal mechanisms. A cardinal mechanism is given access to the distances between agents and alternatives, while an ordinal mechanism is given as input strict linear orderings that are induced by the distances, where an agent \(i\) ranks alternative \(x\) higher than alternative \(y\) in case \(\delta (i,x) \leq \delta (i, y)\). The following table gives an overview of the authors' distortion bounds for the various settings in this paper. Each entry consists of an interval showing a lower bound on the distortion of all deterministic distributed mechanisms for the corresponding setting and an upper bound that is achieved by some mechanism; when a single number is presented, the bound is tight. \begin{center} \begin{tabular}{l|ll|ll} & General Metric & & Line metric & \\ \cline{2-3} \cline{4-5} & Cardinal & Ordinal \ & \ Cardinal & Ordinal \\ \hline AVG \(\circ\) AVG & 3 & [7, 11] & 3 & 7 \\ AVG \(\circ\) MAX & 3 & [\(2 + \sqrt{5}\), 11] & 3 & \(2 + \sqrt{5}\), 5] \\ MAX \(\circ\) MAX & [\(1 + \sqrt{2}\), 3] & [3, 5] & \(1 + \sqrt{2}\) & 3 \\ MAX \(\circ\) AVG & [\(1 + \sqrt{2}\), 3] & [\(2 + \sqrt{5}\), 5] & \(1 + \sqrt{2}\) & [\(2 + \sqrt{5}\), 5] \\ \end{tabular} \end{center}