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:
A cardinal utility function implies a preference relation: implies and implies . Utility functions can have several properties. [1]
Monotonicity means that an agent always (weakly) prefers to have extra items. Formally:
Monotonicity is equivalent to the free disposal assumption: if an agent may always discard unwanted items, then extra items can never decrease the utility.
0 | |
apple | 5 |
hat | 7 |
apple and hat | 12 |
Additivity (also called linearity or modularity) means that "the whole is equal to the sum of its parts." That is, the utility of a set of items is the sum of the utilities of each item separately. This property is relevant only for cardinal utility functions. It says that for every set of items,
assuming that . In other words, is an additive function. An equivalent definition is: for any sets of items and ,
An additive utility function is characteristic of independent goods. For example, an apple and a hat are considered independent: the utility a person receives from having an apple is the same whether or not he has a hat, and vice versa. A typical utility function for this case is given at the right.
0 | |
apple | 5 |
bread | 7 |
apple and bread | 9 |
Submodularity means that "the whole is not more than the sum of its parts (and may be less)." Formally, for all sets and ,
In other words, is a submodular set function.
An equivalent property is diminishing marginal utility, which means that for any sets and with , and every : [2]
A submodular utility function is characteristic of substitute goods. For example, an apple and a bread loaf can be considered substitutes: the utility a person receives from eating an apple is smaller if he has already ate bread (and vice versa), since he is less hungry in that case. A typical utility function for this case is given at the right.
0 | |
apple | 5 |
knife | 7 |
apple and knife | 15 |
Supermodularity is the opposite of submodularity: it means that "the whole is not less than the sum of its parts (and may be more)". Formally, for all sets and ,
In other words, is a supermodular set function.
An equivalent property is increasing marginal utility, which means that for all sets and with , and every :
A supermoduler utility function is characteristic of complementary goods. For example, an apple and a knife can be considered complementary: the utility a person receives from an apple is larger if he already has a knife (and vice versa), since it is easier to eat an apple after cutting it with a knife. A possible utility function for this case is given at the right.
A utility function is additive if and only if it is both submodular and supermodular.
0 | |
X or Y or Z | 2 |
X,Y or Y,Z or Z,X | 3 |
X,Y,Z | 5 |
Subadditivity means that for every pair of disjoint sets
In other words, is a subadditive set function.
Assuming is non-negative, every submodular function is subadditive. However, there are non-negative subadditive functions that are not submodular. For example, assume that there are 3 identical items, , and Z, and the utility depends only on their quantity. The table on the right describes a utility function that is subadditive but not submodular, since
0 | |
X or Y or Z | 1 |
X,Y or Y,Z or Z,X | 3 |
X,Y,Z | 4 |
Superadditivity means that for every pair of disjoint sets
In other words, is a superadditive set function.
Assuming is non-positive, every supermodular function is superadditive. However, there are non-negative superadditive functions that are not supermodular. For example, assume that there are 3 identical items, , and Z, and the utility depends only on their quantity. The table on the right describes a utility function that is non-negative and superadditive but not supermodular, since
A utility function with is said to be additive if and only if it is both superadditive and subadditive.
With the typical assumption that , every submodular function is subadditive and every supermodular function is superadditive. Without any assumption on the utility from the empty set, these relations do not hold.
In particular, if a submodular function is not subadditive, then must be negative. For example, suppose there are two items, , with , and . This utility function is submodular and supermodular and non-negative except on the empty set, but is not subadditive, since
Also, if a supermodular function is not superadditive, then must be positive. Suppose instead that . This utility function is non-negative, supermodular, and submodular, but is not superadditive, since
0 | |
apple | 5 |
pear | 7 |
apple and pear | 7 |
Unit demand (UD) means that the agent only wants a single good. If the agent gets two or more goods, he uses the one of them that gives him the highest utility, and discards the rest. Formally:
A unit-demand function is an extreme case of a submodular function. It is characteristic of goods that are pure substitutes. For example, if there are an apple and a pear, and an agent wants to eat a single fruit, then his utility function is unit-demand, as exemplified in the table at the right.
Gross substitutes (GS) means that the agents regards the items as substitute goods or independent goods but not complementary goods. There are many formal definitions to this property, all of which are equivalent.
See Gross substitutes (indivisible items) for more details.
Hence the following relations hold between the classes:
See diagram on the right.
A utility function describes the happiness of an individual. Often, we need a function that describes the happiness of an entire society. Such a function is called a social welfare function, and it is usually an aggregate function of two or more utility functions. If the individual utility functions are additive, then the following is true for the aggregate functions:
Aggregate function | Property | Example values of functions on {a}, {b} and {a,b} | |||
---|---|---|---|---|---|
f | g | h | aggregate(f,g,h) | ||
Sum | Additive | 1,3; 4 | 3,1; 4 | 4,4; 8 | |
Average | Additive | 1,3; 4 | 3,1; 4 | 2,2; 4 | |
Minimum | Super-additive | 1,3; 4 | 3,1; 4 | 1,1; 4 | |
Maximum | Sub-additive | 1,3; 4 | 3,1; 4 | 3,3; 4 | |
Median | neither | 1,3; 4 | 3,1; 4 | 1,1; 2 | 1,1; 4 |
1,3; 4 | 3,1; 4 | 3,3; 6 | 3,3; 4 |
In economics, an indifference curve connects points on a graph representing different quantities of two goods, points between which a consumer is indifferent. That is, any combinations of two products indicated by the curve will provide the consumer with equal levels of utility, and the consumer has no preference for one combination or bundle of goods over a different combination on the same curve. One can also refer to each point on the indifference curve as rendering the same level of utility (satisfaction) for the consumer. In other words, an indifference curve is the locus of various points showing different combinations of two goods providing equal utility to the consumer. Utility is then a device to represent preferences rather than something from which preferences come. The main use of indifference curves is in the representation of potentially observable demand patterns for individual consumers over commodity bundles.
In mathematics, subadditivity is a property of a function that states, roughly, that evaluating the function for the sum of two elements of the domain always returns something less than or equal to the sum of the function's values at each element. There are numerous examples of subadditive functions in various areas of mathematics, particularly norms and square roots. Additive maps are special cases of subadditive functions.
In mathematics, a function
In economics, an ordinal utility function is a function representing the preferences of an agent on an ordinal scale. Ordinal utility theory claims that it is only meaningful to ask which option is better than the other, but it is meaningless to ask how much better it is or how good it is. All of the theory of consumer decision-making under conditions of certainty can be, and typically is, expressed in terms of ordinal utility.
In mathematics, a sequence {an}, n ≥ 1, is called superadditive if it satisfies the inequality
In mathematics, a polymatroid is a polytope associated with a submodular function. The notion was introduced by Jack Edmonds in 1970. It is also described as the multiset analogue of the matroid.
In economics, convex preferences are an individual's ordering of various outcomes, typically with regard to the amounts of various goods consumed, with the property that, roughly speaking, "averages are better than the extremes". The concept roughly corresponds to the concept of diminishing marginal utility without requiring utility functions.
Competitive equilibrium is a concept of economic equilibrium introduced by Kenneth Arrow and Gérard Debreu in 1951 appropriate for the analysis of commodity markets with flexible prices and many traders, and serving as the benchmark of efficiency in economic analysis. It relies crucially on the assumption of a competitive environment where each trader decides upon a quantity that is so small compared to the total quantity traded in the market that their individual transactions have no influence on the prices. Competitive markets are an ideal standard by which other market structures are evaluated.
In economics and other social sciences, preference is the order that a person gives to alternatives based on their relative utility, a process which results in an optimal "choice". Instead of the prices of goods, personal income, or availability of goods, the character of the preferences is determined purely by a person's tastes. However, persons are still expected to act in their best interest.
In mathematics, a submodular set 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 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.
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.
Fair item allocation is a kind of a fair division problem in which the items to divide are discrete rather than continuous. The items have to be divided among several partners who value them differently, and each item has to be given as a whole to a single person. This situation arises in various real-life scenarios:
In economics, the Debreu theorems are several statements about the representation of a preference ordering by a real-valued function. The theorems were proved by Gerard Debreu during the 1950s.
Envy-freeness, also known as no-envy, is a criterion for fair division. It says that, when resources are allocated among people with equal rights, each person should receive a share that is, in his or her eyes, at least as good as the share received by any other agent. In other words, no person should feel envy.
In economics, additive utility is a cardinal utility function with the sigma additivity property.
In economics and consumer theory, a linear utility function is a function of the form:
In economics, a unit demand agent is an agent who wants to buy a single item, which may be of one of different types. A typical example is a buyer who needs a new car. There are many different types of cars, but usually a buyer will choose only one of them, based on the quality and the price.
In economics, gross substitutes (GS) is a class of utility functions on indivisible goods. An agent is said to have a GS valuation if, whenever the prices of some items increase and the prices of other items remain constant, the agent's demand for the items whose price remain constant weakly increases.
In utility theory, the responsive set (RS) extension is an extension of a preference-relation on individual items, to a partial preference-relation of item-bundles.
A set function is called fractionally subadditive 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.