Maximum Flow is Fair: A Network Flow Approach to Committee Voting

Mashbat Suzuki and Jeremy Vollen

Papers from arXiv.org

Abstract: In the committee voting setting, a subset of $k$ alternatives is selected based on the preferences of voters. In this paper, our goal is to efficiently compute $\textit{ex-ante}$ fair probability distributions over committees. We introduce a new axiom called $\textit{group resource proportionality}$, which strengthens other fairness notions in the literature. We characterize our fairness axiom by a correspondence with max flows on a network formulation of committee voting. Using the connection to flow networks revealed by this characterization, we introduce two voting rules which achieve fairness in conjunction with other desiderata. The first rule - the $\textit{redistributive utilitarian rule}$ - satisfies ex-ante efficiency in addition to our fairness axiom. The second rule - Generalized CUT - reduces instances of our problem to instances of the minimum-cost maximum flow problem. We show that Generalized CUT maximizes social welfare subject to our fairness axiom and additionally satisfies an incentive compatibility property known as $\textit{excludable strategyproofness}$. Lastly, we show our fairness property can be obtained in tandem with strong $\textit{ex-post}$ fairness properties - an approach known as $\textit{best-of-both-worlds}$ fairness. We strengthen existing best-or-both-worlds fairness results in committee voting and resolve an open question posed by Aziz et al. [2023].

Date: 2024-06, Revised 2024-12
New Economics Papers: this item is included in nep-cdm and nep-des
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/2406.14907 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2406.14907

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().