Jump to content

Fractionally subadditive valuation

From Wikipedia, the free encyclopedia
(Redirected from Fractionally subadditive)

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

[edit]

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 (or XOS) if there exists a collection of set functions, , such that:[3]

  • Each is additive, i.e., it assigns to each subset , the sum of the values of the items in .
  • The function is the pointwise maximum of the functions . I.e, for every subset :

Equivalent Definition

[edit]

The name fractionally subadditive comes from the following equivalent definition when restricted to non-negative additive functions: a set function is fractionally subadditive if, for any and any collection with and such that for all , we have .

Relation to other utility functions

[edit]

Every submodular set function is XOS, and every XOS function is a subadditive set function.[1]

See also: Utility functions on indivisible goods.

References

[edit]
  1. ^ a b 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.