{{Short description|Mathematical optimization of resource allocation}} '''Optimal apportionment''' is an approach to apportionment that is based on mathematical optimization.

In a problem of apportionment, there is a ''resource'' to allocate, denoted by <math>h</math>. For example, it can be an integer representing the number of seats in a ''h''ouse of representatives. The resource should be allocated between some <math>n</math> ''agents''. For example, these can be federal states or political parties. The agents have different ''entitlements'', denoted by a vector of fractions <math>t_1,\ldots,t_n</math> with a sum of 1. For example, ''t<sub>i</sub>'' can be the fraction of votes won by party ''i''. The goal is to find an ''allocation'' - a vector <math>a_1,\ldots,a_n</math> with <math>\sum_{i=1}^n a_i = h</math>.

The ideal share for agent ''i'' is his/her ''quota'', defined as <math>q_i := t_i\cdot h</math>. If it is possible to give each agent his/her quota, then the allocation is maximally fair. However, exact fairness is usually unattainable, since the quotas are not integers and the allocations must be integers. There are various approaches to cope with this difficulty (see mathematics of apportionment). The optimization-based approach aims to attain, for eacn instance, an allocation that is "as fair as possible" for this instance. An allocation is "fair" if <math>a_i = q_i</math> for all agents ''i'', that is, each agent's allocation is exactly proportional to his/her entitlement. in this case, we say that the "unfairness" of the allocation is 0. If this equality must be violated, one can define a measure of "total unfairness", and try to minimize it.

== Minimizing the sum of unfairness levels == The most natural measure is the ''sum'' of unfairness levels for individual agents, as in the utilitarian rule:<ref name=":0"/>{{Rp|102–104}}

* One can minimize the sum of differences <math>\sum_{i=1}^n |a_i - q_i|</math>, or the sum of squares <math>\sum_{i=1}^n (a_i - q_i)^2</math>, which weight every state (or party) equally. Both minimization problems are solved by Hamilton's method. * One can weight the elements in the sum by the population, or equivalently by the quota, and try to minimize the chi-squared statistic <math>\sum_{i=1}^n q_i (a_i/q_i - 1)^2</math>. This leads to Webster's method. * One can weight the elements in the sum by the allocations, and try to minimize <math>\sum_{i=1}^n a_i (q_i/a_i - 1)^2</math>. This leads to Hill's method.

== Minimizing the largest unfairneses == One can minimize the ''largest'' unfairness, as in the egalitarian rule:

* One can minimize <math>\max_{i=1}^n |q_i / a_i - 1|</math>, and proceed to minimize the next-largest unfairness etc., using the leximin order. This yields a method called the ''leximin apportionment method''. It was first developed by Biro, Koczy and Sziklai, who presented an efficient algorithm to compute it.<ref name=venice/> Its main goal is to satisfy the requirement of the Venice Commission that the maximum departure from equal distribution of items among agents should be as small as possible. Its disadvantage is that it violates the quota rule and all monotonicity criteria.<ref name=laszlo/> * Burt and Harris (1963) suggested to minimize <math>\max_{i,j=1}^n |q_i / a_i - q_j/a_j|</math>.<ref>{{cite journal | last1 = Burt | first1 = Oscar R. | last2 = Harris | first2 = Curtis C. | date = August 1963 | department = Letters to the editor | doi = 10.1287/opre.11.4.648 | issue = 4 | journal = Operations Research | pages = 648–652 | publisher = Institute for Operations Research and the Management Sciences (INFORMS) | title = Apportionment of the U.S. House of Representatives: A Minimum Range, Integer Solution, Allocation Problem | volume = 11}}</ref> * Minimizing <math>\max_{i=1}^n q_i/a_i</math> leads to Adams's method. * Minimizing <math>\max_{i=1}^n a_i/q_i</math> leads to Jefferson's method. * It is also possible to maximize <math>\min_{i=1}^n (a_i - q_i)</math>, or equivalently, minimize <math>\max_{i=1}^n (q_i - a_i)</math>. This method satisfies both quotas. * The minimax method can be generalized to any chosen priority ordering on the fairness criteria.<ref name=gambarelli/>

== References == {{Reflist|refs= <ref name=":0">{{cite book|last1=Balinski|first1=Michel L.|url=https://archive.org/details/fairrepresentati00bali|title=Fair Representation: Meeting the Ideal of One Man, One Vote|last2=Young|first2=H. Peyton|publisher=Yale University Press|year=1982|isbn=0-300-02724-9|location=New Haven|url-access=registration}}</ref>

<ref name=venice>{{Cite journal|date=2015-09-01|title=Fair apportionment in the view of the Venice Commission's recommendation|url=https://www.sciencedirect.com/science/article/abs/pii/S0165489615000487|journal=Mathematical Social Sciences|language=en|volume=77|pages=32–41|doi=10.1016/j.mathsocsci.2015.06.001|issn=0165-4896|last1=Biró |first1=Péter |last2=Kóczy |first2=László Á. |last3=Sziklai |first3=Balázs |hdl=10419/108309|hdl-access=free|url-access=subscription}}</ref>

<ref name=laszlo>{{Cite journal|last1=Koczy|first1=Laszlo A.|last2=Biro|first2=Peter|last3=Sziklai|first3=Balazs|date=2017-06-01|title=US vs. European Apportionment Practices: The Conflict between Monotonicity and Proportionality|url=https://ideas.repec.org/p/has/discpr/1716.html|journal=Cers-Ie Working Papers|language=en}}</ref>

<ref name=gambarelli>{{Cite journal|last=Gambarelli|first=Gianfranco|date=1999-11-01|title=Minimax Apportionments|url=https://doi.org/10.1023/A:1008675107505|journal=Group Decision and Negotiation|language=en|volume=8|issue=6|pages=441–461|doi=10.1023/A:1008675107505|s2cid=195220285 |issn=1572-9907|url-access=subscription}}</ref> }}

Category:Apportionment method criteria Category:Apportionment (politics) Category:Mathematical optimization Category:Social choice theory Category:Fairness criteria