Extensión de conjunto responsivo

En la teoría de la utilidad , la extensión del conjunto responsivo ( RS ) es una extensión de una relación de preferencia sobre artículos individuales, a una relación de preferencia parcial de paquetes de artículos.

Ejemplo

Supongamos que hay cuatro elementos: . Una persona afirma que clasifica los artículos según el siguiente orden total : ${\displaystyle w,x,y,z}$

${\displaystyle w\prec x\prec y\prec z}$

(es decir, z es su mejor elemento, luego y, luego x, luego w). Suponiendo que los artículos son bienes independientes , se puede deducir que:

${\displaystyle \{w,x\}\prec \{y,z\}}$– la persona prefiere sus dos mejores elementos a sus dos peores;

${\displaystyle \{w,y\}\prec \{x,z\}}$– la persona prefiere sus mejores y terceros mejores artículos a sus segundos mejores y cuartos mejores artículos.

Pero no se puede deducir nada sobre los paquetes ; no sabemos cuál de ellos prefiere la persona. ${\displaystyle \{w,z\},\{x,y\}}$

La extensión RS de la clasificación es un orden parcial de los paquetes de elementos, que incluye todas las relaciones que pueden deducirse de la clasificación de elementos y del supuesto de independencia. ${\displaystyle w\prec x\prec y\prec z}$

Definiciones

Sea un conjunto de objetos y un orden total en . ${\displaystyle O}$ ${\displaystyle \preceq }$ ${\displaystyle O}$

La extensión RS de es un pedido parcial en . Se puede definir de varias formas equivalentes. ^[1] ${\displaystyle \preceq }$ ${\displaystyle 2^{O}}$

Conjunto responsivo (RS)

La extensión RS original ^{[2] : 44–48} se construye de la siguiente manera. Para cada paquete , cada artículo y cada artículo , tome las siguientes relaciones: ${\displaystyle X\subseteq O}$ ${\displaystyle x\in X}$ ${\displaystyle y\notin X}$

• ${\displaystyle X\setminus \{x\}\prec ^{RS}X}$(- agregar un artículo mejora el paquete)
• Si es así (- reemplazar un artículo por uno mejor mejora el paquete). ${\displaystyle x\preceq y}$ ${\displaystyle X\preceq ^{RS}(X\setminus \{x\})\cup \{y\}}$

La extensión RS es el cierre transitivo de estas relaciones.

Dominio por parejas (PD)

La extensión PD se basa en un emparejamiento de los artículos de un paquete con los artículos del otro paquete.

Formalmente, si-y-sólo-si existe una función inyectiva de a tal que, para cada , . ${\displaystyle X\preceq ^{PD}Y}$ ${\displaystyle f}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle x\in X}$ ${\displaystyle x\preceq f(x)}$

Dominio estocástico (SD)

La extensión SD (llamada así por la dominancia estocástica ) se define no solo en paquetes discretos sino también en paquetes fraccionarios (paquetes que contienen fracciones de artículos). Informalmente, SD prefiere un paquete Y a un paquete X si, para cada elemento z, el paquete Y contiene al menos tantos objetos, que sean al menos tan buenos como z, que el paquete X.

Formalmente, si y así, para cada artículo : ${\displaystyle X\preceq ^{SD}Y}$ ${\displaystyle z}$

${\displaystyle \sum _{x\succeq z}X[x]\leq \sum _{y\succeq z}Y[y]}$

¿Dónde está la fracción del artículo en el paquete ? ${\displaystyle X[x]}$ ${\displaystyle x}$ ${\displaystyle X}$

Si los paquetes son discretos, la definición tiene una forma más simple. si, para cada artículo : ${\displaystyle X\preceq ^{SD}Y}$ ${\displaystyle z}$

${\displaystyle |\{x\in X|x\succeq z\}|\leq |\{y\in Y|y\succeq z\}|}$

Utilidad aditiva (AU)

La extensión AU se basa en la noción de función de utilidad aditiva .

Muchas funciones de utilidad diferentes son compatibles con un pedido determinado. Por ejemplo, el pedido es compatible con las siguientes funciones de utilidad: ${\displaystyle w\prec x\prec y\prec z}$

${\displaystyle u_{1}(w)=0,u_{1}(x)=2,u_{1}(y)=4,u_{1}(z)=7}$

${\displaystyle u_{2}(w)=0,u_{2}(x)=2,u_{2}(y)=4,u_{2}(z)=5}$

Suponiendo que los artículos son independientes, la función de utilidad de las cestas es aditiva, por lo que la utilidad de una cesta es la suma de las utilidades de sus artículos, por ejemplo:

${\displaystyle u_{1}(\{w,x\})=2,u_{1}(\{w,z\})=7,u_{1}(\{x,y\})=6}$

${\displaystyle u_{2}(\{w,x\})=2,u_{2}(\{w,z\})=5,u_{2}(\{x,y\})=6}$

La cesta tiene menos utilidad que según ambas funciones de utilidad. Además, para cada función de utilidad compatible con la clasificación anterior: ${\displaystyle \{w,x\}}$ ${\displaystyle \{w.z\}}$ ${\displaystyle u}$

${\displaystyle u(\{w,x\})<u(\{w,z\})}$.

Por el contrario, la utilidad de la cesta puede ser menor o mayor que la utilidad de . ${\displaystyle \{w,z\}}$ ${\displaystyle \{x,y\}}$

Esto motiva la siguiente definición:

${\displaystyle X\preceq ^{AU}Y}$iff, para cada función de utilidad aditiva compatible con : ${\displaystyle u}$ ${\displaystyle \preceq }$

${\displaystyle u(X)\leq u(Y)}$

Equivalencia

• ${\displaystyle X\preceq ^{SD}Y}$implica . ^[1] ${\displaystyle X\preceq ^{RS}Y}$
• ${\displaystyle X\preceq ^{RS}Y}$y son equivalentes. ^[1] ${\displaystyle X\preceq ^{PD}Y}$
• ${\displaystyle X\preceq ^{PD}Y}$implica . Prueba : Si , entonces hay una inyección tal que, para todos , . Por lo tanto, para cada función de utilidad compatible con , . Por lo tanto, si es aditivo, entonces . ^[1] ${\displaystyle X\preceq ^{AU}Y}$ ${\displaystyle X\preceq ^{PD}Y}$ ${\displaystyle f:X\to Y}$ ${\displaystyle x\in X}$ ${\displaystyle x\preceq f(x)}$ ${\displaystyle u}$ ${\displaystyle \preceq }$ ${\displaystyle u(x)\leq u(f(x))}$ ${\displaystyle u}$ ${\displaystyle u(X)\leq u(Y)}$
• Se sabe que y son equivalentes, véase, por ejemplo, ^[3] ${\displaystyle \preceq ^{AU}}$ ${\displaystyle \preceq ^{SD}}$

Por lo tanto, las cuatro extensiones y y y son todas equivalentes. ${\displaystyle \preceq ^{RS}}$ ${\displaystyle \preceq ^{PD}}$ ${\displaystyle \preceq ^{SD}}$ ${\displaystyle \preceq ^{AU}}$

Órdenes y valoraciones responsivas

Un pedido total de paquetes se denomina responsivo ^{[4] : 287–288} si contiene la extensión del conjunto responsivo de algún pedido total de artículos. Es decir, contiene todas las relaciones que están implícitas en el orden subyacente de los elementos y agrega algunas relaciones más que no están implícitas ni se contradicen.

De manera similar, una función de utilidad sobre paquetes se llama responsiva si induce un orden responsivo. Para ser más explícito, ^[5] una función de utilidad u responde si para cada paquete X y cada dos elementos y , z que no están en X :. ${\displaystyle u(y)\geq u(z)\implies u(X\cup \{y\})\geq u(X\cup \{z\})}$

La capacidad de respuesta está implícita en la aditividad, pero no al revés:

• Si un pedido total es aditivo (representado por una función aditiva ), entonces, por definición, contiene la extensión AU , que es equivalente a , por lo que responde. De manera similar, si una función de utilidad es aditiva, entonces se satisface la capacidad de respuesta. ${\displaystyle \preceq ^{AU}}$ ${\displaystyle \preceq ^{RS}}$ ${\displaystyle u(X\cup \{y\})-u(X\cup \{z\})=u(y)-u(z)}$
• Por otro lado, un orden total puede responder pero no ser aditivo: puede contener la extensión AU que es consistente con todas las funciones aditivas, pero también puede contener otras relaciones que son inconsistentes con una sola función aditiva.

Por ejemplo, ^[6] supongamos que hay cuatro elementos con . La capacidad de respuesta limita sólo la relación entre paquetes del mismo tamaño con un artículo reemplazado, o paquetes de diferentes tamaños donde lo pequeño está contenido en lo grande. No dice nada acerca de paquetes de diferentes tamaños que no son subconjuntos entre sí. Entonces, por ejemplo, una orden responsiva puede tener tanto como . Pero esto es incompatible con la aditividad: no existe una función aditiva para la cual while . ${\displaystyle w\prec x\prec y\prec z}$ ${\displaystyle \{z\}\prec \{x,y\}}$ ${\displaystyle \{w,z\}\succ \{w,x,y\}}$ ${\displaystyle u(\{z\})<u(\{x,y\})}$ ${\displaystyle u(\{w,z\})>u(\{w,x,y\})}$

Ver también

• Débilmente aditivo
• Secuencia de recolección

Referencias

1. Aziz, Haris; Gaspers, Serge; MacKenzie, Simón; Walsh, Toby (2015). "Asignación justa de objetos indivisibles según preferencias ordinales". Inteligencia artificial . 227 : 71–92. arXiv : 1312.6546 . doi :10.1016/j.artint.2015.06.002. S2CID  1408197.
2. Barberà, S., Bossert, W., Pattanaik, PK (2004). "Clasificación de conjuntos de objetos". (PDF) . Manual de teoría de la utilidad . Springer Estados Unidos.{{cite book}}: CS1 maint: multiple names: authors list (link)
3. Katta, Akshay-Kumar; Sethuraman, Jay (2006). "Una solución al problema de asignación aleatoria en el dominio de preferencia completo". Revista de teoría económica . 131 (1): 231. doi :10.1016/j.jet.2005.05.001.
4. 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)
5. Kyropoulou, María; Suksompong, Warut; Voudouris, Alexandros A. (12 de noviembre de 2020). "Casi sin envidia en la asignación de recursos grupales" (PDF) . Informática Teórica . 841 : 110-123. doi : 10.1016/j.tcs.2020.07.008. ISSN  0304-3975. S2CID  59222796.
6. Babaioff, Moshé; Nisán, Noam ; Talgam-Cohen, Inbal (2021). "Equilibrio competitivo con bienes indivisibles y presupuestos genéricos". Matemáticas de la Investigación de Operaciones . 46 (1): 382–403. arXiv : 1703.08150 . doi :10.1287/moor.2020.1062. SEÑOR  4224433.