Fractionally subadditive valuation

A set function is called fractionally subadditive, or XOS (not to be confused with OXS), if it is the maximum of several non-negative additive set functions. This valuation class was defined, and termed XOS, by Noam Nisan, in the context of combinatorial auctions.^[1] The term fractionally subadditive was given by Uriel Feige.^[2]

Definition

There is a finite base set of items, ${\displaystyle M:=\{1,\ldots ,m\}}$.

There is a function ${\displaystyle v}$ which assigns a number to each subset of ${\displaystyle M}$.

The function ${\displaystyle v}$ is called fractionally subadditive (or XOS) if there exists a collection of set functions, ${\displaystyle \{a_{1},\ldots ,a_{l}\}}$, such that:^[3]

• Each ${\displaystyle a_{j}}$ is additive, i.e., it assigns to each subset ${\displaystyle X\subseteq M}$, the sum of the values of the items in ${\displaystyle X}$.
• The function ${\displaystyle v}$ is the pointwise maximum of the functions ${\displaystyle a_{j}}$. I.e, for every subset ${\displaystyle X\subseteq M}$:

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

Equivalent Definition

The name fractionally subadditive comes from the following equivalent definition when restricted to non-negative additive functions: a set function ${\displaystyle v}$ is fractionally subadditive if, for any ${\displaystyle S\subseteq M}$ and any collection ${\displaystyle \{\alpha _{i},T_{i}\}_{i=1}^{k}}$ with ${\displaystyle \alpha _{i}>0}$ and ${\displaystyle T_{i}\subseteq M}$ such that ${\displaystyle \sum _{T_{i}\ni j}\alpha _{i}\geq 1}$ for all ${\displaystyle j\in S}$, we have ${\displaystyle v(S)\leq \sum _{i=1}^{k}\alpha _{i}v(T_{i})}$.

Relation to other utility functions

Every submodular set function is XOS, and every XOS function is a subadditive set function.^[1]

See also: Utility functions on indivisible goods.