Coordinate median optimally aggregates agents in euclidean space
Strategyproof Aggregation in Euclidean Spaces: Rigidity and Median Optimality
Computer Science and Game Theory
Summary
When a group of people needs to agree on a single point based on their different opinions in a multi-dimensional space, finding a fair and strategic way to do this is important. The authors found that using the coordinate-wise median—choosing the middle value for each dimension—works best to minimize overall distance and prevent people from gaming the system. They prove this is true for any number of people and dimensions, under certain conditions. Their approach uses mathematical arguments about order and symmetry to show no better method exists.
What this means in practice
- •For distributed system designers: Design aggregation protocols that prevent strategic manipulation while minimizing total distance in multi-dimensional settings.
- •For multiagent system developers: Implement robust consensus mechanisms in systems where agents report multi-attribute preferences and any agent might try to influence outcomes strategically.
A theory result. No direct application yet.
Authors
Jianhao Jia
Abstract
We study deterministic strategyproof aggregation in finite-dimensional Euclidean spaces. For every odd number $n\ge3$ of agents and every finite dimension, we prove that the coordinate-wise median minimizes the worst-case approximation ratio for total Euclidean distance among all continuous, anonymous, deterministic strategyproof mechanisms. The same optimality result holds for every even $n\ge4$ when each coordinate uses a fixed choice of the lower or upper middle rank. The proof combines a rigidity theorem with a normalization that does not increase the approximation ratio: any hypothetical mechanism outperforming the median has a normalized representative that is a fixed coordinate-wise order-statistic rule in a single orthonormal frame. A reflection argument then shows that no such rule improves on the median.