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, M := \{1,\ldots,m\}.

There is a function v which assigns a number to each subset of M.

The function v is called fractionally subadditive (or XOS) if there exists a collection of set functions, \{a_1,\ldots,a_l\}, such that:[3]

  • Each a_j is additive, i.e., it assigns to each subset X\subseteq M, the sum of the values of the items in X.
  • The function v is the pointwise maximum of the functions a_j. I.e, for every subset X\subseteq M:
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 is fractionally subadditive if, for any S\subseteq M and any collection \{\alpha_i, T_i\}_{i=1}^k with \alpha_i > 0 and T_i\subseteq M such that \sum_{T_i \ni j} \alpha_i \ge 1 for all j\in S, we have v(S) \le \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 v(\cdot) such that there exists a value w and item i such that v(S):=w if and only if i \in S, and v(S):=0 otherwise. That is, a Singleton valuation has value w for receiving item i and has no value for any other items.

An OR of valuations \{v_1(\cdot),v_2(\cdot),\ldots,v_k(\cdot)\} interprets each v_j(\cdot) as representing a distinct player. The OR of \{v_1(\cdot),v_2(\cdot),\ldots,v_k(\cdot)\} is a valuation function v(\cdot) such that 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 \{v_1(\cdot),v_2(\cdot),\ldots,v_k(\cdot)\} is the optimal welfare that can be achieved by partitioning S among players with valuations \{v_1(\cdot),v_2(\cdot),\ldots,v_k(\cdot)\}. The term "OR" refers to the fact that any of the players \{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 \{v_1(\cdot),\ldots, v_k(\cdot)\} is a valuation function v(\cdot) such that 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.