6 votos

Problema del corte del pastel si las medidas de valor no son finitamente aditivas

Antecedentes

He incursionado (hace poco) en la teoría de juegos. La necesito para diseñar un algoritmo de reparto de tareas. Evidentemente, se trata de un problema de reparto de tareas. Hasta ahora, me he abierto camino a través de Introducción a la teoría de los juegos de Martin J. Osborne, pero aún no me siento cómodo con él. Tengo una base sólida de cálculo, sé cómo tratar con las EDO y las EDP (pero intento evitarlas si puedo). :) ) Y sí, no soy matemático, soy ingeniero.

Problema

El "pastel" debe repartirse entre $k\geq 2$ jugadores. El giro es que la valoración de los jugadores es no finitamente aditivo, tiene un máximo, es decir, hay una cantidad de pastel que les parecerá más valiosa que una cantidad mayor (algo así como tener miedo a comer en exceso $-$ o estar a dieta).

Pregunta

¿Alguien sabe de un punto de partida para abordar esto? (Las soluciones eficientes o equitativas serían las más interesantes.) Todos los recursos que he encontrado, tratan sólo el caso finitamente aditivo. También agradecería cualquier material que se pueda descargar gratuitamente.

EDITAR : Busco formas eficientes y/o equitativas de repartir el pastel, independientemente del protocolo para lograrlo. Si además existe un protocolo para ello, mejor para mí. :)

1voto

Jonik Puntos 7937

TLDR: El libro de Borgers es \$35 y es impresionante para el caso aditivo de la compensación. A partir de esto puedes multiplicadores de Lagrange para resolver bonitas variaciones. Añade "unimodal" a tu búsqueda para encontrar artículos donde la utilidad marginal sube un poco y luego vuelve a bajar.


He descubierto que el corte de la tarta tiene algunas complicaciones adicionales que pueden resolverse de forma manejable simplemente pagando a la gente un poco para que las cosas sean iguales. En otras palabras, tenemos un pastel en el que la gente tiene diferentes funciones de utilidad (normalmente finitamente aditivas) y esa diferencia produce la oportunidad de un bien extra en la división, pero también tenemos un montón de dinero en el que la función de utilidad de todos coincide y es simplemente "dx", la más fácil de todas.

Los problemas de compensación con un número finito de bienes y funciones de utilidad aditivas son muy fáciles de entender, y se resuelven de una manera muy agradable en Borger, 2010 ( \$35 print, over \$ 960 en línea de la editorial, impresionante esquema de compensación) . Las técnicas utilizadas no cambian demasiado con diferentes funciones de utilidad si no son demasiado raras (por ejemplo, función unimodal y continua en tu caso, o monótona y continua en el caso que he leído), ya que sólo estás optimizando funciones diferenciables de una sola variable, y por tanto los máximos se producen en las esquinas o en las soluciones a las restricciones del multiplicador de Lagrange. En el caso aditivo, todas las funciones de utilidad son lineales, por lo que el cálculo desaparece, y los máximos se producen en (al menos una de las) esquinas.

No he encontrado ningún artículo fácilmente digerible en el que se discuta tu caso (que probablemente sea muy similar al ejemplo que pones: ajustar la compensación para no fomentar ni la infraproducción ni la sobreproducción; "unimodal" debería ayudar a la búsqueda). Los casos que leí eran "subastas" en las que el riesgo implicado hace que las funciones de utilidad sean "sublineales", de modo que la gente está menos dispuesta a arriesgar grandes cantidades de dinero, por lo que la utilidad marginal del efectivo disminuye (pero nunca llega a ser negativa como creo que ocurre en tu caso).

  • Börgers, Christoph. Matemáticas de la elección social: Voto, compensación y división. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2010. xii+245 pp. ISBN: 978-0-898716-95-5 MR 2574481 DOI: 10.1137/1.9780898717624

1voto

Erel Segal-Halevi Puntos 2998

Las funciones de utilidad que describes se llaman "de un solo pico". Aquí están dos referencias :

✔ Soluciones monotónicas de recursos al problema de la división justa cuando las preferencias tienen un solo pico, Social Choice and Welfare, Vol. 11, No. 3. (1994), pp. 205-223, doi:10.1007/bf00193807, por William Thomson

✔ Soluciones poblacionales-monotónicas al problema de la división justa cuando las preferencias tienen un solo pico, Economic Theory, Vol. 5, No. 2. (1995), pp. 229-246, doi:10.1007/bf01215201, por William Thomson

Sin embargo, hay que tener en cuenta que estas referencias se refieren a un recurso homogéneo (es decir, a cada persona sólo le importa la cantidad de recurso que obtiene, no la parte que le toca).

Para el caso de un recurso heterogéneo, con funciones de valoración no aditivas, véase estas referencias .

0voto

Collin K Puntos 6535

Quizá le resulte útil el libro Cake-Cutting Algorithms, de Jack Roberson y William Webb, A.K.Peters, Natick, 1998.

0voto

Bobson Puntos 636

Es necesario definir los términos equitativo o eficiente. Y hay que especificar las opciones de acción. Supongamos que no hay otras opciones de acción y que los jugadores tienen que comer la parte del pastel que les toca. Dejemos que la utilidad/valoración del jugador $i$ sea una función de un solo pico/unimodal $u_i(x_i)$ de su parte $x_i$ .

Supongamos que el objetivo de equidad se centra en los jugadores de menor utilidad: la asignación $a$ con servicios públicos $(a_1,a_2,...,a_n)$ en orden creciente es mejor que la asignación $b$ con servicios públicos $(b_1,b_2,...,b_n)$ en orden creciente si hay un $k$ tal que $a_k>b_k$ y $a_i=b_i$ para $i<k$ . He aquí un enfoque para la asignación más equitativa: Determinar la cuota que maximiza la utilidad $x_i$ para cada jugador. Si la suma de las acciones es superior a 1, habrá que reducir algunas acciones. Si la suma de acciones es inferior a 1, hay que aumentar algunas acciones. Aumente o disminuya las participaciones de los jugadores con mayor utilidad manteniendo su utilidad igual. Por ejemplo, aumentar o disminuir sus participaciones hasta que la suma de participaciones llegue a 1 o si su utilidad alcanza el nivel de la siguiente utilidad más alta. En este último caso, se empiezan a ajustar las cuotas del nuevo conjunto de jugadores con mayores utilidades. El algoritmo puede hacerse eficiente.

Supongamos que la meta eficiente se centra en la suma de utilidades: asignación $a$ con servicios públicos $(a_1,a_2,...,a_n)$ en orden creciente es mejor que la asignación $b$ con servicios públicos $(b_1,b_2,...,b_n)$ si $\sum_i{a_i}>\sum_i{b_i}$ . La idea es equiparar las utilidades marginales.

En primer lugar, algo de notación. Supongamos que las funciones de utilidad son diferenciables y cóncavas. Definir la inversa de las funciones de utilidad marginal $r_i(s)$ como $\mathrm{d}u_i(x_i)/dx_i\mid_{x_i=r_i(s)}=s$ . Si hay varias soluciones para la ecuación anterior, elija la más alta para que sea positiva $s$ y el más bajo para el negativo $s$ (para estar más cerca del pico). Si $\mathrm{d}u_i(x_i)/dx_i<s\forall{x_i}$ , elija $r_i(s)=0$ .

De nuevo, empieza con la acción de maximización de la utilidad $x_i$ para cada jugador. Si la suma de las acciones es superior a 1, se determina el mínimo $s>0$ tal que $\sum_i{r_i(s)}=1$ . Si la suma de las acciones es inferior a 1 determine el máximo $s<0$ tal que $\sum_i{r_i(s)}=1$ . La solución es $x_i=r_i(s)$ . Las torceduras en la función de utilidad y en la no-caoncavidad se pueden acomodar con un poco más de trabajo.

Para ser relevante desde el punto de vista económico, este problema necesita más estructura. Algunas ideas: (1) El supuesto de libre disposición (los jugadores pueden deshacerse sin coste alguno del trozo de pastel que no necesitan) garantizaría funciones de utilidad no decrecientes. (2) No hay razón para que todos los jugadores tengan el mismo peso. Por ejemplo, si una persona es siempre infeliz (la función de utilidad está por debajo de las funciones de utilidad de los demás jugadores), la asignación equitativa para equipararlo a los demás no parece apropiada. (3) Si los jugadores pudieran comerciar (tuvieran suficiente dinero en efectivo o cualquier otra mercancía que valoren de forma idéntica), se podría hacer cualquier asignación y los jugadores comerciarían para acabar con la asignación eficiente. Utilidad marginal $s$ sería el precio de mercado.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X