A
set function is called fractionally subadditive, or XOS (not to be confused with
OXS), if it is the maximum of several
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, .
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]
Each is additive, i.e., it assigns to each subset , the sum of the values of the items in .
The function is the
pointwise maximum of the functions . I.e, for every subset :
Equivalent Definition
The name fractionally subadditive comes from the following equivalent definition: a set function is fractionally subadditive if, for any and any collection with and such that for all , we have .
^
abNisan, Noam (2000). "Bidding and allocation in combinatorial auctions". Proceedings of the 2nd ACM conference on Electronic commerce - EC '00. p. 1.
doi:
10.1145/352871.352872.
ISBN1581132727.