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

CC BY-SA 3.0
2015-09-23T09:27:58.567Z
It is better to post this as a comment.
optimal control
CC BY-SA 3.0
2015-09-24T13:50:02.037Z
I think Debreu's theorem on additivity https://en.wikipedia.org/wiki/Debreu_theorems#Additivity_of_ordinal_utility_function is about an Euclidean space (e.g. the set of all bundles of a finite number of commodities).
Erel Segal-Halevi
CC BY-SA 3.0
2015-09-24T13:51:50.100Z
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)).
Martin Van der Linden
CC BY-SA 3.0
2015-09-22T15:14:50.787Z
2015-09-22T15:14:50.787Z
ChinG
<p>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).</p>

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

<ul>
<li>Kraft, C. H., Pratt, J. W., &amp; Seidenberg, A. (1959). Intuitive Probability on Finite Sets. The Annals of Mathematical Statistics, 30(2), 408–419.</li>
</ul>

<p>the bulk of which is very well summarized in the introduction of</p>

<ul>
<li>Fishburn, P. C. (1996). Finite linear qualitative probability. Journal of Mathematical Psychology, 40(1), 64–77.</li>
</ul>

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

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

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

<ul>
<li>(Order) : $\succeq$ on $2^S$ is a weak order,</li>
<li>(Nonnegativity) : $A \succeq \emptyset$ for every $A \in 2^S$,</li>
<li>(Nontriviality) : $S \succ \emptyset$,</li>
<li>(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)]$.</li>
</ul>

<p>de Finneti observed that these were necessary but could not determine whether they were sufficient. Eventually, Kraft, Pratt &amp; 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:</p>

<ul>
<li>(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&lt;m$, then we do not have $[A_m \succ B_m]$.</li>
</ul>

<p>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 <em>infinite</em> sets, like your real interval.</p>

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

CC BY-SA 3.0
2015-09-23T19:59:49.387Z
Seems like I am only able to answer your questions for slightly different models than the one you are interested in http://cs.stackexchange.com/questions/10877/fair-division-of-two-dimensional-cake/19254#19254 ;)
Martin Van der Linden
CC BY-SA 3.0
2015-09-23T19:58:26.807Z
2016-01-07T05:27:41.970Z
2016-01-07T05:27:41.970Z
Martin Van der Linden
<p>In a standard problem of <a href="https://en.wikipedia.org/wiki/Far_cake-cutting" rel="nofollow noreferrer">fair cake-cutting</a>, there is a real interval which is called &quot;cake&quot;, and it has to be divided among <span class="math-container">$n$</span> partners. Each partner <span class="math-container">$i$</span> has a subjective value function <span class="math-container">$v_i$</span>, which is an <em>additive</em> function on subsets of the cake. This means that, for every two disjoint subsets <span class="math-container">$A$</span> and <span class="math-container">$B$</span>:</p>
<p><span class="math-container">$$v_i(A\cup B)=v_i(A)+v_i(B)$$</span></p>
<p>Suppose that, instead of a value function, each partner has a <em>preference relation</em> <span class="math-container">$\succeq_i$</span>.</p>
<p>A preference relation <span class="math-container">$\succeq_i$</span> is <em>represented</em> by a value function <span class="math-container">$v_i$</span> iff:</p>
<p><span class="math-container">$$A\succeq_i B \iff v_i(A)\geq v_i(B) $$</span></p>
<p>What properties on the preference relation guarantee that it can be represented by an <em>additive</em> value function?</p>
<p>NOTE: The Wikipedia page <a href="https://en.wikipedia.org/wiki/Ordinal_utility" rel="nofollow noreferrer">Ordinal utility</a> 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.</p>
<p>EXAMPLES:</p>
<p><span class="math-container">$$u_1(A) = \text{len}(A)^2$$</span></p>
<p><span class="math-container">$u_1$</span> is not additive, but the preference relation it represents can be represented by the additive function <span class="math-container">$v_1(A) = \text{len}(A)$</span>.</p>
<p><span class="math-container">$$u_2(A) = \min[\text{len}(A\cap[0,4]),\text{len}(A\cap[4,8])]$$</span></p>
<p>The preference relation represented by <span class="math-container">$u_2$</span> cannot be represented by an additive function. Proof: suppose by contradiction that the preference relation is represented by an additive function <span class="math-container">$v_2$</span>. Then, because:</p>
<p><span class="math-container">$$u_2([0,1])=u_2([4,5])=u_2(\emptyset)$$</span></p>
<p>this must also be true for <span class="math-container">$v_2$</span>:</p>
<p><span class="math-container">$$v_2([0,1])=v_2([4,5])=v_2(\emptyset)$$</span></p>
<p>By additivity:</p>
<p><span class="math-container">$$v_2([0,1]\cup[4,5])=v_2(\emptyset\cup\emptyset)=v_2(\emptyset)$$</span></p>
<p>This must also be true for <span class="math-container">$u_2$</span>:</p>
<p><span class="math-container">$$u_2([0,1]\cup[4,5])=u_2(\emptyset)$$</span></p>
<p>a contradiction.</p>

CC BY-SA 3.0
2015-09-22T09:24:20.687Z
Could you give an example where it cannot be done?
Giskard
CC BY-SA 3.0
2015-09-22T11:36:10.183Z
@denesp added an example.
Erel Segal-Halevi
CC BY-SA 3.0
2015-09-23T21:30:50.333Z
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)?
Martin Van der Linden
CC BY-SA 3.0
2015-09-24T13:54:31.490Z
@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.
Erel Segal-Halevi
CC BY-SA 3.0
2015-09-24T13:57:06.780Z
ok I see, I don't know how I feel about that terminology, but thanks for clarifying.
Martin Van der Linden
<utility><preferences>
Conditions for an additive value function
Erel Segal-Halevi
# Conditions for an additive value function

(Asked by: username_0 on 2015-09-22)

In a standard problem of [fair cake-cutting](https://en.wikipedia.org/wiki/Far_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](https://en.wikipedia.org/wiki/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.

**Tags:** utility, preferences

> **Comments:**
> **username_1**: Could you give an example where it cannot be done?  
> **username_0**: @denesp added an example.  
> **username_2**: 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)?  
> **username_0**: @username_2 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.  
> **username_2**: ok I see, I don't know how I feel about that terminology, but thanks for clarifying.  

---

## 2 answers

### Answer by username_2 on 2015-09-23. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_2**: Seems like I am only able to answer your questions for slightly different models than the one you are interested in http://cs.stackexchange.com/questions/10877/fair-division-of-two-dimensional-cake/19254#19254 ;)  

---

### Answer by username_3 on 2015-09-22. Score: 0

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.

> **Comments:**
> **username_4**: It is better to post this as a comment.  
> **username_0**: I think Debreu's theorem on additivity https://en.wikipedia.org/wiki/Debreu_theorems#Additivity_of_ordinal_utility_function is about an Euclidean space (e.g. the set of all bundles of a finite number of commodities).  
> **username_2**: And I believe the theorem @username_3 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)).  

---

