Decreasing Demand procedure: Difference between revisions
Erel Segal (talk | contribs) No edit summary |
Citation bot (talk | contribs) Add: jstor, doi, s2cid. | Use this bot. Report bugs. | Suggested by Superegz | Category:Fair division protocols | #UCB_Category 10/40 |
||
| (One intermediate revision by one other user not shown) | |||
| Line 1: | Line 1: | ||
{{refimprove|date=March 2017}} |
{{refimprove|date=March 2017}} |
||
The '''Decreasing Demand |
The '''Decreasing Demand procedure''' is a procedure for [[fair item allocation]]. It yields a [[Pareto-efficient]] division that maximizes the rank of the agent with the lowest rank. This corresponds to the [[Rawlsian]] justice criterion of taking care of the worst-off agent. |
||
The procedure was developed by Dorothea Herreiner and Clemens Puppe.<ref name="hp02">{{cite journal|doi=10.1007/s003550100119|title=A simple procedure for finding equitable allocations of indivisible goods|journal=Social Choice and Welfare|volume=19|issue=2|pages=415|year=2002|last1=Herreiner|first1=Dorothea|last2=Puppe|first2=Clemens}}</ref> |
The procedure was developed by Dorothea Herreiner and Clemens Puppe.<ref name="hp02">{{cite journal|doi=10.1007/s003550100119|title=A simple procedure for finding equitable allocations of indivisible goods|journal=Social Choice and Welfare|volume=19|issue=2|pages=415|year=2002|last1=Herreiner|first1=Dorothea|last2=Puppe|first2=Clemens|s2cid=38017775 }}</ref> |
||
== Description == |
== Description == |
||
| Line 17: | Line 17: | ||
The procedure requires the agents to rank bundles of items. This is feasible when the number of items is small, but may be difficult when the number of items is large, since the number of bundles grows exponentially with the number of items. |
The procedure requires the agents to rank bundles of items. This is feasible when the number of items is small, but may be difficult when the number of items is large, since the number of bundles grows exponentially with the number of items. |
||
The procedure does not guarantee [[envy-freeness]]; see [[envy-free item assignment]] for procedures that do guarantee it. However, for two agents, if an envy-free allocation exists, it will be found.<ref name=":0">{{Cite journal|last=Ramaekers|first=Eve|date=2013|title=Fair allocation of indivisible goods: the two-agent case|url=https://www.jstor.org/stable/42001409|journal=Social Choice and Welfare|volume=41|issue=2|pages=359–380|issn=0176-1714}}</ref> |
The procedure does not guarantee [[envy-freeness]]; see [[envy-free item assignment]] for procedures that do guarantee it. However, for two agents, if an envy-free allocation exists, it will be found.<ref name=":0">{{Cite journal|last=Ramaekers|first=Eve|date=2013|title=Fair allocation of indivisible goods: the two-agent case|url=https://www.jstor.org/stable/42001409|journal=Social Choice and Welfare|volume=41|issue=2|pages=359–380|doi=10.1007/s00355-012-0684-0 |jstor=42001409 |s2cid=253851223 |issn=0176-1714}}</ref> |
||
== Axiomatization == |
== Axiomatization == |
||
Latest revision as of 00:47, 16 March 2023
 | This article needs additional citations for verification. (March 2017) |
The Decreasing Demand procedure is a procedure for fair item allocation. It yields a Pareto-efficient division that maximizes the rank of the agent with the lowest rank. This corresponds to the Rawlsian justice criterion of taking care of the worst-off agent.
The procedure was developed by Dorothea Herreiner and Clemens Puppe.[1]
Description
[edit]Each agent is supposed to have a linear ranking on all bundles of items.
The agents are queried in a round-robin fashion: each agent, in turn, reports his next bundle in the ranking, going from the best to the worst.
After each report, the procedure checks whether it is possible to construct a complete partition of the items based on the reports made so far. If it is possible, then the procedure stops and returns one such partition. If there is more than one partition, then a Pareto-efficient one is returned.
The procedure produces "balanced" allocations, that is, allocations which maximize the rank in the preference ordering of the bundle obtained by the worst-off agent.[2]: 308
Limitations
[edit]The procedure requires the agents to rank bundles of items. This is feasible when the number of items is small, but may be difficult when the number of items is large, since the number of bundles grows exponentially with the number of items.
The procedure does not guarantee envy-freeness; see envy-free item assignment for procedures that do guarantee it. However, for two agents, if an envy-free allocation exists, it will be found.[3]
Axiomatization
[edit]The allocation returned by the Decreasing Demand procedure - the maximin-rank allocation - satisfies certain natural axioms when there are two agents:[3]
- Pareto-efficiency;
- Anonymity;
- Envy-freeness-if-possible;
- Monotonicity w.r.t. changes in the preferences (more different preferences means a higher utility).
See also
[edit]- Undercut procedure and envy-graph procedure - two additional procedures based on the ordinal ranking of bundles.
References
[edit]- ^ Herreiner, Dorothea; Puppe, Clemens (2002). "A simple procedure for finding equitable allocations of indivisible goods". Social Choice and Welfare. 19 (2): 415. doi:10.1007/s003550100119. S2CID 38017775.
- ^ Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Handbook of Computational Social Choice. Cambridge University Press. ISBN 9781107060432. (free online version)
- ^ a b Ramaekers, Eve (2013). "Fair allocation of indivisible goods: the two-agent case". Social Choice and Welfare. 41 (2): 359–380. doi:10.1007/s00355-012-0684-0. ISSN 0176-1714. JSTOR 42001409. S2CID 253851223.