Wikipedia

Population monotonicity

Not to be confused with population-ratio monotonicity.

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]

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

edit

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

  • When the pieces may be disconnected, any function that maximizes a concave welfare function (a monotonically-increasing function of the utilities) is PM. This holds whether the welfare function operates on the absolute utilities or on the relative utilities. In particular, the Nash-optimal rule, absolute-leximin and relative-leximin rules, absolute-utilitarian and relative utilitarian rules are all PM.[3] It is an open question whether concavity of the welfare function is necessary for PM.
  • When the pieces must be connected, no Pareto-optimal proportional division rule is PM. The absolute-equitable rule and relative-equitable rules are weakly Pareto-optimal and PM.[4]

In fair house allocation

edit

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

edit

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

edit

References

edit
  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.393-506&rft.date=2011&rft_id=info:doi/10.1016/s0169-7218(10)50021-3&rft.isbn=9780444508942&rft.aulast=Thomson&rft.aufirst=William&rfr_id=info:sid/en.wikipedia.org:Population monotonicity" class="Z3988">
  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.363-401&rft.date=2019-09-01&rft_id=info:arxiv/1510.05229&rft_id=https://api.semanticscholar.org/CorpusID:179618#id-name=S2CID&rft.issn=1432-0479&rft_id=info:doi/10.1007/s00199-018-1128-6&rft.aulast=Segal-Halevi&rft.aufirst=Erel&rft.au=Sziklai, Balázs R.&rft_id=https://doi.org/10.1007/s00199-018-1128-6&rfr_id=info:sid/en.wikipedia.org:Population monotonicity" class="Z3988">
  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.19-30&rft.date=2018-09-01&rft_id=info:arxiv/1703.08928&rft_id=https://api.semanticscholar.org/CorpusID:16282641#id-name=S2CID&rft.issn=0165-4896&rft_id=info:doi/10.1016/j.mathsocsci.2018.07.001&rft.aulast=Segal-Halevi&rft.aufirst=Erel&rft.au=Sziklai, Balázs R.&rft_id=http://www.sciencedirect.com/science/article/pii/S0165489618300520&rfr_id=info:sid/en.wikipedia.org:Population monotonicity" class="Z3988">
  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.329-339&rft.date=2002-11-01&rft_id=info:doi/10.1016/S0304-4068(02)50059-9&rft.issn=0304-4068&rft.aulast=Ehlers&rft.aufirst=Lars&rft.au=Klaus, Bettina&rft.au=Pápai, Szilvia&rft_id=https://www.sciencedirect.com/science/article/abs/pii/S0304406802000599&rfr_id=info:sid/en.wikipedia.org:Population monotonicity" class="Z3988">
  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.2142-2160&rft.date=2019-01-17&rft_id=info:doi/10.1287/mnsc.2018.3053&rft.issn=0025-1909&rft.aulast=Chen&rft.aufirst=Xin&rft.au=Gao, Xiangyu&rft.au=Hu, Zhenyu&rft.au=Wang, Qiong&rft_id=https://pubsonline.informs.org/doi/abs/10.1287/mnsc.2018.3053&rfr_id=info:sid/en.wikipedia.org:Population monotonicity" class="Z3988">
  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.125-137&rft.date=1996-10-01&rft_id=info:doi/10.1016/0165-4896(96)00814-1&rft.issn=0165-4896&rft.aulast=Beviá&rft.aufirst=Carmen&rft_id=https://www.sciencedirect.com/science/article/abs/pii/0165489696008141&rfr_id=info:sid/en.wikipedia.org:Population monotonicity" class="Z3988">
Retrieved from "https://en.wikipedia.org/w/index.php?title=Population_monotonicity&oldid=1240584432"