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] There is a finite base set of items,
There is a function
which assigns a number to each subset of
The function
is called fractionally subadditive (or XOS) if there exists a collection of set functions,
, such that:[3] The name fractionally subadditive comes from the following equivalent definition when restricted to non-negative additive functions: a set function
is fractionally subadditive if, for any
and any collection
α
α
Every submodular set function is XOS, and every XOS function is a subadditive set function.
[1] See also: Utility functions on indivisible goods.