📈 economics

Fair Allocation with Optional Selling

Este artículo investiga la asignación justa de bienes indivisibles donde los agentes pueden optar por vender artículos a precios de mercado, adaptando nociones de equidad estándar como MMS y EFX a este entorno híbrido y estableciendo garantías de existencia y límites de aproximación para asignaciones que equilibran la distribución de bienes y de ingresos.

Autores originales: Uriel Feige, Yotam Gafni

Publicado 2026-08-26

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Uriel Feige, Yotam Gafni

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

La división justa es un campo de las matemáticas y la economía dedicado a resolver un problema tan antiguo como la cooperación humana: cómo repartir recursos para que todos sientan que han recibido una parte justa. Durante décadas, los investigadores han estudiado cómo dividir cosas que no se pueden cortar, como una casa, un coche o una colección de libros raros. En estos escenarios, el objetivo es encontrar una disposición en la que nadie sienta envidia de lo que recibió otra persona, o donde se garantice a todos un nivel mínimo de satisfacción basado en sus preferencias personales. Sin embargo, estos modelos clásicos asumen que los artículos en cuestión permanecen en su forma actual. Ignoran una opción muy común en el mundo real: la capacidad de vender un artículo por dinero en efectivo. En un divorcio, por ejemplo, una pareja podría decidir que vender la casa familiar y repartir el dinero es una mejor solución que que una persona se quede con la casa y la otra no reciba nada. Esta simple opción de vender cambia todo el panorama de lo que es posible, pero también introduce nuevas complejidades que las teorías anteriores no abordaron.

Uriel Feige y Yotam Gafni, del Instituto de Ciencia Weizmann, han dado un paso al frente para llenar este vacío, explorando qué sucede cuando los agentes pueden elegir vender bienes a precios de mercado antes de dividir los artículos restantes y el efectivo resultante. Su trabajo plantea una pregunta fundamental: si las personas pueden vender artículos, ¿se vuelve más fácil o más difícil garantizar un resultado justo? Descubrieron que, si bien la venta abre más posibilidades, en realidad hace que sea más difícil garantizar ciertos tipos de equidad en comparación con el entorno tradicional donde la venta está prohibida. Los investigadores desarrollaron nuevas formas de medir la equidad que tienen en cuenta tanto el valor de los artículos que las personas conservan como el dinero que reciben de las ventas. Demostaron que, para dos personas, siempre es posible encontrar una división que satisfaga los estándares de equidad más estrictos, asegurando que nadie envidie el lote de otro incluso después de considerar la opción de vender. Sin embargo, a medida que aumenta el número de personas, las garantías se debilitan ligeramente. Para tres personas, demostraron que es imposible garantizar que todos obtengan su máximo posible de participación justa; en algunos casos, lo mejor a lo que alguien puede aspirar es una fracción específica de esa participación ideal.

Los investigadores también investigaron qué tan bien se pueden aproximar estas participaciones justas para grupos más grandes. Demostraron que, para cualquier número de personas, siempre hay una manera de dividir los bienes y el dinero de modo que todos reciban al menos dos tercios de su participación mínima garantizada. Este es un resultado significativo porque muestra que, incluso con la complejidad añadida de la venta, todavía se puede lograr un nivel de equidad muy alto. Además, descubrieron que es posible combinar esta equidad basada en la participación con un fuerte sentido de la ausencia de envidia, lo que significa que nadie preferiría intercambiar todo su lote de bienes y efectivo por el de otra persona. Lograron esto adaptando un algoritmo conocido como el método del "Divisor Solitario" (Lone Divider), que consiste en que una persona propone una división y los demás eligen sus partes preferidas. En el nuevo escenario con la venta, tuvieron que modificar este enfoque cuidadosamente, asegurándose de que la persona que propone la división sea elegida sabiamente y que los lotes estén estructurados de una manera específica para evitar que la venta de artículos perjudique injustamente a los participantes restantes.

Uno de los hallazgos más sorprendentes del artículo es la diferencia entre el escenario con la venta y el escenario sin ella. Los autores construyeron un ejemplo específico que involucra a tres personas y ocho artículos donde, si se permitiera la venta, sería imposible garantizar que todos obtengan más de once doceavos de su participación ideal. En el entorno tradicional donde los artículos no pueden venderse, el límite mejor conocido para este mismo escenario es mucho más alto, lo que significa que la capacidad de vender en realidad crea una brecha mayor entre lo que es teóricamente posible y lo que se puede garantizar en la práctica. Este resultado contraintuitivo sugiere que, si bien la venta ofrece flexibilidad, también introduce un nuevo tipo de riesgo donde artículos de alto valor podrían venderse por un precio bajo, dejando los artículos restantes insuficientes para satisfacer las necesidades de todos. Los investigadores también exploraron un escenario relacionado con las tareas o labores, o tareas que las personas detestan, donde la opción de subcontratar el trabajo por una tarifa desempeña el mismo papel que la venta de bienes. Encontraron patrones similares, mostrando que la capacidad de pagar a alguien más para que realice una tarea hace que sea más difícil garantizar una distribución perfectamente justa del trabajo restante.

El artículo también aborda el lado práctico de estas pruebas matemáticas, preguntando si estas asignaciones justas pueden ser calculadas eficientemente por una computadora. Los autores demostraron que, para el caso específico de dos personas, una división justa puede encontrarse en un tiempo razonable. Para grupos más grandes, desarrollaron algoritmos que pueden acercarse arbitrariamente a la participación justa ideal, lo que significa que, con suficiente potencia de cálculo, uno puede encontrar una solución que es casi tan buena como la teórica mejor posible. También demostraron que un tipo específico de garantía de equidad, basado en una participación proporcional truncada, puede computarse rápidamente y combinarse con condiciones de ausencia de envidia. Este trabajo proporciona un marco robusto para comprender cómo los mercados y las preferencias personales interactúan en los problemas de división justa, ofreciendo nuevas herramientas para situaciones que van desde los acuerdos de divorcio hasta la división de activos heredados. Al definir rigurosamente qué es posible cuando la venta es una opción, los investigadores han aclarado los límites de la equidad en un mundo donde los recursos pueden convertirse en dinero, asegurando que sepamos exactamente de qué garantías podemos confiar cuando hay mucho en juego.

Resumen Técnico: Asignación Justa con Venta Opcional

Definición del Problema

Este artículo aborda el problema de la asignación justa de bienes indivisibles en un entorno donde los agentes poseen funciones de valoración subjetivas sobre los bienes, pero los bienes también tienen precios de mercado exógenos. A diferencia de los modelos tradicionales de división justa donde los bienes son estrictamente indivisibles, este entorno introduce una "opción externa": los agentes pueden optar por vender los bienes a sus precios de mercado. Los ingresos derivados de estas ventas son divisibles y tienen un valor aditivo uniforme para todos los agentes.

El desafío central consiste en diseñar un mecanismo de asignación que decida simultáneamente:

Qué subconjunto de bienes vender.
Cómo asignar los bienes restantes no vendidos.
Cómo distribuir los ingresos monetarios de los bienes vendidos.

El objetivo es satisfacer nociones de justicia que adapten las garantías estándar basadas en participaciones y basadas en envidia a este entorno híbrido. Los autores asumen valoraciones aditivas tanto para los bienes como para el dinero.

Nociones de Justicia

El artículo adapta dos categorías de definiciones de justicia:

Nociones Basadas en Participaciones (Share-Based):
- Máxima Participación (MMS - Maximin Share): Definida como el valor máximo que un agente puede garantizarse a sí mismo decidiendo óptimamente qué bienes vender y luego particionando los bienes restantes y los ingresos en $n$ paquetes, recibiendo el menos valioso. A diferencia de la MMS estándar, el agente optimiza tanto la decisión de venta como la partición.
- Participación Proporcional Truncada (TPS - Truncated Proportional Share): Una extensión del concepto de TPS de entornos indivisibles, definida como el valor más grande $t$ tal que la suma de $\max\{p(g), \min\{v(g), t\}\}$ sobre todos los bienes, dividida por $n$ , es igual a $t$ .
Nociones Basadas en Envidia:
- SEF1 y SEFX (Envidia Libre de Venta Fuerte/Vendible): Estas son adaptaciones de EF1 y EFX. Una asignación es SEFX si para cualquier agente $i$ y cualquier otro agente $j$ , $i$ no envidia el paquete de $j$ incluso si $j$ vendiera uno de sus bienes (y recibiera el precio de mercado) en lugar de conservarlo. Formalmente, $\bar{v}_i(A_i) + P_i \ge \bar{v}_i(A_j \setminus \{g\}) + p(g)$ para cada bien $g \in A_j$ , donde $\bar{v}_i(g) = \max\{v_i(g), p(g)\}$ .

Metodología y Algoritmos

Los autores emplean una variedad de técnicas algorítmicas, incluyendo variaciones de los paradigmas de "Cortar y Elegir" (Cut & Choose), "Llenado de Bolsas" (Bag-Filling) y "Divisor Solitario" (Lone Divider), modificados para manejar la complejidad introducida por la venta opcional.

Cortar y Dar (n=2): Para dos agentes, los autores introducen un protocolo de "Cortar y Dar" (Cut & Give). Un agente (el que corta o Cutter) propone una partición basada en su MMS. Si el otro agente (el que da o Giver) encuentra un paquete aceptable, lo toma. Si no, el Giver modifica la particcción vendiendo su propio bien destinado y cancelando la venta del Cutter, creando un nuevo paquete que satisface tanto el MMS como el SEFX.
Llenado de Bolsas con Bienes Virtuales (TPS): Para lograr un $n/(2n-1)$ -TPS, el algoritmo utiliza un enfoque de "cuchillo móvil". Los bienes con precios de mercado altos se venden inmediatamente para satisfacer los requisitos de participación mínima de los agentes. Los ingresos restantes se tratan como "bienes virtuales". Un procedimiento de llenado de bolsas luego asigna paquetes hasta que un agente los valora en el umbral requerido.
Particiones Canónicas (Divisor Solitario para MMS): Para un $n$ general, los autores adaptan el método del Divisor Solitario. Una innovación clave es la construcción de "particiones canónicas" propuestas por el agente con el MMS más alto. Estas particiones consisten en "paquetes puros" (sin dinero), "paquetes unitarios" (un bien más los ingresos de al menos otro bien vendido) y un único paquete de "sobrantes". Esta estructura limita la pérdida potencial que un agente sufre si un paquete que rechazó es asignado a otra persona, específicamente acotando la pérdida causada por las ventas forzadas.
Manejo de Artículos de Alto Valor: Los algoritmos incluyen fases preliminares para manejar bienes cuyos valores exceden significativamente el umbral MMS, ya sea vendiéndolos para satisfacer a agentes específicos o asignándolos directamente, asegurando que el problema restante se ajuste al marco de aproximación.

Resultados Clave

1. Garantías Combinadas de Participación y Envidia

Dos Agentes (n=2): Siempre existe una asignación que es simultáneamente MMS y SEFX. Este es un resultado sólido, ya que lograr el MMS completo es generalmente imposible para $n \ge 3$ en entornos estándar, y aquí se logra junto con una noción fuerte de ausencia de envidia.
Agentes Generales (n $\ge$ 2): Existe una asignación que es simultáneamente $n/(2n-1)$ -TPS y SEFX. El ratio $n/(2n-1)$ se demuestra como la mejor aproximación posible para TPS incluso sin el requisito de SEFX.

2. Límites de Aproximación de MMS

Tres Agentes (n=3): El artículo establece una brecha cuantitativa entre los entornos con y sin venta. Mientras que el MMS completo está garantizado para $n=3$ con $m=8$ artículos en el entorno de bienes indivisibles estándar (donde el mejor límite conocido sin venta es $39/40$ ), en el entorno de venta existen instancias donde ninguna asignación garantiza más de $11/12$ -MMS.
Agentes Generales (n $\ge$ 4): Los autores proporcionan una asignación de $2/3$ -MMS. Esto coincide con la mejor aproximación conocida para el entorno de bienes indivisibles estándar (sin el término aditivo $O(1/n)$ que se encuentra en algunos trabajos previos).
Caso Especial (n=3): Al combinar el enfoque general de $n$ con el algoritmo de MMS completo para $n=2$ , los autores logran una asignación de $3/4$ -MMS para tres agentes.

3. Complejidad Computacional

Cálculo de MMS: Calcular el valor exacto de MMS es débilmente NP-duro para $n=2$ $n = 2$ y fuertemente NP-duro para $n$ $n$ general. Sin embargo, el artículo proporciona:
- Un algoritmo de tiempo pseudo-polinomial para un $n$ fijo.
- Un Esquema de Aproximación de Tiempo Polinomial (PTAS) para calcular valores y particiones de MMS.
Cálculo de TPS: El TPS es eficientemente computable en tiempo polinomial.
Garantías Combinadas: Existe un FPTAS para asignaciones que son simultáneamente $n/(2n-1)$ -TPS y $\epsilon$ -SEFX.

4. Extensiones

Ingresos Iguales: El artículo analiza un entorno restringido donde los ingresos de las ventas deben distribuirse equitativamente entre todos los agentes. En este caso, la garantía de aproximación cae a $1/n$ -TPS, y la garantía de MMS puede ser significativamente más débil que en el caso no restringido.
Tareas (Chores) con Outsourcing: El modelo se extiende a tareas (valoraciones negativas) donde los agentes pueden "subcontratar" tareas a un costo de mercado. Los resultados reflejan los del entorno de bienes: se logra una aproximación de 2-MMS, pero la brecha de aproximación es más amplia que en el entorno estándar de tareas indivisibles.

Significado y Reivindicaciones

El artículo afirma proporcionar un marco de "Lo Mejor de Ambos Mundos" para la división justa cuando existen opciones de mercado. Sus principales contribuciones son:

Identificación de la Brecha Teórica: Demuestra que la introducción de opciones de venta, aunque expande el conjunto factible de resultados, puede paradójicamente dificultar la aproximación de ciertas garantías de justicia (específicamente MMS para $n=3$ ) en comparación con el entorno puramente indivisible.
Algoritmos Robustos: Desarrolla técnicas algorítmicas novedosas (particiones canónicas, Divisor Solitario modificado) que logran recuperar los mejores ratios de aproximación conocidos para MMS en presencia de ventas, a pesar de la complejidad añadida de optimizar las decisiones de venta.
Justicia Unificada: Integra con éxito las garantías basadas en participaciones (MMS/TPS) con nociones fuertes de ausencia de envidia (SEFX) en una sola asignación, mostrando que las aproximaciones de alta calidad de la participación no excluyen necesariamente una fuerte ausencia de envidia en este entorno.

Los autores enfatizan que sus resultados son ajustados en varios casos (por ejemplo, el límite de $n/(2n-1)$ para TPS) y que los resultados negativos (la brecha de $11/12$ para $n=3$ ) son limitaciones demostrables del modelo, no solo artefactos de las limitaciones algorítmicas actuales.