ⓘ Fractionally subadditive. A set function is called fractionally subadditive if it is the maximum of several additive set functions. This valuation class was def ..

                                     

ⓘ 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.

                                     

1. Definition

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

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

The function v {\displaystyle v} is called fractionally-subadditive or XOS if there exists a collection of set functions, { a 1, …, a l } {\displaystyle \{a_{1},\ldots,a_{l}\}}, such that:

  • The function v {\displaystyle v} is the pointwise maximum of the functions a j {\displaystyle a_{j}}. I.e, for every subset X ⊆ M {\displaystyle X\subseteq M}
  • Each a j {\displaystyle a_{j}} is additive, i.e., it assigns to each subset X ⊆ M {\displaystyle X\subseteq M}, the sum of the values of the items in X {\displaystyle X}.
v X = max j = 1 l a j X {\displaystyle vX=\max _{j=1}^{l}a_{j}X}
                                     

1.1. Definition Equivalent Definition

The name fractionally subadditive comes from the following equivalent definition: a set function v {\displaystyle v} is fractionally subadditive if, for any S ⊆ M {\displaystyle S\subseteq M} and any collection { α i, T i } i = 1 k {\displaystyle \{\alpha _{i},T_{i}\}_{i=1}^{k}} with α i > 0 {\displaystyle \alpha _{i}> 0} and T i ⊆ M {\displaystyle T_{i}\subseteq M} such that ∑ T i ∋ j α i ≥ 1 {\displaystyle \sum _{T_{i}\ni j}\alpha _{i}\geq 1} for all j ∈ S {\displaystyle j\in S}, we have v S ≤ ∑ i = 1 k α i v T i {\displaystyle vS\leq \sum _{i=1}^{k}\alpha _{i}vT_{i}}. This can be viewed as a fractional relaxation of the definition of subadditivity.

                                     
  • a subadditive set function. Fractionally subadditive set functions are a generalization of submodular functions and a special case of subadditive functions
  • result also holds when the buyers valuations are fractionally subadditive Case 2: fractionally subadditive buyers, 2nd - price auction, incomplete information