Valoración subaditiva fraccionaria

Una función de conjunto se denomina fraccionariamente subaditiva o XOS (no debe confundirse con OXS ) si es el máximo de varias funciones de conjunto aditivas no negativas . Esta clase de valoración fue definida y denominada XOS por Noam Nisan en el contexto de las subastas combinatorias . ^[1] El término fraccionariamente subaditiva fue dado por Uriel Feige. ^[2]

Definición

Hay un conjunto base finito de elementos, . ${\displaystyle M:=\{1,\ldots ,m\}}$

Hay una función que asigna un número a cada subconjunto de . ${\displaystyle v}$ ${\displaystyle M}$

La función se llama subaditiva fraccional (o XOS) si existe una colección de funciones de conjunto, , tales que: ^[3] ${\displaystyle v}$ ${\displaystyle \{a_{1},\ldots ,a_{l}\}}$

• Cada uno es aditivo, es decir , asigna a cada subconjunto , la suma de los valores de los elementos en . ${\displaystyle a_{j}}$ ${\displaystyle X\subseteq M}$ ${\displaystyle X}$
• La función es el máximo puntual de las funciones . Es decir, para cada subconjunto : ${\displaystyle v}$ ${\displaystyle a_{j}}$ ${\displaystyle X\subseteq M}$

${\displaystyle v(X)=\max _{j=1}^{l}a_{j}(X)}$

Definición equivalente

El nombre subaditivo fraccional proviene de la siguiente definición equivalente cuando se restringe a funciones aditivas no negativas: una función de conjunto es subaditiva fraccionalmente si, para cualquier y cualquier colección con y tal que para todo , tenemos . ${\displaystyle v}$ ${\displaystyle S\subseteq M}$ ${\displaystyle \{\alpha _{i},T_{i}\}_{i=1}^{k}}$ ${\displaystyle \alpha _{i}>0}$ ${\displaystyle T_{i}\subseteq M}$ ${\displaystyle \sum _{T_{i}\ni j}\alpha _{i}\geq 1}$ ${\displaystyle j\in S}$ ${\displaystyle v(S)\leq \sum _{i=1}^{k}\alpha _{i}v(T_{i})}$

Relación con otras funciones de utilidad

Toda función de conjunto submodular es XOS, y toda función XOS es una función de conjunto subaditiva . ^[1]

Ver también: Funciones de utilidad sobre bienes indivisibles .

Referencias

1. Nisan, Noam (2000). "Pujas y asignación en subastas combinatorias". Actas de la 2.ª conferencia de la ACM sobre comercio electrónico - EC '00 . p. 1. doi :10.1145/352871.352872. ISBN 1581132727.
2. Feige, Uriel (2009). "Sobre la maximización del bienestar cuando las funciones de utilidad son subaditivas". Revista SIAM de Computación . 39 : 122–142. CiteSeerX 10.1.1.86.9904 . doi :10.1137/070680977. 
3. Christodoulou, George; Kovács, Annamária; Schapira, Michael (2016). "Subastas combinatorias bayesianas". Revista de la ACM . 63 (2): 1. CiteSeerX 10.1.1.721.5346 . doi :10.1145/2835172.