|
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 := \. 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, \, such that: * 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_^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 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Set Function
In mathematics, especially measure theory, a set function is a function whose domain is a family of subsets of some given set and that (usually) takes its values in the extended real number line \R \cup \, which consists of the real numbers \R and \pm \infty. A set function generally aims to subsets in some way. Measures are typical examples of "measuring" set functions. Therefore, the term "set function" is often used for avoiding confusion between the mathematical meaning of "measure" and its common language meaning. Definitions If \mathcal is a family of sets over \Omega (meaning that \mathcal \subseteq \wp(\Omega) where \wp(\Omega) denotes the powerset) then a is a function \mu with domain \mathcal and codomain \infty, \infty/math> or, sometimes, the codomain is instead some vector space, as with vector measures, complex measures, and projection-valued measures. The domain of a set function may have any number properties; the commonly encountered properties and ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Assignment Valuation
In economics, assignment valuation is a kind of a utility function on sets of items. It was introduced by Shapley and further studied by Lehmann, Lehmann and Nisan, who use the term OXS valuation (not to be confused with XOS valuation). Fair item allocation Fair item allocation is a kind of the fair division problem in which the items to divide are ''discrete'' rather than continuous. The items have to be divided among several partners who potentially value them differently, and each item has to be gi ... in this setting was studied by Benabbou, Chakraborty, Elkind, Zick and Igarashi. Assignment valuations correspond to preferences of groups. In each group, there are several individuals; each individual attributes a certain numeric value to each item. The assignment-valuation of the group to a set of items ''S'' is the value of the maximum weight matching of the items in ''S'' to the individuals in the group. The assignment valuations are a subset of the submodular valuations. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Additive Set Function
In mathematics, an additive set function is a function \mu mapping sets to numbers, with the property that its value on a union of two disjoint sets equals the sum of its values on these sets, namely, \mu(A \cup B) = \mu(A) + \mu(B). If this additivity property holds for any two sets, then it also holds for any finite number of sets, namely, the function value on the union of ''k'' disjoint sets (where ''k'' is a finite number) equals the sum of its values on the sets. Therefore, an additive set function is also called a finitely additive set function (the terms are equivalent). However, a finitely additive set function might not have the additivity property for a union of an ''infinite'' number of sets. A σ-additive set function is a function that has the additivity property even for countably infinite many sets, that is, \mu\left(\bigcup_^\infty A_n\right) = \sum_^\infty \mu(A_n). Additivity and sigma-additivity are particularly important properties of measures. They ar ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |