Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Simultaneous eating algorithm
open-in-new
<p>A simultaneous eating algorithm (SE) is an algorithm for allocating divisible objects among agents with <a href="/facts/Ordinal_preferences/pFbpa2dg">ordinal preferences</a>. </p><p>"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 <a href="/facts/SD-efficiency/qKs2yTkw">SD-efficiency</a> - a weak ordinal variant of Pareto-efficiency (it means that the allocation is Pareto-efficient for <i>at least one</i> vector of <a href="/facts/Additive_utility/xWMFGEeN">additive utility functions</a> consistent with the agents' item rankings). </p><p>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 <a href="/facts/Envy-freeness/LbsxvkUR">envy-freeness</a> (it means that the allocation is envy-free for <i>all</i> vectors of additive utility functions consistent with the agents' item rankings). This particular variant of SE is called the Probabilistic Serial rule (PS). </p><p>SE was developed by <a href="/facts/Herv%C3%A9_Moulin/bXdekNvG">Hervé Moulin</a> and <a href="/facts/Anna_Bogomolnaia/Um4aesrC">Anna Bogomolnaia</a> as a solution for the <a href="/facts/Fair_random_assignment/x9KjoBq1">fair random assignment</a> 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 <a href="/facts/Envy-free/LbsxvkUR">envy-free</a> in expectation (<a href="/facts/Ex-ante/yJUjQe0M">ex-ante</a>) for all vectors of utility functions consistent with the agents' item rankings. </p><p>A variant of SE was applied also to <a href="/facts/Fair_cake-cutting/76gbq4GE">cake-cutting</a>, where the allocation is deterministic (not random). </p>