Fractionally subadditive valuation

Last updated October 23, 2024

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}\geq 1$ for all $j\in S$ , we have $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]

Related Research Articles

In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers $n \geq k \geq 0$ and is written $It is the coefficient of the x k term in the polynomial expansion of the binomial power (1 + x) n; this coefficient can be computed by the multiplicative formula$

In mathematics, the concept of a measure is a generalization and formalization of geometrical measures and other common notions, such as magnitude, mass, and probability of events. These seemingly distinct concepts have many similarities and can often be treated together in a single mathematical context. Measures are foundational in probability theory, integration theory, and can be generalized to assume negative values, as with electrical charge. Far-reaching generalizations of measure are widely used in quantum physics and physics in general.

In mathematical analysis and in probability theory, a σ-algebra on a set X is a nonempty collection Σ of subsets of X closed under complement, countable unions, and countable intersections. The ordered pair $is called a measurable space.$

Distributions, also known as Schwartz distributions or generalized functions, are objects that generalize the classical notion of functions in mathematical analysis. Distributions make it possible to differentiate functions whose derivatives do not exist in the classical sense. In particular, any locally integrable function has a distributional derivative.

In set theory, a Woodin cardinal is a cardinal number $such that for all functions, there exists a cardinal with and an elementary embedding from the Von Neumann universe into a transitive inner model with critical point and .$

<span class="mw-page-title-main">Symmetric difference</span> Elements in exactly one of two sets

In mathematics, the symmetric difference of two sets, also known as the disjunctive union and set sum, is the set of elements which are in either of the sets, but not in their intersection. For example, the symmetric difference of the sets $and is .$

In combinatorics, a branch of mathematics, the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as

In the mathematical field of measure theory, an outer measure or exterior measure is a function defined on all subsets of a given set with values in the extended real numbers satisfying some additional technical conditions. The theory of outer measures was first introduced by Constantin Carathéodory to provide an abstract basis for the theory of measurable sets and countably additive measures. Carathéodory's work on outer measures found many applications in measure-theoretic set theory, and was used in an essential way by Hausdorff to define a dimension-like metric invariant now called Hausdorff dimension. Outer measures are commonly used in the field of geometric measure theory.

In functional analysis and related areas of mathematics, locally convex topological vector spaces (LCTVS) or locally convex spaces are examples of topological vector spaces (TVS) that generalize normed spaces. They can be defined as topological vector spaces whose topology is generated by translations of balanced, absorbent, convex sets. Alternatively they can be defined as a vector space with a family of seminorms, and a topology can be defined in terms of that family. Although in general such spaces are not necessarily normable, the existence of a convex local base for the zero vector is strong enough for the Hahn–Banach theorem to hold, yielding a sufficiently rich theory of continuous linear functionals.

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, 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 equals the sum of its values on the sets. Therefore, an additive set function is also called a finitely additive set function . 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,$

In mathematics, particularly in mathematical logic and set theory, a club set is a subset of a limit ordinal that is closed under the order topology, and is unbounded relative to the limit ordinal. The name club is a contraction of "closed and unbounded".

In mathematics, the Jack function is a generalization of the Jack polynomial, introduced by Henry Jack. The Jack polynomial is a homogeneous, symmetric polynomial which generalizes the Schur and zonal polynomials, and is in turn generalized by the Heckman–Opdam polynomials and Macdonald polynomials.

In mathematics, in particular in measure theory, a content $is a real-valued function defined on a collection of subsets such that$

In mathematics, in the area of additive number theory, the Erdős–Fuchs theorem is a statement about the number of ways that numbers can be represented as a sum of elements of a given additive basis, stating that the average order of this number cannot be too close to being a linear 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 $which consists of the real numbers and$

In mathematics, a submodular set function is a set function that, informally, describes the relationship between a set of inputs and an output, where adding more of one input has a decreasing additional benefit. The natural diminishing returns property which makes them suitable for many applications, including approximation algorithms, game theory and electrical networks. Recently, submodular functions have also found 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.

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.

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.

The Price of Anarchy (PoA) is a concept in game theory and mechanism design that measures how the social welfare of a system degrades due to selfish behavior of its agents. It has been studied extensively in various contexts, particularly in auctions.

The welfare maximization problem is an optimization problem studied in economics and computer science. Its goal is to partition a set of items among agents with different utility functions, such that the welfare – defined as the sum of the agents' utilities – is as high as possible. In other words, the goal is to find an item allocation satisfying the utilitarian rule.

References

1 2 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.
↑ 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.
↑ 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.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[n00-1] 1 2 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.

[f09-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.

[cks16-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.

[1]

[2]

[3]