En la teoría de juegos , la división justa es el problema de dividir un conjunto de recursos entre varias personas que tienen derecho a ellos, de modo que cada persona reciba su parte correspondiente. Este problema surge en varios entornos del mundo real, tales como: división de herencia, disolución de sociedades, acuerdos de divorcio , asignación de frecuencias electrónicas , gestión del tráfico aeroportuario y explotación de satélites de observación de la Tierra . Esta es un área de investigación activa en matemáticas , economía (especialmente teoría de la elección social ), resolución de disputas., y más. 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 solo los 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 un pastel de tal manera que cada uno crea que se llevó la mejor pieza. La investigación en la división de ferias 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 "el pastel") y un grupo de jugadores. Una división es una partición de dentro subconjuntos disjuntos: , un subconjunto por jugador.
El conjunto puede ser de varios tipos:
- puede ser un conjunto finito de elementos indivisibles, por ejemplo: , de modo que cada artículo debe entregarse íntegramente a una sola persona.
- puede ser un conjunto infinito que representa 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 un pastel largo y estrecho, que tiene que cortarse en pedazos paralelos. El disco unitario puede representar una tarta de manzana.
Además, el conjunto a dividir puede ser:
- homogéneo, como el dinero, donde solo 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.
Sobre la base de estas distinciones, se han estudiado varios tipos generales de problemas de división equitativa:
- 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 .
- Corte justo de pasteles : dividir un bien heterogéneo y divisible . Un caso especial es cuando el pastel es un círculo; entonces el problema se llama corte de pastel justo .
- División de tareas justas : dividir un mal heterogéneo y divisible.
Las combinaciones y casos especiales también son comunes:
- Armonía de alquiler (también conocido como el problema de los compañeros de casa): dividir un conjunto de bienes heterogéneos indivisibles (por ejemplo, habitaciones en un apartamento) y, simultáneamente, un mal divisible homogéneo (el alquiler del apartamento).
- Reparto equitativo de los ríos : división de las aguas que fluyen en un río internacional entre los países a lo largo de su curso.
- La asignación aleatoria justa (dividir loterías entre 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 denomina una división justa es así debido al uso del arbitraje . Este tipo de situación ocurre con bastante frecuencia con las teorías matemáticas que llevan el nombre 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 de rabinos en lugar 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 las personas definen el concepto de equidad [2] conducen a resultados no concluyentes.
Por lo tanto, la mayoría de las investigaciones actuales sobre equidad se enfocan en conceptos de equidad subjetiva . Cada una de lasSe supone que las personas tienen una función de utilidad o función de valor subjetiva 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 todo el conjunto de elementos como 1 (para todo i) si los elementos son deseables y -1 si los elementos no son deseables. Algunos ejemplos son:
- 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 al igual que cualquier otro elemento. Bob puede asignar el valor 1 al conjunto {coche, apartamento} y el valor 0 a todos los demás conjuntos excepto X; esto significa que sólo quiere juntar el coche y el apartamento; el coche solo o el apartamento solo, o cada uno de ellos junto con el piano, no tiene ningún valor para él.
- Si es un pastel largo y estrecho (modelado como el intervalo [0,1]), entonces, Alice puede asignar a cada subconjunto un valor proporcional a su longitud, lo que significa que quiere tanto pastel como sea posible, independientemente de los glaseados. Bob puede asignar valor solo a subconjuntos de [0.4, 0.6], por ejemplo, porque esta parte del pastel contiene cerezas y Bob solo se preocupa por las cerezas.
Sobre la base de estas funciones de valor subjetivo, hay una serie de criterios ampliamente utilizados para una división justa. Algunos de estos entran en conflicto entre sí, pero a menudo se pueden combinar. Los criterios descritos aquí son solo para cuando cada jugador tiene derecho a la misma cantidad:
- Una división proporcional significa que cada persona obtiene al menos la parte que le corresponde de acuerdo con su propia función de valor . Por ejemplo, si tres personas se 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 deque valora como al menos 1 / n del valor total:
- por todo i.
- Una división superproporcional es aquella en la que cada jugador recibe estrictamente más de 1 / n (tal división existe solo si los jugadores tienen valoraciones diferentes):
- por todo i .
- Una división sin envidia garantiza que nadie querrá la parte de otra persona más que la suya propia, es decir, cada persona obtiene una parte que valora al menos tanto como todas las demás acciones:
- 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 todas las personas sienten exactamente la misma felicidad, es decir, la proporción del pastel que un jugador recibe 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 ser sinceros si se les pregunta su valoración:
- para todo i y j.
- Una división exacta (también conocida como división de consenso) es aquella en la que todos los jugadores están de acuerdo en el valor de cada acción:
- para todo i y j.
Todos los criterios anteriores asumen 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. Consulte Corte proporcional de pasteles con diferentes derechos .
Requerimientos adicionales
Además de la equidad, a veces se desea que la división sea óptima en el sentido de Pareto , es decir, ninguna otra asignación mejoraría la situación de alguien sin empeorar la situación de otra persona. 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 participación justa. Vea también corte de pasteles eficiente y el precio de la justicia .
En el mundo real, las personas a veces tienen una idea muy precisa de cómo los otros jugadores valoran los bienes y puede 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 elaboración y el estudio de procedimientos que funcionan bien a pesar de conocimientos parciales o pequeños errores.
Un requisito adicional es que el procedimiento de división equitativa sea un mecanismo veraz , es decir, debe ser una estrategia dominante para que los participantes informen sus valoraciones reales. Este requisito suele ser muy difícil de satisfacer en combinación con la equidad y la eficiencia de Pareto.
Una generalización del problema es permitir que cada parte interesada se componga de varios jugadores que comparten el mismo conjunto de recursos pero tienen preferencias diferentes. [3] [4]
Procedimientos
Un procedimiento de división justa enumera las acciones que deben realizar los jugadores en términos 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 consistente. 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 reclamar que el segundo jugador obtuvo más.
Lo que hacen los jugadores es:
- Acuerde sus criterios para una división justa
- Seleccione un procedimiento válido y siga sus reglas
Se asume que el objetivo de cada jugador es maximizar la cantidad mínima que podrían obtener, o en otras palabras, lograr el máximo .
Los procedimientos se pueden dividir en procedimientos discretos o continuos . Un procedimiento discreto, por ejemplo, involucraría solo a una persona a la vez cortando o marcando un pastel. Los procedimientos continuos implican cosas como que un jugador mueva un cuchillo y el otro diga "detente". 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 .
Extensiones
Recientemente, el modelo de división justa se ha extendido de agentes individuales a familias (grupos predeterminados) de agentes. En este modelo extendido, los miembros de cada familia consumen el mismo paquete, pero pueden tener preferencias diferentes. Hay varias formas de extender las nociones de equidad al entorno familiar, como por unanimidad, agregación o mayoría. Las variantes de división justa que se han estudiado en el entorno familiar incluyen:
- Corte justo de pasteles ; [5]
- Armonía de alquiler ; [6]
- Asignación sin envidia pareto-eficiente ; [7]
- Asignación justa de artículos . [8] [9] [10] [11]
Historia
Según Sol Garfunkel , el problema de cortar el pastel había sido uno de los problemas abiertos más importantes en las matemáticas del siglo XX, [12] cuando la variante más importante del problema fue finalmente resuelta con el procedimiento de Brams-Taylor de Steven Brams y Alan Taylor. en 1995.
Los orígenes de Dividir y elegir 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 solo 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 Scottish Café en Lvov (entonces en Polonia). En 1944 se ideó una división proporcional (división justa) para cualquier número de jugadores llamada "último disminuidor". Steinhaus se lo atribuyó 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 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
- En el episodio "Una hora" de la temporada 3 de Numb3rs , Charlie habla sobre el problema de cortar el pastel aplicado a la cantidad de dinero que un secuestrador estaba exigiendo.
- Hugo Steinhaus escribió sobre una serie de variantes de la división justa en su libro Mathematical Snapshots . En su libro dice que G. Krochmainy en Berdechów en 1944 ideó una versión especial para tres personas de la división justa y la Sra. L Kott ideó otra. [13]
- Martin Gardner e Ian Stewart han publicado libros con secciones sobre el problema. [14] [15] 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 un pastel. [dieciséis]
- 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. Dado que solo hay 7 personas, una pieza debe descartarse, en el espíritu del comunismo.
Ver también
- La división de ferias en línea es una variante de la división de ferias 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 división justa
- Juego de negociación de Nash
- Teorema de pizza
- Precio de la justicia
- Rencor (teoría de juegos)
- División ferial estratégica
- Tragedia de los anticommons
- Tragedia de los comunes
Referencias
- ^ Aumann, Robert J .; Maschler, Michael (1985). "Análisis teórico del juego de un problema de quiebra del Talmud" (PDF) . Revista de teoría económica . 36 : 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 dividir con justicia". Elección social y bienestar . 1 : 1. doi : 10.1007 / BF00297056 .
- ^ Manurangsi, Pasin; Suksompong, Warut (2017). "Existencia asintótica de divisiones justas para grupos". Ciencias Sociales Matemáticas . 89 : 100-108. arXiv : 1706.03184 . doi : 10.1016 / j.mathsocsci.2017.05.006 .
- ^ Suksompong, Warut (2018). "Acciones aproximadas de Maximin para grupos de agentes". Ciencias Sociales Matemáticas . 92 : 40–47. arXiv : 1706.09869 . doi : 10.1016 / j.mathsocsci.2017.09.004 .
- ^ Segal-Halevi, Erel; Nitzan, Shmuel (1 de diciembre de 2019). "Feria del corte de tartas entre familias" . Elección social y bienestar . 53 (4): 709–740. doi : 10.1007 / s00355-019-01210-9 . ISSN 1432-217X .
- ^ "Optimización combinatoria y aplicaciones | SpringerLink" . doi : 10.1007 / 978-3-030-04651-4 # page = 583 . Cite journal requiere
|journal=
( ayuda ) - ^ Bade, Sophie; Segal-Halevi, Erel (20 de octubre de 2020). "División justa y eficiente entre familias" . arXiv: 1811.06684 [econ] .
- ^ "Asignación justa democrática de bienes indivisibles" . Inteligencia artificial . 277 : 103167. 2019-12-01. arXiv : 1709.02564 . doi : 10.1016 / j.artint.2019.103167 . ISSN 0004-3702 .
- ^ "Acciones aproximadas de maximin para grupos de agentes" . Ciencias Sociales Matemáticas . 92 : 40–47. 2018-03-01. arXiv : 1706.09869 . doi : 10.1016 / j.mathsocsci.2017.09.004 . ISSN 0165-4896 .
- ^ "Casi sin envidia en la asignación de recursos de grupo" . Informática Teórica . 841 : 110-123. 2020-11-12. doi : 10.1016 / j.tcs.2020.07.008 . ISSN 0304-3975 .
- ^ "Existencia asintótica de divisiones justas para grupos" . Ciencias Sociales Matemáticas . 89 : 100-108. 2017-09-01. arXiv : 1706.08219 . doi : 10.1016 / j.mathsocsci.2017.05.006 . ISSN 0165-4896 .
- ^ Sol Garfunkel. Más igual que otros: voto ponderado. Para todos los propósitos prácticos. COMAP. 1988
- ^ Instantáneas matemáticas. H.Steinhaus. 1950, 1969 ISBN 0-19-503267-5
- ^ ¡Ajá! Visión. Martín. 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
- ^ http://www.qwantz.com/index.php?comic=1345
Libros de texto
- Young, 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 de la torta 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 .
- Herve Moulin (2004). División Justa y Bienestar Colectivo . Cambridge, Massachusetts: MIT Press. ISBN 9780262134231.
- Barbanel, Julius B .; con una introducción de Alan D. Taylor (2005). La geometría de una división justa eficiente . Cambridge: Cambridge University Press. doi : 10.1017 / CBO9780511546679 . ISBN 0-521-84248-4. Señor 2132232 . El resumen breve está disponible en: Barbanel, J. (2010). "Un enfoque geométrico de 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 división justa . Princeton, Nueva Jersey: Princeton University Press. ISBN 9780691133218.
Artículos de encuestas
- Vincent P. Crawford (1987). "división justa", The New Palgrave: A Dictionary of Economics , v. 2, págs. 274–75.
- Hal Varian (1987). "equidad", 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 participación justa". Científico estadounidense . 88 : 325–331. doi : 10.1511 / 2000.4.325 .
- Brandt, Felix; Conitzer, Vincent; 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-13.
- División justa por Christian Klamler - en Handbook of Group Decision and Negotiation pp 183-202.
- Cake-Cutting: Fair Division of Divisible Goods 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
- Fair Division del Discrete Mathematics Project de la Universidad de Colorado en Boulder.
- División justa: método de marcadores
- División justa: método de ofertas selladas