División justa

La división justa es el problema de la teoría de juegos que consiste en dividir un conjunto de recursos entre varias personas que tienen derecho a ellos, de modo que cada una reciba la parte que le corresponde. Ese problema surge en diversos escenarios del mundo real, como la división de herencias, las disoluciones de sociedades, los acuerdos de divorcio , la asignación de frecuencias electrónicas , 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 la teoría de la elección social ) y resolución de disputas . El principio central de la división justa es que dicha división debe ser realizada por los propios jugadores, sin necesidad de arbitraje externo , ya que solo los propios jugadores saben realmente cómo valoran los bienes.

El algoritmo arquetípico de división justa es dividir y elegir . Demuestra que dos agentes con gustos diferentes pueden dividir una torta de tal manera que cada uno de ellos crea que obtuvo la mejor porción. La investigación sobre división justa puede verse como una extensión de este procedimiento a varios 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 mediante un conjunto (a menudo llamado "la torta") y un grupo de jugadores. Una división es una partición de en subconjuntos disjuntos: , un subconjunto por jugador. ${\estilo de visualización C}$ ${\estilo de visualización n}$ ${\estilo de visualización C}$ ${\estilo de visualización n}$ $C=X_{1}\sqcup X_{2}\sqcup \cdots \sqcup X_{n}$

El conjunto puede ser de varios tipos: ${\estilo de visualización C}$

${\estilo de visualización 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. $C=\{{\text{piano}},{\text{coche}},{\text{apartamento}}\}$
${\estilo de visualización C}$ puede ser un conjunto infinito que representa un recurso divisible, por ejemplo: dinero o un pastel. Matemáticamente, un recurso divisible se modela a menudo como un subconjunto de un espacio real, por ejemplo, la sección [0,1] puede representar un pastel largo y angosto, 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.

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

bienes, como un coche o un pastel, o
cosas malas, como las tareas del hogar.

A partir de estas distinciones, se han estudiado varios tipos generales de problemas de división justa:

Asignación justa de bienes : división de un conjunto de bienes indivisibles y heterogéneos .
Asignación justa de recursos: división de un conjunto de bienes divisibles y homogéneos . Un caso especial es la división justa de un único recurso homogéneo .
Corte justo de la torta : división de un bien divisible y heterogéneo . Un caso especial es cuando la torta es un círculo; en ese caso, el problema se denomina corte justo de la torta .
División justa de tareas : dividir un mal divisible y heterogéneo.

También son comunes las combinaciones y los casos especiales:

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

Definiciones de equidad

La mayor parte de lo que normalmente se denomina una división justa no se considera así en la teoría debido al uso del arbitraje . Este tipo de situación ocurre con bastante frecuencia con teorías matemáticas que tienen nombres de problemas de la vida real. Las decisiones del Talmud sobre los derechos cuando un patrimonio está en quiebra reflejan el desarrollo de ideas complejas sobre la equidad. ^[1] Sin embargo, son el resultado de debates legales de rabinos más que 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, no es posible la justicia objetiva , ya que diferentes personas pueden asignar diferentes valores a cada artículo. Los experimentos empíricos sobre cómo las personas definen el concepto de justicia han dado resultados no concluyentes. ^[2]

Por lo tanto, la mayoría de las investigaciones actuales sobre la justicia se centran en conceptos de justicia subjetiva . Se supone que cada una de las personas tiene una función de utilidad subjetiva personal o función de valor , 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 todos los i), y el conjunto completo de elementos como 1 ( para todos los i) si los elementos son deseables, y -1 si los elementos son indeseables. Algunos ejemplos son: ${\estilo de visualización n}$ $Estilo de visualización V_{i}}$ ${\estilo de visualización C}$ $V_{i}(\emptyset)=0$ $Estilo de visualización V_{i}(C)=1$

Si es el conjunto de elementos indivisibles {piano, coche, apartamento}, entonces Alice 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 de 0 a todos los demás conjuntos excepto X; esto significa que quiere obtener solo el coche y el apartamento juntos; el coche solo o el apartamento solo, o cada uno de ellos junto con el piano, no tienen ningún valor para él. ${\estilo de visualización C}$
Si es un pastel largo y angosto (modelado como el intervalo [0,1]), entonces, Alice puede asignar a cada subconjunto un valor proporcional a su longitud, lo que significa que quiere la mayor cantidad posible de pastel, independientemente de los glaseados. Bob puede asignar valores solo a subconjuntos de [0.4, 0.6], por ejemplo, porque esta parte del pastel contiene cerezas y a Bob solo le interesan las cerezas. ${\estilo de visualización C}$

En función de estas funciones de valor subjetivas, existen varios criterios ampliamente utilizados para una división justa. Algunos de ellos entran en conflicto entre sí, pero a menudo se pueden combinar. Los criterios que se describen aquí se aplican únicamente cuando cada jugador tiene derecho a la misma cantidad:

Una división proporcional significa que cada jugador recibe al menos la parte que le corresponde según su propia función de valor . Por ejemplo, si tres personas se dividen una tarta, cada una recibe al menos un tercio según su propia valoración, es decir, cada una de las n personas recibe un subconjunto cuyo valor es al menos 1/ n del valor total: ${\estilo de visualización C}$
- $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. (Dicha división existe solo si los jugadores tienen diferentes valoraciones):
- $V_{i}(X_{i})>V_{i}(C)/n$ para todo yo .
Una división libre de envidia garantiza que nadie querrá la parte de otro más que la suya, es decir, cada persona valora su propia parte al menos tanto como todas las demás:
- $V_{i}(X_{i})\geq V_{i}(X_{j})$ para todos i y j.
Una división libre de envidia grupal garantiza que ningún subconjunto de agentes envidie a otro subconjunto del mismo tamaño; esta es una condición más fuerte que la libre de envidia.
Una división equitativa significa que la valoración que cada jugador hace de su propia porción es igual, es decir, que cada uno recibe el mismo valor o “experimenta la misma felicidad”. Este es un objetivo difícil, ya que los jugadores no necesitan ser sinceros si se les pregunta su valoración.
- $V_{i}(X_{i})=V_{j}(X_{j})$ para todos i y j.
Una división exacta (también conocida como división por consenso) es aquella en la que todos los jugadores están de acuerdo con el valor de cada acción:
- $V_{i}(X_{i})=V_{j}(X_{i})$ para todos i y j.

Todos los criterios anteriores suponen que los participantes tienen derechos iguales . Si los distintos 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. Véase reparto proporcional de la parte del pastel con diferentes derechos .

Requisitos adicionales

Además de la equidad, a veces se desea que la distribución sea óptima en el sentido de Pareto , es decir, que ninguna otra distribución beneficiaría a alguien sin perjudicar a otro. El término eficiencia proviene de la idea económica del mercado eficiente . Una distribució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 reparto eficiente de la torta y el precio de la equidad .

En el mundo real, las personas a veces tienen una idea muy precisa de cómo los otros jugadores valoran los bienes y pueden preocuparse mucho por ello. El caso en que tienen un conocimiento completo de las valoraciones de los demás se puede modelar 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 funcionen bien a pesar de ese conocimiento parcial o de pequeños errores.

Un requisito adicional es que el procedimiento de división justa sea a prueba de estrategias , es decir, que los participantes deberían informar sus valoraciones reales como estrategia dominante. Este requisito suele ser muy difícil de satisfacer, especialmente en combinación con la equidad y la eficiencia de Pareto. Como resultado, a menudo se debilita ante la compatibilidad de incentivos , que solo requiere que los participantes informen sus valoraciones reales si se comportan de acuerdo con un concepto de solución específico .

Procedimientos

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 de acuerdo con 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 la tarta 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 pueda obtener, o en otras palabras, lograr el maximin .

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

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

Ningún protocolo finito (aunque no tenga límites) puede garantizar una división libre de envidias de una torta entre tres o más jugadores, si cada jugador va a recibir una sola pieza conectada. ^[3] Sin embargo, este resultado se aplica sólo al modelo presentado en ese trabajo y no a 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 desde agentes individuales a familias (grupos predeterminados) de agentes. Véase 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 en las matemáticas del siglo XX, ^[5] cuando la variante más importante del problema fue finalmente resuelta con el procedimiento Brams-Taylor por Steven Brams y Alan Taylor en 1995.

Los orígenes de Divide and choose no están documentados. Las actividades relacionadas con el regateo y el trueque también son antiguas. Las negociaciones en las que participan 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 al final de la Segunda Guerra Mundial. Fue ideada 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 "última disminución". Steinhaus atribuyó esto a Banach y Knaster cuando hizo público el problema por primera vez en una reunión de la Econometric Society 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 cortes necesarios para tales divisiones.

Para conocer la historia del corte de pastel sin envidia, consulte corte de pastel 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 rompecabezas 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 "Una hora" de la temporada 3 de Numb3rs , Charlie habla sobre el problema del corte del pastel aplicado a la cantidad de dinero que exigía un secuestrador.
Hugo Steinhaus escribió sobre una serie de variantes de la división justa en su libro Instantáneas matemáticas . En su libro dice que una versión especial de tres personas de la división justa fue ideada por G. Krochmainy en Berdechów en 1944 y otra por la Sra. 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 cómic de Dinosaur Comics se basa en el problema del corte de la tarta. ^[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 un pastel circular de manera justa entre siete personas. Su respuesta es hacer tres cortes rectos en el medio, lo que da ocho porciones iguales. Como solo hay siete personas, se debe descartar una porción, en el espíritu del comunismo.

Véase también

Referencias

^ Aumann, Robert J.; Maschler, Michael (1985). "Análisis teórico de juegos de un problema de bancarrota a partir del Talmud" (PDF) . Journal of Economic Theory . 36 (2): 195–213. doi :10.1016/0022-0531(85)90102-4. Archivado desde el original (PDF) el 20 de febrero de 2006.
^ Yaari, ME; Bar-Hillel, M. (1984). "Sobre la división justa". Elección social y bienestar . 1 : 1. doi :10.1007/BF00297056. S2CID 153443060.
^ Stromquist, Walter (2008). "Las divisiones de tortas sin envidia no se pueden encontrar mediante protocolos finitos". The Electronic Journal of Combinatorics . 15 . doi : 10.37236/735 . Consultado el 26 de octubre de 2022 .
^ Aumann, Yonatan; Dombb, Yair (2010). "La eficiencia de la división justa con piezas conectadas". Internet and Network Economics . Taller internacional sobre Internet y economía de redes. Springer. pp. 26–37. doi :10.1007/978-3-642-17572-5_3.
^ Sol Garfunkel. Más iguales que los demás: votación ponderada. Para todos los efectos prácticos. COMAP. 1988
^ 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-14.
^ Instantáneas matemáticas. H. Steinhaus. 1950, 1969 ISBN 0-19-503267-5
^ ¡ Ajá! Perspicacia. Martin. Gardner, 1978. ISBN 978-0-7167-1017-2
^ Cómo cortar un pastel y otros acertijos matemáticos. Ian Stewart. 2006. ISBN 978-0-19-920590-5
^ "¡Cómics de dinosaurios!".

Libros de texto

Young, Peyton H. (1995). Equidad: en teoría y en la práctica . Princeton University Press.
Brams, Steven J.; Taylor, Alan D. (1996). División justa: del corte de la torta a la resolución de disputas . Cambridge University Press. ISBN 0-521-55644-9.
Robertson, Jack; Webb, William (1998). Algoritmos para cortar la tarta: sea justo si puede . Natick, Massachusetts: AK Peters. ISBN 978-1-56881-076-8. Número de serie 97041258. OL 2730675W.
Hervé Moulin (2004). División justa y bienestar colectivo . Cambridge, Massachusetts: MIT Press. ISBN 9780262134231.
Barbanel, Julius B. (2005). La geometría de la división justa y eficiente. Introducción de Alan D. Taylor. Cambridge: Cambridge University Press. doi :10.1017/CBO9780511546679. ISBN 0-521-84248-4. Sr. 2132232. Un breve resumen está disponible en: Barbanel, J. (2010). "Un enfoque geométrico para la división justa". The College Mathematics Journal . 41 (4): 268. doi :10.4169/074683410x510263.
Steven J. Brams (2008). Matemáticas y democracia: diseño de mejores procedimientos de votación y de división justa . Princeton, NJ: Princeton University Press. ISBN 9780691133218.

Artículos de encuesta

Vincent P. Crawford (1987). "división justa", The New Palgrave: A Dictionary of Economics , v. 2, págs. 274–75.
Hal Varian (1987). "justicia", 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
Hill, TP (2000). "Dispositivos matemáticos para obtener una parte justa". American Scientist . 88 (4): 325–331. Bibcode :2000AmSci..88..325H. doi :10.1511/2000.4.325. S2CID 221539202.
Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Manual de elección social computacional. Cambridge University Press. ISBN 9781107060432.(versión gratuita en línea), capítulos 11–13.
División justa de Christian Klamler – en Manual de decisión grupal y negociación pp 183–202.
El corte de la torta: división justa de bienes divisibles, por Claudia Lindner y Jörg Rothe – en Economía y Computación, pp. 395–491.
División justa de bienes indivisibles por Jérôme Lang y Jörg Rothe – en Economía y Computación pp 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 selladas