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 between two or more agents.

It is usually assumed that every agent assigns subjective utility to every subset of the items. This can be represented by 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 marked 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 $A \succ B$ and $u(A)\geq u(B)$ implies $A \succeq B$.

Utility functions can have several properties.^[1]

Monotonicity

Monotonicity means that an agent always (weakly) prefers to have extra items. Formally:

• For a preference relation: $A\supseteq B$ implies $A \succeq B$.
• For a utility function: $A\supseteq B$ implies $u(A) \geq B$ (i.e. u is a monotone function).

Monotonicity is equivalent to the free disposal assumption: if an agent may always discard unwanted items, then extra items can never decrease the utility.

Additivity

Additive utility

$A$	$u(A)$
$\emptyset$	0
apple	5
hat	7
apple and hat	12

Additivity (also called: linearity) means that "the whole is equal to the sum of its parts". I.e, 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 $A$:

$u(A)=\sum_{x\in A}u({x})$

In other words, $u$ is an additive function.

An equivalent definition is: for all sets $A$ and $B$:

$u(A)+u(B) = u(A\cup B)+u(A\cap B)$

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.

Submodularity and Supermodularity

Submodular utility

$A$	$u(A)$
$\emptyset$	0
apple	5
bread	7
apple and bread	9

Submodularity means that "the whole is not more than the sum of its parts (but may be less)". Formally, for all sets $A$ and $B$:

$u(A\cup B)+u(A\cap B)\leq u(A)+u(B)$

In other words, $u$ is a submodular set function.

An equivalent property is Diminishing marginal utility, which means that for every sets $A$ and $B$ with $A \subseteq B$, and every $x \notin B$:^[2]

$u(A\cup \{x\})-u(A)\geq u(B\cup \{x\})-u(B)$.

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.

Supermodular utility

$A$	$u(A)$
$\emptyset$	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 (but may be more)". I.e, if $A$ and $B$ are sets, then:

$u(A)+u(B) \leq u(A\cup B)+u(A\cap B)$

In other words, $u$ is a supermodular set function.

An equivalent property is Increasing marginal utility, which means that for all sets $A$ and $B$ with $A \subseteq B$, and every $x \notin B$:

$u(B\cup \{x\})-u(B)\geq u(A\cup \{x\})-u(A)$.

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 supermodular and submodular.

Subadditivity and Superadditivity

Subadditive which is not submodular

$A$	$u(A)$
$\emptyset$	0
X or Y or Z	4
X,Y or Y,Z or Z,X	6
X,Y,Z	9

Subadditivity means that for every pair of disjoint sets $A,B$:

$u(A\cup B)\leq u(A)+u(B)$

In other words, $u$ is a subadditive set function.

Every submodular function is subadditive, but the opposite is not true. For example, assume that there are 3 identical items, X Y 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:

$u(\{X,Y\})+u(\{Y,Z\}) < u(\{X,Y\}\cup\{Y,Z\})+u(\{X,Y\}\cap\{Y,Z\})$

Superadditivity is the opposite of subadditivity and means that for every pair of disjoint sets $A,B$:

$u(A\cup B)\geq u(A)+u(B)$

In other words, $u$ is a superadditive set function.

Every supermodular function is superadditive.

A utility function is additive if and only if it is both superadditive and subadditive.

Special types of submodular utilities

Because of their relation to diminishing marginal utility, submodular utility functions are very common in economics. Several sub-families of the submodular family are described below, in order of containment, from the more specific to the more general.

Unit demand

Unit demand utility

$A$	$u(A)$
$\emptyset$	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:

• For a preference relation: for every set $B$ there is a subset $A\subseteq B$ with cardinality $|A|=1$, such that $A \succeq B$.
• For a utility function: For every set $A$:^[3]

$u(A)=\max_{x\in A}u({x})$

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.

Strong no complementarities

A utility function satisfies the strong no complementarities condition (SNC) if for all sets $A$ and $B$ and for every subset $X\subseteq A$, there is a subset $Y\subseteq B$ such that:

$u(A)+u(B)\leq u(A\setminus A' \cup B')+u(B\setminus B' \cup A)$

This property has the following interpretation. Suppose Alice and Bob both have utility function $u$, and are endowed with bundles $A$ and $B$ respectively. For every subset $A'$ that Alice hands Bob, there is an equivalent subset $B'$ that Bob can handle Alice, such that their total utility after the swap is preserved or increased.^[1]

Note: to check whether u has no complementarities, it is sufficient to consider the cases in which $A'\subseteq A\setminus B$. And it is sufficient to check the non-trivial subsets, i.e, the cases in which $A'\neq \emptyset$ and $A'\neq A\setminus B$. And for these cases, we only need to search among bundles $B'\subseteq B\setminus A$.

A utility function $u$ has SNC, if-and-only-if for every price-vector $p$, the net-utility function $u-p$ also has SNC (since the SNC condition is invariant to price).

Gross substitutes

Submodular which is not GS

$A$	$u(A)$
$\emptyset$	0
X	50
Y	50
Z	51
X,Y	92
X,Z	90
Y,Z	89
X,Y,Z	100

The gross substitutes (GS) family^[4] is defined based on a price vector and a demand set.

• A price vector $p$ is a vector containing a price for each item.
• Given a utility function $u$ and a price vector $p$, a set $A$ is called a demand if it maximizes the net utility of the agent: $u(A)-p\cdot A$.
• The demand set $D(u,p)$ is the set of all demands.

A utility function is GS if it has either one of the following properties, which are all equivalent for monotone function:^[1]

• GS: When the price of some items increases, the demand for other items does not decrease. Formally, for any two price vectors $q$ and $p$ such that $q\geq p$, and any $A \in D(u,p)$, there is a $B \in D(u,q)$ such that $B \supseteq \{a\in A|p_a=q_a\}$ (B contains all items in A whose price remained constant).
• SI (Single Improvement): A non-optimal set can be improved by adding, removing or substituting a single item. Formally, for any price vector $p$ and bundle $A \notin D(u,p)$, there exists a bundle $B$ such that $u(B)-p\cdot B > u(A)-p\cdot A$, $|A\setminus B|\leq 1$ and $|B\setminus A|\leq 1$.
• NC (No Complementarities): Every subset of a demanded bundle has a substitute. Formally: for any price vector $p$ and demanded bundles $A,B \in D(u,p)$, and for every subset $A'\subseteq A$, there is a subset $B'\subseteq B$ such that: $A\setminus A' \cup B' \in D(u,p)$

Relations between families of utility functions

An illustration of the containment relations between common classes of utility functions.

Every monotone GS utility function is submodular. Moreover, if u is monotone and GS, then for every price-vector p, the utility function u−p is also submodular.^{[1] :100}

The converse is not true: there are submodular functions which are not GS.^[5] An example is given in the table to the right. The utility is submodular since it satisfies the decreasing-marginal-utility property: the marginal-utility of an item is 50-51 when added to an empty set, 38-42 when added to a single item and 8-11 when added to a pair of items. But it violates the 3 equivalent requirements of the GS family:

• GS is violated with prices $p_X=p_Y=p_Z=40$, since the demanded bundle is {X,Y}, but when $p_X$ increases to e.g. 200 (such that X is no longer demanded), the new demanded bundle is {Z}. The increase in $p_X$ decreased the demand for item Y.
• SI is violated with prices $p_X=p_Y=p_Z=40$, since the bundle {Z} is not optimal but the only way to improve it is to change it to {X,Y}, which requires to add two items.
• NC is violated with prices $p_X=p_Y=40$ and $p_Z=39$, since there are two demanded bundles: {X,Y} and {Z} (both have net utility 12). But, if Y is taken from the first set, there is nothing from the second set that can substitute it.

Every unit-demand (UD) utility function satisfies the strong-no-complementarities (SNC) property.

Every SNC function satisfies the NC condition (hence also GS and SI). Proof: Fix an SNC utility function $u$ and a price-vector $p$. Let $A,B$ be two bundles in the demand-set $D(u,p)$. This means that they have the same net-utility, E.g, $U_p:=u_p(A)=u_p(B)$, and all other bundles have a net-utility of at most $U_p$. By the SNC condition, for every $A'\subset A$, there exists $B'\subseteq B$ such that $u_p(A\setminus A'\cup B)+u_p(B\setminus B'\cup A) \geq u_p(A)+u_p(B) = 2\cdot U_p$. But $u_p(A\setminus A'\cup B)$ and $u_p(B\setminus B'\cup A)$ are both at most $U_p$. Hence, both must be exactly $U_p$. Hence, both are also in $D(u,p)$.

Hence the following relations hold between the classes:

$UD \subsetneq SNC\subsetneq NC = SI = GS \subsetneq Submodular \subsetneq Subadditive$

See diagram on the right.

Aggregates of utility functions

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[6]
		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

See also

• Subjective theory of value
• Competitive equilibrium#Indivisible item assignment

References

1. Gul, F.; Stacchetti, E. (1999). "Walrasian Equilibrium with Gross Substitutes". Journal of Economic Theory 87: 95. doi:10.1006/jeth.1999.2531.
2. Moulin, Hervé (1991). Axioms of cooperative decision making. Cambridge England New York: Cambridge University Press. ISBN 9780521424585.
3. Koopmans, T. C.; Beckmann, M. (1957). "Assignment Problems and the Location of Economic Activities". Econometrica 25: 53. doi:10.2307/1907742. JSTOR 1907742.
4. Kelso, A. S.; Crawford, V. P. (1982). "Job Matching, Coalition Formation, and Gross Substitutes". Econometrica 50 (6): 1483. doi:10.2307/1913392. JSTOR 1913392.
5. Ben-Zwi, Oren; Lavi, Ron; Newman, Ilan (2013). "Ascending auctions and Walrasian equilibrium". arXiv:1301.1153 [cs.GT].
6. values of functions on {a}, {b} and {a,b}.