|
Fractionally Subadditive
A set function is called fractionally subadditive (or XOS) if it is the maximum of several 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: a set function v is ''fractionally subadditive'' if, for any S\subseteq M and any collection \_^k with \alpha_i ... [...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 is a set function may have any number properties; the commonly encountered properties and categor ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Additive Set Function
In mathematics, an additive set function is a function 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 are abstrac ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Combinatorial Auction
A combinatorial auction is a type of smart market in which participants can place bids on combinations of discrete heterogeneous items, or “packages”, rather than individual items or continuous quantities. These packages can be also called lots and the whole auction a multi-lot auction. Combinatorial auctions are applicable when bidders have non-additive valuations on bundles of items, that is, they value combinations of items more or less than the sum of the valuations of individual elements of the combination. Simple combinatorial auctions have been used for many years in estate auctions, where a common procedure is to accept bids for packages of items. They have been used recently for truckload transportation, bus routes, industrial procurement, and in the allocation of radio spectrum for wireless communications. In recent years, procurement teams have applied reverse combinatorial auctions in the procurement of goods and services. This application is often referred to as ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pointwise Maximum
In mathematics, the lower envelope or pointwise minimum of a finite set of functions is the pointwise minimum of the functions, the function whose value at every point is the minimum of the values of the functions in the given set. The concept of a lower envelope can also be extended to partial functions by taking the minimum only among functions that have values at the point. The upper envelope or pointwise maximum is defined symmetrically. For an infinite set of functions, the same notions may be defined using the infimum in place of the minimum, and the supremum in place of the maximum. For continuous functions from a given class, the lower or upper envelope is a piecewise function whose pieces are from the same class. For functions of a single real variable whose graphs have a bounded number of intersection points, the complexity of the lower or upper envelope can be bounded using Davenport–Schinzel sequences, and these envelopes can be computed efficiently by a divide-and-co ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Submodular Set Function
In mathematics, a submodular set function (also known as a submodular function) is a set function whose value, informally, has the property that the difference in the incremental value of the function that a single element makes when added to an input set decreases as the size of the input set increases. Submodular functions have a natural diminishing returns property which makes them suitable for many applications, including approximation algorithms, game theory (as functions modeling user preferences) and electrical networks. Recently, submodular functions have also found immense utility in several real world problems in machine learning and artificial intelligence, including automatic summarization, multi-document summarization, feature selection, active learning, sensor placement, image collection summarization and many other domains. Definition If \Omega is a finite set, a submodular function is a set function f:2^\rightarrow \mathbb, where 2^\Omega denotes the power set of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Subadditive Set Function
In mathematics, a subadditive set function is a set function whose value, informally, has the property that the value of function on the union of two sets is at most the sum of values of the function on each of the sets. This is thematically related to the subadditivity property of real-valued functions. Definition Let \Omega be a set and f \colon 2^ \rightarrow \mathbb be a set function, where 2^\Omega denotes the power set of \Omega. The function ''f'' is ''subadditive'' if for each subset S and T of \Omega, we have f(S) + f(T) \geq f(S \cup T). Examples of subadditive functions Every non-negative submodular set function is subadditive (the family of non-negative submodular functions is strictly contained in the family of subadditive functions). The function that counts the number of sets required to cover a given set is subadditive. Let T_1, \dotsc, T_m \subseteq \Omega such that \cup_^m T_i=\Omega. Define f as the minimum number of subsets required to cover a given set. F ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Utility Functions On Indivisible Goods
Some branches of economics and game theory deal with indivisible goods, discrete items that can be traded only as a whole. For example, in combinatorial auctions there is a finite set of items, and every agent can buy a subset of the items, but an item cannot be divided among two or more agents. It is usually assumed that every agent assigns subjective utility to every subset of the items. This can be represented in one of two ways: * An ordinal utility preference relation, usually marked by \succ. The fact that an agent prefers a set A to a set B is written A \succ B. If the agent only weakly prefers A (i.e. either prefers A or is indifferent between A and B) then this is written A \succeq B. * A cardinal utility function, usually denoted by u. The utility an agent gets from a set A is written u(A). Cardinal utility functions are often normalized such that u(\emptyset)=0, where \emptyset is the empty set. A cardinal utility function implies a preference relation: u(A)>u(B) implies ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
