Search Results for “utility functions on indivisible goods”

Source: 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

≻

{\displaystyle \succ }

. The fact that an agent prefers a set

A

{\displaystyle A}

to a set

B

{\displaystyle B}

is written

A
≻
B

{\displaystyle A\succ B}

. If the agent only weakly prefers

A

{\displaystyle A}

(i.e. either prefers

A

{\displaystyle A}

or is indifferent between

A

{\displaystyle A}

and

B

{\displaystyle B}

) then this is written

A
⪰
B

{\displaystyle A\succeq B}

.
A cardinal utility function, usually denoted by

u

{\displaystyle u}

. The utility an agent gets from a set

A

{\displaystyle A}

is written

u
(
A
)

{\displaystyle u(A)}

. Cardinal utility functions are often normalized such that

u
(
∅
)
=
0

{\displaystyle u(\emptyset )=0}

, where

∅

{\displaystyle \emptyset }

is the empty set.
A cardinal utility function implies a preference relation:

u
(
A
)
>
u
(
B
)

{\displaystyle u(A)>u(B)}

implies

A
≻
B

{\displaystyle A\succ B}

and

u
(
A
)
≥
u
(
B
)

{\displaystyle u(A)\geq u(B)}

implies

A
⪰
B

{\displaystyle A\succeq B}

. Utility functions can have several properties.

Monotonicity

utility

Additivity

Submodularity and supermodularity

Subadditivity and superadditivity

functions

utility

Superadditivity means that for every pair of disjoint sets

A
,
B

{\displaystyle A,B}

u
(
A
∪
B
)
≥
u
(
A
)
+
u
(
B
)

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

In other words,

u

{\displaystyle u}

is a superadditive set function.
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

u
(
{
X
,
Y
}
)
+
u
(
{
Y
,
Z
}
)
<
u
(
{
X
,
Y
}
∪
{
Y
,
Z
}
)
+
u
(
{
X
,
Y
}
∩
{
Y
,
Z
}
)
.

{\displaystyle u(\{X,Y\})+u(\{Y,Z\})

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.
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.
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

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

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

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

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

{\displaystyle u(\{X,Y\})

Unit demand

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

{\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}

.
For a utility function: For every set

A

{\displaystyle A}

:

u
(
A
)
=

max

x
∈
A

u
(

x

)

{\displaystyle 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.

Gross substitutes

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:

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}

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: