Simultaneous eating algorithm - Revision history

Rob Formi at 12:15, 20 January 2025

2025-01-20T12:15:34Z

← Previous revision		Revision as of 12:15, 20 January 2025
Line 1:		Line 1:
	A '''simultaneous eating algorithm''' ~~'''(SE)~~<ref name="bm01">{{cite journal \|last1=Bogomolnaia \|first1=Anna \|author1-link=Anna Bogomolnaia \|last2=Moulin \|first2=Hervé \|author2-link=Hervé Moulin \|year=2001 \|title=A New Solution to the Random Assignment Problem \|journal=Journal of Economic Theory \|volume=100 \|issue=2 \|pages=295 \|doi=10.1006/jeth.2000.2710}}</ref>~~''' is an algorithm for allocating divisible objects among agents with [[ordinal preferences]].~~ "Ordinal preferences" means that each agent can rank the items from best to worst, but cannot (or does not want to) specify a numeric value for each item. The SE allocation satisfies '''[[SD-efficiency]]''' - a weak ordinal variant of Pareto-efficiency (it means that the allocation is Pareto-efficient for ''at least one'' vector of [[Additive utility\|additive utility functions]] consistent with the agents' item rankings).		A '''simultaneous eating algorithm (SE)''' is an algorithm for allocating divisible objects among agents with [[ordinal preferences]].<ref name="bm01">{{cite journal \|last1=Bogomolnaia \|first1=Anna \|author1-link=Anna Bogomolnaia \|last2=Moulin \|first2=Hervé \|author2-link=Hervé Moulin \|year=2001 \|title=A New Solution to the Random Assignment Problem \|journal=Journal of Economic Theory \|volume=100 \|issue=2 \|pages=295 \|doi=10.1006/jeth.2000.2710}}</ref>

			"Ordinal preferences" means that each agent can rank the items from best to worst, but cannot (or does not want to) specify a numeric value for each item. The SE allocation satisfies '''[[SD-efficiency]]''' - a weak ordinal variant of Pareto-efficiency (it means that the allocation is Pareto-efficient for ''at least one'' vector of [[Additive utility\|additive utility functions]] consistent with the agents' item rankings).

	SE is parametrized by the "eating speed" of each agent. If all agents are given the same eating speed, then the SE allocation satisfies '''SD-envy-freeness''' - a strong ordinal variant of [[envy-freeness]] (it means that the allocation is envy-free for ''all'' vectors of additive utility functions consistent with the agents' item rankings). This particular variant of SE is called the '''Probabilistic Serial rule''' (PS).<ref name="bm01" />		SE is parametrized by the "eating speed" of each agent. If all agents are given the same eating speed, then the SE allocation satisfies '''SD-envy-freeness''' - a strong ordinal variant of [[envy-freeness]] (it means that the allocation is envy-free for ''all'' vectors of additive utility functions consistent with the agents' item rankings). This particular variant of SE is called the '''Probabilistic Serial rule''' (PS).<ref name="bm01" />

132.170.212.15: /* Fairness */

2024-04-03T17:16:14Z

Fairness

← Previous revision		Revision as of 17:16, 3 April 2024
Line 57:		Line 57:

	=== Fairness ===		=== Fairness ===
	SE with equal eating speeds (called PS) satisfies a fairness property called ex-ante '''[[Stochastic dominance\|stochastic-~~dominace~~]] [[envy-freeness]]''' (sd-envy-free). Informally it means that each agent, considering the resulting probability matrix, weakly prefers his/her own row of probabilities to the row of any other agent. Formally, for every two agents ''i'' and ''j'':		SE with equal eating speeds (called PS) satisfies a fairness property called ex-ante '''[[Stochastic dominance\|stochastic-dominance]] [[envy-freeness]]''' (sd-envy-free). Informally it means that each agent, considering the resulting probability matrix, weakly prefers his/her own row of probabilities to the row of any other agent. Formally, for every two agents ''i'' and ''j'':
	* Agent ''i'' has a weakly-higher probability to get his best item in row ''i'' than in row ''j'';		* Agent ''i'' has a weakly-higher probability to get his best item in row ''i'' than in row ''j'';
	* Agent ''i'' has a weakly-higher probability to get one of his two best items in row ''i'' than in row ''j'';		* Agent ''i'' has a weakly-higher probability to get one of his two best items in row ''i'' than in row ''j'';

132.170.212.15: /* Strategy */

2024-04-03T17:15:18Z

Strategy

← Previous revision		Revision as of 17:15, 3 April 2024
Line 68:		Line 68:

	=== Strategy ===		=== Strategy ===
	SE is not a [[truthful mechanism]]: an agent who knows that his most preferred item is not wanted by any other agent, can manipulate the algorithm by eating his second-most preferred item, knowing that his best item will remain intact. The following is known about strategic manipulation of PS:		SE is not a [[truthful mechanism]]: an agent who knows that his most preferred item is not wanted by any other agent can manipulate the algorithm by eating his second-most preferred item, knowing that his best item will remain intact. The following is known about strategic manipulation of PS:

	* PS is truthful when agents compare bundles using the [[downward lexicographic]] relation.<ref name=":2" />		* PS is truthful when agents compare bundles using the [[downward lexicographic]] relation.<ref name=":2" />

BD2412: clean up spacing around commas and other punctuation fixes, replaced: ,t → , t, ,x → , x, ,y → , y, ,z → , z

2024-03-18T19:40:44Z

clean up spacing around commas and other punctuation fixes, replaced: ,t → , t, ,x → , x, ,y → , y, ,z → , z

← Previous revision		Revision as of 19:40, 18 March 2024
Line 12:		Line 12:
	Whenever an item is fully eaten, each of the agents who ate it goes to their favorite remaining item and starts eating it in the same way, until all items are consumed.		Whenever an item is fully eaten, each of the agents who ate it goes to their favorite remaining item and starts eating it in the same way, until all items are consumed.

	For each item, the fraction of that item eaten by each agent is recorded. In the context of random assignments,these fractions are considered as probabilities. Based on these probabilities, a lottery is done. The type of lottery depends on the problem:		For each item, the fraction of that item eaten by each agent is recorded. In the context of random assignments, these fractions are considered as probabilities. Based on these probabilities, a lottery is done. The type of lottery depends on the problem:

	* If each agent is allowed to receive any number of items, then a separate lottery can be done for each item. Each item is given to one of the agents who ate a part of it, chosen at random according to the probability distribution for that item.		* If each agent is allowed to receive any number of items, then a separate lottery can be done for each item. Each item is given to one of the agents who ate a part of it, chosen at random according to the probability distribution for that item.
Line 20:		Line 20:

	== Examples ==		== Examples ==
	There are four agents and four items (denoted w,x,y,z). The preferences of the agents are:		There are four agents and four items (denoted w, x, y, z). The preferences of the agents are:
	* Alice and Bob prefer w to x to y to z.		* Alice and Bob prefer w to x to y to z.
	* Chana and Dana prefer x to w to z to y.		* Chana and Dana prefer x to w to z to y.

OAbot: Open access bot: arxiv updated in citation with #oabot.

2024-01-02T07:49:33Z

Open access bot: arxiv updated in citation with #oabot.

← Previous revision		Revision as of 07:49, 2 January 2024
Line 74:		Line 74:
	Older technical report: https://arxiv.org/abs/1401.6523.</ref>		Older technical report: https://arxiv.org/abs/1401.6523.</ref>
	*Best responses w.r.t. expected utility can cycle. However, a pure [[Nash equilibrium]] exists for any number of agents and items. When there are two agents, there are linear-time algorithms to compute a preference-profile that is in Nash equilibrium w.r.t. the original preferences. In some empirical settings, PS is less prone to manipulation. When an agent is [[Risk aversion\|risk-averse]] and has no information about the other agents' strategies, his [[maximin strategy]] is to be truthful.<ref name=":0" />		*Best responses w.r.t. expected utility can cycle. However, a pure [[Nash equilibrium]] exists for any number of agents and items. When there are two agents, there are linear-time algorithms to compute a preference-profile that is in Nash equilibrium w.r.t. the original preferences. In some empirical settings, PS is less prone to manipulation. When an agent is [[Risk aversion\|risk-averse]] and has no information about the other agents' strategies, his [[maximin strategy]] is to be truthful.<ref name=":0" />
	*A manipulating agent can increase his utility by a factor of at most 3/2. This was first observed empirically on random instances,<ref>{{Cite journal \|last1=Hosseini \|first1=Hadi \|last2=Larson \|first2=Kate \|last3=Cohen \|first3=Robin \|date=2018-07-01 \|title=Investigating the characteristics of one-sided matching mechanisms under various preferences and risk attitudes \|url=https://doi.org/10.1007/s10458-018-9387-y \|journal=Autonomous Agents and Multi-Agent Systems \|language=en \|volume=32 \|issue=4 \|pages=534–567 \|doi=10.1007/s10458-018-9387-y \|arxiv=1703.00320 \|s2cid=14041902 \|issn=1573-7454}}</ref> and then proved formally.<ref>{{Cite journal \|last1=Wang \|first1=Zihe \|last2=Wei \|first2=Zhide \|last3=Zhang \|first3=Jie \|date=2020-04-03 \|title=Bounded Incentives in Manipulating the Probabilistic Serial Rule \|url=https://ojs.aaai.org/index.php/AAAI/article/view/5605 \|journal=Proceedings of the AAAI Conference on Artificial Intelligence \|language=en \|volume=34 \|issue=2 \|pages=2276–2283 \|doi=10.1609/aaai.v34i02.5605 \|s2cid=210943079 \|issn=2374-3468\|doi-access=free }}</ref>		*A manipulating agent can increase his utility by a factor of at most 3/2. This was first observed empirically on random instances,<ref>{{Cite journal \|last1=Hosseini \|first1=Hadi \|last2=Larson \|first2=Kate \|last3=Cohen \|first3=Robin \|date=2018-07-01 \|title=Investigating the characteristics of one-sided matching mechanisms under various preferences and risk attitudes \|url=https://doi.org/10.1007/s10458-018-9387-y \|journal=Autonomous Agents and Multi-Agent Systems \|language=en \|volume=32 \|issue=4 \|pages=534–567 \|doi=10.1007/s10458-018-9387-y \|arxiv=1703.00320 \|s2cid=14041902 \|issn=1573-7454}}</ref> and then proved formally.<ref>{{Cite journal \|last1=Wang \|first1=Zihe \|last2=Wei \|first2=Zhide \|last3=Zhang \|first3=Jie \|date=2020-04-03 \|title=Bounded Incentives in Manipulating the Probabilistic Serial Rule \|url=https://ojs.aaai.org/index.php/AAAI/article/view/5605 \|journal=Proceedings of the AAAI Conference on Artificial Intelligence \|language=en \|volume=34 \|issue=2 \|pages=2276–2283 \|doi=10.1609/aaai.v34i02.5605 \|s2cid=210943079 \|issn=2374-3468\|doi-access=free \|arxiv=2001.10640 }}</ref>
	Note that the [[random priority item allocation\|random priority]] rule, which solves the same problem as PS, is truthful.		Note that the [[random priority item allocation\|random priority]] rule, which solves the same problem as PS, is truthful.

Headbomb: Alter: template type. Add: title. | Use this tool. Report bugs. | #UCB_Gadget

2023-09-04T11:28:27Z

Alter: template type. Add: title. | Use this tool. Report bugs. | #UCB_Gadget

← Previous revision		Revision as of 11:28, 4 September 2023
Line 71:		Line 71:

	* PS is truthful when agents compare bundles using the [[downward lexicographic]] relation.<ref name=":2" />		* PS is truthful when agents compare bundles using the [[downward lexicographic]] relation.<ref name=":2" />
	* An agent can compute in polynomial time a [[Best response\|best-response]] w.r.t. the [[downward lexicographic]] relation. When there are two agents, each agent can compute in polynomial time a best response w.r.t. expected utility. When the number of agents can vary, computing a best response w.r.t. EU is NP-hard.<ref name=":0">{{Cite ~~journal~~\|last1=Aziz\|first1=Haris\|last2=Gaspers\|first2=Serge\|last3=Mackenzie\|first3=Simon\|last4=Mattei\|first4=Nicholas\|last5=Narodytska\|first5=Nina\|last6=Walsh\|first6=Toby\|date=2015-05-04~~\|title=Manipulating the Probabilistic Serial~~ ~~Rule~~\|url=https://dl.acm.org/doi/abs/10.5555/2772879.2773337~~\|journal=Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems\|series=AAMAS~~ ~~'15~~\|location=Istanbul, Turkey\|publisher=International Foundation for Autonomous Agents and Multiagent Systems\|pages=1451–1459\|doi=\|isbn=978-1-4503-3413-6}}.		* An agent can compute in polynomial time a [[Best response\|best-response]] w.r.t. the [[downward lexicographic]] relation. When there are two agents, each agent can compute in polynomial time a best response w.r.t. expected utility. When the number of agents can vary, computing a best response w.r.t. EU is NP-hard.<ref name=":0">{{Cite book\|last1=Aziz\|first1=Haris\|last2=Gaspers\|first2=Serge\|last3=Mackenzie\|first3=Simon\|last4=Mattei\|first4=Nicholas\|last5=Narodytska\|first5=Nina\|last6=Walsh\|first6=Toby\|title=Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems \|date=2015-05-04 \|url=https://dl.acm.org/doi/abs/10.5555/2772879.2773337 \|location=Istanbul, Turkey\|publisher=International Foundation for Autonomous Agents and Multiagent Systems\|pages=1451–1459\|doi=\|isbn=978-1-4503-3413-6}}.
	Older technical report: https://arxiv.org/abs/1401.6523.</ref>		Older technical report: https://arxiv.org/abs/1401.6523.</ref>
	*Best responses w.r.t. expected utility can cycle. However, a pure [[Nash equilibrium]] exists for any number of agents and items. When there are two agents, there are linear-time algorithms to compute a preference-profile that is in Nash equilibrium w.r.t. the original preferences. In some empirical settings, PS is less prone to manipulation. When an agent is [[Risk aversion\|risk-averse]] and has no information about the other agents' strategies, his [[maximin strategy]] is to be truthful.<ref name=":0" />		*Best responses w.r.t. expected utility can cycle. However, a pure [[Nash equilibrium]] exists for any number of agents and items. When there are two agents, there are linear-time algorithms to compute a preference-profile that is in Nash equilibrium w.r.t. the original preferences. In some empirical settings, PS is less prone to manipulation. When an agent is [[Risk aversion\|risk-averse]] and has no information about the other agents' strategies, his [[maximin strategy]] is to be truthful.<ref name=":0" />

Citation bot: Alter: title, template type. Add: chapter-url, chapter. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar

2023-09-04T11:21:03Z

Alter: title, template type. Add: chapter-url, chapter. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar

← Previous revision		Revision as of 11:21, 4 September 2023
Line 5:		Line 5:
	SE was developed by [[Hervé Moulin]] and [[Anna Bogomolnaia]] as a solution for the [[fair random assignment]] problem, where the fraction that each agent receives of each item is interpreted as a probability. If the integral of the eating speed of all agents is 1, then the sum of fractions assigned to each agent is 1, so the matrix of fractions can be decomposed into a lottery over assignments in which each agent gets exactly one item. With equal eating speeds, the lottery is [[envy-free]] in expectation ([[ex-ante]]) for all vectors of utility functions consistent with the agents' item rankings.		SE was developed by [[Hervé Moulin]] and [[Anna Bogomolnaia]] as a solution for the [[fair random assignment]] problem, where the fraction that each agent receives of each item is interpreted as a probability. If the integral of the eating speed of all agents is 1, then the sum of fractions assigned to each agent is 1, so the matrix of fractions can be decomposed into a lottery over assignments in which each agent gets exactly one item. With equal eating speeds, the lottery is [[envy-free]] in expectation ([[ex-ante]]) for all vectors of utility functions consistent with the agents' item rankings.

	A variant of SE was applied also to [[Fair cake-cutting\|cake-cutting]], where the allocation is deterministic (not random).<ref>{{Cite ~~journal~~ \|last1=Aziz \|first1=Haris \|last2=Ye \|first2=Chun \|date=2014 \|editor-last=Liu \|editor-first=Tie-Yan \|editor2-last=Qi \|editor2-first=Qi \|editor3-last=Ye \|editor3-first=Yinyu \|~~title=Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations \|~~url=https://link.springer.com/chapter/10.1007/978-3-319-13129-0_1 ~~\|journal=Web and Internet Economics~~ \|series=Lecture Notes in Computer Science \|volume=8877 \|language=en \|location=Cham \|publisher=Springer International Publishing \|pages=1–14 \|doi=10.1007/978-3-319-13129-0_1 \|isbn=978-3-319-13129-0\|s2cid=18365892 }}</ref>		A variant of SE was applied also to [[Fair cake-cutting\|cake-cutting]], where the allocation is deterministic (not random).<ref>{{Cite book \|last1=Aziz \|first1=Haris \|last2=Ye \|first2=Chun \|title=Web and Internet Economics \|chapter=Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations \|date=2014 \|editor-last=Liu \|editor-first=Tie-Yan \|editor2-last=Qi \|editor2-first=Qi \|editor3-last=Ye \|editor3-first=Yinyu \|chapter-url=https://link.springer.com/chapter/10.1007/978-3-319-13129-0_1 \|series=Lecture Notes in Computer Science \|volume=8877 \|language=en \|location=Cham \|publisher=Springer International Publishing \|pages=1–14 \|doi=10.1007/978-3-319-13129-0_1 \|isbn=978-3-319-13129-0\|s2cid=18365892 }}</ref>

	== Description ==		== Description ==
Line 91:		Line 91:
	As explained above, the allocation determined by PS is fair only ex-ante but not ex-post. Moreover, when each agent may get any number of items, the ex-post unfairness might be arbitrarily bad: theoretically it is possible that one agent will get all the items while other agents get none. Recently, several algorithms have been suggested, that guarantee both ex-ante fairness and ex-post approximate-fairness.		As explained above, the allocation determined by PS is fair only ex-ante but not ex-post. Moreover, when each agent may get any number of items, the ex-post unfairness might be arbitrarily bad: theoretically it is possible that one agent will get all the items while other agents get none. Recently, several algorithms have been suggested, that guarantee both ex-ante fairness and ex-post approximate-fairness.

	Freeman, Shah and Vaish<ref>{{Cite ~~journal~~\|last1=Freeman\|first1=Rupert\|last2=Shah\|first2=Nisarg\|last3=Vaish\|first3=Rohit\|~~date~~=~~2020-07-13~~\|~~title~~=Best of Both Worlds: Ex-Ante and Ex-Post Fairness in Resource Allocation\|url=https://doi.org/10.1145/3391403.3399537~~\|journal=Proceedings of the 21st ACM Conference on Economics and Computation~~\|series=EC '20\|location=Virtual Event, Hungary\|publisher=Association for Computing Machinery\|pages=21–22\|doi=10.1145/3391403.3399537\|isbn=978-1-4503-7975-5\|arxiv=2005.14122\|s2cid=211141200}}</ref> show:		Freeman, Shah and Vaish<ref>{{Cite book\|last1=Freeman\|first1=Rupert\|last2=Shah\|first2=Nisarg\|last3=Vaish\|first3=Rohit\|title=Proceedings of the 21st ACM Conference on Economics and Computation \|chapter=Best of Both Worlds: Ex-Ante and Ex-Post Fairness in Resource Allocation \|date=2020-07-13\|chapter-url=https://doi.org/10.1145/3391403.3399537\|series=EC '20\|location=Virtual Event, Hungary\|publisher=Association for Computing Machinery\|pages=21–22\|doi=10.1145/3391403.3399537\|isbn=978-1-4503-7975-5\|arxiv=2005.14122\|s2cid=211141200}}</ref> show:

	* The '''Recursive Probabilistic Serial''' (RecPS) algorithm, which returns a probability distribution over allocations that are all envy-free-except-one-item (EF1). The distribution is ex-ante EF, and the allocation is ex-post EF1. A naive version of this algorithm yields a distribution over a possibly exponential number of deterministic allocations, a support size polynomial in the number of agents and goods is sufficient, and thus the algorithm runs in polynomial time. The algorithm uses [[separation oracle]]s.		* The '''Recursive Probabilistic Serial''' (RecPS) algorithm, which returns a probability distribution over allocations that are all envy-free-except-one-item (EF1). The distribution is ex-ante EF, and the allocation is ex-post EF1. A naive version of this algorithm yields a distribution over a possibly exponential number of deterministic allocations, a support size polynomial in the number of agents and goods is sufficient, and thus the algorithm runs in polynomial time. The algorithm uses [[separation oracle]]s.
Line 98:		Line 98:
	* The RecPS can be modified to attain similar guarantees (ex-ante EF and ex-post EF1) for bads.		* The RecPS can be modified to attain similar guarantees (ex-ante EF and ex-post EF1) for bads.

	Aziz<ref>{{Cite ~~journal~~ \|last=Aziz \|first=Haris \|~~date~~=~~2020-12-07~~ \|~~title~~=Simultaneously Achieving Ex-ante and Ex-post Fairness \|url=https://doi.org/10.1007/978-3-030-64946-3_24 ~~\|journal=Web and Internet Economics: 16th International Conference, WINE 2020, Beijing, China, December 7–11, 2020, Proceedings~~ \|series=Lecture Notes in Computer Science \|volume=12495 \|location=Berlin, Heidelberg \|publisher=Springer-Verlag \|pages=341–355 \|doi=10.1007/978-3-030-64946-3_24 \|arxiv=2004.02554 \|isbn=978-3-030-64945-6\|s2cid=214802174 }}</ref> shows:		Aziz<ref>{{Cite book \|last=Aziz \|first=Haris \|title=Web and Internet Economics \|chapter=Simultaneously Achieving Ex-ante and Ex-post Fairness \|date=2020-12-07 \|chapter-url=https://doi.org/10.1007/978-3-030-64946-3_24 \|series=Lecture Notes in Computer Science \|volume=12495 \|location=Berlin, Heidelberg \|publisher=Springer-Verlag \|pages=341–355 \|doi=10.1007/978-3-030-64946-3_24 \|arxiv=2004.02554 \|isbn=978-3-030-64945-6\|s2cid=214802174 }}</ref> shows:

	* The '''PS-lottery algorithm''', in which the allocation is ex-ante sd-EF, and the lottery is done only among deterministic allocations that are sd-EF1, i.e., the EF and EF1 guarantees hold for ''any'' cardinal utilities consistent with the ordinal ranking. Moreover, the outcome is sd-PO both ex-ante and ex-post. The algorithm uses as subroutines both the PS algorithm and the [[Birkhoff algorithm]]. The ex-ante allocation is equivalent to the one returned by PS; this shows that the outcome of PS can be decomposed into EF1 allocations.		* The '''PS-lottery algorithm''', in which the allocation is ex-ante sd-EF, and the lottery is done only among deterministic allocations that are sd-EF1, i.e., the EF and EF1 guarantees hold for ''any'' cardinal utilities consistent with the ordinal ranking. Moreover, the outcome is sd-PO both ex-ante and ex-post. The algorithm uses as subroutines both the PS algorithm and the [[Birkhoff algorithm]]. The ex-ante allocation is equivalent to the one returned by PS; this shows that the outcome of PS can be decomposed into EF1 allocations.

OAbot: Open access bot: doi added to citation with #oabot.

2023-01-30T04:55:07Z

Open access bot: doi added to citation with #oabot.

← Previous revision		Revision as of 04:55, 30 January 2023
Line 74:		Line 74:
	Older technical report: https://arxiv.org/abs/1401.6523.</ref>		Older technical report: https://arxiv.org/abs/1401.6523.</ref>
	*Best responses w.r.t. expected utility can cycle. However, a pure [[Nash equilibrium]] exists for any number of agents and items. When there are two agents, there are linear-time algorithms to compute a preference-profile that is in Nash equilibrium w.r.t. the original preferences. In some empirical settings, PS is less prone to manipulation. When an agent is [[Risk aversion\|risk-averse]] and has no information about the other agents' strategies, his [[maximin strategy]] is to be truthful.<ref name=":0" />		*Best responses w.r.t. expected utility can cycle. However, a pure [[Nash equilibrium]] exists for any number of agents and items. When there are two agents, there are linear-time algorithms to compute a preference-profile that is in Nash equilibrium w.r.t. the original preferences. In some empirical settings, PS is less prone to manipulation. When an agent is [[Risk aversion\|risk-averse]] and has no information about the other agents' strategies, his [[maximin strategy]] is to be truthful.<ref name=":0" />
	*A manipulating agent can increase his utility by a factor of at most 3/2. This was first observed empirically on random instances,<ref>{{Cite journal \|last1=Hosseini \|first1=Hadi \|last2=Larson \|first2=Kate \|last3=Cohen \|first3=Robin \|date=2018-07-01 \|title=Investigating the characteristics of one-sided matching mechanisms under various preferences and risk attitudes \|url=https://doi.org/10.1007/s10458-018-9387-y \|journal=Autonomous Agents and Multi-Agent Systems \|language=en \|volume=32 \|issue=4 \|pages=534–567 \|doi=10.1007/s10458-018-9387-y \|arxiv=1703.00320 \|s2cid=14041902 \|issn=1573-7454}}</ref> and then proved formally.<ref>{{Cite journal \|last1=Wang \|first1=Zihe \|last2=Wei \|first2=Zhide \|last3=Zhang \|first3=Jie \|date=2020-04-03 \|title=Bounded Incentives in Manipulating the Probabilistic Serial Rule \|url=https://ojs.aaai.org/index.php/AAAI/article/view/5605 \|journal=Proceedings of the AAAI Conference on Artificial Intelligence \|language=en \|volume=34 \|issue=2 \|pages=2276–2283 \|doi=10.1609/aaai.v34i02.5605 \|s2cid=210943079 \|issn=2374-3468}}</ref>		*A manipulating agent can increase his utility by a factor of at most 3/2. This was first observed empirically on random instances,<ref>{{Cite journal \|last1=Hosseini \|first1=Hadi \|last2=Larson \|first2=Kate \|last3=Cohen \|first3=Robin \|date=2018-07-01 \|title=Investigating the characteristics of one-sided matching mechanisms under various preferences and risk attitudes \|url=https://doi.org/10.1007/s10458-018-9387-y \|journal=Autonomous Agents and Multi-Agent Systems \|language=en \|volume=32 \|issue=4 \|pages=534–567 \|doi=10.1007/s10458-018-9387-y \|arxiv=1703.00320 \|s2cid=14041902 \|issn=1573-7454}}</ref> and then proved formally.<ref>{{Cite journal \|last1=Wang \|first1=Zihe \|last2=Wei \|first2=Zhide \|last3=Zhang \|first3=Jie \|date=2020-04-03 \|title=Bounded Incentives in Manipulating the Probabilistic Serial Rule \|url=https://ojs.aaai.org/index.php/AAAI/article/view/5605 \|journal=Proceedings of the AAAI Conference on Artificial Intelligence \|language=en \|volume=34 \|issue=2 \|pages=2276–2283 \|doi=10.1609/aaai.v34i02.5605 \|s2cid=210943079 \|issn=2374-3468\|doi-access=free }}</ref>
	Note that the [[random priority item allocation\|random priority]] rule, which solves the same problem as PS, is truthful.		Note that the [[random priority item allocation\|random priority]] rule, which solves the same problem as PS, is truthful.

Line 85:		Line 85:
	* Budish, Che, Kojima and Milgrom<ref name=":1">{{Cite journal\|last1=Budish\|first1=Eric\|last2=Che\|first2=Yeon-Koo\|last3=Kojima\|first3=Fuhito\|last4=Milgrom\|first4=Paul\|date=2013-04-01\|title=Designing Random Allocation Mechanisms: Theory and Applications\|url=https://www.aeaweb.org/articles?id=10.1257/aer.103.2.585\|journal=American Economic Review\|language=en\|volume=103\|issue=2\|pages=585–623\|doi=10.1257/aer.103.2.585\|issn=0002-8282}}</ref> present ''Generalized PS'', which allows multiple units per item, more items than agents, each agent can get several units, upper quotas, and bi-hierarchical constraints on the feasible allocations.		* Budish, Che, Kojima and Milgrom<ref name=":1">{{Cite journal\|last1=Budish\|first1=Eric\|last2=Che\|first2=Yeon-Koo\|last3=Kojima\|first3=Fuhito\|last4=Milgrom\|first4=Paul\|date=2013-04-01\|title=Designing Random Allocation Mechanisms: Theory and Applications\|url=https://www.aeaweb.org/articles?id=10.1257/aer.103.2.585\|journal=American Economic Review\|language=en\|volume=103\|issue=2\|pages=585–623\|doi=10.1257/aer.103.2.585\|issn=0002-8282}}</ref> present ''Generalized PS'', which allows multiple units per item, more items than agents, each agent can get several units, upper quotas, and bi-hierarchical constraints on the feasible allocations.
	* Ashlagi, Saberi and Shameli<ref>{{Cite journal \|last1=Ashlagi \|first1=Itai \|last2=Saberi \|first2=Amin \|last3=Shameli \|first3=Ali \|date=2020-03-01 \|title=Assignment Mechanisms Under Distributional Constraints \|url=https://pubsonline.informs.org/doi/abs/10.1287/opre.2019.1887 \|journal=Operations Research \|volume=68 \|issue=2 \|pages=467–479 \|doi=10.1287/opre.2019.1887 \|arxiv=1810.04331 \|issn=0030-364X}}</ref> present another ''Generalized PS'', which allows lower and upper quotas, and distributional constraints (constraints on the probability distribution and not only the final allocation).		* Ashlagi, Saberi and Shameli<ref>{{Cite journal \|last1=Ashlagi \|first1=Itai \|last2=Saberi \|first2=Amin \|last3=Shameli \|first3=Ali \|date=2020-03-01 \|title=Assignment Mechanisms Under Distributional Constraints \|url=https://pubsonline.informs.org/doi/abs/10.1287/opre.2019.1887 \|journal=Operations Research \|volume=68 \|issue=2 \|pages=467–479 \|doi=10.1287/opre.2019.1887 \|arxiv=1810.04331 \|issn=0030-364X}}</ref> present another ''Generalized PS'', which allows lower and upper quotas, and distributional constraints (constraints on the probability distribution and not only the final allocation).
	* Aziz and Stursberg<ref>{{Cite journal \|last1=Aziz \|first1=Haris \|last2=Stursberg \|first2=Paul \|date=2014-06-20 \|title=A Generalization of Probabilistic Serial to Randomized Social Choice \|url=https://ojs.aaai.org/index.php/AAAI/article/view/8796 \|journal=Proceedings of the AAAI Conference on Artificial Intelligence \|language=en \|volume=28 \|issue=1 \|doi=10.1609/aaai.v28i1.8796 \|s2cid=16265016 \|issn=2374-3468}}</ref> present ''Egalitarian Simultaneous Reservation (ESR)'', which allows not only fair item allocation but also general [[Social choice theory\|social choice]] problems, with possible indifferences.		* Aziz and Stursberg<ref>{{Cite journal \|last1=Aziz \|first1=Haris \|last2=Stursberg \|first2=Paul \|date=2014-06-20 \|title=A Generalization of Probabilistic Serial to Randomized Social Choice \|url=https://ojs.aaai.org/index.php/AAAI/article/view/8796 \|journal=Proceedings of the AAAI Conference on Artificial Intelligence \|language=en \|volume=28 \|issue=1 \|doi=10.1609/aaai.v28i1.8796 \|s2cid=16265016 \|issn=2374-3468\|doi-access=free }}</ref> present ''Egalitarian Simultaneous Reservation (ESR)'', which allows not only fair item allocation but also general [[Social choice theory\|social choice]] problems, with possible indifferences.
	* Aziz and Brandl<ref>{{Cite journal \|last1=Aziz \|first1=Haris \|last2=Brandl \|first2=Florian \|date=2022-09-01 \|title=The vigilant eating rule: A general approach for probabilistic economic design with constraints \|url=https://www.sciencedirect.com/science/article/pii/S0899825622001014 \|journal=Games and Economic Behavior \|language=en \|volume=135 \|pages=168–187 \|doi=10.1016/j.geb.2022.06.002 \|arxiv=2008.08991 \|s2cid=221186811 \|issn=0899-8256}}</ref> present ''Vigilant Eating (VE)'', which allows even more general constraints.		* Aziz and Brandl<ref>{{Cite journal \|last1=Aziz \|first1=Haris \|last2=Brandl \|first2=Florian \|date=2022-09-01 \|title=The vigilant eating rule: A general approach for probabilistic economic design with constraints \|url=https://www.sciencedirect.com/science/article/pii/S0899825622001014 \|journal=Games and Economic Behavior \|language=en \|volume=135 \|pages=168–187 \|doi=10.1016/j.geb.2022.06.002 \|arxiv=2008.08991 \|s2cid=221186811 \|issn=0899-8256}}</ref> present ''Vigilant Eating (VE)'', which allows even more general constraints.

Citation bot: Alter: issue, template type. Add: eprint, class, arxiv, s2cid, volume, series, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 16/24

2022-09-26T04:28:34Z

Alter: issue, template type. Add: eprint, class, arxiv, s2cid, volume, series, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 16/24

Headbomb: Various citation & identifier cleanup, plus AWB genfixes (arxiv version pointless when published)

2022-09-26T04:03:54Z

Various citation & identifier cleanup, plus AWB genfixes (arxiv version pointless when published)

← Previous revision		Revision as of 04:03, 26 September 2022
Line 1:		Line 1:
	A '''simultaneous eating algorithm''' '''(SE)<ref name="bm01">{{cite journal \|last1=Bogomolnaia \|first1=Anna \|author1-link=Anna Bogomolnaia \|last2=Moulin \|first2=Hervé \|author2-link=Hervé Moulin \|year=2001 \|title=A New Solution to the Random Assignment Problem \|journal=Journal of Economic Theory \|volume=100 \|issue=2 \|pages=295 \|doi=10.1006/jeth.2000.2710}}</ref>''' is an algorithm for allocating divisible objects among agents with [[ordinal preferences]]. "Ordinal preferences" means that each agent can rank the items from best to worst, but cannot (or does not want to) specify a numeric value for each item. The SE allocation satisfies '''[[SD-efficiency]]''' - a weak ordinal variant of Pareto-efficiency (it means that the allocation is Pareto-efficient for ''at least one'' vector of [[Additive utility\|additive utility functions]] consistent with the agents' item rankings).		A '''simultaneous eating algorithm''' '''(SE)<ref name="bm01">{{cite journal \|last1=Bogomolnaia \|first1=Anna \|author1-link=Anna Bogomolnaia \|last2=Moulin \|first2=Hervé \|author2-link=Hervé Moulin \|year=2001 \|title=A New Solution to the Random Assignment Problem \|journal=Journal of Economic Theory \|volume=100 \|issue=2 \|pages=295 \|doi=10.1006/jeth.2000.2710}}</ref>''' is an algorithm for allocating divisible objects among agents with [[ordinal preferences]]. "Ordinal preferences" means that each agent can rank the items from best to worst, but cannot (or does not want to) specify a numeric value for each item. The SE allocation satisfies '''[[SD-efficiency]]''' - a weak ordinal variant of Pareto-efficiency (it means that the allocation is Pareto-efficient for ''at least one'' vector of [[Additive utility\|additive utility functions]] consistent with the agents' item rankings).

	SE is parametrized by the "eating speed" of each agent. If all agents are given the same eating speed, then the SE allocation satisfies '''SD-envy-freeness''' - a strong ordinal variant of [[envy-freeness]] (it means that the allocation is envy-free for ''all'' vectors of additive utility functions consistent with the agents' item rankings). This particular variant of SE is called the '''Probabilistic Serial rule''' (PS).<ref name="bm01" />		SE is parametrized by the "eating speed" of each agent. If all agents are given the same eating speed, then the SE allocation satisfies '''SD-envy-freeness''' - a strong ordinal variant of [[envy-freeness]] (it means that the allocation is envy-free for ''all'' vectors of additive utility functions consistent with the agents' item rankings). This particular variant of SE is called the '''Probabilistic Serial rule''' (PS).<ref name="bm01" />

	SE was developed by [[Hervé Moulin]] and [[Anna Bogomolnaia]] as a solution for the [[fair random assignment]] problem, where the fraction that each agent receives of each item is interpreted as a probability. If the integral of the eating speed of all agents is 1, then the sum of fractions assigned to each agent is 1, so the matrix of fractions can be decomposed into a lottery over assignments in which each agent gets exactly one item. With equal eating speeds, the lottery is [[envy-free]] in expectation ([[ex-ante]]) for all vectors of utility functions consistent with the agents' item rankings.		SE was developed by [[Hervé Moulin]] and [[Anna Bogomolnaia]] as a solution for the [[fair random assignment]] problem, where the fraction that each agent receives of each item is interpreted as a probability. If the integral of the eating speed of all agents is 1, then the sum of fractions assigned to each agent is 1, so the matrix of fractions can be decomposed into a lottery over assignments in which each agent gets exactly one item. With equal eating speeds, the lottery is [[envy-free]] in expectation ([[ex-ante]]) for all vectors of utility functions consistent with the agents' item rankings.

	A variant of SE was applied also to [[Fair cake-cutting\|cake-cutting]], where the allocation is deterministic (not random).<ref>{{Cite journal \|last=Aziz \|first=Haris \|last2=Ye \|first2=Chun \|date=2014 \|editor-last=Liu \|editor-first=Tie-Yan \|editor2-last=Qi \|editor2-first=Qi \|editor3-last=Ye \|editor3-first=Yinyu \|title=Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations \|url=https://link.springer.com/chapter/10.1007/978-3-319-13129-0_1 \|journal=Web and Internet Economics \|language=en \|location=Cham \|publisher=Springer International Publishing \|pages=1–14 \|doi=10.1007/978-3-319-13129-0_1 \|isbn=978-3-319-13129-0}}</ref>		A variant of SE was applied also to [[Fair cake-cutting\|cake-cutting]], where the allocation is deterministic (not random).<ref>{{Cite journal \|last=Aziz \|first=Haris \|last2=Ye \|first2=Chun \|date=2014 \|editor-last=Liu \|editor-first=Tie-Yan \|editor2-last=Qi \|editor2-first=Qi \|editor3-last=Ye \|editor3-first=Yinyu \|title=Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations \|url=https://link.springer.com/chapter/10.1007/978-3-319-13129-0_1 \|journal=Web and Internet Economics \|language=en \|location=Cham \|publisher=Springer International Publishing \|pages=1–14 \|doi=10.1007/978-3-319-13129-0_1 \|isbn=978-3-319-13129-0}}</ref>

	== Description ==		== Description ==
Line 50:		Line 50:

	=== Efficiency ===		=== Efficiency ===
	SE with any vector of eating speeds satisfies an efficiency property called '''[[SD-efficiency]]''' (also called ordinal efficiency). Informally it means that, considering the resulting probability matrix, there is no other matrix that all agents weakly-sd-prefer and at least one agent strictly-sd-prefers.		SE with any vector of eating speeds satisfies an efficiency property called '''[[SD-efficiency]]''' (also called ordinal efficiency). Informally it means that, considering the resulting probability matrix, there is no other matrix that all agents weakly-sd-prefer and at least one agent strictly-sd-prefers.

	In the context of random assignments, SD-efficiency implies ex-post efficiency: every deterministic assignment selected by the lottery is [[Pareto-efficient]].		In the context of random assignments, SD-efficiency implies ex-post efficiency: every deterministic assignment selected by the lottery is [[Pareto-efficient]].
Line 109:		Line 109:
	* A polynomial-time algorithm for computing allocations that are ex-ante proportional, and ex-post both PROP1 and 1/2-fraction [[Maximin share\|maximin-share]] (and also 1/2-fraction ''truncated-proportional share'').		* A polynomial-time algorithm for computing allocations that are ex-ante proportional, and ex-post both PROP1 and 1/2-fraction [[Maximin share\|maximin-share]] (and also 1/2-fraction ''truncated-proportional share'').
	* These properties are nearly optimal - it is impossible to guarantee more than PROP ex-ante, and more than ''n''/(2''n''-1) truncated-proportional share ex-post.		* These properties are nearly optimal - it is impossible to guarantee more than PROP ex-ante, and more than ''n''/(2''n''-1) truncated-proportional share ex-post.
	Hoefer, Schmalhofer and Varricchio<ref>{{~~Cite~~ ~~journal~~ \|last=Hoefer \|first=Martin \|last2=Schmalhofer \|first2=Marco \|last3=Varricchio \|first3=Giovanna \|date=2022-09-08 \|title=Best of Both Worlds: Agents with Entitlements \|~~url=http://~~arxiv~~.org/abs/2209.03908 \|journal~~=~~arXiv:~~2209.03908 ~~[cs]~~}}</ref> extend the notion of "Best-of-Both-Worlds" lottery to agents with different [[Entitlement (fair division)\|entitlements]].		Hoefer, Schmalhofer and Varricchio<ref>{{cite arxiv \|last=Hoefer \|first=Martin \|last2=Schmalhofer \|first2=Marco \|last3=Varricchio \|first3=Giovanna \|date=2022-09-08 \|title=Best of Both Worlds: Agents with Entitlements \|arxiv=2209.03908 }}</ref> extend the notion of "Best-of-Both-Worlds" lottery to agents with different [[Entitlement (fair division)\|entitlements]].

	== See also ==		== See also ==

← Previous revision		Revision as of 04:55, 30 January 2023
Line 74:		Line 74:
	Older technical report: https://arxiv.org/abs/1401.6523.</ref>		Older technical report: https://arxiv.org/abs/1401.6523.</ref>
	*Best responses w.r.t. expected utility can cycle. However, a pure [[Nash equilibrium]] exists for any number of agents and items. When there are two agents, there are linear-time algorithms to compute a preference-profile that is in Nash equilibrium w.r.t. the original preferences. In some empirical settings, PS is less prone to manipulation. When an agent is [[Risk aversion\|risk-averse]] and has no information about the other agents' strategies, his [[maximin strategy]] is to be truthful.<ref name=":0" />		*Best responses w.r.t. expected utility can cycle. However, a pure [[Nash equilibrium]] exists for any number of agents and items. When there are two agents, there are linear-time algorithms to compute a preference-profile that is in Nash equilibrium w.r.t. the original preferences. In some empirical settings, PS is less prone to manipulation. When an agent is [[Risk aversion\|risk-averse]] and has no information about the other agents' strategies, his [[maximin strategy]] is to be truthful.<ref name=":0" />
	*A manipulating agent can increase his utility by a factor of at most 3/2. This was first observed empirically on random instances,<ref>{{Cite journal \|last1=Hosseini \|first1=Hadi \|last2=Larson \|first2=Kate \|last3=Cohen \|first3=Robin \|date=2018-07-01 \|title=Investigating the characteristics of one-sided matching mechanisms under various preferences and risk attitudes \|url=https://doi.org/10.1007/s10458-018-9387-y \|journal=Autonomous Agents and Multi-Agent Systems \|language=en \|volume=32 \|issue=4 \|pages=534–567 \|doi=10.1007/s10458-018-9387-y \|arxiv=1703.00320 \|s2cid=14041902 \|issn=1573-7454}}</ref> and then proved formally.<ref>{{Cite journal \|last1=Wang \|first1=Zihe \|last2=Wei \|first2=Zhide \|last3=Zhang \|first3=Jie \|date=2020-04-03 \|title=Bounded Incentives in Manipulating the Probabilistic Serial Rule \|url=https://ojs.aaai.org/index.php/AAAI/article/view/5605 \|journal=Proceedings of the AAAI Conference on Artificial Intelligence \|language=en \|volume=34 \|issue=2 \|pages=2276–2283 \|doi=10.1609/aaai.v34i02.5605 \|s2cid=210943079 \|issn=2374-3468}}</ref>		*A manipulating agent can increase his utility by a factor of at most 3/2. This was first observed empirically on random instances,<ref>{{Cite journal \|last1=Hosseini \|first1=Hadi \|last2=Larson \|first2=Kate \|last3=Cohen \|first3=Robin \|date=2018-07-01 \|title=Investigating the characteristics of one-sided matching mechanisms under various preferences and risk attitudes \|url=https://doi.org/10.1007/s10458-018-9387-y \|journal=Autonomous Agents and Multi-Agent Systems \|language=en \|volume=32 \|issue=4 \|pages=534–567 \|doi=10.1007/s10458-018-9387-y \|arxiv=1703.00320 \|s2cid=14041902 \|issn=1573-7454}}</ref> and then proved formally.<ref>{{Cite journal \|last1=Wang \|first1=Zihe \|last2=Wei \|first2=Zhide \|last3=Zhang \|first3=Jie \|date=2020-04-03 \|title=Bounded Incentives in Manipulating the Probabilistic Serial Rule \|url=https://ojs.aaai.org/index.php/AAAI/article/view/5605 \|journal=Proceedings of the AAAI Conference on Artificial Intelligence \|language=en \|volume=34 \|issue=2 \|pages=2276–2283 \|doi=10.1609/aaai.v34i02.5605 \|s2cid=210943079 \|issn=2374-3468\|doi-access=free }}</ref>
	Note that the [[random priority item allocation\|random priority]] rule, which solves the same problem as PS, is truthful.		Note that the [[random priority item allocation\|random priority]] rule, which solves the same problem as PS, is truthful.

Line 85:		Line 85:
	* Budish, Che, Kojima and Milgrom<ref name=":1">{{Cite journal\|last1=Budish\|first1=Eric\|last2=Che\|first2=Yeon-Koo\|last3=Kojima\|first3=Fuhito\|last4=Milgrom\|first4=Paul\|date=2013-04-01\|title=Designing Random Allocation Mechanisms: Theory and Applications\|url=https://www.aeaweb.org/articles?id=10.1257/aer.103.2.585\|journal=American Economic Review\|language=en\|volume=103\|issue=2\|pages=585–623\|doi=10.1257/aer.103.2.585\|issn=0002-8282}}</ref> present ''Generalized PS'', which allows multiple units per item, more items than agents, each agent can get several units, upper quotas, and bi-hierarchical constraints on the feasible allocations.		* Budish, Che, Kojima and Milgrom<ref name=":1">{{Cite journal\|last1=Budish\|first1=Eric\|last2=Che\|first2=Yeon-Koo\|last3=Kojima\|first3=Fuhito\|last4=Milgrom\|first4=Paul\|date=2013-04-01\|title=Designing Random Allocation Mechanisms: Theory and Applications\|url=https://www.aeaweb.org/articles?id=10.1257/aer.103.2.585\|journal=American Economic Review\|language=en\|volume=103\|issue=2\|pages=585–623\|doi=10.1257/aer.103.2.585\|issn=0002-8282}}</ref> present ''Generalized PS'', which allows multiple units per item, more items than agents, each agent can get several units, upper quotas, and bi-hierarchical constraints on the feasible allocations.
	* Ashlagi, Saberi and Shameli<ref>{{Cite journal \|last1=Ashlagi \|first1=Itai \|last2=Saberi \|first2=Amin \|last3=Shameli \|first3=Ali \|date=2020-03-01 \|title=Assignment Mechanisms Under Distributional Constraints \|url=https://pubsonline.informs.org/doi/abs/10.1287/opre.2019.1887 \|journal=Operations Research \|volume=68 \|issue=2 \|pages=467–479 \|doi=10.1287/opre.2019.1887 \|arxiv=1810.04331 \|issn=0030-364X}}</ref> present another ''Generalized PS'', which allows lower and upper quotas, and distributional constraints (constraints on the probability distribution and not only the final allocation).		* Ashlagi, Saberi and Shameli<ref>{{Cite journal \|last1=Ashlagi \|first1=Itai \|last2=Saberi \|first2=Amin \|last3=Shameli \|first3=Ali \|date=2020-03-01 \|title=Assignment Mechanisms Under Distributional Constraints \|url=https://pubsonline.informs.org/doi/abs/10.1287/opre.2019.1887 \|journal=Operations Research \|volume=68 \|issue=2 \|pages=467–479 \|doi=10.1287/opre.2019.1887 \|arxiv=1810.04331 \|issn=0030-364X}}</ref> present another ''Generalized PS'', which allows lower and upper quotas, and distributional constraints (constraints on the probability distribution and not only the final allocation).
	* Aziz and Stursberg<ref>{{Cite journal \|last1=Aziz \|first1=Haris \|last2=Stursberg \|first2=Paul \|date=2014-06-20 \|title=A Generalization of Probabilistic Serial to Randomized Social Choice \|url=https://ojs.aaai.org/index.php/AAAI/article/view/8796 \|journal=Proceedings of the AAAI Conference on Artificial Intelligence \|language=en \|volume=28 \|issue=1 \|doi=10.1609/aaai.v28i1.8796 \|s2cid=16265016 \|issn=2374-3468}}</ref> present ''Egalitarian Simultaneous Reservation (ESR)'', which allows not only fair item allocation but also general [[Social choice theory\|social choice]] problems, with possible indifferences.		* Aziz and Stursberg<ref>{{Cite journal \|last1=Aziz \|first1=Haris \|last2=Stursberg \|first2=Paul \|date=2014-06-20 \|title=A Generalization of Probabilistic Serial to Randomized Social Choice \|url=https://ojs.aaai.org/index.php/AAAI/article/view/8796 \|journal=Proceedings of the AAAI Conference on Artificial Intelligence \|language=en \|volume=28 \|issue=1 \|doi=10.1609/aaai.v28i1.8796 \|s2cid=16265016 \|issn=2374-3468\|doi-access=free }}</ref> present ''Egalitarian Simultaneous Reservation (ESR)'', which allows not only fair item allocation but also general [[Social choice theory\|social choice]] problems, with possible indifferences.
	* Aziz and Brandl<ref>{{Cite journal \|last1=Aziz \|first1=Haris \|last2=Brandl \|first2=Florian \|date=2022-09-01 \|title=The vigilant eating rule: A general approach for probabilistic economic design with constraints \|url=https://www.sciencedirect.com/science/article/pii/S0899825622001014 \|journal=Games and Economic Behavior \|language=en \|volume=135 \|pages=168–187 \|doi=10.1016/j.geb.2022.06.002 \|arxiv=2008.08991 \|s2cid=221186811 \|issn=0899-8256}}</ref> present ''Vigilant Eating (VE)'', which allows even more general constraints.		* Aziz and Brandl<ref>{{Cite journal \|last1=Aziz \|first1=Haris \|last2=Brandl \|first2=Florian \|date=2022-09-01 \|title=The vigilant eating rule: A general approach for probabilistic economic design with constraints \|url=https://www.sciencedirect.com/science/article/pii/S0899825622001014 \|journal=Games and Economic Behavior \|language=en \|volume=135 \|pages=168–187 \|doi=10.1016/j.geb.2022.06.002 \|arxiv=2008.08991 \|s2cid=221186811 \|issn=0899-8256}}</ref> present ''Vigilant Eating (VE)'', which allows even more general constraints.

← Previous revision		Revision as of 04:28, 26 September 2022
Line 5:		Line 5:
	SE was developed by [[Hervé Moulin]] and [[Anna Bogomolnaia]] as a solution for the [[fair random assignment]] problem, where the fraction that each agent receives of each item is interpreted as a probability. If the integral of the eating speed of all agents is 1, then the sum of fractions assigned to each agent is 1, so the matrix of fractions can be decomposed into a lottery over assignments in which each agent gets exactly one item. With equal eating speeds, the lottery is [[envy-free]] in expectation ([[ex-ante]]) for all vectors of utility functions consistent with the agents' item rankings.		SE was developed by [[Hervé Moulin]] and [[Anna Bogomolnaia]] as a solution for the [[fair random assignment]] problem, where the fraction that each agent receives of each item is interpreted as a probability. If the integral of the eating speed of all agents is 1, then the sum of fractions assigned to each agent is 1, so the matrix of fractions can be decomposed into a lottery over assignments in which each agent gets exactly one item. With equal eating speeds, the lottery is [[envy-free]] in expectation ([[ex-ante]]) for all vectors of utility functions consistent with the agents' item rankings.

	A variant of SE was applied also to [[Fair cake-cutting\|cake-cutting]], where the allocation is deterministic (not random).<ref>{{Cite journal \|~~last~~=Aziz \|~~first~~=Haris \|last2=Ye \|first2=Chun \|date=2014 \|editor-last=Liu \|editor-first=Tie-Yan \|editor2-last=Qi \|editor2-first=Qi \|editor3-last=Ye \|editor3-first=Yinyu \|title=Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations \|url=https://link.springer.com/chapter/10.1007/978-3-319-13129-0_1 \|journal=Web and Internet Economics \|language=en \|location=Cham \|publisher=Springer International Publishing \|pages=1–14 \|doi=10.1007/978-3-319-13129-0_1 \|isbn=978-3-319-13129-0}}</ref>		A variant of SE was applied also to [[Fair cake-cutting\|cake-cutting]], where the allocation is deterministic (not random).<ref>{{Cite journal \|last1=Aziz \|first1=Haris \|last2=Ye \|first2=Chun \|date=2014 \|editor-last=Liu \|editor-first=Tie-Yan \|editor2-last=Qi \|editor2-first=Qi \|editor3-last=Ye \|editor3-first=Yinyu \|title=Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations \|url=https://link.springer.com/chapter/10.1007/978-3-319-13129-0_1 \|journal=Web and Internet Economics \|series=Lecture Notes in Computer Science \|volume=8877 \|language=en \|location=Cham \|publisher=Springer International Publishing \|pages=1–14 \|doi=10.1007/978-3-319-13129-0_1 \|isbn=978-3-319-13129-0\|s2cid=18365892 }}</ref>

	== Description ==		== Description ==
Line 74:		Line 74:
	Older technical report: https://arxiv.org/abs/1401.6523.</ref>		Older technical report: https://arxiv.org/abs/1401.6523.</ref>
	*Best responses w.r.t. expected utility can cycle. However, a pure [[Nash equilibrium]] exists for any number of agents and items. When there are two agents, there are linear-time algorithms to compute a preference-profile that is in Nash equilibrium w.r.t. the original preferences. In some empirical settings, PS is less prone to manipulation. When an agent is [[Risk aversion\|risk-averse]] and has no information about the other agents' strategies, his [[maximin strategy]] is to be truthful.<ref name=":0" />		*Best responses w.r.t. expected utility can cycle. However, a pure [[Nash equilibrium]] exists for any number of agents and items. When there are two agents, there are linear-time algorithms to compute a preference-profile that is in Nash equilibrium w.r.t. the original preferences. In some empirical settings, PS is less prone to manipulation. When an agent is [[Risk aversion\|risk-averse]] and has no information about the other agents' strategies, his [[maximin strategy]] is to be truthful.<ref name=":0" />
	*A manipulating agent can increase his utility by a factor of at most 3/2. This was first observed empirically on random instances,<ref>{{Cite journal \|~~last~~=Hosseini \|~~first~~=Hadi \|last2=Larson \|first2=Kate \|last3=Cohen \|first3=Robin \|date=2018-07-01 \|title=Investigating the characteristics of one-sided matching mechanisms under various preferences and risk attitudes \|url=https://doi.org/10.1007/s10458-018-9387-y \|journal=Autonomous Agents and Multi-Agent Systems \|language=en \|volume=32 \|issue=4 \|pages=534–567 \|doi=10.1007/s10458-018-9387-y \|issn=1573-7454}}</ref> and then proved formally.<ref>{{Cite journal \|~~last~~=Wang \|~~first~~=Zihe \|last2=Wei \|first2=Zhide \|last3=Zhang \|first3=Jie \|date=2020-04-03 \|title=Bounded Incentives in Manipulating the Probabilistic Serial Rule \|url=https://ojs.aaai.org/index.php/AAAI/article/view/5605 \|journal=Proceedings of the AAAI Conference on Artificial Intelligence \|language=en \|volume=34 \|issue=02 \|pages=2276–2283 \|doi=10.1609/aaai.v34i02.5605 \|issn=2374-3468}}</ref>		*A manipulating agent can increase his utility by a factor of at most 3/2. This was first observed empirically on random instances,<ref>{{Cite journal \|last1=Hosseini \|first1=Hadi \|last2=Larson \|first2=Kate \|last3=Cohen \|first3=Robin \|date=2018-07-01 \|title=Investigating the characteristics of one-sided matching mechanisms under various preferences and risk attitudes \|url=https://doi.org/10.1007/s10458-018-9387-y \|journal=Autonomous Agents and Multi-Agent Systems \|language=en \|volume=32 \|issue=4 \|pages=534–567 \|doi=10.1007/s10458-018-9387-y \|arxiv=1703.00320 \|s2cid=14041902 \|issn=1573-7454}}</ref> and then proved formally.<ref>{{Cite journal \|last1=Wang \|first1=Zihe \|last2=Wei \|first2=Zhide \|last3=Zhang \|first3=Jie \|date=2020-04-03 \|title=Bounded Incentives in Manipulating the Probabilistic Serial Rule \|url=https://ojs.aaai.org/index.php/AAAI/article/view/5605 \|journal=Proceedings of the AAAI Conference on Artificial Intelligence \|language=en \|volume=34 \|issue=2 \|pages=2276–2283 \|doi=10.1609/aaai.v34i02.5605 \|s2cid=210943079 \|issn=2374-3468}}</ref>
	Note that the [[random priority item allocation\|random priority]] rule, which solves the same problem as PS, is truthful.		Note that the [[random priority item allocation\|random priority]] rule, which solves the same problem as PS, is truthful.

Line 82:		Line 82:
	* Bogomolnaia<ref name=":2" /> presented a simpler definition of the PS rule for weak preferences, based on the [[leximin order]].		* Bogomolnaia<ref name=":2" /> presented a simpler definition of the PS rule for weak preferences, based on the [[leximin order]].
	* Yilmaz<ref name="y09">{{cite journal \|last1=Yılmaz \|first1=Özgür \|year=2009 \|title=Random assignment under weak preferences \|url=http://cdm21054.contentdm.oclc.org/cdm/ref/collection/IR/id/6207 \|journal=Games and Economic Behavior \|volume=66 \|pages=546–558 \|doi=10.1016/j.geb.2008.04.017}}</ref> allows both indifferences and endowments.		* Yilmaz<ref name="y09">{{cite journal \|last1=Yılmaz \|first1=Özgür \|year=2009 \|title=Random assignment under weak preferences \|url=http://cdm21054.contentdm.oclc.org/cdm/ref/collection/IR/id/6207 \|journal=Games and Economic Behavior \|volume=66 \|pages=546–558 \|doi=10.1016/j.geb.2008.04.017}}</ref> allows both indifferences and endowments.
	* Athanassoglout and Sethuraman<ref>{{Cite journal \|~~last~~=Athanassoglou \|~~first~~=Stergios \|last2=Sethuraman \|first2=Jay \|date=2011-08-01 \|title=House allocation with fractional endowments \|url=https://doi.org/10.1007/s00182-010-0251-9 \|journal=International Journal of Game Theory \|language=en \|volume=40 \|issue=3 \|pages=481–513 \|doi=10.1007/s00182-010-0251-9 \|issn=1432-1270}}</ref> present the ''controlled consuming (CC)'' rule, which allows indifferences and fractional endowments of any quantity.		* Athanassoglout and Sethuraman<ref>{{Cite journal \|last1=Athanassoglou \|first1=Stergios \|last2=Sethuraman \|first2=Jay \|date=2011-08-01 \|title=House allocation with fractional endowments \|url=https://doi.org/10.1007/s00182-010-0251-9 \|journal=International Journal of Game Theory \|language=en \|volume=40 \|issue=3 \|pages=481–513 \|doi=10.1007/s00182-010-0251-9 \|s2cid=15909570 \|issn=1432-1270}}</ref> present the ''controlled consuming (CC)'' rule, which allows indifferences and fractional endowments of any quantity.
	* Budish, Che, Kojima and Milgrom<ref name=":1">{{Cite journal\|last1=Budish\|first1=Eric\|last2=Che\|first2=Yeon-Koo\|last3=Kojima\|first3=Fuhito\|last4=Milgrom\|first4=Paul\|date=2013-04-01\|title=Designing Random Allocation Mechanisms: Theory and Applications\|url=https://www.aeaweb.org/articles?id=10.1257/aer.103.2.585\|journal=American Economic Review\|language=en\|volume=103\|issue=2\|pages=585–623\|doi=10.1257/aer.103.2.585\|issn=0002-8282}}</ref> present ''Generalized PS'', which allows multiple units per item, more items than agents, each agent can get several units, upper quotas, and bi-hierarchical constraints on the feasible allocations.		* Budish, Che, Kojima and Milgrom<ref name=":1">{{Cite journal\|last1=Budish\|first1=Eric\|last2=Che\|first2=Yeon-Koo\|last3=Kojima\|first3=Fuhito\|last4=Milgrom\|first4=Paul\|date=2013-04-01\|title=Designing Random Allocation Mechanisms: Theory and Applications\|url=https://www.aeaweb.org/articles?id=10.1257/aer.103.2.585\|journal=American Economic Review\|language=en\|volume=103\|issue=2\|pages=585–623\|doi=10.1257/aer.103.2.585\|issn=0002-8282}}</ref> present ''Generalized PS'', which allows multiple units per item, more items than agents, each agent can get several units, upper quotas, and bi-hierarchical constraints on the feasible allocations.
	* Ashlagi, Saberi and Shameli<ref>{{Cite journal \|~~last~~=Ashlagi \|~~first~~=Itai \|last2=Saberi \|first2=Amin \|last3=Shameli \|first3=Ali \|date=2020-03-01 \|title=Assignment Mechanisms Under Distributional Constraints \|url=https://pubsonline.informs.org/doi/abs/10.1287/opre.2019.1887 \|journal=Operations Research \|volume=68 \|issue=2 \|pages=467–479 \|doi=10.1287/opre.2019.1887 \|issn=0030-364X}}</ref> present another ''Generalized PS'', which allows lower and upper quotas, and distributional constraints (constraints on the probability distribution and not only the final allocation).		* Ashlagi, Saberi and Shameli<ref>{{Cite journal \|last1=Ashlagi \|first1=Itai \|last2=Saberi \|first2=Amin \|last3=Shameli \|first3=Ali \|date=2020-03-01 \|title=Assignment Mechanisms Under Distributional Constraints \|url=https://pubsonline.informs.org/doi/abs/10.1287/opre.2019.1887 \|journal=Operations Research \|volume=68 \|issue=2 \|pages=467–479 \|doi=10.1287/opre.2019.1887 \|arxiv=1810.04331 \|issn=0030-364X}}</ref> present another ''Generalized PS'', which allows lower and upper quotas, and distributional constraints (constraints on the probability distribution and not only the final allocation).
	* Aziz and Stursberg<ref>{{Cite journal \|~~last~~=Aziz \|~~first~~=Haris \|last2=Stursberg \|first2=Paul \|date=2014-06-20 \|title=A Generalization of Probabilistic Serial to Randomized Social Choice \|url=https://ojs.aaai.org/index.php/AAAI/article/view/8796 \|journal=Proceedings of the AAAI Conference on Artificial Intelligence \|language=en \|volume=28 \|issue=1 \|doi=10.1609/aaai.v28i1.8796 \|issn=2374-3468}}</ref> present ''Egalitarian Simultaneous Reservation (ESR)'', which allows not only fair item allocation but also general [[Social choice theory\|social choice]] problems, with possible indifferences.		* Aziz and Stursberg<ref>{{Cite journal \|last1=Aziz \|first1=Haris \|last2=Stursberg \|first2=Paul \|date=2014-06-20 \|title=A Generalization of Probabilistic Serial to Randomized Social Choice \|url=https://ojs.aaai.org/index.php/AAAI/article/view/8796 \|journal=Proceedings of the AAAI Conference on Artificial Intelligence \|language=en \|volume=28 \|issue=1 \|doi=10.1609/aaai.v28i1.8796 \|s2cid=16265016 \|issn=2374-3468}}</ref> present ''Egalitarian Simultaneous Reservation (ESR)'', which allows not only fair item allocation but also general [[Social choice theory\|social choice]] problems, with possible indifferences.
	* Aziz and Brandl<ref>{{Cite journal \|~~last~~=Aziz \|~~first~~=Haris \|last2=Brandl \|first2=Florian \|date=2022-09-01 \|title=The vigilant eating rule: A general approach for probabilistic economic design with constraints \|url=https://www.sciencedirect.com/science/article/pii/S0899825622001014 \|journal=Games and Economic Behavior \|language=en \|volume=135 \|pages=168–187 \|doi=10.1016/j.geb.2022.06.002 \|issn=0899-8256}}</ref> present ''Vigilant Eating (VE)'', which allows even more general constraints.		* Aziz and Brandl<ref>{{Cite journal \|last1=Aziz \|first1=Haris \|last2=Brandl \|first2=Florian \|date=2022-09-01 \|title=The vigilant eating rule: A general approach for probabilistic economic design with constraints \|url=https://www.sciencedirect.com/science/article/pii/S0899825622001014 \|journal=Games and Economic Behavior \|language=en \|volume=135 \|pages=168–187 \|doi=10.1016/j.geb.2022.06.002 \|arxiv=2008.08991 \|s2cid=221186811 \|issn=0899-8256}}</ref> present ''Vigilant Eating (VE)'', which allows even more general constraints.

	== Guaranteeing ex-post approximate fairness ==		== Guaranteeing ex-post approximate fairness ==
Line 98:		Line 98:
	* The RecPS can be modified to attain similar guarantees (ex-ante EF and ex-post EF1) for bads.		* The RecPS can be modified to attain similar guarantees (ex-ante EF and ex-post EF1) for bads.

	Aziz<ref>{{Cite journal \|last=Aziz \|first=Haris \|date=2020-12-07 \|title=Simultaneously Achieving Ex-ante and Ex-post Fairness \|url=https://doi.org/10.1007/978-3-030-64946-3_24 \|journal=Web and Internet Economics: 16th International Conference, WINE 2020, Beijing, China, December 7–11, 2020, Proceedings \|location=Berlin, Heidelberg \|publisher=Springer-Verlag \|pages=341–355 \|doi=10.1007/978-3-030-64946-3_24 \|isbn=978-3-030-64945-6}}</ref> shows:		Aziz<ref>{{Cite journal \|last=Aziz \|first=Haris \|date=2020-12-07 \|title=Simultaneously Achieving Ex-ante and Ex-post Fairness \|url=https://doi.org/10.1007/978-3-030-64946-3_24 \|journal=Web and Internet Economics: 16th International Conference, WINE 2020, Beijing, China, December 7–11, 2020, Proceedings \|series=Lecture Notes in Computer Science \|volume=12495 \|location=Berlin, Heidelberg \|publisher=Springer-Verlag \|pages=341–355 \|doi=10.1007/978-3-030-64946-3_24 \|arxiv=2004.02554 \|isbn=978-3-030-64945-6\|s2cid=214802174 }}</ref> shows:

	* The '''PS-lottery algorithm''', in which the allocation is ex-ante sd-EF, and the lottery is done only among deterministic allocations that are sd-EF1, i.e., the EF and EF1 guarantees hold for ''any'' cardinal utilities consistent with the ordinal ranking. Moreover, the outcome is sd-PO both ex-ante and ex-post. The algorithm uses as subroutines both the PS algorithm and the [[Birkhoff algorithm]]. The ex-ante allocation is equivalent to the one returned by PS; this shows that the outcome of PS can be decomposed into EF1 allocations.		* The '''PS-lottery algorithm''', in which the allocation is ex-ante sd-EF, and the lottery is done only among deterministic allocations that are sd-EF1, i.e., the EF and EF1 guarantees hold for ''any'' cardinal utilities consistent with the ordinal ranking. Moreover, the outcome is sd-PO both ex-ante and ex-post. The algorithm uses as subroutines both the PS algorithm and the [[Birkhoff algorithm]]. The ex-ante allocation is equivalent to the one returned by PS; this shows that the outcome of PS can be decomposed into EF1 allocations.
Line 109:		Line 109:
	* A polynomial-time algorithm for computing allocations that are ex-ante proportional, and ex-post both PROP1 and 1/2-fraction [[Maximin share\|maximin-share]] (and also 1/2-fraction ''truncated-proportional share'').		* A polynomial-time algorithm for computing allocations that are ex-ante proportional, and ex-post both PROP1 and 1/2-fraction [[Maximin share\|maximin-share]] (and also 1/2-fraction ''truncated-proportional share'').
	* These properties are nearly optimal - it is impossible to guarantee more than PROP ex-ante, and more than ''n''/(2''n''-1) truncated-proportional share ex-post.		* These properties are nearly optimal - it is impossible to guarantee more than PROP ex-ante, and more than ''n''/(2''n''-1) truncated-proportional share ex-post.
	Hoefer, Schmalhofer and Varricchio<ref>{{cite ~~arxiv~~ \|~~last~~=Hoefer \|~~first~~=Martin \|last2=Schmalhofer \|first2=Marco \|last3=Varricchio \|first3=Giovanna \|date=2022-09-08 \|title=Best of Both Worlds: Agents with Entitlements \|~~arxiv~~=2209.03908 }}</ref> extend the notion of "Best-of-Both-Worlds" lottery to agents with different [[Entitlement (fair division)\|entitlements]].		Hoefer, Schmalhofer and Varricchio<ref>{{cite arXiv \|last1=Hoefer \|first1=Martin \|last2=Schmalhofer \|first2=Marco \|last3=Varricchio \|first3=Giovanna \|date=2022-09-08 \|title=Best of Both Worlds: Agents with Entitlements \|class=cs.GT \|eprint=2209.03908 }}</ref> extend the notion of "Best-of-Both-Worlds" lottery to agents with different [[Entitlement (fair division)\|entitlements]].

	== See also ==		== See also ==