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, .
Hay una función que asigna un número a cada subconjunto de .
La función se llama subaditiva fraccional (o XOS) si existe una colección de funciones de conjunto, , tales que: [3]
- Cada uno es aditivo, es decir , asigna a cada subconjunto , la suma de los valores de los elementos en .
- La función es el máximo puntual de las funciones . Es decir, para cada subconjunto :
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 .
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
- ^ ab 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.
- ^ 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.
- ^ 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.