Plurality in Spatial Voting Games with constant $\beta$

Abstract

Consider a set $V$ of voters, represented by a multiset in a metric space $(X,d)$. The voters have to reach a decision -- a point in $X$. A choice $p\in X$ is called a $\beta$-plurality point for $V$, if for any other choice $q\in X$ it holds that $|\{v\in V\mid \beta \cdot d(p,v)\le d(q,v)\}|\ge \frac{|V|}{2}$. In other words, at least half of the voters ``prefer'' $p$ over $q$, when an extra factor of $\beta$ is taken in favor of $p$. For $\beta =1$, this is equivalent to Condorcet winner, which rarely exists. The concept of $\beta$-plurality was suggested by Aronov, de Berg, Gudmundsson, and Horton [TALG 2021] as a relaxation of the Condorcet criterion. Let $β^*_{(X,d)}=\sup\{β\mid \mbox{every finite multiset $V$in$X$admitsa$β$-plurality point}\}$. The parameter ${\beta }^{\ast }$ determines the amount of relaxation required in order to reach a stable decision. Aronov et al. showed that for the Euclidean plane ${\beta }_{({\mathbb{R}}^2,\Vert \cdot {\Vert }_2)}^{\ast }=\frac{\sqrt{3}}{2}$, and more generally, for $d$-dimensional Euclidean space, $\frac{1}{\sqrt{d}}\le {\beta }_{({\mathbb{R}}^d,\Vert \cdot {\Vert }_2)}^{\ast }\le \frac{\sqrt{3}}{2}$. In this paper, we show that $0.557\le {\beta }_{({\mathbb{R}}^d,\Vert \cdot {\Vert }_2)}^{\ast }$ for any dimension $d$ (notice that $\frac{1}{\sqrt{d}}<0.557$ for any $d\ge 4$). In addition, we prove that for every metric space $(X,d)$ it holds that $\sqrt{2}-1\le {\beta }_{(X,d)}^{\ast }$, and show that there exists a metric space for which ${\beta }_{(X,d)}^{\ast }\le \frac{1}{2}$.