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\).