In This Apportionment Lottery, the House Always Wins

References

• Ageev AA, Sviridenko MI (2004) Pipage rounding: A new method of constructing algorithms with proven performance guarantee. J. Combin. Optim. 8(3):307–328.Crossref, Google Scholar
• Agnew RA (2008) Optimal congressional apportionment. Amer. Math. Monthly 115(4):297–303.Crossref, Google Scholar
• Akbarpour M, Nikzad A (2020) Approximate random allocation mechanisms. Rev. Econom. Stud. 87(6):2473–2510.Crossref, Google Scholar
• Aziz H, Ganguly A, Micha E (2023a) Best of both worlds fairness under entitlements. Agmon N, An B, Ricci A, Yeoh W, eds. Proc. 2023 Internat. Conf. Autonomous Agents Multiagent Systems (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 941–948.Google Scholar
• Aziz H, Moulin H, Sandomirskiy F (2020) A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation. Oper. Res. Lett. 48(5):573–578.Crossref, Google Scholar
• Aziz H, Freeman R, Shah N, Vaish R (2023b) Best of both worlds: Ex ante and ex post fairness in resource allocation. Oper. Res. 72(4):1674–1688.Link, Google Scholar
• Aziz H, Lev O, Mattei N, Rosenschein JS, Walsh T (2019) Strategyproof peer selection using randomization, partitioning, and apportionment. Artificial Intelligence 275:295–309.Crossref, Google Scholar
• Babaioff M, Ezra T, Feige U (2022) On best-of-both-worlds fair-share allocations. Hansen KA, Liu TX, Malekian A, eds. Web Internet Econom. WINE 2022, Lecture Notes in Computer Science, vol. 13778 (Springer, Cham), 237–255.Google Scholar
• Balinski M (1993) The problem with apportionment. J. Oper. Res. Soc. Japan 36(3):134–148.Google Scholar
• Balinski M, Demange G (1989a) Algorithms for proportional matrices in reals and integers. Math. Programming 45(1–3):193–210.Crossref, Google Scholar
• Balinski M, Demange G (1989b) An axiomatic approach to proportionality between matrices. Math. Oper. Res. 14(4):700–719.Link, Google Scholar
• Balinski M, Ramírez V (1999) Parametric methods of apportionment, rounding and production. Math. Social Sci. 37(2):107–122.Crossref, Google Scholar
• Balinski M, Ramírez V (2014) Parametric vs. divisor methods of apportionment. Ann. Oper. Res. 215(1):39–48.Crossref, Google Scholar
• Balinski M, Shahidi N (1998) A simple approach to the product rate variation problem via axiomatics. Oper. Res. Lett. 22(4–5):129–135.Crossref, Google Scholar
• Balinski M, Young HP (1975) The quota method of apportionment. Amer. Math. Monthly 82(7):701–730.Crossref, Google Scholar
• Balinski M, Young HP (1979) Quotatone apportionment methods. Math. Oper. Res. 4(1):31–38.Link, Google Scholar
• Balinski M, Young HP (1982) Fair Representation: Meeting the Ideal of One Man, One Vote (Yale University Press, New Haven, CT).Google Scholar
• Bansal N, Gupta A, Li J, Mestre J, Nagarajan V, Rudra A (2012) When LP is the cure for your matching woes: Improved bounds for stochastic matchings. Algorithmica 63(4):733–762.Crossref, Google Scholar
• Barbanel J (1996) Game-theoretic algorithms for fair and strongly fair cake division with entitlements. Colloquium Mathematicae 69(1):59–73.Crossref, Google Scholar
• Bautista J, Companys R, Corominas A (1996) A note on the relation between the product rate variation (PRV) problem and the apportionment problem. J. Oper. Res. Soc. 47(11):1410–1414.Crossref, Google Scholar
• Benadè G, Kazachkov AM, Procaccia AD, Psomas A, Zeng D (2023) Fair and efficient online allocations. Oper. Res. 72(4):1438–1452.Link, Google Scholar
• Birkhoff G (1946) Three observations on linear algebra. Universidad Nacional Tucumán Revista A 5:147–151.Google Scholar
• Bogomolnaia A, Moulin H (2001) A new solution to the random assignment problem. J. Econom. Theory 100(2):295–328.Crossref, Google Scholar
• Brewer KRW, Hanif M (1983) An Introduction to Sampling with Unequal Probabilities, Lecture Notes in Statistics, vol. 15 (Springer, New York).Crossref, Google Scholar
• Buchstein H, Hein M (2009) Randomizing Europe: The lottery as a decision-making procedure for policy creation in the EU. Critical Policy Stud. 3(1):29–57.Crossref, Google Scholar
• Buchstein H, Hein M, Jünger J (2013) Die,EU-Kommissionslotterie. Eine Simulationsstudie. Die Versprechen der Demokratie (Nomos, Baden-Baden), 190–227.Crossref, Google Scholar
• Budish E, Che YK, Kojima F, Milgrom P (2013) Designing random allocation mechanisms: Theory and applications. Amer. Econom. Rev. 103(2):585–623.Crossref, Google Scholar
• Burt OR, Harris CC (1963) Letter to the editor—Apportionment of the U.S. House of Representatives: A minimum range, integer solution, allocation problem. Oper. Res. 11(4):648–652.Link, Google Scholar
• Cembrano J, Correa J, Verdugo V (2022) Multidimensional political apportionment. Proc. Natl. Acad. Sci. USA 119(15):e2109305119.Crossref, Google Scholar
• Cembrano J, Correa J, Schmidt-Kraepelin U, Tsigonias-Dimitriadis A, Verdugo V (2024) New combinatorial insights for monotone apportionment. Preprint, submitted October 31, https://arxiv.org/abs/1401.0212.Google Scholar
• Chakraborty M, Schmidt-Kraepelin U, Suksompong W (2021) Picking sequences and monotonicity in weighted fair division. Artificial Intelligence 301:103578.Crossref, Google Scholar
• Cheng Y, Jiang Z, Munagala K, Wang K (2020) Group fairness in committee selection. ACM Trans. Econom. Comput. 8(4):1–18.Google Scholar
• Correa J, Gölz P, Schmidt-Kraepelin U, Tucker-Foltz J, Verdugo V (2024) Monotone randomized apportionment. Bergemann D, Kleinberg R, Saban D, eds. Proc. 25th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 71.Google Scholar
• Deville JC, Tille Y (1998) Unequal probability sampling without replacement through a splitting method. Biometrika 85(1):89–101.Crossref, Google Scholar
• El-Helaly S (2019) The Mathematics of Voting and Apportionment: An Introduction, Compact Textbooks in Mathematics (Birkhäuser, Cham).Crossref, Google Scholar
• Elliott D, Martin S, Shakesprere J, Kelly J (2021) Simulating the 2020 census: Miscounts and the fairness of outcomes. Research Report, Urban Institute, Washington, DC.Google Scholar
• Ernst LR (1994) Apportionment methods for the House of Representatives and the court challenges. Management Sci. 40(10):1207–1227.Link, Google Scholar
• Evren H, Khanna M (2024) Affirmative action’s cumulative fractional assignments. Preprint, submitted November 23, 2021, https://arxiv.org/abs/2111.11963.Google Scholar
• Feldman M, Mauras S, Narayan VV, Ponitka T (2023) Breaking the envy cycle: Best-of-both-worlds guarantees for subadditive valuations. Bergemann D, Kleinberg R, Saban D, eds. Pro. 25th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 1236–1266.Google Scholar
• Flanigan B, Gölz P, Gupta A, Hennig B, Procaccia AD (2021) Fair algorithms for selecting citizens’ assemblies. Nature 596(7873):548–552.Crossref, Google Scholar
• Gandhi R, Khuller S, Parthasarathy S, Srinivasan A (2006) Dependent rounding and its applications to approximation algorithms. J. ACM 53(3):324–360.Crossref, Google Scholar
• Goldman J, Procaccia AD (2014) Spliddit: Unleashing fair division algorithms. SIGecom Exchanges 13(2):41–46.Crossref, Google Scholar
• Grimmett G (2004) Stochastic apportionment. Amer. Math. Monthly 11(4):299–307.Crossref, Google Scholar
• Hall P (1935) On representatives of subsets. J. London Math. Soc. s1-10(1):26–30.Crossref, Google Scholar
• Hoefer M, Schmalhofer M, Varricchio G (2024) Best of both worlds: Agents with entitlements. J. Artificial Intelligence Res. 80:559–591.Google Scholar
• Hong JI, Najnudel J, Rao SM, Yen JY (2023) Random apportionment: A stochastic solution to the Balinski–Young impossibility. Methodology Comput. Appl. Probab. 25(4):91.Crossref, Google Scholar
• Huntington EV (1928) The apportionment of representatives in Congress. Trans. Amer. Math. Soc. 30(1):85–110.Crossref, Google Scholar
• Hylland A, Zeckhauser R (1979) The efficient allocation of individuals to positions. J. Political Econom. 87(2):293–314.Crossref, Google Scholar
• Janson S (2014) Asymptotic bias of some election methods. Ann. Oper. Res. 215(1):89–136.Crossref, Google Scholar
• Kingman JFC (1993) Poisson Processes (Clarendon Press, Oxford).Google Scholar
• Kubiak W (1993) Minimizing variation of production rates in just-in-time systems: A survey. Eur. J. Oper. Res. 66(3):259–271.Crossref, Google Scholar
• Kumar VA, Marathe MV, Parthasarathy S, Srinivasan A (2009) A unified approach to scheduling on unrelated parallel machines. J. ACM 56(5):1–31.Crossref, Google Scholar
• Kurokawa D, Procaccia AD, Shah N (2018) Leximin allocations in the real world. ACM Trans. Econ. Comput. 6(3–4):1–24.Crossref, Google Scholar
• Lauwers L, Van Puyenbroeck T (2006) The Hamilton apportionment method is between the Adams method and the Jefferson method. Math. Oper. Res. 31(2):390–397.Link, Google Scholar
• Maier S, Zachariassen P, Zachariasen M (2010) Divisor-based biproportional apportionment in electoral systems: A real-life benchmark study. Management Sci. 56(2):373–387.Link, Google Scholar
• Marshall AW, Olkin I, Pukelsheim F (2002) A majorization comparison of apportionment methods in proportional representation. Soc. Choice Welfare 19(4):885–900.Crossref, Google Scholar
• Mathieu C, Verdugo V (2022) Apportionment with parity constraints. Math. Programming 203:135–168.Crossref, Google Scholar
• Nisan N, Ronen A (2001) Algorithmic mechanism design. Games Econom. Behav. 35(1–2):166–196.Crossref, Google Scholar
• Organisation for Economic Co-operation and Development (2020) Innovative Citizen Participation and New Democratic Institutions: Catching the Deliberative Wave (OECD, Paris).Google Scholar
• Palomares A, Pukelsheim F, Ramírez V (2024) Note on axiomatic properties of apportionment methods for proportional representation systems. Math. Programming 203(1–2):169–185.Crossref, Google Scholar
• Panconesi A, Srinivasan A (1997) Randomized distributed edge coloring via an extension of the Chernoff–Hoeffding bounds. SIAM J. Comput. 26(2):350–368.Crossref, Google Scholar
• Pólya G (1919) Proportionalwahl und Wahrscheinlichkeitsrechnung. Z. Gesamte Staatswiss 74(3):297–322.Google Scholar
• Pukelsheim F (2017) Proportional Representation: Apportionment Methods and Their Applications, 2nd ed. (Springer, Cham, Switzerland).Crossref, Google Scholar
• Robinson EA, Ullman D (2010) A Mathematical Look at Politics (CRC Press, Boca Raton, FL).Crossref, Google Scholar
• Saha B, Srinivasan A (2018) A new approximation technique for resource-allocation problems. Random Structures Algorithms 52(4):680–715.Crossref, Google Scholar
• Sandomirskiy F, Segal-Halevi E (2022) Efficient fair division with minimal sharing. Oper. Res. 70(3):1762–1782.Link, Google Scholar
• Steiner G, Yeomans S (1993) Level schedules for mixed-model, just-in-time processes. Management Sci. 39(6):728–735.Link, Google Scholar
• Still JW (1979) A class of new methods for congressional apportionment. SIAM J. Appl. Math. 37(2):401–418.Crossref, Google Scholar
• Stone P (2011) The Luck of the Draw: The Role of Lotteries in Decision Making (Oxford University Press, Oxford).Crossref, Google Scholar
• Szpiro GG (2010) Numbers Rule: The Vexing Mathematics of Democracy, from Plato to the Present (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• von Neumann J (1953) A certain zero-sum two-person game equivalent to the optimal assignment problem. Kuhn W, Tucker AW, eds. Contributions to the Theory of Games, vol. 2 (Princeton University Press, Princeton, NJ), 5–12.Crossref, Google Scholar