El procedimiento de gráfico de envidia (también llamado procedimiento de ciclos de envidia ) es un procedimiento para la asignación justa de elementos . Puede ser utilizado por varias personas que deseen dividir entre ellas varios artículos discretos, como reliquias familiares, dulces o asientos en una clase.
Idealmente, nos gustaría que la asignación esté libre de envidia (EF). es decir, dar a cada agente un paquete que prefiera sobre los paquetes de todos los demás agentes. Sin embargo, los artículos son discretos y no se pueden cortar, por lo que una asignación sin envidia podría ser imposible (por ejemplo, considere un solo artículo y dos agentes). El procedimiento del gráfico de envidia tiene como objetivo lograr la opción "siguiente mejor": la ausencia de envidia hasta como máximo un solo bien (EF1): encuentra una asignación en la que la envidia de cada persona hacia cualquier otra persona está limitada por el máxima utilidad marginal que se deriva de un solo artículo. En otras palabras, por cada dos personas i y j , existe un ítem tal que, si se quita ese ítem, i no envidia a j.
El procedimiento fue presentado por Lipton y Markakis y Mossel y Saberi [1] y también se describe en . [2] : 300–301
El procedimiento del gráfico de envidia asume que cada persona tiene una función de utilidad cardinal en paquetes de artículos. Esta función de utilidad tiene que ser monótona (la utilidad de un conjunto es al menos tan grande como la utilidad de sus subconjuntos). Sin embargo, no tiene que ser aditivo. Es decir, no se supone que los artículos sean bienes independientes .
Los agentes no tienen que informar realmente su utilidad cardinal: es suficiente que sepan cómo clasificar los paquetes.
En el paso 2, si no hay ningún agente no envidiado, significa que hay un ciclo dirigido en el gráfico de envidia , un gráfico dirigido en el que cada agente señala a todos los agentes que envidia. Los ciclos se pueden eliminar mediante el intercambio cíclico de paquetes. Después de eliminar todos los ciclos, el gráfico de envidia debe tener un nodo sin bordes entrantes; este nodo representa un agente no envidiado.