Utility functions on indivisible goods

<h2 id="monotonicity">Monotonicity</h2>
<p><a href="/facts/Monotonicity/MjQK0YL2">Monotonicity</a> means that an agent always (weakly) prefers to have extra items. Formally:
</p>
<ul><li>For a preference relation: 
  
    
      
        A
        ⊇
        B
      
    
    {\displaystyle A\supseteq B}
  
 implies 
  
    
      
        A
        ⪰
        B
      
    
    {\displaystyle A\succeq B}
  
.</li>
<li>For a utility function: 
  
    
      
        A
        ⊇
        B
      
    
    {\displaystyle A\supseteq B}
  
 implies 
  
    
      
        u
        (
        A
        )
        ≥
        u
        (
        B
        )
      
    
    {\displaystyle u(A)\geq u(B)}
  
 (i.e. <i>u</i> is a <a href="/facts/Monotone_function/MjQK0YL2">monotone function</a>).</li></ul>
<p>Monotonicity is equivalent to the <i>free disposal</i> assumption: if an agent may always discard unwanted items, then extra items can never decrease the utility.
</p>
<h2 id="additivity">Additivity</h2>
<p class="note">Main article: <a href="/facts/Additive_utility/xWMFGEeN">Additive utility</a></p>
Additive utility<table><tbody><tr><th>                    A              {\displaystyle A}  </th><th>                    u        (        A        )              {\displaystyle u(A)}  </th></tr><tr><td>                    ∅              {\displaystyle \emptyset }  </td><td>0</td></tr><tr><td>apple</td><td>5</td></tr><tr><td>hat</td><td>7</td></tr><tr><td>apple and hat</td><td>12</td></tr></tbody></table>
<p>Additivity (also called <i>linearity</i> or <i>modularity</i>) 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 
  
    
      
        A
      
    
    {\displaystyle A}
  
 of items,
</p>

u
        (
        A
        )
        =
        
          ∑
          
            x
            ∈
            A
          
        
        u
        (
        
          x
        
        )
      
    
    {\displaystyle u(A)=\sum _{x\in A}u({x})}

<p>assuming that 
  
    
      
        u
        (
        ∅
        )
        =
        0
      
    
    {\displaystyle u(\emptyset )=0}
  
. In other words, 
  
    
      
        u
      
    
    {\displaystyle u}
  
 is an <a href="/facts/Additive_map/lyCB3yy0">additive function</a>. An equivalent definition is: for any sets of items 
  
    
      
        A
      
    
    {\displaystyle A}
  
 and 
  
    
      
        B
      
    
    {\displaystyle B}
  
,
</p>

u
        (
        A
        )
        +
        u
        (
        B
        )
        =
        u
        (
        A
        ∪
        B
        )
        +
        u
        (
        A
        ∩
        B
        )
        .
      
    
    {\displaystyle u(A)+u(B)=u(A\cup B)+u(A\cap B).}

<p>An additive utility function is characteristic of <a href="/facts/Independent_goods/6FDMlQGT">independent goods</a>. 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.
</p>
<h2 id="submodularity-and-supermodularity">Submodularity and supermodularity</h2>
Submodular utility<table><tbody><tr><th>                    A              {\displaystyle A}  </th><th>                    u        (        A        )              {\displaystyle u(A)}  </th></tr><tr><td>                    ∅              {\displaystyle \emptyset }  </td><td>0</td></tr><tr><td>apple</td><td>5</td></tr><tr><td>bread</td><td>7</td></tr><tr><td>apple and bread</td><td>9</td></tr></tbody></table>
<p>Submodularity means that "the whole is not more than the sum of its parts (and may be less)." Formally, for all sets 
  
    
      
        A
      
    
    {\displaystyle A}
  
 and 
  
    
      
        B
      
    
    {\displaystyle B}
  
,
</p>

u
        (
        A
        )
        +
        u
        (
        B
        )
        ≥
        u
        (
        A
        ∪
        B
        )
        +
        u
        (
        A
        ∩
        B
        )
      
    
    {\displaystyle u(A)+u(B)\geq u(A\cup B)+u(A\cap B)}

<p>In other words, 
  
    
      
        u
      
    
    {\displaystyle u}
  
 is a <a href="/facts/Submodular_set_function/YNnlKb4U">submodular set function</a>.
</p><p>An equivalent property is <a href="/facts/Marginal_utility/ElXNboxy">diminishing marginal utility</a>, which means that for any sets 
  
    
      
        A
      
    
    {\displaystyle A}
  
 and 
  
    
      
        B
      
    
    {\displaystyle B}
  
 with 
  
    
      
        A
        ⊆
        B
      
    
    {\displaystyle A\subseteq B}
  
, and every 
  
    
      
        x
        ∉
        B
      
    
    {\displaystyle x\notin B}
  
:<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a>
</p>

u
        (
        A
        ∪
        {
        x
        }
        )
        −
        u
        (
        A
        )
        ≥
        u
        (
        B
        ∪
        {
        x
        }
        )
        −
        u
        (
        B
        )
      
    
    {\displaystyle u(A\cup \{x\})-u(A)\geq u(B\cup \{x\})-u(B)}
  
.
<p>A submodular utility function is characteristic of <a href="/facts/Substitute_goods/oK7UJNjw">substitute goods</a>. 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.
</p>
Supermodular utility<table><tbody><tr><th>                    A              {\displaystyle A}  </th><th>                    u        (        A        )              {\displaystyle u(A)}  </th></tr><tr><td>                    ∅              {\displaystyle \emptyset }  </td><td>0</td></tr><tr><td>apple</td><td>5</td></tr><tr><td>knife</td><td>7</td></tr><tr><td>apple and knife</td><td>15</td></tr></tbody></table>
<p>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 
  
    
      
        A
      
    
    {\displaystyle A}
  
 and 
  
    
      
        B
      
    
    {\displaystyle B}
  
,
</p>

u
        (
        A
        )
        +
        u
        (
        B
        )
        ≤
        u
        (
        A
        ∪
        B
        )
        +
        u
        (
        A
        ∩
        B
        )
      
    
    {\displaystyle u(A)+u(B)\leq u(A\cup B)+u(A\cap B)}

<p>In other words, 
  
    
      
        u
      
    
    {\displaystyle u}
  
 is a <a href="/facts/Supermodular_function/EkrRrU0f">supermodular set function</a>.
</p><p>An equivalent property is <i>increasing marginal utility</i>, which means that for all sets 
  
    
      
        A
      
    
    {\displaystyle A}
  
 and 
  
    
      
        B
      
    
    {\displaystyle B}
  
 with 
  
    
      
        A
        ⊆
        B
      
    
    {\displaystyle A\subseteq B}
  
, and every 
  
    
      
        x
        ∉
        B
      
    
    {\displaystyle x\notin B}
  
: 
</p>

u
        (
        B
        ∪
        {
        x
        }
        )
        −
        u
        (
        B
        )
        ≥
        u
        (
        A
        ∪
        {
        x
        }
        )
        −
        u
        (
        A
        )
      
    
    {\displaystyle u(B\cup \{x\})-u(B)\geq u(A\cup \{x\})-u(A)}
  
.
<p>A supermoduler utility function is characteristic of <a href="/facts/Complementary_goods/rl5DuIKa">complementary goods</a>. 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.
</p><p>A utility function is additive if and only if it is both submodular and supermodular.
</p>
<h2 id="subadditivity-and-superadditivity">Subadditivity and superadditivity</h2>
Subadditive but not submodular<table><tbody><tr><th>                    A              {\displaystyle A}  </th><th>                    u        (        A        )              {\displaystyle u(A)}  </th></tr><tr><td>                    ∅              {\displaystyle \emptyset }  </td><td>0</td></tr><tr><td>X or Y or Z</td><td>2</td></tr><tr><td>X,Y or Y,Z or Z,X</td><td>3</td></tr><tr><td>X,Y,Z</td><td>5</td></tr></tbody></table>
<p>Subadditivity means that for every pair of disjoint sets 
  
    
      
        A
        ,
        B
      
    
    {\displaystyle A,B}

</p>

u
        (
        A
        ∪
        B
        )
        ≤
        u
        (
        A
        )
        +
        u
        (
        B
        )
      
    
    {\displaystyle u(A\cup B)\leq u(A)+u(B)}

<p>In other words, 
  
    
      
        u
      
    
    {\displaystyle u}
  
 is a <a href="/facts/Subadditive_set_function/xHkWC2UG">subadditive set function</a>.
</p><p>Assuming 
  
    
      
        u
        (
        ∅
        )
      
    
    {\displaystyle u(\emptyset )}
  
 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, 
  
    
      
        X
        ,
        Y
      
    
    {\displaystyle 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
</p>

u
        (
        {
        X
        ,
        Y
        }
        )
        +
        u
        (
        {
        Y
        ,
        Z
        }
        )
        <
        u
        (
        {
        X
        ,
        Y
        }
        ∪
        {
        Y
        ,
        Z
        }
        )
        +
        u
        (
        {
        X
        ,
        Y
        }
        ∩
        {
        Y
        ,
        Z
        }
        )
        .
      
    
    {\displaystyle u(\{X,Y\})+u(\{Y,Z\})<u(\{X,Y\}\cup \{Y,Z\})+u(\{X,Y\}\cap \{Y,Z\}).}

Superadditive but not supermodular<table><tbody><tr><th>                    A              {\displaystyle A}  </th><th>                    u        (        A        )              {\displaystyle u(A)}  </th></tr><tr><td>                    ∅              {\displaystyle \emptyset }  </td><td>0</td></tr><tr><td>X or Y or Z</td><td>1</td></tr><tr><td>X,Y or Y,Z or Z,X</td><td>3</td></tr><tr><td>X,Y,Z</td><td>4</td></tr></tbody></table>
<p>Superadditivity means that for every pair of disjoint sets 
  
    
      
        A
        ,
        B
      
    
    {\displaystyle A,B}

</p>

u
        (
        A
        ∪
        B
        )
        ≥
        u
        (
        A
        )
        +
        u
        (
        B
        )
      
    
    {\displaystyle u(A\cup B)\geq u(A)+u(B)}

<p>In other words, 
  
    
      
        u
      
    
    {\displaystyle u}
  
 is a <a href="/facts/Superadditive_set_function/j42fFuIW">superadditive set function</a>.
</p><p>Assuming 
  
    
      
        u
        (
        ∅
        )
      
    
    {\displaystyle u(\emptyset )}
  
 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, 
  
    
      
        X
        ,
        Y
      
    
    {\displaystyle X,Y}
  
, 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
</p>

<p>A utility function with 
  
    
      
        u
        (
        ∅
        )
        =
        0
      
    
    {\displaystyle u(\emptyset )=0}
  
 is said to be additive if and only if it is both superadditive and subadditive.
</p><p>With the typical assumption that 
  
    
      
        u
        (
        ∅
        )
        =
        0
      
    
    {\displaystyle u(\emptyset )=0}
  
, 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.
</p><p>In particular, if a submodular function is not subadditive, then 
  
    
      
        u
        (
        ∅
        )
      
    
    {\displaystyle u(\emptyset )}
  
 must be negative.
For example, suppose there are two items, 
  
    
      
        X
        ,
        Y
      
    
    {\displaystyle X,Y}
  
, with 
  
    
      
        u
        (
        ∅
        )
        =
        −
        1
      
    
    {\displaystyle u(\emptyset )=-1}
  
, 
  
    
      
        u
        (
        {
        X
        }
        )
        =
        u
        (
        {
        Y
        }
        )
        =
        1
      
    
    {\displaystyle u(\{X\})=u(\{Y\})=1}
  
 and 
  
    
      
        u
        (
        {
        X
        ,
        Y
        }
        )
        =
        3
      
    
    {\displaystyle u(\{X,Y\})=3}
  
.
This utility function is submodular and supermodular and non-negative except on the empty set, but is not subadditive, since
</p>

u
        (
        {
        X
        ,
        Y
        }
        )
        >
        u
        (
        {
        X
        }
        )
        +
        u
        (
        {
        Y
        }
        )
        .
      
    
    {\displaystyle u(\{X,Y\})>u(\{X\})+u(\{Y\}).}

<p>Also, if a supermodular function is not superadditive, then 
  
    
      
        u
        (
        ∅
        )
      
    
    {\displaystyle u(\emptyset )}
  
 must be positive.
Suppose instead that 
  
    
      
        u
        (
        ∅
        )
        =
        u
        (
        {
        X
        }
        )
        =
        u
        (
        {
        Y
        }
        )
        =
        u
        (
        {
        X
        ,
        Y
        }
        )
        =
        1
      
    
    {\displaystyle u(\emptyset )=u(\{X\})=u(\{Y\})=u(\{X,Y\})=1}
  
.
This utility function is non-negative, supermodular, and submodular, but is not superadditive, since
</p>

u
        (
        {
        X
        ,
        Y
        }
        )
        <
        u
        (
        {
        X
        }
        )
        +
        u
        (
        {
        Y
        }
        )
        .
      
    
    {\displaystyle u(\{X,Y\})<u(\{X\})+u(\{Y\}).}

<h2 id="unit-demand">Unit demand</h2>
<p class="note">Main article: <a href="/facts/Unit_demand/KhESgJnV">Unit demand</a></p>
Unit demand utility<table><tbody><tr><th>                    A              {\displaystyle A}  </th><th>                    u        (        A        )              {\displaystyle u(A)}  </th></tr><tr><td>                    ∅              {\displaystyle \emptyset }  </td><td>0</td></tr><tr><td>apple</td><td>5</td></tr><tr><td>pear</td><td>7</td></tr><tr><td>apple and pear</td><td>7</td></tr></tbody></table>
<p>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:
</p>
<ul><li>For a preference relation: for every set 
  
    
      
        B
      
    
    {\displaystyle B}
  
 there is a subset 
  
    
      
        A
        ⊆
        B
      
    
    {\displaystyle A\subseteq B}
  
 with cardinality 
  
    
      
        
          |
        
        A
        
          |
        
        =
        1
      
    
    {\displaystyle |A|=1}
  
, such that 
  
    
      
        A
        ⪰
        B
      
    
    {\displaystyle A\succeq B}
  
.</li>
<li>For a utility function:  For every set 
  
    
      
        A
      
    
    {\displaystyle A}
  
:<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a></li></ul>

u
        (
        A
        )
        =
        
          max
          
            x
            ∈
            A
          
        
        u
        (
        
          x
        
        )
      
    
    {\displaystyle u(A)=\max _{x\in A}u({x})}

<p>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.
</p>
<h2 id="gross-substitutes">Gross substitutes</h2>

<p class="note">Main article: <a href="/facts/Gross_substitutes_(indivisible_items)/0oopxzVJ">Gross substitutes (indivisible items)</a></p>
<p>Gross substitutes (GS) means that the agents regards the items as <a href="/facts/Substitute_goods/oK7UJNjw">substitute goods</a> or <a href="/facts/Independent_goods/6FDMlQGT">independent goods</a> but not <a href="/facts/Complementary_goods/rl5DuIKa">complementary goods</a>. There are many formal definitions to this property, all of which are equivalent. 
</p>
<ul><li>Every UD valuation is GS, but the opposite is not true.</li>
<li>Every GS valuation is submodular, but the opposite is not true.</li></ul>
<p>See <a href="/facts/Gross_substitutes_(indivisible_items)/0oopxzVJ">Gross substitutes (indivisible items)</a> for more details.
</p><p>Hence the following relations hold between the classes:
</p>

U
        D
        ⊊
        G
        S
        ⊊
        S
        u
        b
        m
        o
        d
        u
        l
        a
        r
        ⊊
        S
        u
        b
        a
        d
        d
        i
        t
        i
        v
        e
      
    
    {\displaystyle UD\subsetneq GS\subsetneq Submodular\subsetneq Subadditive}

<p>See diagram on the right.
</p>
<h2 id="aggregates-of-utility-functions">Aggregates of utility functions</h2>
<p>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 <a href="/facts/Social_welfare_function/m5f7lA1t">social welfare function</a>, and it is usually an <a href="/facts/Aggregate_function/685obrqz">aggregate function</a> of two or more utility functions. If the individual utility functions are additive, then the following is true for the aggregate functions:
</p>
<table><tbody><tr><th rowspan="2">Aggregatefunction</th><th rowspan="2">Property</th><th colspan="4">Examplevalues of functionson {a}, {b} and {a,b}</th></tr><tr><th>f</th><th>g</th><th>h</th><th>aggregate(f,g,h)</th></tr><tr><td><a href="/facts/Summation/V2WUxoKn">Sum</a></td><td>Additive</td><td>1,3; 4</td><td>3,1; 4</td><td></td><td>4,4; 8</td></tr><tr><td><a href="/facts/Average/etawWjw4">Average</a></td><td>Additive</td><td>1,3; 4</td><td>3,1; 4</td><td></td><td>2,2; 4</td></tr><tr><td><a href="/facts/Minimum/ADlgnyzV">Minimum</a></td><td>Super-additive</td><td>1,3; 4</td><td>3,1; 4</td><td></td><td>1,1; 4</td></tr><tr><td><a href="/facts/Maximum/ADlgnyzV">Maximum</a></td><td>Sub-additive</td><td>1,3; 4</td><td>3,1; 4</td><td></td><td>3,3; 4</td></tr><tr><td rowspan="2"><a href="/facts/Median/YwXGWTyr">Median</a></td><td rowspan="2">neither</td><td>1,3; 4</td><td>3,1; 4</td><td>1,1; 2</td><td>1,1; 4</td></tr><tr><td>1,3; 4</td><td>3,1; 4</td><td>3,3; 6</td><td>3,3; 4</td></tr></tbody></table>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Utility_functions_on_divisible_goods/J71DywVR">Utility functions on divisible goods</a></li>
<li><a href="/facts/Single-minded_agent/9tXCJaKH">Single-minded agent</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Gul, F.; Stacchetti, E. (1999). "Walrasian Equilibrium with Gross Substitutes". Journal of Economic Theory. 87: 95–124. doi:10.1006/jeth.1999.2531. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Moulin, Hervé (1991). Axioms of cooperative decision making. Cambridge England New York: Cambridge University Press. ISBN 9780521424585. <a href="9780521424585" target="_blank">9780521424585</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Koopmans, T. C.; Beckmann, M. (1957). "Assignment Problems and the Location of Economic Activities" (PDF). Econometrica. 25 (1): 53–76. doi:10.2307/1907742. JSTOR 1907742. <a href="http://cowles.yale.edu/sites/default/files/files/pub/d00/d0004.pdf" target="_blank">http://cowles.yale.edu/sites/default/files/files/pub/d00/d0004.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
</ol>

Utility functions on indivisible goods open-in-new

Utility functions on indivisible goods