Procedimiento AL
Un procedimiento AL es un procedimiento para distribuir objetos equitativamente entre dos personas. El procedimiento encuentra una distribución de un subconjunto de objetos que estarán libres de envidia . Además, la distribución resultante es eficiente en el sentido de Pareto en el siguiente sentido: no existe una distribución libre de envidia que sea mejor para una persona y no peor para otra.
El procedimiento AL fue publicado por primera vez por Brahms y Klamler [1] . Más tarde, Aziz lo generalizó para el caso en que los agentes no pueden distinguir ciertos objetos por su significado [2] .
Suposiciones
AL-procedimiento para el cumplimiento de las siguientes condiciones:
- Cada persona puede clasificar los elementos de mejor a peor (es decir, cada persona puede proporcionar una relación de preferencia estricta [3] sobre los elementos).
- Cada persona tiene una relación de preferencia sobre conjuntos de elementos que es compatible con la extensión adaptativa de la ordenación de elementos.
Requisitos
NO se pretende que una persona pueda indicar sus preferencias en los conjuntos de elementos. Hay muchos conjuntos disponibles y puede ser difícil compilar una lista completa de preferencias en conjuntos de artículos.
Por lo tanto, el procedimiento debe dar una distribución libre de envidia para cualquier relación de preferencia que sea consistente con el orden de los elementos y la aditividad débil . En otras palabras, el procedimiento debe devolver una distribución en la que definitivamente no habrá envidia (necesariamente sin envidia, OBZ-distribution, inglés necesariamente sin envidia , NEF) [4] .
Que las dos caras sean Alice y George. Una distribución es una distribución OBZ para Alice si la inyección de f de los artículos de George en los artículos de Alice es tal que para cada artículo x recibido por George, Alice prefiere el artículo f ( x ) sobre el artículo x . La distribución es una distribución OBZ para George si se cumple la propiedad simétrica. Una distribución de artículos es una distribución OBZ si es una distribución OBZ para ambos socios. Tenga en cuenta que en la distribución OBZ, Alice y George reciben la misma cantidad de artículos.
La asignación vacía es obviamente una asignación OBZ, pero es muy ineficiente. Por lo tanto, buscamos la "mejor" distribución entre todas las distribuciones OBZ. Una distribución OBZ se llama Pareto eficiente si no hay otra distribución OBZ que sea mejor para un elemento y peor para otro.
Procedimiento BT
Como introducción, presentamos el siguiente procedimiento de división simple:
- Coloque todos los elementos sobre la mesa.
- Mientras haya elementos sobre la mesa, haga lo siguiente:
- Se les pide a los participantes que elijan su artículo preferido de los artículos en la mesa.
- Si se seleccionan elementos diferentes, le damos a cada participante el elemento seleccionado y continuamos.
- Si hay una coincidencia, coloque el artículo seleccionado en la "Pila en disputa". Este artículo no se distribuye.
Este procedimiento devuelve la distribución OBZ. El procedimiento es muy simple, pero no muy efectivo, ya que se arrojará una gran cantidad de elementos a la "Pila de concurso". El procedimiento AL es un poco más complicado, pero garantiza que el Montón disputado nunca sea más grande que el montón resultante en el procedimiento BT, pero puede ser más pequeño.
Procedimiento AL
El procedimiento AL funciona de manera similar al procedimiento BT, pero antes de ser enviado a la "Pila en disputa", el procedimiento intenta dar el artículo a un participante, como compensación , para darle al otro participante otro artículo. Solo cuando dicha compensación falla, el artículo se envía a la "Pila en disputa".
Por ejemplo, supongamos que hay cuatro sujetos (1, 2, 3, 4) y las preferencias de los participantes son las siguientes:
- Alicia: 1 > 2 > 3 > 4
- Jorge: 2 > 3 > 4 > 1
El procedimiento BT le da el ítem 1 a Alice y el ítem 2 a George porque son los más deseables y son diferentes. Ahora, tanto Alice como George eligen el elemento 3, por lo que se descarta. Ahora ambos eligen el ítem 4 y también se descarta. Distribución final: Alice George . La distribución es una distribución OBZ pero no es eficiente en el sentido de Pareto.
El procedimiento AL también comienza entregando el artículo 1 a Alice y el artículo 2 a George. Ahora, en lugar de descartar el elemento 3, el procedimiento se lo da a Alice, y George recibe el elemento 4 para compensar.Distribución final: Alice George La distribución es una distribución OBZ y es eficiente en el sentido de Pareto.
Ambos procedimientos están disponibles para la manipulación: el participante puede obtener ganancias adicionales al indicar las preferencias incorrectas. Sin embargo, tal manipulación requiere el conocimiento de las preferencias de los socios, por lo que es difícil de usar en la práctica.
Procedimiento AL con indistinguibilidad de objetos
El procedimiento AL original se basa fundamentalmente en la suposición de que el orden de los elementos es estricto (no indistinguibles). Aziz [5] generalizó este procedimiento a pedidos generales con posibilidad de tener objetos indistinguibles.
Notas
- ↑ Brams, Kilgour, Klamler, 2014 , pág. 130.
- ↑ Aziz, 2015 , pág. 307–324.
- ↑ Aquí, estricto significa que para un participante no puede haber dos objetos que no distinga en importancia.
- ↑ Brandt, Conitzer et al., 2016 , pág. 303.
- ↑ Aziz, 2015 , pág. 307-324.
Literatura
- Steven J. Brams, D. Marc Kilgour, Christian Klamler. División justa de dos personas de elementos indivisibles: un algoritmo eficiente y sin envidia // Avisos de la Sociedad Matemática Estadounidense. - 2014. - febrero ( vol. 61 , número 2 ). -doi : 10.1090/ noti1075 .
- Haris Aziz. Una generalización del método AL para la asignación justa de objetos indivisibles // Boletín de teoría económica. - 2015. - Vol. 4 , núm. 2 . -doi : 10.1007/ s40505-015-0089-1 . -arXiv : 1409.6765 . _
- Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, Ariel D. Procaccia. Manual de Elección Social Computacional . - Cambridge University Press, 2016. - ISBN 9781107060432 . ( versión en línea )