Likelihood of the Existence of Average Justified Representation

We study the approval-based multi-winner election problem where $n$ voters jointly decide a committee of $k$ winners from $m$ candidates. We focus on the axiom average justified representation (AJR) proposed by Fernández, Elkind, Lackner, García, Arias-Fisteus, Basanta-Val, and Skowron (2017). AJR postulates that every group of voters with a common preference should be sufficiently represented in that their average satisfaction should be no less than their Hare quota. Formally, for every group of $\lceil \ell \cdot \tfrac{n}{k} \rceil$ voters with $\ell$ common approved candidates, the average number of approved winners for this group should be at least $\ell$. It is well-known that a winning committee satisfying AJR is not guaranteed to exist for all multi-winner election instances. In this paper, we study the likelihood of the existence of AJR under the Erdos–Rényi model. We consider the Erdos–Rényi model parameterized by $p \in [0,1]$ that samples multi-winner election instances from the distribution where each voter approves each candidate with probability $p$ (and the events that voters approve candidates are independent), and we provide a clean and complete characterization of the existence of AJR committees in the case where $m$ is a constant and $n$ tends to infinity. We show that there are two phase transition points $p_1$ and $p_2$ (with $p_1 \le p_2$) for the parameter $p$ such that: 1) when $p \lt p_1$ or $p \gt p_2$, an AJR committee exists with probability $1 - o(1)$, 2) when $p_1 \lt p \lt p_2$, an AJR committee exists with probability $o(1)$, and 3) when $p = p_1$ or $p = p_2$, the probability that an AJR committee exists is bounded away from both $0$ and $1$.