# A verifiably secure and proportional committee election rule

arXiv: https://arxiv.org/abs/2004.12990 · HTML: https://mlsanity.com/paper/2004.12990/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Apr 2020.

## Built on by (most cited first, 6 of 6)

- [Strengthening Proportionality in Temporal Voting](https://mlsanity.com/paper/2505.22513/) (2025)
- [Method of Equal Shares with Bounded Overspending](https://mlsanity.com/paper/2409.15005/) (2024)
- [Core-Stable Committees under Restricted Domains](https://mlsanity.com/paper/2108.01987/) (2021)
- [Large Language Models for Designing Participatory Budgeting Rules](https://mlsanity.com/paper/2602.09349/) (2026)
- [Computing Thiele Rules on Interval Elections and their Generalizations](https://mlsanity.com/paper/2605.03067/) (2026)
- [From Validator Selection to Portfolio Collection Optimization in Proof-of-Stake Blockchains](https://mlsanity.com/paper/2606.08282/) (2026)

## Abstract (arXiv)

The property 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 is directly linked to the opposite goal of avoiding 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. Our work is motivated by an application on blockchain networks that implement Nominated Proof-of-Stake, where the community elects a committee of validators to participate in the consensus protocol, and where preventing overrepresentation protects the network against attacks by an adversarial minority. Our election rule enables a validator selection protocol with formal guarantees on security and proportionality, and its adaptation as a verifiable computing scheme with a parallelized verification proves to be key for its successful implementation given the computationally limited nature of the blockchain architecture.