• Source: 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. The term fractionally subadditive was given by Uriel Feige.




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:

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}

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

:




v
(
X
)
=

max

j
=
1


l



a

j


(
X
)


{\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



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 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.
See also: Utility functions on indivisible goods.




References

Kata Kunci Pencarian:

• Fractionally subadditive valuation
• Welfare maximization
• Price of anarchy in auctions
• Maximin share
• Fair item allocation
• Envy-free pricing