2
$\begingroup$

In a standard problem of fair cake-cutting, there is a real interval which is called "cake", and it has to be divided among $n$ partners. Each partner $i$ has a subjective value function $v_i$, which is an additive function on subsets of the cake. This means that, for every two disjoint subsets $A$ and $B$:

$$v_i(A\cup B)=v_i(A)+v_i(B)$$

Suppose that, instead of a value function, each partner has a preference relation $\succeq_i$.

A preference relation $\succeq_i$ is represented by a value function $v_i$ iff:

$$A\succeq_i B \iff v_i(A)\geq v_i(B) $$

What properties on the preference relation guarantee that it can be represented by an additive value function?

NOTE: The Wikipedia page Ordinal utility describes some conditions under which a preference relation can be represented by an additive value function. But, it deals with preferences on bundles of homogeneous goods. Here, the preferences are on subsets of a heterogeneous good.

EXAMPLES:

$$u_1(A) = \text{len}(A)^2$$

$u_1$ is not additive, but the preference relation it represents can be represented by the additive function $v_1(A) = \text{len}(A)$.

$$u_2(A) = \min[\text{len}(A\cap[0,4]),\text{len}(A\cap[4,8])]$$

The preference relation represented by $u_2$ cannot be represented by an additive function. Proof: suppose by contradiction that the preference relation is represented by an additive function $v_2$. Then, because:

$$u_2([0,1])=u_2([4,5])=u_2(\emptyset)$$

this must also be true for $v_2$:

$$v_2([0,1])=v_2([4,5])=v_2(\emptyset)$$

By additivity:

$$v_2([0,1]\cup[4,5])=v_2(\emptyset\cup\emptyset)=v_2(\emptyset)$$

This must also be true for $u_2$:

$$u_2([0,1]\cup[4,5])=u_2(\emptyset)$$

a contradiction.

$\endgroup$
  • $\begingroup$ Could you give an example where it cannot be done? $\endgroup$ – Giskard Sep 22 '15 at 9:24
  • 2
    $\begingroup$ @denesp added an example. $\endgroup$ – Erel Segal-Halevi Sep 22 '15 at 11:36
  • $\begingroup$ I think @Nick comment in his answer is on point : why not speak of "utility function" instead of "value function" (which traditionally has many other meanings in econ, e.g. in intertemporal optimization)? $\endgroup$ – Martin Van der Linden Sep 23 '15 at 21:30
  • $\begingroup$ @MartinVanderLinden in some books, "value" means an ordinal function which represents preferences on sure outcomes, and "utility" means a cardinal function which represents preferences on lotteries. This is not consistent, though. $\endgroup$ – Erel Segal-Halevi Sep 24 '15 at 13:54
  • $\begingroup$ ok I see, I don't know how I feel about that terminology, but thanks for clarifying. $\endgroup$ – Martin Van der Linden Sep 24 '15 at 13:57
4
$\begingroup$

This is only a partial answer because it does not exactly fit your framework, but I hope it will still be helpful (and it's too long for a comment).

If you are ok with discretizing your cake into (possibly arbitrarilly small) pieces of cake, then you will find an answer in

  • Kraft, C. H., Pratt, J. W., & Seidenberg, A. (1959). Intuitive Probability on Finite Sets. The Annals of Mathematical Statistics, 30(2), 408–419.

the bulk of which is very well summarized in the introduction of

  • Fishburn, P. C. (1996). Finite linear qualitative probability. Journal of Mathematical Psychology, 40(1), 64–77.

Althought the setup of the papers is in terms of probability jugments, it can be reinterpreted from a preference point of view as follows :

  • A finite set of objects $S = \{1,2,\dots,n\}$ (in your problem $S$ could contain the pieces of the cake)
  • A preference relation $\succeq$ over $2^S$ the set of subsets of $S$.
  • The question : when is $\succeq$ representable by an additive utility function $U$ on $2^S$.

A classical conjecture by de Finetti's was that the following conditions should suffice (here I follows the presentation in Fishburn (1996)):

  • (Order) : $\succeq$ on $2^S$ is a weak order,
  • (Nonnegativity) : $A \succeq \emptyset$ for every $A \in 2^S$,
  • (Nontriviality) : $S \succ \emptyset$,
  • (Additivity) : For all $A,B,C \in 2^S$, if $(A\cup B) \cap C = \emptyset$, then $[A \succ B] \Leftrightarrow [(A\cup C) \succ (B\cup C)]$.

de Finneti observed that these were necessary but could not determine whether they were sufficient. Eventually, Kraft, Pratt & Seidenberg (1959) provided a counter-example as well as an additional condition which, together with the four others implied the existence of an additive representation:

  • (Strong additivity) : for all $m\geq 2$ and all $A_j,B_j \in 2^S$, if $(A_1,\dots,A_M)$ and $(B_1,\dots,B_M)$ contain the same number of replicas of each elements of $S$ (i.e. if $s_1$ appears three times in all the $A_j$ sets, it also appears three times in all the $B_j$ sets, etc) and $A_j \succeq B_j$ for all $j<m$, then we do not have $[A_m \succ B_m]$.

The last condition is often referred to in the literature as the "cancelation" property. Now (Strong additivity) is not the most intuitive condition. In general, it can be hard to to check and navigate, which has spurred a large literature on alternative sufficient condition. I can send you a reading list if you are interested. Unfortunately, I don't remember of any paper directly tackling preferences over subsets of infinite sets, like your real interval.

From my experience with these kinds of problems, changing the domain over which preferences are defined makes a huge difference in terms of the results that hold and the proof techniques you can use. If a result is not already out there in the literature, it is rarely easy to derive it from apparently similar results on different domains.

$\endgroup$
0
$\begingroup$

The only thing I can think of which may be related to your question is Debreu's theorem, which states that preferences which are continuous can be represented by a continuous utility function. Of course, if the utility function is continuous, so is the value function. Also, I think monotonicity could play a role.

$\endgroup$
  • 2
    $\begingroup$ It is better to post this as a comment. $\endgroup$ – optimal control Sep 23 '15 at 9:27
  • 1
    $\begingroup$ I think Debreu's theorem on additivity en.wikipedia.org/wiki/… is about an Euclidean space (e.g. the set of all bundles of a finite number of commodities). $\endgroup$ – Erel Segal-Halevi Sep 24 '15 at 13:50
  • 1
    $\begingroup$ And I believe the theorem @ChinG is refering to is the one on representability of continuous preferences (Debreu (1954), not the one on additive representability of continuous and separable preferences over multidimensional Euclidean spaces (Debreu (1960)). $\endgroup$ – Martin Van der Linden Sep 24 '15 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.