View source for 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 <math>\succ</math>. The fact that an agent prefers a set <math>A</math> to a set <math>B</math> is written <math>A \succ B</math>. If the agent only weakly prefers <math>A</math> (i.e. either prefers <math>A</math> or is indifferent between <math>A</math> and <math>B</math>) then this is written <math>A \succeq B</math>.
* A [[cardinal utility]] function, usually denoted by <math>u</math>. The utility an agent gets from a set <math>A</math> is written <math>u(A)</math>. Cardinal utility functions are often normalized such that <math>u(\emptyset)=0</math>, where <math>\emptyset</math> is the empty set.

A cardinal utility function implies a preference relation: <math>u(A)>u(B)</math> implies <math>A \succ B</math> and <math>u(A)\geq u(B)</math> implies <math>A \succeq B</math>. Utility functions can have several properties.<ref name=gs99>{{Cite journal | doi = 10.1006/jeth.1999.2531| title = Walrasian Equilibrium with Gross Substitutes| journal = Journal of Economic Theory| volume = 87| pages = 95–124| year = 1999| last1 = Gul | first1 = F. | last2 = Stacchetti | first2 = E. }}</ref>

== Monotonicity ==
[[Monotonicity]] means that an agent always (weakly) prefers to have extra items. Formally:
* For a preference relation: <math>A\supseteq B</math> implies <math>A \succeq B</math>.
* For a utility function: <math>A\supseteq B</math> implies <math>u(A) \geq  u(B)</math> (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 ==
{{Main|Additive utility}}
{| class="wikitable" style="float:right"
|+Additive utility
|-
! <math>A</math> !! <math>u(A)</math>
|-
| <math>\emptyset</math> || 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 <math>A</math> of items,
:<math>u(A)=\sum_{x\in A}u({x})</math>
assuming that <math>u(\emptyset)=0</math>. In other words, <math>u</math> is an [[additive map|additive function]]. An equivalent definition is: for any sets of items <math>A</math> and <math>B</math>,
:<math>u(A)+u(B) = u(A\cup B)+u(A\cap B).</math>

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.

== {{Anchor|submodular|supermodular}}Submodularity and supermodularity ==

{| class="wikitable" style="float:right"
|+Submodular utility
|-
! <math>A</math> !! <math>u(A)</math>
|-
| <math>\emptyset</math> || 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 <math>A</math> and <math>B</math>,
:<math>u(A)+u(B)\ge u(A\cup B)+u(A\cap B)</math>
In other words, <math>u</math> is a [[submodular set function]].

An equivalent property is [[Marginal utility#Diminishing marginal utility|diminishing marginal utility]], which means that for any sets <math>A</math> and <math>B</math> with <math>A \subseteq B</math>, and every <math>x \notin B</math>:<ref>{{cite book | last = Moulin | first = Hervé | title = Axioms of cooperative decision making | publisher = Cambridge University Press | location = Cambridge England New York | year = 1991 | isbn = 9780521424585 }}</ref>
:<math>u(A\cup \{x\})-u(A)\geq u(B\cup \{x\})-u(B)</math>.

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.

{| class="wikitable" style="float:right"
|+Supermodular utility
|-
! <math>A</math> !! <math>u(A)</math>
|-
| <math>\emptyset</math> || 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 <math>A</math> and <math>B</math>,
:<math>u(A)+u(B) \leq u(A\cup B)+u(A\cap B)</math>
In other words, <math>u</math> is a [[Supermodular_function#Supermodular_functions_of_subsets|supermodular set function]].

An equivalent property is ''increasing marginal utility'', which means that for all sets <math>A</math> and <math>B</math> with <math>A \subseteq B</math>, and every <math>x \notin B</math>: 
:<math>u(B\cup \{x\})-u(B)\geq u(A\cup \{x\})-u(A)</math>.

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 [[#Additivity|additive]] if and only if it is both submodular and supermodular.

== Subadditivity and superadditivity ==
{| class="wikitable" style="float:right; width:300px"
|+Subadditive but not submodular
|-
! <math>A</math> !! <math>u(A)</math>
|-
| <math>\emptyset</math> || 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 <math>A,B</math>
::<math>u(A\cup B)\leq u(A)+u(B)</math>
In other words, <math>u</math> is a [[subadditive set function]].

Assuming <math>u(\emptyset)</math> 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, <math>X, Y</math>, 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
::<math> u(\{X,Y\})+u(\{Y,Z\}) < u(\{X,Y\}\cup\{Y,Z\})+u(\{X,Y\}\cap\{Y,Z\}). </math>



{| class="wikitable" style="float:right; width:300px"
|+Superadditive but not supermodular
|-
! <math>A</math> !! <math>u(A)</math>
|-
| <math>\emptyset</math> || 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 <math>A,B</math>
::<math>u(A\cup B)\geq u(A)+u(B)</math>
In other words, <math>u</math> is a [[superadditive set function]].

Assuming <math>u(\emptyset)</math> 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, <math>X, Y</math>, 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
::<math> u(\{X,Y\})+u(\{Y,Z\}) < u(\{X,Y\}\cup\{Y,Z\})+u(\{X,Y\}\cap\{Y,Z\}). </math>

A utility function with <math>u(\emptyset) = 0</math> is said to be [[#Additivity|additive]] if and only if it is both superadditive and subadditive.

With the typical assumption that <math>u(\emptyset) = 0</math>, 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 <math>u(\emptyset)</math> must be negative.
For example, suppose there are two items, <math>X, Y</math>, with <math>u(\emptyset) = -1</math>, <math>u(\{X\}) = u(\{Y\}) = 1</math> and <math>u(\{X, Y\}) = 3</math>.
This utility function is submodular and supermodular and non-negative except on the empty set, but is not subadditive, since
::<math>u(\{X,Y\}) > u(\{X\}) + u(\{Y\}).</math>
Also, if a supermodular function is not superadditive, then <math>u(\emptyset)</math> must be positive.
Suppose instead that <math>u(\emptyset) = u(\{X\}) = u(\{Y\}) = u(\{X, Y\}) = 1</math>.
This utility function is non-negative, supermodular, and submodular, but is not superadditive, since
::<math>u(\{X,Y\}) < u(\{X\}) + u(\{Y\}).</math>

== Unit demand ==
{{Main|Unit demand}}
{| class="wikitable" style="float:right"
|+Unit demand utility
|-
! <math>A</math> !! <math>u(A)</math>
|-
| <math>\emptyset</math> || 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 <math>B</math> there is a subset <math>A\subseteq B</math> with cardinality <math>|A|=1</math>, such that <math>A \succeq B</math>.
* For a utility function:  For every set <math>A</math>:<ref name=kb57>{{Cite journal | doi = 10.2307/1907742| jstor = 1907742| title = Assignment Problems and the Location of Economic Activities| journal = Econometrica| volume = 25| issue = 1| pages = 53–76| year = 1957| last1 = Koopmans | first1 = T. C. | last2 = Beckmann | first2 = M. | url = http://cowles.yale.edu/sites/default/files/files/pub/d00/d0004.pdf}}</ref>
:<math>u(A)=\max_{x\in A}u({x})</math>

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 ==
[[File:Utilities.png|thumb|An illustration of the containment relations between common classes of utility functions.]]
{{Main|Gross substitutes (indivisible items)}}
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. 
* Every UD valuation is GS, but the opposite is not true. 
* Every GS valuation is submodular, but the opposite is not true. 
See [[Gross substitutes (indivisible items)]] for more details.

Hence the following relations hold between the classes:
:<math>UD \subsetneq GS \subsetneq Submodular \subsetneq Subadditive</math>
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 [[#Additivity|additive]], then the following is true for the aggregate functions:

{| class="wikitable"
|-
! rowspan=2 | Aggregate<br/>function !!  rowspan=2 | Property !! colspan=4| Example<br/>{{small|values of functions<br/>on {a}, {b} and {a,b}}}
|-
! f        !! g        !! h        !! aggregate(f,g,h)
|-
| [[Summation|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
|-
|rowspan="2"| [[Median]]  ||rowspan="2"| 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==

*[[Utility functions on divisible goods]]
*[[Single-minded agent]]

== References ==
{{reflist}}

[[Category:Utility function types]]
[[Category:Combinatorial optimization]]