The Degree of (Extended) Justified Representation and Its Optimization

Biaoshuai Tao, Chengkai Zhang, Houyu Zhou · 2024

Read The Degree of (Extended) Justified Representation and Its Optimization by Biaoshuai Tao, Chengkai Zhang, Houyu Zhou (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-19933.txt.

Introduction

Biaoshuai Tao and co-authors ask, in a 2024 paper, how well a voting committee can represent not just one member of each like-minded group, but many. In multiwinner approval voting, the classic fairness rules demand that every cohesive group see at least one of its members represented. The authors define a stronger yardstick: the degree of representation, the smallest number of represented voters across all such groups, and pose the search for a committee that maximizes it.

The news is mixed. Simple committees found by the classic algorithms already guarantee a modest fraction of the best degree. But doing much better is provably hard: even rough approximations are NP-hard, and the problem stays hard when the committee size is the parameter. Easier special cases, where cohesion rests on few shared candidates, close the paper. The work maps where fairer committees can and cannot be computed.

Catalog record

CREATORBiaoshuai Tao, Chengkai Zhang, Houyu Zhou
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE69 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-19933

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Degree of (Extended) Justified Representation and Its Optimization Biaoshuai Tao, Chengkai Zhang, Houyu Zhou Abstract Justified Representation (JR)/Extended Justified Representation (EJR) is a desirable axiom in multiwinner approval voting. In contrast to that (E)JR only requires at least one voter to be represented in every cohesive group, we study its optimization version that maximizes the number of represented voters in each group. Given an instance, we say a winning committee provides a JR degree (EJR degree, resp.) of c c if at least c c voters in each ℓ \ell -cohesive group ( 1 1 -cohesive group, resp.) have approved ℓ \ell ( 1 1 , resp.) winning candidates. Hence, every (E)JR committee provides the (E)JR degree of at least 1 1 . Besides proposing this new property, we propose the optimization problem of finding a winning committee that achieves the maximum possible (E)JR degree, called MDJR and MDEJR , corresponding to JR and EJR respectively. We study the computational complexity and approximability of MDJR of MDEJR . An (E)JR committee, which can be found in polynomial time, straightforwardly gives a ( k / n ) (k/n) -approximation. We also show that the original algorithms for finding a JR and an EJR winner committee are also 1 / k 1/k and 1 / ( k + 1 ) 1/(k+1) approximation algorithms for MDJR and MDEJR respectively. On the other hand, we show that it is NP-hard to approximate MDJR and MDEJR to within a factor of ( k / n ) 1 − ϵ \left(k/n\right)^{1-\epsilon} and to within a factor of ( 1 / k ) 1 − ε (1/k)^{1-\varepsilon} , for any ϵ > 0 \epsilon>0 , which complements the positive results. Next, we study the fixed-parameter-tractability of this problem. We show that both problems are W[2]-hard if k k , the size of the winning committee, is specified as the parameter. However, when c max c_{\text{max}} , the maximum value of c c such that a committee that provides an (E)JR degree of c c exists, is additionally given as a parameter, we show that both MDJR and MDEJR are fixed-parameter-tractable. 1 Introduction An approval-based committee voting rule (ABC rule) plays a crucial role in collective decision-making by determining a committee from a set of m candidates C=\{c_{1},\dots,c_{m}\} , a set of n voters N=\{1,\dots,n\} who each approve a subset A_{i} of C , and an integer k representing the desired committee size. Let the list \mathbf{A}=(A_{1},\dots,A_{n}) of approval ballots be the ballot profile. Formally, ABC rules take a tuple (N,C,\mathbf{A},k) as input, where k is a positive integer that satisfies k\leq|C| , and return one or more size- k subsets W\subseteq C , which are called the winning committees. In many concrete voting systems a tiebreaking method is included so that a resolute outcome is guaranteed. In some cases, N and C are omitted from the notation when they are clear from the context. ABC rules are widely applied in various contexts, including the election of representative bodies (such as supervisory boards and trade unions), identifying responses to database queries [ 12 , 34 , 19 ] , selecting validators in consensus protocols like blockchain [ 10 ] , making collective recommendations for groups [ 24 , 25 ] , and facilitating discussions on proposals within liquid democracy [ 5 ] . Additionally, as committee elections fall under the domain of participatory budgeting (PB) [ 9 , 18 ] , a strong grasp of ABC rules is indispensable for designing effective PB methods. The applicability of various ABC rules often depends on the particular context, yet an important requirement one often imposes on an ABC rule is that it can accurately reflect the voters’ preferences, e.g., every large group of voters should justify a seat in the committee. In recent years, a desirable axiom has been proposed and developed, Justified Representation (JR), which requires every group of at least n/k voters that have at least one common candidate should be represented. Given a profile \mathbf{A} of n approval preferences, a subgroup of voters, denoted by N^{\prime}\subseteq N is called an \ell -cohesive group for some \ell\in\mathbb{N} , if |N^{\prime}|\geq\ell\cdot\frac{n}{k} and |\bigcap_{i\in N^{\prime}}A_{i}|\geq\ell . If \ell=1 , we say it is a cohesive group for short. Definition 1 (Justified representation (JR)) . [ 2 ] Given a ballot profile \mathbf{A}=(A_{1},\dots,A_{n}) over a candidate set C and a committee size k , we say that a set of candidates W of size |W|=k satisfies JR for (\mathbf{A},k) if, for every cohesive group (defined right above), there is at least one voter which approves at least one candidate in W . We say that an ABC rule satisfies JR if for each profile \mathbf{A} and committee size k , each winning committee provide JR. Many well-known ABC rules have been shown to satisfy JR, from a simple greedy approval voting rule to a more complex proportional approval voting (PAV) rule. Hence, some stronger JR axioms are proposed to distinguish the existing approval voting rules, such as Extended Justified Representation (EJR). EJR requires that in every \ell -cohesive group, at least one member is represented. Hence, EJR implies JR. Definition 2 (Extended Justified Representation) . [ 2 ] Given a ballot profile \mathbf{A}=(A_{1},\dots,A_{n}) over a candidate set C and a committee size k , we say that a set of candidates W of size |W|=k satisfies EJR for (\mathbf{A},k) if, for every \ell -cohesive group with every \ell\in[k] , there is at least one voter which approves at least \ell candidates in W . We say that an ABC rule satisfies EJR if for each profile \mathbf{A} and committee size k , each winning committee provide EJR. While there are a wealth of concepts associated with JR, there are instances where comparing the performance of different winning committees becomes impossible. To illustrate this situation, consider a brief example. Example 1 . Let k=1 , N=\{1,2,3,4\} , C=\{c_{1},c_{2},c_{3},c_{4}\} , A_{1}=\{c_{1}\} , and A_{i}=A_{i-1}\cup\{c_{i}\} for every i=2,3,4 . We are interested in four different committees W_{i}=\{c_{i}\} for every i\in[4] . Since Example 1 is a single winner voting instance, we have k=\ell=1 . Clearly, N is the only cohesive group in this example, and all four committees in Example 1 satisfy all the above JR axioms: besides the JR and EJR axioms mentioned earlier, one can verify that those committees also satisfy some other JR axioms such as FJR [ 32 ] , PJR+, and EJR+ [ 7 ] . However, W_{i-1} is intuitively better than W_{i} since it satisfies more voters. To distinguish the performance of these committees, besides proposing new JR variants, another approach to addressing this scenario involves leveraging quantitative techniques to model a hierarchy of JR, which has a similar spirit to the work of using quantitative techniques to model proportionality. Definition 3 (Proportionality degree) . [ 33 ] Fix a function f:\mathbb{N}\rightarrow\mathbb{R} . An ABC rule has a proportionality degree of f if for each instance (A,k) , each winning committee W , and each \ell -cohesive group V , the average number of winners that voters from V approve is at least f(\ell) , i.e., \frac{1}{|V|}\sum_{i\in V}|A_{i}\cap W|\geq f(\ell). Since k=1 in Example 1 , it

Read the complete text