Extensión de conjunto responsivo

En la teoría de la utilidad , la extensión del conjunto responsivo ( CR ) 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 elementos 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 artículo, 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 objetos a sus dos peores objetos;

${\displaystyle \{w,y\}\prec \{x,z\}}$– la persona prefiere sus mejores y terceros mejores artículos a sus segundo y cuarto 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 en los conjuntos de elementos, que incluye todas las relaciones que pueden deducirse de la clasificación de elementos y el 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 orden parcial en . Puede definirse de varias maneras 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 entonces (- reemplazar un artículo con un artículo 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 pares (PD)

La extensión PD se basa en el emparejamiento de los elementos de un paquete con los elementos 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)}$

Dominancia estocástica (SD)

La extensión SD (denominada así por la dominancia estocástica ) se define no solo en paquetes discretos sino también en paquetes fraccionarios (paquetes que contienen fracciones de elementos). De manera informal, un paquete Y es SD-preferido a un paquete X si, para cada elemento z, el paquete Y contiene al menos tantos objetos, que son al menos tan buenos como z, como el paquete X.

Formalmente, si y solo si, para cada elemento : ${\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 y solo si, para cada elemento : ${\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 una función de utilidad aditiva .

Muchas funciones de utilidad diferentes son compatibles con un orden determinado. Por ejemplo, el orden 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 los paquetes es aditiva, por lo que la utilidad de un paquete 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}$

El conjunto tiene una utilidad menor que la que se obtiene de acuerdo con 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 del paquete 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}$y si, 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 . Demostración : Si , entonces hay una inyección tal que, para todo , . Por lo tanto, para cada función de utilidad compatible con , . Por lo tanto, si es aditiva, 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}}$

Pedidos y valoraciones reactivas

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

De manera similar, una función de utilidad sobre paquetes se denomina responsiva si induce un orden responsivo. Para ser más explícito, ^[5] una función de utilidad u es responsiva si para cada paquete X y cada dos artículos 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 orden 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 es responsivo. De manera similar, si una función de utilidad es aditiva, entonces , por lo que se satisface la responsividad. ${\displaystyle \preceq ^{AU}}$ ${\displaystyle \preceq ^{RS}}$ ${\displaystyle u(X\cup \{y\})-u(X\cup \{z\})=u(y)-u(z)}$
• Por otra parte, un orden total puede ser responsivo pero no 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 restringe solo la relación entre paquetes del mismo tamaño con un elemento reemplazado, o paquetes de diferentes tamaños donde el pequeño está contenido en el grande. No dice nada sobre paquetes de diferentes tamaños que no son subconjuntos entre sí. Entonces, por ejemplo, un orden responsivo puede tener tanto y . Pero esto es incompatible con la aditividad: no hay una función aditiva para la cual mientras . ${\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\})}$

Véase también

• Débilmente aditivo
• Secuencia de selección

Referencias

1. Aziz, Haris; Gaspers, Serge; MacKenzie, Simon; Walsh, Toby (2015). "Asignación justa de objetos indivisibles bajo 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 US.{{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". Journal of Economic Theory . 131 (1): 231. doi :10.1016/j.jet.2005.05.001.
4. 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)
5. Kyropoulou, Maria; Suksompong, Warut; Voudouris, Alexandros A. (12 de noviembre de 2020). "Asignación de recursos grupales casi sin envidia" (PDF) . Ciencias Informáticas Teóricas . 841 : 110–123. doi :10.1016/j.tcs.2020.07.008. ISSN  0304-3975. S2CID  59222796.
6. Babaioff, Moshe; Nisan, 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. MR  4224433.