Fractionally subadditive valuation

Last updated January 04, 2024

A set function is called fractionally subadditive, or XOS (not to be confused with OXS), 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.^[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: 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, any vector space has a corresponding dual vector space consisting of all linear forms on together with the vector space structure of pointwise addition and scalar multiplication by constants.

The knapsack problem is the following problem in combinatorial optimization:

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.

<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 mathematics, in set theory, the constructible universe, denoted by $, is a particular class of sets that can be described entirely in terms of simpler sets. is the union of the constructible hierarchy . It was introduced by Kurt Gödel in his 1938 paper "The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis". In this paper, he proved that the constructible universe is an inner model of ZF set theory, and also that the axiom of choice and the generalized continuum hypothesis are true in the constructible universe. This shows that both propositions are consistent with the basic axioms of set theory, if ZF itself is consistent. Since many other theorems only hold in systems in which one or both of the propositions is true, their consistency is an important result.$

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.

<span class="mw-page-title-main">Dirichlet distribution</span> Probability distribution

In probability and statistics, the Dirichlet distribution (after Peter Gustav Lejeune Dirichlet), often denoted $, is a family of continuous multivariate probability distributions parameterized by a vector of positive reals. It is a multivariate generalization of the beta distribution, hence its alternative name of multivariate beta distribution (MBD) . Dirichlet distributions are commonly used as prior distributions in Bayesian statistics, and in fact, the Dirichlet distribution is the conjugate prior of the categorical distribution and multinomial distribution.$

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 linear algebra, the computation of the permanent of a matrix is a problem that is thought to be more difficult than the computation of the determinant of a matrix despite the apparent similarity of the definitions.

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.

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.

In the mathematical discipline of functional analysis, a differentiable vector-valued function from Euclidean space is a differentiable function valued in a topological vector space (TVS) whose domains is a subset of some finite-dimensional Euclidean space. It is possible to generalize the notion of derivative to functions whose domain and codomain are subsets of arbitrary topological vector spaces (TVSs) in multiple ways. But when the domain of a TVS-valued function is a subset of a finite-dimensional Euclidean space then many of these notions become logically equivalent resulting in a much more limited number of generalizations of the derivative and additionally, differentiability is also more well-behaved compared to the general case. This article presents the theory of $-times continuously differentiable functions on an open subset of Euclidean space, which is an important special case of differentiation between arbitrary TVSs. This importance stems partially from the fact that every finite-dimensional vector subspace of a Hausdorff topological vector space is TVS isomorphic to Euclidean space so that, for example, this special case can be applied to any function whose domain is an arbitrary Hausdorff TVS by restricting it to finite-dimensional vector subspaces.$

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]