close
Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2024;203(1-2):47-76.
doi: 10.1007/s10107-023-01926-8. Epub 2023 Mar 6.

Phragmén's voting methods and justified representation

Markus Brill  1   2 , Rupert Freeman  3 , Svante Janson  4 , Martin Lackner  5
Affiliations

Phragmén's voting methods and justified representation

Markus Brill et al. Math Program. 2024.

Abstract

In the late 19th century, Swedish mathematician Edvard Phragmén proposed a load-balancing approach for selecting committees based on approval ballots. We consider three committee voting rules resulting from this approach: two optimization variants-one minimizing the maximum load and one minimizing the variance of loads-and a sequential variant. We study Phragmén 's methods from an axiomatic point of view, focusing on properties capturing proportional representation. We show that the sequential variant satisfies proportional justified representation, which is a rare property for committee monotonic methods. Moreover, we show that the optimization variants satisfy perfect representation. We also analyze the computational complexity of Phragmén 's methods and provide mixed-integer programming based algorithms for computing them.

Keywords: 91B14.

PubMed Disclaimer

Conflict of interest statement

Conflict of InterestAll authors declare that they have no conflicts of interest.

Figures

Fig. 1
Fig. 1
Edvard Phragmén
Fig. 2
Fig. 2
Illustration of Example 4.3. The diagram on the left illustrates a load distribution minimizing the maximum voter load maxi∈Nx¯i, and the diagram on the right illustrates the unique load distribution minimizing ∑i∈Nx¯i2
Fig. 3
Fig. 3
Illustration of Example 4.6. The diagram on the left (respectively, right) illustrates the load distributions obtained by seq-Phragmén with ties broken in favor of candidate c (respectively, d)
See this image and copyright information in PMC

References

    1. Aziz H, Lee BE. The expanding approvals rule: improving proportional representation and monotonicity. Soc. Choice Welfare. 2020;54:1–45. doi: 10.1007/s00355-019-01208-3. - DOI
    1. Aziz, H., Lee, B.E.: Proportionally representative participatory budgeting with ordinal preferences. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pp. 5110–5118. AAAI Press (2021)
    1. Aziz, H., Shah, N.: Participatory budgeting: models and approaches. In: Rudas T., Péli, G., (eds) Pathways Between Social Science and Computational Social Science. Springer, Berlin, pp. 215–236 (2021)
    1. Aziz, H., Gaspers, S., Gudmundsson, J., Mackenzie, S., Mattei, N., Walsh, T.: Computational aspects of multi-winner approval voting. In: Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 107–115. IFAAMAS (2015)
    1. Aziz H, Brill M, Conitzer V, Elkind E, Freeman R, Walsh T. Justified representation in approval-based committee voting. Soc. Choice Welfare. 2017;48(2):461–485. doi: 10.1007/s00355-016-1019-3. - DOI

LinkOut - more resources