División justa

Problema de compartir recursos.

La división justa es el problema en la teoría de juegos de dividir un conjunto de recursos entre varias personas que tienen derecho a ellos, de modo que cada persona reciba su parte correspondiente. Ese problema surge en diversos entornos del mundo real, como la división de herencias, la disolución de sociedades, los acuerdos de divorcio , la asignación electrónica de frecuencias , la gestión del tráfico aeroportuario y la explotación de satélites de observación de la Tierra . Es un área de investigación activa en matemáticas , economía (especialmente teoría de la elección social ), resolución de disputas , etc. El principio central de la división justa es que dicha división debe ser realizada por los propios jugadores, tal vez utilizando un mediador pero ciertamente no un árbitro. ya que sólo los jugadores saben realmente cómo valoran los productos.

El algoritmo arquetípico de división justa es divide y elige . Demuestra que dos agentes con gustos diferentes pueden dividir un pastel de manera que cada uno crea que obtuvo el mejor trozo. La investigación sobre la división equitativa puede verse como una extensión de este procedimiento a diversos entornos más complejos.

Hay muchos tipos diferentes de problemas de división justa, dependiendo de la naturaleza de los bienes a dividir, los criterios de equidad, la naturaleza de los jugadores y sus preferencias, y otros criterios para evaluar la calidad de la división.

Cosas que se pueden dividir

Formalmente, un problema de división justa se define por un conjunto (a menudo llamado "el pastel") y un grupo de jugadores. Una división es una partición en subconjuntos disjuntos: , un subconjunto por jugador. ${\displaystyle C}$ ${\displaystyle n}$ ${\displaystyle C}$ ${\displaystyle n}$ ${\displaystyle C=X_{1}\sqcup X_{2}\sqcup \cdots \sqcup X_{n}}$

El conjunto puede ser de varios tipos: ${\displaystyle C}$

• ${\displaystyle C}$puede ser un conjunto finito de elementos indivisibles, por ejemplo: , de modo que cada elemento debe entregarse en su totalidad a una sola persona. ${\displaystyle C=\{{\text{piano}},{\text{car}},{\text{apartment}}\}}$
• ${\displaystyle C}$puede ser un conjunto infinito que represente un recurso divisible, por ejemplo: dinero o un pastel. Matemáticamente, un recurso divisible a menudo se modela como un subconjunto de un espacio real; por ejemplo, la sección [0,1] puede representar una torta larga y estrecha, que debe cortarse en pedazos paralelos. El disco unitario puede representar una tarta de manzana.

Además, el conjunto a dividir podrá ser:

• homogéneo – como el dinero, donde sólo importa la cantidad, o
• heterogéneo, como un pastel que puede tener diferentes ingredientes, diferentes glaseados, etc.

Finalmente, es común hacer algunas suposiciones sobre si los elementos a dividir son:

• bienes, como un automóvil o un pastel, o
• males, como las tareas del hogar.

Con base en estas distinciones, se han estudiado varios tipos generales de problemas de división justa:

• Asignación justa de artículos : dividir un conjunto de bienes indivisibles y heterogéneos .
• Asignación justa de recursos: dividir un conjunto de bienes divisibles y homogéneos . Un caso especial es la división justa de un único recurso homogéneo .
• "Cortar el pastel de manera justa : dividir un bien divisible y heterogéneo" . Un caso especial es cuando el pastel es un círculo; entonces el problema se llama corte justo de pastel .
• División justa de tareas : dividir un mal divisible y heterogéneo.

También son habituales las combinaciones y casos especiales:

• Armonía en el alquiler (también conocido como el problema de los compañeros de casa): dividir un conjunto de bienes heterogéneos e indivisibles (por ejemplo, las habitaciones de un apartamento) y, simultáneamente, un bien divisible homogéneo (el alquiler del apartamento).
• Distribución justa de ríos : dividir las aguas que fluyen en un río internacional entre los países a lo largo de su corriente.
• La asignación aleatoria justa (dividir loterías en divisiones) es especialmente común cuando se asignan bienes indivisibles.

Definiciones de equidad

La teoría no considera que la mayor parte de lo que normalmente se llama una división justa debido al uso del arbitraje . Este tipo de situación ocurre con bastante frecuencia con teorías matemáticas que llevan nombres de problemas de la vida real. Las decisiones del Talmud sobre los derechos cuando un patrimonio está en quiebra reflejan algunas ideas bastante complejas sobre la justicia, ^[1] y la mayoría de la gente las consideraría justas. Sin embargo, son el resultado de debates legales entre rabinos y no de divisiones según las valoraciones de los demandantes.

Según la teoría subjetiva del valor , no puede haber una medida objetiva del valor de cada artículo. Por lo tanto, la equidad objetiva no es posible, ya que diferentes personas pueden asignar valores diferentes a cada elemento. Los experimentos empíricos sobre cómo la gente define el concepto de justicia ^[2] no han dado resultados concluyentes.

Por lo tanto, la mayoría de las investigaciones actuales sobre equidad se centran en conceptos de equidad subjetiva . Se supone que cada una de las personas tiene una función de utilidad o función de valor subjetiva y personal , que asigna un valor numérico a cada subconjunto de . A menudo se supone que las funciones están normalizadas, de modo que cada persona valora el conjunto vacío como 0 ( para todo i) y el conjunto completo de elementos como 1 ( para todo i) si los elementos son deseables y -1 si los elementos son indeseables. Ejemplos son: ${\displaystyle n}$ ${\displaystyle V_{i}}$ ${\displaystyle C}$ ${\displaystyle V_{i}(\emptyset )=0}$ ${\displaystyle V_{i}(C)=1}$

• Si es el conjunto de elementos indivisibles {piano, coche, apartamento}, entonces Alicia puede asignar un valor de 1/3 a cada elemento, lo que significa que cada elemento es importante para ella igual que cualquier otro elemento. Bob puede asignar el valor de 1 al conjunto {coche, apartamento} y el valor 0 a todos los demás conjuntos excepto X; esto significa que quiere tener sólo el coche y el apartamento juntos; el coche solo o el apartamento solo, o cada uno de ellos junto con el piano, no valen nada para él. ${\displaystyle C}$
• Si se trata de un pastel largo y estrecho (modelado como el intervalo [0,1]), entonces Alicia puede asignar a cada subconjunto un valor proporcional a su longitud, lo que significa que quiere la mayor cantidad de pastel posible, independientemente de los glaseados. Bob puede asignar valor sólo a subconjuntos de [0,4, 0,6], por ejemplo, porque esta parte del pastel contiene cerezas y a Bob sólo le importan las cerezas. ${\displaystyle C}$

Sobre la base de estas funciones de valor subjetivo, existen una serie de criterios ampliamente utilizados para una división justa. Algunos de estos entran en conflicto entre sí, pero a menudo pueden combinarse. Los criterios aquí descritos son sólo para cuando cada jugador tiene derecho a la misma cantidad:

• Una división proporcional significa que cada persona recibe al menos la parte que le corresponde según su propia función de valor . Por ejemplo, si tres personas dividen un pastel, cada una obtiene al menos un tercio según su propia valoración, es decir, cada una de las n personas obtiene un subconjunto del cual valora como al menos 1/ n del valor total: ${\displaystyle C}$
  • ${\displaystyle V_{i}(X_{i})\geq V_{i}(C)/n}$para todos yo.
• Una división superproporcional es aquella en la que cada jugador recibe estrictamente más de 1/ n (tal división existe sólo si los jugadores tienen valoraciones diferentes):
  • ${\displaystyle V_{i}(X_{i})>V_{i}(C)/n}$para todos yo .
• Una división sin envidia garantiza que nadie querrá la parte ajena más que la propia, es decir, cada persona recibe una parte que valora al menos tanto como todas las demás:
  • ${\displaystyle V_{i}(X_{i})\geq V_{i}(X_{j})}$para todo i y j.
• Una división sin envidia de grupo garantiza que ningún subconjunto de agentes envidia a otro subconjunto del mismo tamaño; es mucho más fuerte que la ausencia de envidia.
• Una división equitativa significa que cada persona siente exactamente la misma felicidad, es decir, la proporción del pastel que recibe un jugador según su propia valoración es la misma para todos los jugadores. Este es un objetivo difícil ya que los jugadores no necesitan decir la verdad si se les pregunta su valoración:
  • ${\displaystyle V_{i}(X_{i})=V_{j}(X_{j})}$para todo i y j.
• Una división exacta (también conocida como división por consenso) es aquella en la que todos los jugadores acuerdan el valor de cada acción:
  • ${\displaystyle V_{i}(X_{i})=V_{j}(X_{i})}$para todo i y j.

Todos los criterios anteriores suponen que los participantes tienen los mismos derechos . Si diferentes participantes tienen diferentes derechos (por ejemplo, en una sociedad en la que cada socio invirtió una cantidad diferente), entonces los criterios de equidad deben adaptarse en consecuencia. Ver Corte de pastel proporcional con diferentes derechos .

Requerimientos adicionales

Además de la equidad, a veces se desea que la división sea óptima de Pareto , es decir, ninguna otra asignación mejoraría la situación de alguien sin empeorar la situación de otro. El término eficiencia proviene de la idea económica del mercado eficiente . Una división en la que un jugador obtiene todo es óptima según esta definición, por lo que por sí sola no garantiza ni siquiera una parte justa. Véase también corte eficiente del pastel y el precio de la justicia .

Berlín dividido por la Conferencia de Potsdam

En el mundo real, la gente a veces tiene una idea muy precisa de cómo los otros jugadores valoran los bienes y es posible que les importe mucho. El caso en el que tienen un conocimiento completo de las valoraciones de los demás puede modelarse mediante la teoría de juegos . El conocimiento parcial es muy difícil de modelar. Una parte importante del aspecto práctico de la división justa es la concepción y el estudio de procedimientos que funcionan bien a pesar de ese conocimiento parcial o pequeños errores.

Un requisito adicional es que el procedimiento de división justa sea un mecanismo veraz , es decir, debe ser una estrategia dominante para que los participantes informen sus valoraciones verdaderas. Este requisito suele ser muy difícil de satisfacer en combinación con la equidad y la eficiencia de Pareto.

Trámites

Un procedimiento de división justa enumera las acciones que deben realizar los jugadores en función de los datos visibles y sus valoraciones. Un procedimiento válido es aquel que garantiza una división justa para cada jugador que actúa racionalmente según su valoración. Cuando una acción depende de la valoración de un jugador, el procedimiento describe la estrategia que seguirá un jugador racional. Un jugador puede actuar como si una pieza tuviera un valor diferente pero debe ser coherente. Por ejemplo, si un procedimiento dice que el primer jugador corta el pastel en dos partes iguales y luego el segundo jugador elige una pieza, entonces el primer jugador no puede afirmar que el segundo jugador obtuvo más.

Lo que hacen los jugadores es:

• Acordar sus criterios para una división justa
• Seleccione un procedimiento válido y siga sus reglas.

Se supone que el objetivo de cada jugador es maximizar la cantidad mínima que podría obtener, o en otras palabras, alcanzar el máximo .

Los procedimientos se pueden dividir en procedimientos discretos y continuos . Un procedimiento discreto implicaría, por ejemplo, que sólo una persona a la vez cortara o marcara un pastel. Los procedimientos continuos implican cosas como que un jugador mueva un cuchillo y el otro diga "para". Otro tipo de procedimiento continuo implica que una persona asigne un valor a cada parte del pastel.

Para obtener una lista de procedimientos de división justa, consulte Categoría: Protocolos de división justa .

Ningún protocolo finito (incluso si es ilimitado) puede garantizar una división libre de envidia de un pastel entre tres o más jugadores, si cada jugador debe recibir una sola pieza conectada. ^[3] Sin embargo, este resultado se aplica sólo al modelo presentado en ese trabajo y no para los casos en los que, por ejemplo, un mediador tiene información completa de las funciones de valoración de los jugadores y propone una división basada en esta información. ^[4]

Extensiones

Recientemente, el modelo de división justa se ha extendido de agentes individuales a familias (grupos predeterminados) de agentes. Ver División justa entre grupos .

Historia

Según Sol Garfunkel , el problema del corte de la torta había sido uno de los problemas abiertos más importantes de las matemáticas del siglo XX, ^[5] cuando la variante más importante del problema fue finalmente resuelta con el procedimiento de Brams-Taylor por Steven Brams y Alan Taylor. en 1995.

Los orígenes de divide y elige no están documentados. Las actividades relacionadas con la negociación y el trueque también son antiguas. Las negociaciones que involucran a más de dos personas también son bastante comunes; la Conferencia de Potsdam es un ejemplo reciente notable.

La teoría de la división justa se remonta sólo al final de la Segunda Guerra Mundial. Fue ideado por un grupo de matemáticos polacos , Hugo Steinhaus , Bronisław Knaster y Stefan Banach , que solían reunirse en el Café Escocés de Lvov (entonces en Polonia). En 1944 se ideó una división proporcional (división justa) para cualquier número de jugadores, llamada "último reductor". Steinhaus atribuyó esto a Banach y Knaster cuando hizo público el problema por primera vez en una reunión de la Sociedad Econométrica en Washington, DC, el 17 de septiembre de 1947. En esa reunión también propuso el problema de encontrar el menor número de recortes necesarios para tales divisiones.

Para conocer la historia del corte de pasteles sin envidia, consulte Corte de pasteles sin envidia .

En la cultura popular

• El rompecabezas de la herencia de los 17 animales implica la división justa de 17 camellos (o elefantes o caballos) en las proporciones 1/2, 1/3 y 1/9. Es un acertijo matemático popular , del que a menudo se afirma que tiene un origen antiguo, pero su primera publicación documentada fue en el Irán del siglo XVIII. ^[6]
• En el episodio "One Hour" de la temporada 3 de Numb3rs , Charlie habla sobre el problema de cortar el pastel aplicado a la cantidad de dinero que exigía un secuestrador.
• Hugo Steinhaus escribió sobre varias variantes de la división justa en su libro Mathematical Snapshots . En su libro afirma que G. Krochmainy en Berdechów ideó en 1944 una versión especial de la división justa entre tres personas y otra la señora L. Kott. ^[7]
• Martin Gardner e Ian Stewart han publicado libros con secciones sobre el problema. ^{[8] [9]} Martin Gardner introdujo la forma de división de tareas del problema. Ian Stewart ha popularizado el problema de la división justa con sus artículos en Scientific American y New Scientist .
• Una tira de Dinosaur Comics se basa en el problema de cortar pasteles. ^[10]
• En la película israelí Santa Clara , un inmigrante ruso le pregunta a un profesor de matemáticas israelí, ¿cómo se puede dividir equitativamente un pastel circular entre 7 personas? Su respuesta es hacer 3 cortes rectos por el medio, formando 8 piezas iguales. Como sólo hay 7 personas, se debe descartar una pieza, en el espíritu del comunismo.

Ver también

• Reparto y matemáticas del reparto
• La división justa en línea es una variante de la división justa en la que no todos los artículos o agentes están disponibles en el momento de la división.
• Equidad (economía)
• El comercio internacional
• Justicia (economía)
• problema de mochila
• Lista de problemas no resueltos en la división justa
• Juego de negociación de Nash
• Teorema de la pizza
• Precio de la justicia
• Rencor (teoría de juegos)
• División estratégica de ferias
• Tragedia de los anticomunes
• Tragedia de los comunes

Referencias

1. Aumann, Robert J.; Maschler, Michael (1985). "Análisis de la teoría de juegos de un problema de quiebra del Talmud" (PDF) . Revista de teoría económica . 36 (2): 195–213. doi :10.1016/0022-0531(85)90102-4. Archivado desde el original (PDF) el 20 de febrero de 2006.
2. Yaari, YO; Bar-Hillel, M. (1984). "Sobre dividir con justicia". Elección social y bienestar . 1 : 1. doi : 10.1007/BF00297056. S2CID  153443060.
3. Stromquist, Walter (2008). "Las divisiones de pastel sin envidia no se pueden encontrar mediante protocolos finitos". La Revista Electrónica de Combinatoria . 15 . doi : 10.37236/735 . Consultado el 26 de octubre de 2022 .
4. Aumann, Yonatan; Dombb, Yair (2010). "La eficiencia de la división justa con piezas conectadas". Internet y economía de redes . Taller Internacional sobre Internet y Economía de Redes. Saltador. págs. 26-37. doi :10.1007/978-3-642-17572-5_3.
5. Sol Garfunkel. Más iguales que otros: votación ponderada. Para todos los propósitos prácticos. COMAP. 1988
6. Agerón, Pierre (2013). "Le partage des dix-sept chameaux et autres arithmétiques atributos à l'immam 'Alî: Mouvance et circulation de récits de la tradition musulmane chiite" (PDF) . Revue d'histoire des mathématiques (en francés). 19 (1): 1–41.; véanse en particular las págs. 13 y 14.
7. Instantáneas matemáticas. H. Steinhaus. 1950, 1969 ISBN 0-19-503267-5 
8. ajá! Conocimiento. Martín. Gardner, 1978. ISBN 978-0-7167-1017-2 
9. Cómo cortar un pastel y otros acertijos matemáticos. Ian Stewart. 2006. ISBN 978-0-19-920590-5 
10. "¡Cómics de dinosaurios!".

Libros de texto

• Joven, Peyton H. (1995). Equidad: en teoría y práctica . Prensa de la Universidad de Princeton.
• 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.
• Robertson, Jack; Webb, William (1998). "Algoritmos para cortar pasteles: sea justo si puede" . Natick, Massachusetts: AK Peters. ISBN 978-1-56881-076-8. LCCN  97041258. OL  2730675W.
• Hervé Moulin (2004). División Justa y Bienestar Colectivo . Cambridge, Massachusetts: MIT Press. ISBN 9780262134231.
• Barbanel, Julio B. (2005). La geometría de la división justa eficiente. Introducción de Alan D. Taylor. Cambridge: Prensa de la Universidad de Cambridge. doi :10.1017/CBO9780511546679. ISBN 0-521-84248-4. SEÑOR  2132232. Un breve resumen está disponible en: Barbanel, J. (2010). "Un enfoque geométrico para la división justa". La revista universitaria de matemáticas . 41 (4): 268. doi : 10.4169/074683410x510263.
• Steven J. Brams (2008). Matemáticas y democracia: diseño de mejores procedimientos de votación y división justa . Princeton, Nueva Jersey: Princeton University Press. ISBN 9780691133218.

Artículos de encuesta

• Vicente P. Crawford (1987). "división justa", The New Palgrave: A Dictionary of Economics , v. 2, págs. 274–75.
• Hal Varian (1987). "imparcialidad", The New Palgrave: A Dictionary of Economics , v. 2, págs. 275–76.
• Bryan Skyrms (1996). La evolución del contrato social Cambridge University Press. ISBN 978-0-521-55583-8 
• Colina, TP (2000). "Dispositivos matemáticos para conseguir una parte justa". Científico americano . 88 (4): 325–331. Código Bib : 2000AmSci..88..325H. doi :10.1511/2000.4.325. S2CID  221539202.
• Brandt, Félix; Conitzer, Vicente; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Manual de elección social computacional. Prensa de la Universidad de Cambridge. ISBN 9781107060432.(versión gratuita en línea), capítulos 11 a 13.
• División justa de Christian Klamler, en Manual de negociación y decisión grupal, págs. 183–202.
• Corte de pasteles: división justa de bienes divisibles por Claudia Lindner y Jörg Rothe - en Economía y Computación, págs. 395–491.
• División justa de bienes indivisibles por Jérôme Lang y Jörg Rothe - en Economía y Computación, págs. 493–550.

enlaces externos

• División Justa del Proyecto de Matemáticas Discretas de la Universidad de Colorado en Boulder.
• División justa: método de marcadores
• División justa: método de ofertas en sobre cerrado