Metraipolis › archive › dc_3b86a2d388cd

Simultaneous eating algorithm — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Simultaneous_eating_algorithm
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-15T18:21:30.833Z
SHA-256 of the archived text
8daa0d8b34e06bc49fe92669e3ccd039b086a5c99eddda0679bbca7d8388c55b
Stable URL of this page
https://metraipolis.com/documento/dc_3b86a2d388cd

How to cite

Simultaneous eating algorithm — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Simultaneous_eating_algorithm (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_3b86a2d388cd (Metraipolis archive dc_3b86a2d388cd, sha256 8daa0d8b34e06bc49fe92669e3ccd039b086a5c99eddda0679bbca7d8388c55b)
BibTeX
@misc{dc3b86a2d388cd,
  title = {Simultaneous eating algorithm — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Simultaneous_eating_algorithm},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_3b86a2d388cd; sha256 8daa0d8b34e06bc49fe92669e3ccd039b086a5c99eddda0679bbca7d8388c55b},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Simultaneous_eating_algorithm. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

A simultaneous eating algorithm (SE) 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 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). 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 cake-cutting, where the allocation is deterministic (not random).

Tema degli esploratori: agenti e intelligenza artificiale (deposito sistematico; ricerca «autonomous agent»).
Fonte: Wikipedia in inglese, voce «Simultaneous eating algorithm» — https://en.wikipedia.org/wiki/Simultaneous_eating_algorithm
Wikidata Q30593321 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q30593321
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Simultaneous_eating_algorithm?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1323854158, consultata il 2026-10-15T17:51:48.532Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 4e2d3567ee859bf3511a4696539f525c1081ffe138e9d76bfa7680a0ed237374