Valoración subaditiva fraccionaria

Una función de conjunto se denomina subaditiva fraccionaria , o XOS (que 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 subaditiva fraccionaria fue acuñado por Uriel Feige . ^{[ 2 ]}

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

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

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

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

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

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

Véase también: Funciones de utilidad en bienes indivisibles .

El término XOS significa X OR-de- OR de valoraciones de Singleton . ^{[ 4 ]}

Una valoración Singleton es una función de valoración${\displaystyle v(\cdot )}$de tal manera que exista un valor${\displaystyle w}$y artículo${\displaystyle i}$de tal manera que${\displaystyle v(S):=w}$si y solo si${\displaystyle i\in S}$, y${\displaystyle v(S):=0}$de lo contrario. Es decir, una valoración Singleton tiene valor${\displaystyle w}$para recibir el artículo${\displaystyle i}$y no tiene valor para ningún otro artículo.

Un OR de valoraciones${\displaystyle \{v_{1}(\cdot ),v_{2}(\cdot ),\ldots ,v_{k}(\cdot )\}}$interpreta cada${\displaystyle v_{j}(\cdot )}$como representante de un jugador distinto. El OR de${\displaystyle \{v_{1}(\cdot ),v_{2}(\cdot ),\ldots ,v_{k}(\cdot )\}}$es una función de valoración${\displaystyle v(\cdot )}$de tal manera que${\displaystyle v(S):=\max _{S_{1},\ldots ,S_{k}{\text{ s.th. }}S_{j}\cap S_{\ell }=\emptyset \ \forall j,\ell {\text{ and }}\cup _{j}S_{j}=S}\{\sum _{j=1}^{k}v_{j}(S_{j})\}}$. Es decir, el OR de las valoraciones${\displaystyle \{v_{1}(\cdot ),v_{2}(\cdot ),\ldots ,v_{k}(\cdot )\}}$es el bienestar óptimo que se puede lograr mediante la partición${\displaystyle S}$entre los jugadores con valoraciones${\displaystyle \{v_{1}(\cdot ),v_{2}(\cdot ),\ldots ,v_{k}(\cdot )\}}$El término "O" se refiere al hecho de que cualquiera de los jugadores${\displaystyle \{v_{1}(\cdot ),v_{2}(\cdot ),\ldots ,v_{k}(\cdot )\}}$puede recibir artículos. Observe que una OR de valoraciones Singleton es una función aditiva.

Una XOR de valoraciones${\displaystyle \{v_{1}(\cdot ),\ldots ,v_{k}(\cdot )\}}$es una función de valoración${\displaystyle v(\cdot )}$de tal manera que${\displaystyle v(S):=\max _{j}\{v_{j}(S)\}}$El término "XOR" se refiere al hecho de que exactamente uno (un " o exclusivo ") de los jugadores puede recibir objetos. Nótese que el XOR de funciones aditivas es XOS.