New Combinatorial Insights for Monotone Apportionment

References

• [1] Ahuja RK, Magnanti TL, Orlin JB (1988) Network Flows (MIT, Cambridge, MA).Crossref, Google Scholar
• [2] 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
• [3] Balinski M, Demange G (1989a) Algorithms for proportional matrices in reals and integers. Math. Programming 45(1–3):193–210.Crossref, Google Scholar
• [4] Balinski M, Demange G (1989b) An axiomatic approach to proportionality between matrices. Math. Oper. Res. 14(4):700–719.Link, Google Scholar
• [5] Balinski M, Young HP (1974) A new method for congressional apportionment. Proc. Natl. Acad. Sci. USA 71(11):4602–4606.Crossref, Google Scholar
• [6] Balinski M, Young HP (1975) The quota method of apportionment. Amer. Math. Monthly 82(7):701–730.Crossref, Google Scholar
• [7] Balinski M, Young HP (1979) Quotatone apportionment methods. Math. Oper. Res. 4(1):31–38.Link, Google Scholar
• [8] Balinski M, Young HP (2010) Fair Representation: Meeting the Ideal of One Man, One Vote (Brookings Institution Press, Washington, DC).Google Scholar
• [9] 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
• [10] Cembrano J, Correa J, Verdugo V (2022) Multidimensional political apportionment. Proc. Natl. Acad. Sci. USA 119(15):e2109305119.Crossref, Google Scholar
• [11] Cembrano J, Correa J, Díaz G, Verdugo V (2025) Proportionality in multiple dimensions to design electoral systems. Soc. Choice Welfare, ePub ahead of print August 29, https://doi.org/10.1007/s00355-025-01623-9.Crossref, Google Scholar
• [12] Chan TM (1999) Remarks on k-level algorithms in the plane. Technical report MPI-I-90-207, Max-Planck-Institut für Informatik, Saarbrücken, Germany.Google Scholar
• [13] Correa J, Gölz P, Schmidt-Kraepelin U, Tucker-Foltz J, Verdugo V (2024) Monotone randomized apportionment. Proc. 25th ACM Conf. Econom. Comput. (ACM, New York), 71.Google Scholar
• [14] Dey TK (1998) Improved bounds for planar k-sets and related problems. Discrete Comput. Geometry 19:373–382.Crossref, Google Scholar
• [15] Edelsbrunner H, Welzl E (1986) Constructing belts in two-dimensional arrangements with applications. SIAM J. Comput. 15(1):271–284.Crossref, Google Scholar
• [16] Gaffke N, Pukelsheim F (2008a) Divisor methods for proportional representation systems: An optimization approach to vector and matrix apportionment problems. Math. Soc. Sci. 56(2):166–184.Crossref, Google Scholar
• [17] Gaffke N, Pukelsheim F (2008b) Vector and matrix apportionment problems and separable convex integer optimization. Math. Methods Oper. Res. 67(1):133–159.Crossref, Google Scholar
• [18] 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
• [19] Gölz P, Peters D, Procaccia AD (2022) In this apportionment lottery, the house always wins. Proc. 23rd ACM Conf. Econom. Comput. (ACM, New York), 562.Google Scholar
• [20] Grimmett G (2004) Stochastic apportionment. Amer. Math. Monthly 111(4):299–307.Crossref, Google Scholar
• [21] Hoeffding W (1994) Probability inequalities for sums of bounded random variables. The Collected Works of Wassily Hoeffding (Springer, New York), 409–426.Crossref, Google Scholar
• [22] Hong JI, Najnudel J, Rao SM, Yen JY (2023) Random apportionment: A stochastic solution to the Balinski-Young impossibility. Methodol. Comput. Appl. Probab. 25(4):1–11.Crossref, Google Scholar
• [23] Józefowska J, Józefowski Ł, Kubiak W (2006) Characterization of just in time sequencing via apportionment. Stochastic Processes, Optimization, and Control Theory: Applications in Financial Engineering, Queueing Networks, and Manufacturing Systems: A Volume in Honor of Suresh Sethi, 175–200.Crossref, Google Scholar
• [24] Li X (2022) Webster sequences, apportionment problems, and just-in-time sequencing. Discrete Appl. Math. (1979) 306:52–69.Crossref, Google Scholar
• [25] 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
• [26] Mathieu C, Verdugo V (2022) Apportionment with parity constraints. Math. Programming 203(1):135–168.Google Scholar
• [27] Matousek J (2013) Lectures on Discrete Geometry, vol. 212 (Springer Science & Business Media, New York).Google Scholar
• [28] 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
• [29] Pukelsheim F (2017) Proportional Representation (Springer International Publishing, New York).Crossref, Google Scholar
• [30] Pukelsheim F, Ricca F, Simeone B, Scozzari A, Serafini P (2011) Network flow methods for electoral systems. Networks 59(1):73–88.Crossref, Google Scholar
• [31] Rote G, Zachariasen M (2007) Matrix scaling by network flow. Proc. 18th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 848–854.Google Scholar
• [32] Serafini P, Simeone B (2011) Parametric maximum flow methods for minimax approximation of target quotas in biproportional apportionment. Networks 59(2):191–208.Crossref, Google Scholar
• [33] Shechter SM (2024) Congressional apportionment: A multiobjective optimization approach. Management Sci. 71(2):1464–1487.Link, Google Scholar
• [34] Still JW (1979) A class of new methods for congressional apportionment. SIAM J. Appl. Math. 37(2):401–418.Crossref, Google Scholar
• [35] Tamaki H, Tokuyama T (2003) A characterization of planar graphs by pseudo-line arrangements. Algorithmica 35:269–285.Crossref, Google Scholar
• [36] Tóth G (2000) Point sets with many k-sets. Proc. 16th Annual ACM Sympos. Computat. Geometry (ACM, New York), 37–42.Google Scholar