{"ID":2852312,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.18718","arxiv_id":"2510.18718","title":"Likelihood of the Existence of Average Justified Representation","abstract":"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 \\emph{average justified representation} (AJR) proposed by Fernandez, Elkind, Lackner, Garcia, 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\\frac{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 Erdős--Rényi model. We consider the Erdős--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\\leq p_2$) for the parameter $p$ such that: 1) when $p\u003cp_1$ or $p\u003ep_2$, an AJR committee exists with probability $1-o(1)$, 2) when $p_1\u003cp\u003cp_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$.","short_abstract":"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 \\emph{average justified representation} (AJR) proposed by Fernandez, Elkind, Lackner, Garcia, Arias-Fisteus, Basanta-Val, and Skowron (2017). AJR postulates tha...","url_abs":"https://arxiv.org/abs/2510.18718","url_pdf":"https://arxiv.org/pdf/2510.18718v1","authors":"[\"Qishen Han\",\"Biaoshuai Tao\",\"Lirong Xia\",\"Chengkai Zhang\",\"Houyu Zhou\"]","published":"2025-10-21T15:19:53Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[]","has_code":false}