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.^[1] The term fractionally subadditive was given by Uriel Feige.^[2]

Definition

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

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

The function ${\displaystyle v}$  is called fractionally subadditive (or XOS) if there exists a collection of set functions, ${\displaystyle \{a_{1},\ldots ,a_{l}\}}$ , such that:^[3]

• Each ${\displaystyle a_{j}}$  is additive, i.e., it assigns to each subset ${\displaystyle X\subseteq M}$ , the sum of the values of the items in ${\displaystyle X}$ .
• The function ${\displaystyle v}$  is the pointwise maximum of the functions ${\displaystyle a_{j}}$ . I.e, for every subset ${\displaystyle X\subseteq M}$ :

${\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 ${\displaystyle v}$  is fractionally subadditive if, for any ${\displaystyle S\subseteq M}$  and any collection ${\displaystyle \{\alpha _{i},T_{i}\}_{i=1}^{k}}$  with ${\displaystyle \alpha _{i}>0}$  and ${\displaystyle T_{i}\subseteq M}$  such that ${\displaystyle \sum _{T_{i}\ni j}\alpha _{i}\geq 1}$  for all ${\displaystyle j\in S}$ , we have ${\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.^[1]

See also: Utility functions on indivisible goods.

Etymology

The term XOS stands for XOR-of-ORs of Singleton valuations.^[4]

A Singleton valuation is a valuation function ${\displaystyle v(\cdot )}$  such that there exists a value ${\displaystyle w}$  and item ${\displaystyle i}$  such that ${\displaystyle v(S):=w}$  if and only if ${\displaystyle i\in S}$ , and ${\displaystyle v(S):=0}$  otherwise. That is, a Singleton valuation has value ${\displaystyle w}$  for receiving item ${\displaystyle i}$  and has no value for any other items.

An OR of valuations ${\displaystyle \{v_{1}(\cdot ),v_{2}(\cdot ),\ldots ,v_{k}(\cdot )\}}$  interprets each ${\displaystyle v_{j}(\cdot )}$  as representing a distinct player. The OR of ${\displaystyle \{v_{1}(\cdot ),v_{2}(\cdot ),\ldots ,v_{k}(\cdot )\}}$  is a valuation function ${\displaystyle v(\cdot )}$  such that ${\displaystyle v(S):=\max _{S_{1},\ldots ,S_{k}{\text{ s.th. }}S_{j}\cap S_{\ell }=\emptyset \ \forall j,\ell {\text{ and }}\cup _{j}S_{j}=S}\{\sum _{j=1}^{k}v_{j}(S_{j})\}}$ . That is, the OR of valuations ${\displaystyle \{v_{1}(\cdot ),v_{2}(\cdot ),\ldots ,v_{k}(\cdot )\}}$  is the optimal welfare that can be achieved by partitioning ${\displaystyle S}$  among players with valuations ${\displaystyle \{v_{1}(\cdot ),v_{2}(\cdot ),\ldots ,v_{k}(\cdot )\}}$ . The term "OR" refers to the fact that any of the players ${\displaystyle \{v_{1}(\cdot ),v_{2}(\cdot ),\ldots ,v_{k}(\cdot )\}}$  can receive items. Observe that an OR of Singleton valuations is an additive function.

An XOR of valuations ${\displaystyle \{v_{1}(\cdot ),\ldots ,v_{k}(\cdot )\}}$  is a valuation function ${\displaystyle v(\cdot )}$  such that ${\displaystyle v(S):=\max _{j}\{v_{j}(S)\}}$ . The term "XOR" refers to the fact that exactly one (an "exclusive or") of the players can receive items. Observe that an XOR of additive functions is XOS.

References

1. Nisan, 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. ISBN 1581132727.
2. Feige, Uriel (2009). "On Maximizing Welfare when Utility Functions Are Subadditive". SIAM Journal on Computing. 39: 122–142. CiteSeerX 10.1.1.86.9904. doi:10.1137/070680977.
3. Christodoulou, George; Kovács, Annamária; Schapira, Michael (2016). "Bayesian Combinatorial Auctions". Journal of the ACM. 63 (2): 1. CiteSeerX 10.1.1.721.5346. doi:10.1145/2835172.
4. Lehmann, Benny; Lehmann, Daniel; Nisan, Noam (2001-10-14). "Combinatorial auctions with decreasing marginal utilities". Proceedings of the 3rd ACM conference on Electronic Commerce. EC '01. New York, NY, USA: Association for Computing Machinery. pp. 18–28. arXiv:cs/0202015. doi:10.1145/501158.501161. ISBN 978-1-58113-387-5.