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 . The fact that an agent prefers a set to a set is written . If the agent only weakly prefers (i.e. either prefers or is indifferent between and ) then this is written . A cardinal utility function, usually denoted by . The utility an agent gets from a set is written . Cardinal utility functions are often normalized such that , where is the empty set. A cardinal utility function implies a preference relation: implies and implies . Utility functions can have several properties. Monotonicity means that an agent always (weakly) prefers to have extra items. Formally: For a preference relation: implies . For a utility function: implies (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. Additive utility 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.