Fractionally subadditive


A set function is called fractionally subadditive 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. The term fractionally-subadditive was given by Uriel Feige.

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 if there exists a collection of set functions,, such that:
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. This can be viewed as a fractional relaxation of the definition of subadditivity.

Relation to other utility functions

Every submodular set function is XOS, and every XOS function is a subadditive set function.
See also: Utility functions on indivisible goods.