stringtranslate.com

Procedimiento de ganador ajustado

Logo

El ganador ajustado (AW) es un algoritmo para la asignación de artículos sin envidia . Dadas dos partes y algunos bienes discretos, devuelve una partición de los bienes entre las dos partes que es:

  1. Sin envidia : cada parte cree que su parte de los bienes es tan buena o mejor que la de su oponente;
  2. Equitativo : Los "niveles relativos de felicidad" de ambas partes a partir de sus acciones son iguales;
  3. Óptimo de Pareto : ninguna otra asignación es mejor para una parte y al menos igual de buena para la otra; y
  4. Implica dividir como máximo un bien entre las partes.

Es el único procedimiento que puede satisfacer las cuatro propiedades simultáneamente. [1] Sin embargo, a pesar de esto, no hay relatos de que el algoritmo se haya utilizado realmente para resolver disputas.

El procedimiento fue diseñado por Steven Brams y Alan D. Taylor y publicado en su libro sobre división justa [2] : 65–94  y posteriormente en un libro independiente. [3] [ página necesaria ] La ganancia ajustada estaba patentada anteriormente en los Estados Unidos, pero expiró en 2016. [4]

Algoritmo

Cada parte recibe la lista de bienes y un número igual y fijo de puntos para distribuir entre ellos. Luego asignan valores a cada bien y presentan su lista (sellada) de ofertas a un árbitro, quien asigna cada artículo al mejor postor.

Si el valor combinado de los bienes de una parte es mayor que el de la otra, el algoritmo ordena los bienes de la parte de mayor valor en orden creciente según la relación y comienza a transferirlos de la parte de mayor valor combinado a la de menor valor combinado. valoran a la parte hasta que sus valoraciones sean casi iguales (mover más bienes causaría que la parte con menor valor combinado tenga ahora un valor combinado más alto que la otra). Luego, el siguiente bien se divide entre las partes de modo que sus valores sean los mismos.

A modo de ejemplo, si dos partes tienen las siguientes valoraciones de cuatro bienes:

Los bienes se dividirían primero de manera que Alicia reciba el bien 1, mientras que Bob reciba los bienes 2, 3 y 4. En este punto, la valoración combinada de Alicia de sus bienes es 86, mientras que la de Bob es 81 + 60 + 40 = 181; como tal, los productos de Bob se ordenan según la proporción , lo que da

Mover el bien 2 de Bob a Alice provocaría que Alice tuviera una valoración mayor que la de Bob (161 frente a 100), por lo que no se transfieren bienes. En cambio, el bien 2 se divide entre Alice y Bob: Alice recibe la cuarta parte del bien (aproximadamente el 60,9%), mientras que Bob recibe la cuarta parte (aproximadamente el 39,1%). Sus valoraciones ahora se convierten en y respectivamente, que son iguales.

Simulaciones

No hay casos en los que se utilice el Ganador Ajustado para resolver disputas de la vida real. Sin embargo, algunos estudios han simulado cómo habrían resultado ciertas disputas si se hubiera utilizado el algoritmo, incluyendo

Limitaciones

AW no es un mecanismo veraz : una parte puede ganar espiando a su oponente y modificando sus informes para obtener una porción mayor. [2] Sin embargo, el Ganador Ajustado siempre tiene un equilibrio de Nash aproximado y, en caso de desempate informado, también un equilibrio de Nash puro. [1]

Tal como está patentado, el algoritmo supone que las partes tienen funciones de utilidad aditivas : el valor de sus bienes es igual a la suma de los valores de los bienes individuales. No maneja, por ejemplo, múltiples instancias de un bien con utilidades marginales decrecientes .

El algoritmo también está diseñado sólo para dos partes; cuando hay tres o más partes, puede que no haya ninguna asignación que sea simultáneamente libre de envidia, equitativa y óptima en términos de Pareto. Esto se puede demostrar con el siguiente ejemplo, construido por JHReijnierse, [2] : 82–83  que involucra a tres partes y sus valoraciones:

La única asignación Pareto óptima y equitativa sería la que le daría el bien 1 a Alice, el bien 2 a Bob y el bien 3 a Carl; sin embargo, esta asignación no estaría libre de envidia ya que Alice envidiaría a Bob.

Dos de estas tres propiedades pueden satisfacerse simultáneamente:

Además, es posible encontrar una asignación que, aunque sea óptima en el sentido de Pareto/libre de envidia o óptima en el sentido de Pareto/equitativa, minimice el número de objetos que deben compartirse entre dos o más partes. Esto suele considerarse la generalización del procedimiento de Ganador Ajustado a tres o más partidos. [10]

Winner ajustado está diseñado para agentes con valoraciones positivas sobre los artículos. Sin embargo, se puede generalizar para partidos con valoraciones mixtas (positivas y negativas). [11]

Trámites relacionados

El procedimiento Brams-Taylor fue diseñado por los mismos autores, pero es más bien un procedimiento para cortar el pastel sin envidia : maneja recursos heterogéneos ("pastel") que son más difíciles de dividir que los bienes homogéneos de la ganancia ajustada. [ ¿cómo? ] Por lo tanto, BT sólo garantiza la ausencia de envidia, no ningún otro atributo.

El artículo sobre experimentos de división justa describe algunos experimentos de laboratorio que comparan AW con procedimientos relacionados.

Referencias

  1. ^ ab Aziz, Haris.; Brânzei, Simina; Filos-Ratsikas, Aris; Søren Kristoffer Stiil, Søren (2015). "El procedimiento ganador ajustado: caracterizaciones y equilibrios". Actas de la Vigésima Cuarta Conferencia Internacional Conjunta sobre Inteligencia Artificial . págs. 454–460. arXiv : 1503.06665 . Código Bib : 2015arXiv150306665A.
  2. ^ abcd Brams, Steven J.; Taylor, Alan D. (1996). "División justa: del corte del pastel a la resolución de disputas" . Prensa de la Universidad de Cambridge. ISBN 0-521-55644-9.
  3. ^ Steven J. Brams y Alan D. Taylr (2000). La solución beneficiosa para todos: garantizar una participación justa para todos . Norton. ISBN 978-0393320817.
  4. ^ Patente estadounidense 5.983.205 , Método informático para la división justa de la propiedad de bienes .
  5. ^ Brams, Steven J.; Togman, Jeffrey M. (1996). "Camp David: ¿Fue justo el acuerdo?". Gestión de conflictos y ciencias de la paz . 15 (1): 99-112. doi :10.1177/073889429601500105. ISSN  0738-8942. S2CID  154854128.
  6. ^ Massoud, Tansa George (1 de junio de 2000). "División justa, procedimiento de ganador ajustado (AW) y el conflicto palestino-israelí". Revista de resolución de conflictos . 44 (3): 333–358. doi :10.1177/0022002700044003003. ISSN  0022-0027. S2CID  154593488.
  7. ^ Mediodía, DBH; Brams, SJ (1 de febrero de 1997). "División justa: un nuevo enfoque a la controversia de las islas Spratly". Negociación Internacional . 2 (2): 303–329. doi :10.1163/15718069720847997. ISSN  1571-8069.
  8. ^ Willson, Stephen J. (1995). "División Justa mediante Programación Lineal" (PDF) . Universidad Estatal de Iowa (manuscrito inédito) .
  9. ^ Samuel Bismuto; Iván Bliznets; Erel Segal-Halevi. "División justa con participación limitada: valoraciones binarias y no degeneradas". arXiv : 1912.00459 .
  10. ^ Sandomirskiy, Fedor; Segal-Halevi, Erel (1 de mayo de 2022). "División justa eficiente con un intercambio mínimo". Investigación de Operaciones . 70 (3): 1762–1782. arXiv : 1908.01669 . doi :10.1287/opre.2022.2279. ISSN  0030-364X. S2CID  247922344.
  11. ^ Aziz, Haris; Caragiannis, Ioannis; Igarashi, Ayumi; Walsh, Toby (1 de agosto de 2019). "Asignación justa de bienes y tareas indivisibles". Actas de la Vigésima Octava Conferencia Internacional Conjunta sobre Inteligencia Artificial . California: Conferencias internacionales conjuntas sobre organización de inteligencia artificial. págs. 53–59. doi : 10.24963/ijcai.2019/8 . ISBN 978-0-9992411-4-1. S2CID  197468732.

Enlaces externos