Population monotonicity

Last updated

Population monotonicity (PM) is a principle of consistency in allocation problems. It says that, when the set of agents participating in the allocation changes, the utility of all agents should change in the same direction. For example, if the resource is good, and an agent leaves, then all remaining agents should receive at least as much utility as in the original allocation. [1] : 46–51  [2]

Contents

The term "population monotonicity" is used in an unrelated meaning in the context of apportionment of seats in the congress among states. There, the property relates to the population of an individual state, which determines the state's entitlement. A population-increase means that a state is entitled to more seats. This different property is described in the page state-population monotonicity .

In fair cake cutting

In the fair cake-cutting problem, classic allocation rules such as divide and choose are not PM. Several rules are known to be PM:

In fair house allocation

In the house allocation problem, a rule is PM and strategyproof and Pareto-efficient, if-and-only-if it assigns the houses iteratively, where at each iteration, at most two agents trade houses from their initial endowments. [5]

In fair item allocation

In the fair item allocation problem, the Nash-optimal rule is no longer PM. In contrast, round-robin item allocation is PM. Moreover, round-robin can be adapted to yield picking sequences appropriate for agents with different entitlements. Picking-sequences based on divisor methods are PM too. [6] However, a picking-sequence based on the quota method is not PM.

See also

Related Research Articles

Entitlement in fair division describes that proportion of the resources or goods to be divided that a player can expect to receive. In many fair division settings, all agents have equal entitlements, which means that each agent is entitled to 1/n of the resource. But there are practical settings in which agents have different entitlements. Some examples are:

Efficient cake-cutting is a problem in economics and computer science. It involves a heterogeneous resource, such as a cake with different toppings or a land with different coverings, that is assumed to be divisible - it is possible to cut arbitrarily small pieces of it without destroying their value. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible, etc. The allocation should be economically efficient. Several notions of efficiency have been studied:

Equitable (EQ) cake-cutting is a kind of a fair cake-cutting problem, in which the fairness criterion is equitability. It is a cake-allocation in which the subjective value of all partners is the same, i.e., each partner is equally happy with his/her share. Mathematically, that means that for all partners i and j:

Fair item allocation is a kind of the fair division problem in which the items to divide are discrete rather than continuous. The items have to be divided among several partners who potentially value them differently, and each item has to be given as a whole to a single person. This situation arises in various real-life scenarios:

Efficiency and fairness are two major goals of welfare economics. Given a set of resources and a set of agents, the goal is to divide the resources among the agents in a way that is both Pareto efficient (PE) and envy-free (EF). The goal was first defined by David Schmeidler and Menahem Yaari. Later, the existence of such allocations has been proved under various conditions.

Weller's theorem is a theorem in economics. It says that a heterogeneous resource ("cake") can be divided among n partners with different valuations in a way that is both Pareto-efficient (PE) and envy-free (EF). Thus, it is possible to divide a cake fairly without compromising on economic efficiency.

Utilitarian cake-cutting is a rule for dividing a heterogeneous resource, such as a cake or a land-estate, among several partners with different cardinal utility functions, such that the sum of the utilities of the partners is as large as possible. It is a special case of the utilitarian social choice rule. Utilitarian cake-cutting is often not "fair"; hence, utilitarianism is often in conflict with fair cake-cutting.

Resource monotonicity is a principle of fair division. It says that, if there are more resources to share, then all agents should be weakly better off; no agent should lose from the increase in resources. The RM principle has been studied in various division problems.

A picking sequence is a protocol for fair item assignment. Suppose m items have to be divided among n agents. One way to allocate the items is to let one agent select a single item, then let another agent select a single item, and so on. A picking-sequence is a sequence of m agent-names, where each name determines what agent is the next to pick an item.

Envy-free (EF) item allocation is a fair item allocation problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that they believe to be at least as good as the bundle of any other agent.

Egalitarian equivalence (EE) is a criterion of fair division. In an egalitarian-equivalent division, there exists a certain "reference bundle" such that each agent feels that his/her share is equivalent to .

Various experiments have been made to evaluate various procedures for fair division, the problem of dividing resources among several people. These include case studies, computerized simulations, and lab experiments.

In mathematics, leximin order is a total preorder on finite-dimensional vectors. A more accurate, but less common term is leximin preorder. The leximin order is particularly important in social choice theory and fair division.

Egalitarian item allocation, also called max-min item allocation is a fair item allocation problem, in which the fairness criterion follows the egalitarian rule. The goal is to maximize the minimum value of an agent. That is, among all possible allocations, the goal is to find an allocation in which the smallest value of an agent is as large as possible. In case there are two or more allocations with the same smallest value, then the goal is to select, from among these allocations, the one in which the second-smallest value is as large as possible, and so on. Therefore, an egalitarian item allocation is sometimes called a leximin item allocation.

Online fair division is a class of fair division problems in which the resources, or the people to whom they should be allocated, or both, are not all available when the allocation decision is made. Some situations in which not all resources are available include:

In social choice and operations research, the egalitarian rule is a rule saying that, among all possible alternatives, society should pick the alternative which maximizes the minimum utility of all individuals in society. It is a formal mathematical representation of the egalitarian philosophy. It also corresponds to John Rawls' principle of maximizing the welfare of the worst-off individual.

Egalitarian cake-cutting is a kind of fair cake-cutting in which the fairness criterion is the egalitarian rule. The cake represents a continuous resource, that has to be allocated among people with different valuations over parts of the resource. The goal in egalitarian cake-cutting is to maximize the smallest value of an agent; subject to this, maximize the next-smallest value; and so on. It is also called leximin cake-cutting, since the optimization is done using the leximin order on the vectors of utilities.

Optimal apportionment is an approach to apportionment that is based on mathematical optimization.

Fair allocation of items and money is a class of fair item allocation problems in which, during the allocation process, it is possible to give or take money from some of the participants. Without money, it may be impossible to allocate indivisible items fairly. For example, if there is one item and two people, and the item must be given entirely to one of them, the allocation will be unfair towards the other one. Monetary payments make it possible to attain fairness, as explained below.

Donor coordination is a problem in social choice. There are several donors, each of whom wants to donate some money. Each donor supports a different set of targets. The goal is to distribute the total donated amount among the various targets in a way that respects the donors' preferences.

References

  1. ↑ Herve Moulin (2004). Fair Division and Collective Welfare. Cambridge, Massachusetts: MIT Press. ISBN   9780262134231.
  2. ↑ Thomson, William (2011). Fair Allocation Rules. Handbook of Social Choice and Welfare. Vol. 2. pp. 393–506. doi:10.1016/s0169-7218(10)00021-3. ISBN   9780444508942.
  3. ↑ Segal-Halevi, Erel; Sziklai, Balázs R. (2019-09-01). "Monotonicity and competitive equilibrium in cake-cutting". Economic Theory. 68 (2): 363–401. arXiv: 1510.05229 . doi:10.1007/s00199-018-1128-6. ISSN   1432-0479. S2CID   179618.
  4. ↑ Segal-Halevi, Erel; Sziklai, Balázs R. (2018-09-01). "Resource-monotonicity and population-monotonicity in connected cake-cutting". Mathematical Social Sciences. 95: 19–30. arXiv: 1703.08928 . doi:10.1016/j.mathsocsci.2018.07.001. ISSN   0165-4896. S2CID   16282641.
  5. ↑ Ehlers, Lars; Klaus, Bettina; Pápai, Szilvia (2002-11-01). "Strategy-proofness and population-monotonicity for house allocation problems". Journal of Mathematical Economics. 38 (3): 329–339. doi:10.1016/S0304-4068(02)00059-9. ISSN   0304-4068.
  6. ↑ Chakraborty, Mithun; Schmidt-Kraepelin, Ulrike; Suksompong, Warut (2021-04-29). "Picking sequences and monotonicity in weighted fair division". Artificial Intelligence. 301: 103578. arXiv: 2104.14347 . doi:10.1016/j.artint.2021.103578. S2CID   233443832.
  7. ↑ Sonmez, Tayfun O. (2014-09-01). "Population-Monotonicity of the Nucleolus on a Class of Public Good Problems". mpra.ub.uni-muenchen.de. Retrieved 2021-08-05.
  8. ↑ Chen, Xin; Gao, Xiangyu; Hu, Zhenyu; Wang, Qiong (2019-01-17). "Population Monotonicity in Newsvendor Games". Management Science. 65 (5): 2142–2160. doi:10.1287/mnsc.2018.3053. ISSN   0025-1909.
  9. ↑ Beviá, Carmen (1996-10-01). "Population monotonicity in economies with one indivisible good". Mathematical Social Sciences. 32 (2): 125–137. doi:10.1016/0165-4896(96)00814-1. ISSN   0165-4896.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.