A verifiably secure and proportional committee election rule
Alfonso Cevallos, Alistair Stewart
Abstract
The concept of proportional representation in approval-based committee elections has appeared in the social choice literature for over a century and is typically understood as avoiding the underrepresentation of minorities. However, we argue that the security of some distributed systems critically depends on the opposite goal of preventing the overrepresentation of any minority, a goal not previously formalized that leads us to an optimization objective known as maximin support. After providing a thorough analysis of the computational complexity of this objective, we propose a new efficient election rule that simultaneously achieves a) a constant-factor approximation guarantee for it, and b) the property of proportional justified representation (PJR) - one of the strongest forms of proportional representation. However, the most striking feature of the new rule is that one can verify in linear time that the winning committee satisfies the two aforementioned guarantees, even when the algorithm is executed by an untrusted party who only communicates the output. As a result, the rule can be adapted into a verifiable computing scheme. Moreover, its verification procedure easily admits parallel processing for further efficiency.