Incentive Compatible Two Player Cake Cutting

Introduction

The question of allocating resources among multiple people is one of the most basic questions that humans have been studying. At this level of generality one may say that most of the economic theory is devoted to this problem, as well as other fields of study. One class of scenarios of this form, with an enormous amount of literature, goes by the name of “cake cutting”. In this type of scenario the goods are modeled as the (infinitely divisible) unit interval (the cake), the preferences as (measurable) valuation functions on the cake and the allocation as a partition of the cake. Many variants of this model have been considered and the usual goals are various notions of fairness and efficiency. See, e.g. for an introduction.

Recently the research community has started looking at such models from a mechanism design point of view, i.e., considering the incentives of the players. From this perspective, players act rationally to maximize their utility and will thus “tell” the cake cutting algorithm whatever will make it maximize their own piece’s value. In the simplest formWhich by the revelation mechanisms is really without loss of generality since an arbitrary one, when analyzed at equilibrium, may be converted to an incentive-compatible one where truth is an equilibrium. we would ask for an“incentive compatible” (equivalently, truthful or strategy-proof) cake cutting allocation mechanism where each bidder always maximizes his utility by reporting his true valuation.

Several recent papers have designed incentive-compatible cake cutting mechanisms. For example, in an incentive-compatible, envy-free, Pareto-efficient, and proportional cake cutting mechanism is obtained for the model where player valuations are “uniform”: each player $\displaystyle i$ desires a subset $\displaystyle S_{i}$ of the items, and has a uniform value over this subset with the total value of each player normalized to 1.For purposes of efficient computation, it is also required that the sets would be given as a finite collection of intervals. In , an incentive-compatible, proportional, and Pareto-efficient mechanism is constructed for the case of arbitrary (not necessarily uniform) preferences. A “randomized” cake cutting mechanism that is truthful in expectation with better guarantees is also provided in that paper.

In this paper we seek to characterize incentive-compatible cake cutting mechanisms, and show bounds on possible performance measures. As our model has no “money” (i.e. no transferable utilities) the standard tools of mechanism design with quasi-linear utilities (such as Vickrey-Clarke-Groves or Myerson ) do not apply. In this sense our work lies within the framework of approximate mechanism design without money, advocated, e.g., by . As opposed to most of the cake cutting literature, we focus solely on incentive compatibility and efficiency and do not consider notions of fairness. As our results are mostly “negative”, this only strengthens them. We should mention that the positive results that we provide, i.e. the mechanisms that have the “best” properties among all incentive-compatible ones, turn out to also be envy-free.

Our general model, following that of , considers an infinitely-divisible atom-less cake and considers only the restricted class of uniform player valuations.Again, as our results are mostly “negative” this limited setting strengthens them. Formally, the “cake” is modeled as the real interval $\displaystyle$, each player desires a (measurable) set $\displaystyle A\subseteq$ and his valuation is uniform over that set (and normalized to 1): $\displaystyle V_{A}(S)=|S\cap A|/|A|$, where $\displaystyle|\cdot|$ specifies the usual Lebesgue measure. We restrict ourselves to “non-wasteful” mechanisms, where no piece that is desired by some player may be left unallocated and no piece is allocated to a player that does not want it (this is essentially equivalent to Pareto-efficiency of the outcome.The inessential technical difference is detailed in the next section. While it does not seem that leaving pieces of the cake unallocated can be useful, whether this is really the case remains open.) We restrict ourselves to the case of two players. Thus a non-wasteful mechanism accepts as input the sets $\displaystyle A$ and $\displaystyle B$ desired by the two players and returns two disjoint (measurable) sets $\displaystyle C=C(A,B)\subseteq A$ and $\displaystyle D=D(A,B)\subseteq B$. In this case, the first player’s utility is given by $\displaystyle V_{A}(C)=|C|/|A|$ and the second’s by $\displaystyle V_{B}(D)=|D|/|B|$. A mechanism is called “incentive-compatible” if for every $\displaystyle A,B$ and $\displaystyle A^{\prime}$ we get that $\displaystyle V_{A}(C(A,B))\geq V_{A}(C(A^{\prime},B))$ and similarly for the second player.

As a tool for studying this model, we introduce a simple, one-dimensional “aligned” model. In the aligned model we first restrict the possible player valuations: the first player desires the sub-interval $\displaystyle A=[0,a]$ and the second player desires the sub-interval $\displaystyle B=[1-b,1]$. This is interesting when $\displaystyle 1-b<a$ in which case the question is how to allocate the overlap $\displaystyle[1-b,a]$ between the players. We then also restrict the allowed allocation by the mechanism: the first player must be allocated an interval $\displaystyle C=[0,c]$ and the second an interval $\displaystyle D=[1-d,1]$. Thus, in the aligned model the input is fully specified by its lengths $\displaystyle a$,$\displaystyle b$, the output by its lengths $\displaystyle c$,$\displaystyle d$, and a mechanism is a pair of real valued functions $\displaystyle f=(c(a,b),d(a,b))$. It turns out that these two restrictions offset each other in some sense, allowing us to convert mechanisms between the two models. As the aligned model is really single-dimensional, we are able to fully characterize incentive-compatible mechanisms in it, a characterization that then has strong implications in the general model as well.

(Characterization of Aligned Model) A non-wasteful deterministic mechanism for two-players in the aligned model is incentive-compatible if and only if it is from the following family, characterized by $\displaystyle 0\leq\theta\leq 1$: the allocation gives the first player the interval $\displaystyle\left[0,\min\left\{a,\max\left\{1-b,\theta\right\}\right\}\right]$ while the second player gets the interval $\displaystyle\left[1-\min\left\{b,\max\left\{1-a,1-\theta\right\}\right\},1\right]$.

This characterization holds regardless of any issues of fairness, and the only mechanism in this family that is fair in any sense is that with $\displaystyle\theta=\frac{1}{2}$ which gives envy-freeness and turns out to be equivalent to the mechanism of for the case of two players. This tight characterization in the aligned model allows the calculation of the best achievable results – under any desired performance measure – for incentive-compatible mechanisms. Specifically, we are interested in performance measures that depend on relative lengths of demands and allocations, formally on the set of 4-tuples $\displaystyle(\alpha,\beta,\gamma,\delta)$ where $\displaystyle\alpha=|A|/|A\cup B|$, $\displaystyle\beta=|B|/|A\cup B|$, $\displaystyle\gamma=|C|/|A\cup B|$, and $\displaystyle\delta=|D|/|A\cup B|$.Note that as $\displaystyle|A\cap B|/|A\cup B|=\alpha+\beta-1$, $\displaystyle C\subseteq A$, $\displaystyle D\subseteq B$, $\displaystyle C\cap D=\emptyset$, and $\displaystyle A\cup B=C\cup D$ we have all the information regarding the sizes in the Venn diagram. A typical performance measure of this form is the competitive ratio for social welfare: the worst case ratio between the social welfare achieved by the mechanism (which is $\displaystyle\gamma/\alpha+\delta/\beta$) and that achieved at the optimal allocation (which turns out to be $\displaystyle 1+(1-\min\{\alpha,\beta\})/\max\{\alpha,\beta\}$). Many other variants can be considered, such as looking at other aggregations of the two players’ utility (e.g. $\displaystyle\min\{\gamma/\alpha,\delta/\beta\}$ or $\displaystyle\log(\gamma/\alpha)+\log(\delta/\beta)$), assigning different weights to the different players, using a different comparison benchmark (e.g. the one splitting the intersection equally), using additive regret rather than multiplicative ratio, etc.

We prove the following reductions, which preserve the 4-tuples of ratios $\displaystyle(\alpha,\beta,\gamma,\delta)$, between these models.

Let $\displaystyle f=(c(a,b),d(a,b))$ be an incentive-compatible and non-wasteful mechanism in the aligned model. There exists an incentive-compatible and non-wasteful mechanism $\displaystyle F=(C(A,B),D(A,B))$ in the general model such that for all $\displaystyle A,B$: $\displaystyle|C(A,B)|/|A\cup B|=c(a,b)$ and $\displaystyle|D(A,B)|/|A\cup B|=d(a,b)$ where $\displaystyle a=|A|/|A\cup B|$ and $\displaystyle b=|B|/|A\cup B|$.

Let $\displaystyle F=(C(A,B),D(A,B))$ be an incentive-compatible and non-wasteful mechanism in the general model. There exists an incentive-compatible and non-wasteful mechanism $\displaystyle f=(c(a,b),d(a,b))$ in the aligned model such that for all $\displaystyle a,b$ there exist $\displaystyle A,B$ such that $\displaystyle|A|=a$, $\displaystyle|B|=b$, $\displaystyle c(a,b)=|C(A,B)|$ and $\displaystyle d(a,b)=|D(A,B)|$, and furthermore whenever $\displaystyle a+b\geq 1$ we have that $\displaystyle A\cup B=$.

These two reductions imply that while the general model may be (and actually is) richer, this richness cannot buy anything in terms of performance – for any notion of performance that depends on relative lengths of bids and allocations. For every mechanism with a certain performance level in the general model there exists a mechanism with the same performance level in the aligned model and vice-versa.

Thus our characterization in the aligned model implies the same bounds on performance in the general model as well. For example, in the aligned model, one may easily calculate that at most a fraction of $\displaystyle(8-4\sqrt{3})^{-1}\approx 0.93$ of social welfare can be extracted by any mechanism in the characterized family, and this competitive ratio is in fact obtained by the envy-free mechanism with $\displaystyle\theta=\frac{1}{2}$. The reductions imply that this same bound also applies to mechanisms in the general model. This ratio may thus be termed “the price of truthfulness” in this setting. A complementary result appears in , where the “price of fairness” is studied, comparing envy-free allocations to general ones, and obtaining the same numeric bound on the fraction of the optimal welfare that can be extracted by any envy-free allocation. Our results do not require any notion of fairness, but instead show that incentive-compatibility by itself implies this bound. In fact, for the special case of social welfare we also provide a direct proof for this bound, a proof that also applies to randomized mechanisms.

(Price of Truthfulness) Any deterministic or randomized incentive-compatible mechanism for cake cutting for two-players in the general model, achieves at most a $\displaystyle(8-4\sqrt{3})^{-1}\approx 0.93$ fraction of the optimal welfare for some player valuations.

It should be noted that this is tight, as indeed the deterministic mechanism of achieves this ratio when restricted to two players.

The paper is structured as follows: in section 2 we present our two models, the general one and the aligned one. Section 3 provides the characterization of the aligned model, and section 4 shows the reductions between the models. In section 5 we provide a direct proof of the price of truthfulness result for a randomized mechanism.

Models

Our model has two players each desiring a measurable subset of $\displaystyle$. We will denote by $\displaystyle A\subseteq$ the set desired player I and by $\displaystyle B\subseteq$ the set desired by the player II. We view $\displaystyle A$ and $\displaystyle B$ as private information. Everything else is common knowledge. The players will be assigned disjoint measurable subsets, $\displaystyle C\subseteq$ to player I and $\displaystyle D\subseteq$ to player II. We assume that player valuations are uniform over the subsets they desire and normalized to 1.

The valuation of a player who desires subset $\displaystyle A\subseteq$ for a subset $\displaystyle C\subseteq$ is $\displaystyle V_{A}(C)=|C\cap A|/|A|$, where $\displaystyle|\cdot|$ specifies the Lebesgue measure.

A mechanism is a function which divides the cake between the two players. The function receives as inputs two measurable subsets of $\displaystyle$: $\displaystyle A$ and $\displaystyle B$ (the demands of the players), and outputs two disjoint measurable subsets of $\displaystyle$, $\displaystyle C$ and $\displaystyle D$, where $\displaystyle C$ is the subset that player I receives and $\displaystyle D$ is the subset that player II receives.

We denote a mechanism by $\displaystyle F(A,B)=(C(A,B),D(A,B))$, where $\displaystyle C(\cdot),D(\cdot)$ denote the functions that determine the allocations to the two players, respectively, and must satisfy $\displaystyle C(A,B)\cap D(A,B)=\emptyset$ for all $\displaystyle A,B$.

Our point of view is that the two players are strategic, aiming to maximize their valuation and since $\displaystyle A$ and $\displaystyle B$ are private information the players may “lie” to the mechanism regarding their real interest in the cake if that may give them an allocation with a higher valuation for them.

$\displaystyle F=(C(A,B),D(A,B))$ is called incentive-compatible if none of the players can gain by declaring a subset which is different from the real subset he is interested in. Formally, for all $\displaystyle A,B,A^{\prime}$: $\displaystyle V_{A}(C(A,B))\geq V_{A}(C(A^{\prime},B))$ and similarly for the second player: for all $\displaystyle A,B,B^{\prime}$: $\displaystyle V_{B}(D(A,B))\geq V_{B}(D(A,B^{\prime}))$.

A mechanism $\displaystyle F=(C(A,B),D(A,B))$ is said to be Pareto-efficient if for every input $\displaystyle A,B$ and the corresponding allocation made by the mechanism $\displaystyle C(A,B),D(A,B)$, any other possible allocation $\displaystyle C^{\prime},D^{\prime}$ can not be strictly better for one of the players and at least as good for the other.

Note that two possible allocations $\displaystyle C,D$ and $\displaystyle C^{\prime},D^{\prime}$, which differ only in the division of areas which none of the players is interested in, are equivalent in the eyes of the players. Therefore, we would use a specific Pareto-efficient allocation – a non-wasteful allocation, in which pieces of the cake that neither of the players demanded will not be allocated.

A mechanism $\displaystyle F=(C(A,B),D(A,B))$ is called non-wasteful if for every $\displaystyle A,B$ we have that $\displaystyle C(A,B)\subseteq A$, $\displaystyle D(A,B)\subseteq B$, and $\displaystyle C(A,B)\cup D(A,B)=A\cup B$.

Every non-wasteful mechanism is Pareto-efficient. Every Pareto-efficient mechanism $\displaystyle F=(C(A,B),(D(A,B))$ can be converted to an equivalent non-wasteful one by defining $\displaystyle C^{\prime}(A,B)=C(A,B)\cap A$ and $\displaystyle D^{\prime}(A,B)=D(A,B)\cap B$.

Thus any analysis of non-wasteful mechanisms directly implies a similar one for Pareto-efficient ones, as do all our results in this paper. For a non-wasteful mechanism the valuations of the players are simply $\displaystyle|C|/|A|$ for player I and $\displaystyle|D|/|B|$ for player II.

Although we do not deal directly with the envy-freeness of mechanisms, a mechanism that is described in this paper has this property, as described below.

$\displaystyle F=(C(A,B),D(A,B))$ is called envy-free if each player weakly prefers the piece he received to the piece the other player received. Formally, for all $\displaystyle A,B$: $\displaystyle V_{A}(C(A,B))\geq V_{A}(D(A,B))$ and similarly for the second player, for all $\displaystyle A,B$: $\displaystyle V_{B}(D(A,B))\geq V_{B}(C(A,B))$.

2 The Aligned Model

A special case of the above general model is called the aligned model. The model makes two specializing assumptions, one on player valuations, and the other on mechanism allocations:

The two players are interested in subsets of the form $\displaystyle[0,a]$ for player I and $\displaystyle[1-b,1]$ for player II.

The mechanism must divide te cake so that player I and player II would receive subsets of the form $\displaystyle[0,c]$ and $\displaystyle[1-d,1]$ respectively.

3 The Price of Truthfulness

As noted in the introduction, using the two reductions that will be proved in section 4, it is possible to study a family of performance measures for the aligned model and conclude from that implications for the general models. For example, one of these performance measures is the Price of Truthfulness.

The social welfare of a mechanism $\displaystyle F=(C(A,B),D(A,B))$ on input $\displaystyle A,B$, denoted by $\displaystyle SW_{F}(A,B)$, is $\displaystyle SW_{F}(A,B)=V_{A}(C(A,B))+V_{B}(D(A,B))$.

Denoted by $\displaystyle SW_{max}(A,B)$ is the sum of valuations of the two players in the allocation that maximizes social welfare: $\displaystyle SW_{max}(A,B)=\max_{F}SW_{F}(A,B)$.

The competitive ratio for social welfare of a mechanism $\displaystyle F$ is $\displaystyle\eta_{F}=\min_{A,B}\eta_{F}(A,B)$, where $\displaystyle\eta_{F}(A,B)=\frac{SW_{F}(A,B)}{SW_{max}(A,B)}$.

Similar to the price of anarchy, the price of truthfulness is the highest possible competitive ratio of a truthful mechanism. Formally:

The price of truthfulness is $\displaystyle PoT\equiv\max_{F}\eta_{F}$, where $\displaystyle F$ ranges over all non-wasteful truthful mechanisms.

4 Randomized Mechanisms

In the last part of our paper we will also consider randomized mechanisms. For the purposes of this paper, one may either consider those as a probability distribution over deterministic mechanisms, or allow the mechanism’s allocation $\displaystyle(C,D)$ to be a random variable.

The Aligned Model

(Characterization of Aligned Model) A non-wasteful deterministic mechanism for two-players in the aligned model is incentive-compatible if and only if it is from the following family, characterized by $\displaystyle 0\leq\theta\leq 1$: the allocation gives the first player the interval $\displaystyle\left[0,\min\left\{a,\max\left\{1-b,\theta\right\}\right\}\right]$ while the second player gets the interval $\displaystyle\left[1-\min\left\{b,\max\left\{1-a,1-\theta\right\}\right\},1\right]$.

The remainder of this subsection is a proof of the above theorem.

Assume $\displaystyle f(a,b)=(c(a,b),d(a,b))$ is a non-wasteful incentive-compatible deterministic mechanism for two-players in the aligned model.

In case $\displaystyle a+b\leq 1$, there is no overlap between the demands of the players which are aligned to the sides. Therefore, from non-wastefulness, the mechanism would have to give each player all of his demand (and that is clearly incentive-compatible and deterministic). We can also notice that this scenario matches the expressions for the pieces of the cake allocated to the players from the theorem, regardless of $\displaystyle\theta$.

During the rest of this proof, we will assume that there is an overlap between the demands of the player, i.e. $\displaystyle a+b>1$.

For the mechanism $\displaystyle f(a,b)=(c(a,b),d(a,b))$ and a fixed demand $\displaystyle b$ for player II, we will denote by $\displaystyle c_{b}(a)$ the function $\displaystyle c(a,b)$, which determines the size of the piece that the mechanism gives to player I according to his demands $\displaystyle a$. In a similar way $\displaystyle d_{a}(b)$ is also defined.

For every $\displaystyle b$, the function $\displaystyle c_{b}(a)$ of the mechanism $\displaystyle f(a,b)$ is non decreasing and Lipschitz continuous (with a Lipschitz constant $\displaystyle K=1$).

For $\displaystyle a<a^{\prime}$, say that $\displaystyle c_{b}(a)>c_{b}(a^{\prime})$, then from non-wastefulness, $\displaystyle a^{\prime}>a\geq c_{b}(a)>c_{b}(a^{\prime})$. Therefore, if player I’s real interest is a piece of size $\displaystyle a^{\prime}$, he can gain strictly more by demanding $\displaystyle a$ instead. He would receive not only a larger piece of the cake, but also a larger piece of his interest, due to the alignment of the piece to the side. That stands in contradiction to the incentive-compatibility of the mechanism. Hence, $\displaystyle c_{b}(a)\leq c_{b}(a^{\prime})$, meaning that $\displaystyle c_{b}(a)$ is non decreasing.

Furthermore, for $\displaystyle a<a^{\prime}$, $\displaystyle c_{b}(a^{\prime})-c_{b}(a)\leq a^{\prime}-a$. Otherwise, if $\displaystyle c_{b}(a^{\prime})-c_{b}(a)>a^{\prime}-a$, this means that $\displaystyle c_{b}(a^{\prime})-a^{\prime}+a>c_{b}(a)$. Since the mechanism is non-wasteful, $\displaystyle c_{b}(a^{\prime})\leq a^{\prime}$, and therefore $\displaystyle a>c_{b}(a)$. In such a case, if player I’s real interest is of size $\displaystyle a$, he will not receive all of his demand. Therefore, he might lie and demand $\displaystyle a^{\prime}$ instead. By asking for $\displaystyle a^{\prime}$ he would receive a larger piece ($\displaystyle c_{b}(a^{\prime})-a^{\prime}+a>c_{b}(a)\Rightarrow c_{b}(a^{\prime})>c_{b}(a)$), which because of the alignment, has a larger intersection with his real interest. Again, this contradicts the incentive-compatibility of the mechanism.

We have that $\displaystyle c_{b}(a)$ is Lipschitz continuous (with a Lipschitz constant $\displaystyle K=1$).

Therefore $\displaystyle c_{b}(a)$ is continuous. Hence, in the interval $\displaystyle$ it must attain a maximum value, and the following quantities are well defined.

$\displaystyle\mu(b)$ is the maximal piece size that player I can receive, when player II demands a piece of size $\displaystyle b$. Formally, $\displaystyle\mu(b)\equiv\max_{a}{c_{b}(a)}$.

In the same way $\displaystyle\nu(a)\equiv\max_{b}{d_{a}(b)}$ is defined for player II.

We will denote by $\displaystyle a_{m}$ the minimal $\displaystyle a$ for which $\displaystyle c_{b}(a_{m})=\mu(b)$.

For the mechanism $\displaystyle f(a,b)$ as mentioned, for every $\displaystyle b$:

For $\displaystyle a<a_{m}$, $\displaystyle c_{b}(a)$ can not be larger than $\displaystyle a$, because of the non-wastefulness of $\displaystyle f(a,b)$. If $\displaystyle c_{b}(a)<a$, then player I, whose real interest is of size $\displaystyle a$, does not receive all of his interest and therefore would prefer to lie and ask for $\displaystyle a_{m}$. Since $\displaystyle a<a_{m}$, by definition of $\displaystyle a_{m}$, $\displaystyle c_{b}(a)<c_{b}(a_{m})$. Not only would player I receive a strictly larger piece by lying, since the piece is aligned to the side, he would also receive a strictly larger piece of his real interest. This stands in contradiction to the incentive-compatibility of $\displaystyle f$. Therefore, $\displaystyle c_{b}(a)=a$.

For $\displaystyle a>a_{m}$, since $\displaystyle c_{b}(a)$ is non-decreasing, $\displaystyle c_{b}(a)\geq c_{b}(a_{m})$. It is also known that $\displaystyle c_{b}(a_{m})=\mu(b)$ is the maximal value of $\displaystyle c_{b}(a)$. Therefore, $\displaystyle c_{b}(a)=\mu(b)$.

We showed that for $\displaystyle a<a_{m}$, $\displaystyle c_{b}(a)=a$, hence $\displaystyle c_{b}(a_{m})=a_{m}$ by continuity. Since $\displaystyle c_{b}(a_{m})=\mu(b)$, $\displaystyle a_{m}=\mu(b)$.

Putting everything together, we get that $\displaystyle c_{b}(a)=\min\left\{a,\mu(b)\right\}$.

Characterization of player II’s piece size for a fixed $\displaystyle a$ can be done in the same way to obtain $\displaystyle d_{a}(b)=\min\left\{b,\nu(a)\right\}$.

Now, we can continue to the characterization of the function $\displaystyle\mu(b)$.

We should notice that $\displaystyle\mu(1)+\nu(1)=1$ (from non-wastefulness, in case both players want the whole cake we should divide the whole cake).

The function $\displaystyle\mu(b)$ must be of the form:

(For $\displaystyle\theta\in$). (see Figure 2)

According to the function $\displaystyle c_{b}(a)$, which we found earlier, the size of the piece that player I receives is $\displaystyle\min\{a,\mu(b)\}$. As mentioned in the beginning of the subsection, we assume that $\displaystyle a+b>1$. As we are examining the aligned model, the mechanism should divide the whole interval $\displaystyle$. Therefore, player II would receive $\displaystyle 1-\min\{a,\mu(b)\}$. We also know that the form of the function $\displaystyle d_{a}(b)$ resembles the form of $\displaystyle c_{b}(a)$ and that means that the size of the piece that player II receives is $\displaystyle\min\{b,\nu(a)\}$. Combined together:

Let us look at the last equation for $\displaystyle a=1$:

We also know that $\displaystyle\mu(b)$ does not depend on $\displaystyle a$. Therefore, the last statement is true in general and not only for $\displaystyle a=1$. We showed previously that $\displaystyle\mu(1)+\nu(1)=1$. Let us denote $\displaystyle\theta\equiv\mu(1)=1-\nu(1)$, and rewrite $\displaystyle\mu(b)$ ($\displaystyle\nu(a)$ can be found in a similar way):

If we insert those $\displaystyle\mu(b)$ and $\displaystyle\nu(a)$ into the expressions for $\displaystyle c_{b}(a)$ and $\displaystyle d_{a}(b)$ that we found earlier, we would get that $\displaystyle c(a,b)=\min\{a,\max\{1-b,\theta\}\}$ and $\displaystyle d(a,b)=\min\{b,\max\{1-a,1-\theta\}\}$, as in the statement of the theorem.

In the opposite direction, it can be noticed that the allocation is deterministic. Furthermore, for all values of $\displaystyle a,b$ and $\displaystyle\theta$, each of the players either receives all of his demand, or a maximal value which depends only on the other player. Therefore, he cannot gain by lying. Moreover, $\displaystyle c(a,b)+d(a,b)=\min\{a+b,1\}$, and because of the alignment of the interests and allocations, this type of allocation is non-wasteful.

We conclude that this is in fact the family of all possible mechanisms. We will denote by $\displaystyle f_{\theta}$ the mechanism with the parameter $\displaystyle\theta$ from that family.

2 Social Welfare in the Aligned Model

The non-wasteful and incentive-compatible deterministic mechanism $\displaystyle f_{\frac{1}{2}}$ for the aligned model achieves $\displaystyle\eta_{f_{\frac{1}{2}}}=(8-4\sqrt{3})^{-1}\approx 0.93$.

Moreover, it can be noticed that $\displaystyle\theta=\frac{1}{2}$ is the only $\displaystyle\theta$ for which $\displaystyle f_{\theta}$ is envy-free.

Reductions

Let $\displaystyle f=(c(a,b),d(a,b))$ be an incentive-compatible and non-wasteful mechanism for the aligned model. There exists an incentive-compatible and non-wasteful mechanism $\displaystyle F=(C(A,B),D(A,B))$ for the general model such that for all $\displaystyle A,B$: $\displaystyle|C(A,B)|/|A\cup B|=c(a,b)$ and $\displaystyle|D(A,B)|/|A\cup B|=d(a,b)$ where $\displaystyle a\equiv|A|/|A\cup B|$ and $\displaystyle b\equiv|B|/|A\cup B|$.

Note that from the properties of $\displaystyle f$ it has to be from the family of mechanisms described in the previous section. Therefore there is a $\displaystyle\theta$ such that $\displaystyle f$ is $\displaystyle f_{\theta}$.

For that $\displaystyle f_{\theta}$, we will define mechanism $\displaystyle F(A,B)$ as follows:

Use the mechanism $\displaystyle f_{\theta}$ to calculate the size of the players’ allocations $\displaystyle(c(a,b),d(a,b))$ when:The division by $\displaystyle|A\cup B|$ in this phase is a normalization of the original demands over a full $\displaystyle$ interval.

$\displaystyle a=\frac{|A|}{|A\cup B|}$, meaning player I demands the section $\displaystyle[0,\frac{|A|}{|A\cup B|}]$.

$\displaystyle b=\frac{|B|}{|A\cup B|}$, meaning player II demands the section $\displaystyle[1-\frac{|B|}{|A\cup B|},1]$.

Calculate $\displaystyle|C(A,B)|\equiv c(a,b)\cdot|A\cup B|$ and $\displaystyle|D(A,B)|\equiv d(a,b)\cdot|A\cup B|$. A normalization of the results back to the original interval.

Give player I pieces in a total size of $\displaystyle|C(A,B)|$ and Player II pieces in a total size of $\displaystyle|D(A,B)|$. For each of them – start at first from giving the cake intervals that only he asked for, then move to intervals in the joint area.

The size of the piece that mechanism $\displaystyle F$ would allocate to player I is: $\displaystyle|C(A,B)|=|A\cup B|\cdot\min\{\frac{|A|}{|A\cup B|},\max\{1-\frac{|B|}{|A\cup B|},\theta\}\}=\min\{|A|,\max\{|A\cup B|-|B|,\theta\cdot|A\cup B|\}\}=\min\{|A|,\max\{|A\setminus B|,\theta\cdot|A\cup B|\}\}$. In a similar way we can get the expression for the size of player II’s piece.

The mechanism assigns two pieces with total size of $\displaystyle|C(A,B)|+|D(A,B)|=(c(a,b)+d(a,b))\cdot|A\cup B|\underset{a+b\geq 1\rightarrow c+d=1}{=}|A\cup B|$, meaning the total size that was assigned is equal to the total requested size. Moreover, $\displaystyle c(a,b)\leq a=\frac{|A|}{|A\cup B|}$, therefore $\displaystyle|C(A,B)|\leq|A|$ and in the same way $\displaystyle|D(A,B)|\leq|B|$. This means that the mechanism gives each player no more than his demand. Therefore, it is possible to construct the player’s allocation only from intervals he has asked for. Since the allocation of those pieces starts with intervals that only one player asked for and because the total size allocated is $\displaystyle|A\cup B|$, the division is non-wasteful.

$\displaystyle F$ is incentive-compatible.

In this proof we examine a general subset $\displaystyle A_{1}$ which differs from the real interest of player I, $\displaystyle A$. We look at the symmetric difference between those two subsets, divide it into 4 disjoint sets, and one after the other show that zeroing the size of a set cannot damage the player. Therefore, he has no interest to lie. This lemma is fully proved in the appendix.

Concluding, the mechanism $\displaystyle F$ meets the demands of the theorem, thus completing the proof.

Say we choose $\displaystyle f$ and examine the matching mechanism $\displaystyle F$, as described. If the inputs for mechanism $\displaystyle F$ are $\displaystyle A,B$, we can look at the 4-tuple of ratios created by $\displaystyle F$: $\displaystyle\left(\frac{|A|}{|A\cup B|},\frac{|B|}{|A\cup B|},\frac{|C|}{|A\cup B|},\frac{|D|}{|A\cup B|}\right)$. The above reduction shows that the inputs $\displaystyle a=\frac{|A|}{|A\cup B|},b=\frac{|B|}{|A\cup B|}$ for mechanism $\displaystyle f$ will result in the output $\displaystyle c=\frac{|C|}{|A\cup B|},d=\frac{|D|}{|A\cup B|}$. Since $\displaystyle a+b=\frac{|A|}{|A\cup B|}+\frac{|B|}{|A\cup B|}\geq 1$ and since the requests are aligned to different sides, the total demand made by the two players is of size 1. Therefore, in this case, the 4-tuple of ratios is $\displaystyle(a,b,c,d)$, which is identical to the 4-tuple that was obtained by $\displaystyle F$ on the inputs $\displaystyle A,B$.

2 Reduction From the General to the Aligned Model

Let $\displaystyle F=(C(A,B),D(A,B))$ be an incentive-compatible and non-wasteful mechanism for the general model. There exists an incentive-compatible and non-wasteful mechanism $\displaystyle f=(c(a,b),d(a,b))$ for the aligned model, such that for all $\displaystyle a,b$ there exist $\displaystyle A,B$ such that $\displaystyle|A|=a$, $\displaystyle|B|=b$, $\displaystyle c(a,b)=|C(A,B)|$ and $\displaystyle d(a,b)=|D(A,B)|$, and furthermore whenever $\displaystyle a+b\geq 1$ we have that $\displaystyle A\cup B=$.

For mechanism $\displaystyle F(A,B)$ as mentioned, we will define mechanism $\displaystyle f(a,b)$ as follows:

Give players I and II pieces $\displaystyle\left[0,c(a,b)\right]$ and $\displaystyle\left[1-d(a,b),1\right]$ respectively.

$\displaystyle f=(c(a,b),d(a,b))$ is non-wasteful and incentive-compatible.

For $\displaystyle F=(C(A,B),D(A,B))$ and $\displaystyle f=(c(a,b),d(a,b))$ as defined, for all $\displaystyle a,b$ there exists $\displaystyle A,B$ such that $\displaystyle|A|=a$, $\displaystyle|B|=b$, $\displaystyle c(a,b)=|C(A,B)|$ and $\displaystyle d(a,b)=|D(A,B)|$, and furthermore whenever $\displaystyle a+b\geq 1$ we have that $\displaystyle A\cup B=$.

Concluding, the mechanism $\displaystyle f$ meets the demands of the theorem, completing the proof.

Say we choose $\displaystyle F$ and examine the matching mechanism $\displaystyle f$, as described. Denote the inputs of mechanism $\displaystyle f$ as $\displaystyle a,b$. If $\displaystyle a+b\leq 1$, choosing $\displaystyle A=[0,a],B=[1-b,1]$ as inputs for $\displaystyle F$ will result in each of the players receiving all of his demand, causing an identical 4-tuple of ratios for the two mechanisms: $\displaystyle\left(\frac{a}{a+b},\frac{b}{a+b},\frac{a}{a+b},\frac{b}{a+b}\right)$. If $\displaystyle a+b>1$, the union of the players’ demands is of size 1. The theorem shows that there are $\displaystyle A,B$ such that $\displaystyle|A|=a,|B|=b,|C(A,B)|=c(a,b),|D(A,B)|=d(a,b)$ and furthermore, $\displaystyle|A\cup B|=1$. Therefore, the ratio 4-tuples obtained by $\displaystyle f(a,b)$ and $\displaystyle F(A,B)$ (for the specific $\displaystyle A$ and $\displaystyle B$ suggested in the theorem) are identical: $\displaystyle(a,b,c,d)$.

The Price of Truthfulness

As was mentioned in Remark 3, it is possible to show that for any $\displaystyle 0\leq\theta\leq 1~{},~{}\theta\neq\frac{1}{2}$, the competitive ratio of the social welfare of the mechanism $\displaystyle f_{\theta}$ (marked as $\displaystyle\eta_{f_{\theta}}$), is $\displaystyle<(8-4\sqrt{3})^{-1}$. Using the two reductions from the last section, we can conclude that there isn’t a non-wasteful, incentive-compatible, deterministic mechanism for the general model with higher $\displaystyle\eta$. Moreover, Since $\displaystyle\eta_{f_{\frac{1}{2}}}=(8-4\sqrt{3})^{-1}$, there is an incentive-compatible, non-wasteful deterministic mechanism $\displaystyle F$ for general modelThis mechanism is $\displaystyle F$ that is generated by reduction 4.2 using the mechanism $\displaystyle f_{\frac{1}{2}}$. which achieves $\displaystyle\eta_{F}=(8-4\sqrt{3})^{-1}\approx 0.93$.

We will now prove a stronger claim - this upper bound still holds even if the mechanism can be wasteful or randomized, as long as the valuation functions are of the same form which we defined in the general model (actually, the exact proof is even stronger and also works even if the players are limited only to the aligned model’s valuation functions).

(Price of Truthfulness) Any deterministic or randomized incentive-compatible mechanism for cake cutting for two-players in the general model, achieves at most a $\displaystyle(8-4\sqrt{3})^{-1}\approx 0.93$ fraction of the optimal welfare for some player valuations.

Say each of the two players’ real demand is the whole cake: $\displaystyle$. We will denote by $\displaystyle p$ and $\displaystyle q$ the expected sizes of the pieces of cake that the mechanism gives player I and player II in that case, respectively. W.l.o.g we assume that player I received the (weakly) smaller piece, $\displaystyle p\leq q$ and since $\displaystyle p+q\leq 1$, $\displaystyle p\leq\frac{1}{2}$.

Now, we will examine what happens if player I’s demand is $\displaystyle A=[0,1-\tau]$ for some $\displaystyle 0\leq\tau\leq 1$, and player II’s demand remains unchanged. Intuitively, in order to maximize the social welfare, as a player demands a smaller piece, the mechanism needs to give him a larger allocation (in case he really asks for his real demand). However, from incentive-compatibility, the size of the piece that player I will receive can not be greater than $\displaystyle p$ (if it did, it would have been better for him to lie in the previous case and ask for the smaller piece instead of the whole cake). We denote by $\displaystyle p^{\prime},q^{\prime}$ the expected size of the pieces that the players receive in that case.

The minimal value of this expression is $\displaystyle(8-4\sqrt{3})^{-1}$ at $\displaystyle\tau=2-\sqrt{3}$.

Therefore, $\displaystyle\eta_{F}\leq(8-4\sqrt{3})^{-1}$

We remark again – there exists a mechanism $\displaystyle F$, in the general model, which achieves the bound for a mechanism in that model, $\displaystyle(8-4\sqrt{3})^{-1}\approx 0.93$. This is the price of truthfulness.

On top of being incentive compatible, this mechanism is also deterministic, non-wasteful and envy-free.

References

Appendix 0.A Social Welfare in the Aligned Model

In the cases in which $\displaystyle a+b\leq 1$, as stated earlier, each of the players gets all of his demand. Therefor, $\displaystyle SW_{f_{\frac{1}{2}}}=SW_{max}=2$, and $\displaystyle\eta_{f_{\frac{1}{2}}}$ is at its maximal possible value ($\displaystyle 1$).

$\displaystyle SW_{f_{\frac{1}{2}}}(a,b)=\frac{c(a,b)}{a}+\frac{1-c(a,b)}{b}=\frac{1}{a}[\min\{a,\max\{1-b,\frac{1}{2}\}\}]+\frac{1}{b}[1-\min\{a,\max\{1-b,\frac{1}{2}\}\}]=$

Now, we will check the value of $\displaystyle\eta_{f_{\frac{1}{2}}}(a,b)=\frac{SW_{f_{\frac{1}{2}}}(a,b)}{SW_{max}(a,b)}$ for each of the possible orders (from lowest to highest) of $\displaystyle a,1-a,b,1-b,\frac{1}{2}$. It is not possible that $\displaystyle a$ and $\displaystyle 1-a$ would both be smaller or larger than $\displaystyle\frac{1}{2}$ (because $\displaystyle 0\leq a\leq 1$). The same is true also for $\displaystyle b$ and $\displaystyle 1-b$. Moreover, $\displaystyle a$ and $\displaystyle b$, can not be both smaller than $\displaystyle\frac{1}{2}$, because their sum should be $\displaystyle>1$. Finally, from the same reason, it is also not possible that $\displaystyle b\leq 1-a$ or $\displaystyle a\leq 1-b$. Therefore, there are only 4 possible permutations:

In cases 1 and 3, $\displaystyle\eta_{f_{\frac{1}{2}}}(a,b)$ gets to its maximum (1).

In both cases 2 and 4, The value of $\displaystyle\eta_{f_{\frac{1}{2}}}(a,b)$ at its minima is $\displaystyle\frac{1}{8-4\sqrt{3}}\approx 0.93$, and this is $\displaystyle\eta_{f_{\frac{1}{2}}}$

Appendix 0.B Reduction From the Aligned to the General Model

Without loss of generality, we will show that player I can’t benefit from lying. Say that player I demanded some $\displaystyle A_{1}$, which differs from his real will $\displaystyle A$. It is possible to divide the symmetric difference between $\displaystyle A$ and $\displaystyle A_{1}$ into four disjoint subsets:

$\displaystyle\Delta_{1}\equiv(A_{1}\setminus A)\cap B$

$\displaystyle\Delta_{2}\equiv(A\setminus A_{1})\cap B$

$\displaystyle\Delta_{3}\equiv(A_{1}\setminus A)\cap\bar{B}$

$\displaystyle\Delta_{4}\equiv(A\setminus A_{1})\cap\bar{B}$

Note that $\displaystyle\Delta_{1}$ and $\displaystyle\Delta_{3}$ are the subsets that are not in $\displaystyle A$ but were added to $\displaystyle A_{1}$. $\displaystyle\Delta_{2}$ and $\displaystyle\Delta_{4}$ are the subsets of $\displaystyle A$ that are not in $\displaystyle A_{1}$.

In this proof, we will show (one after the other) that zeroing the size of those $\displaystyle\Delta$’s, can only raise the profit of player I (for every $\displaystyle A$ and $\displaystyle A_{1}$). Therefore player I has no incentive to lie.

The total size of the pieces that player I would get from demanding $\displaystyle A_{1}$ is: $\displaystyle C(A_{1},B)=\min\{|A_{1}|,\max\{|A_{1}\setminus B|,\theta\cdot|A_{1}\cup B|\}\}$. We should note that although the piece that player I would receive from mechanism $\displaystyle F$ must be included in $\displaystyle A_{1}$, it is not necessarily included in $\displaystyle A$.

We will define $\displaystyle A_{2}$ as $\displaystyle A_{1}$ without the subset that was added $\displaystyle\Delta_{1}$, $\displaystyle A_{2}\equiv A_{1}\setminus\Delta_{1}$ and show that player I can only benefit from demanding $\displaystyle A_{2}$ instead of $\displaystyle A_{1}$. The size of the piece that player II would receive after demanding $\displaystyle A_{2}$ is: $\displaystyle C(A_{2},B)=\min\{|A_{2}|,\max\{|A_{2}\setminus B|,\theta\cdot|A_{2}\cup B|\}\}$. If the minimum of this expression is $\displaystyle|A_{2}|$, then Player I gets all $\displaystyle A_{2}$, and since the difference between $\displaystyle A_{1}$ and $\displaystyle A_{2}$ is only $\displaystyle\Delta_{1}$, which player I doesn’t really want ($\displaystyle A_{1}\cap A\subseteq A_{2}$), player I couldn’t do better by asking $\displaystyle A_{1}$.

If the minimum of $\displaystyle C(A_{2},B)$ is one of the two elements in the maximum argument, this element is also the minimal value for the demand $\displaystyle A_{1}$, because those two elements has the same size in $\displaystyle C(A_{2},B)$ and in $\displaystyle C(A_{1},B)$, and the third expression ($\displaystyle|A_{1}|$) has larger value than $\displaystyle|A_{2}|$.

Regarding the position of the allocation itself, from non-wastefulness, the allocation must contain $\displaystyle A_{1}\cap\bar{B}$ in case the player demanded $\displaystyle A_{1}$ and $\displaystyle A_{2}\cap\bar{B}$ in case the player demanded $\displaystyle A_{2}$. Those subsets are identical $\displaystyle A_{1}\cap\bar{B}=A_{2}\cap\bar{B}$. In case player I demanded $\displaystyle A_{2}$, The rest of the allocation would have to be from $\displaystyle A\cap A_{1}\cap B\subseteq A$ (his real will). Therefore, also in this case, player I couldn’t do better by asking $\displaystyle A_{1}$ instead of $\displaystyle A_{2}$.

In either case, player I can’t lose by removing $\displaystyle\Delta_{1}$ from his demand, and asking for $\displaystyle A_{2}$.

We will define $\displaystyle A_{3}$ as $\displaystyle A_{2}$, only with $\displaystyle|\Delta_{2}|=0$ (adding back to the demand the subset $\displaystyle\Delta_{2}$ that was removed from $\displaystyle A$) $\displaystyle A_{3}\equiv A_{2}\cup\Delta_{2}$. All of the three elements in the expression for $\displaystyle C(A_{3},B)$ can only be larger than in $\displaystyle C(A_{2},B)$, therefore $\displaystyle C(A_{2},B)\leq C(A_{3},B)$. Since the intervals that aren’t joint with $\displaystyle B$ are the same between $\displaystyle A_{2}$ and $\displaystyle A_{3}$, and from non-wastefulness Player I would get all of them, the extra intervals that player I would get by asking $\displaystyle A_{3}$, would have to be from $\displaystyle A_{3}\cap B$, but since $\displaystyle|\Delta_{1}|=0$ there aren’t any intervals in $\displaystyle A_{3}\cap B$ which Player I doesn’t really want. Therefore he can only benefit from reducing $\displaystyle|\Delta_{2}|$ to 0.

We will define $\displaystyle A_{4}$ as $\displaystyle A_{3}$, only with $\displaystyle|\Delta_{3}|=0$: $\displaystyle A_{4}\equiv A_{3}\setminus\Delta_{3}$. Each of the three expressions in $\displaystyle C(A_{4},B)$ is between $\displaystyle\theta\cdot|\Delta_{3}|$ and $\displaystyle|\Delta_{3}|$, and is smaller than in $\displaystyle C(A_{3},B)$. Therefore by demanding $\displaystyle A_{4}$ instead of $\displaystyle A_{3}$, player I would get a smaller piece of cake. But the piece of cake that the player would get from demanding $\displaystyle A_{3}$ would necessarily include the subset $\displaystyle\Delta_{3}$ (because this subset is not included in player II demand and the non-wastefulness of $\displaystyle F$). This means that out of the piece that player I will receive, there is a subset with total size of $\displaystyle|\Delta_{3}|$ which he doesn’t want. There aren’t such intervals in $\displaystyle A_{4}$, Therefore the whole piece $\displaystyle C(A_{4},B)$ would be from areas that the player wants, and he can only benefit (between 0 and $\displaystyle(1-\theta)\cdot|\Delta_{4}|$) by demanding $\displaystyle A_{4}$ instead of $\displaystyle A_{3}$.

For the last stage, we will show that $\displaystyle A_{5}$, which is defined as $\displaystyle A_{4}$, only with $\displaystyle|\Delta_{4}|=0$, meaning $\displaystyle A_{5}\equiv A_{4}\cup\Delta_{4}$ (adding back the subset that was removed in $\displaystyle\Delta_{4}$ to the demand), is better for player I than $\displaystyle A_{4}$. $\displaystyle C(A_{5},B)=\min\{|A_{5}|,\max\{|A_{5}\setminus B|,\theta\cdot|A_{5}\cup B|\}\}=\min\{|A_{4}|+|\Delta_{4}|,\max\{|A_{4}\setminus B|+|\Delta_{4}|,\theta\cdot(|A_{4}\cup B|+|\Delta_{4}|)\}\}$. Each one of the three elements in this expression is larger than the elements in $\displaystyle C(A_{4},B)$, therefore $\displaystyle C(A_{4},B)\leq C(A_{5},B)$. Since $\displaystyle|\Delta_{1}|=0$ and $\displaystyle|\Delta_{3}|=0$ there aren’t any intervals in $\displaystyle A_{5}$ that player I doesn’t really wants, therefore Player I can only benefit from zeroing $\displaystyle\Delta_{4}$.

At this point we should notice that $\displaystyle A_{5}=A$, therefore for any $\displaystyle A$ and $\displaystyle A_{1}$ player I can only benefit from telling the truth, and mechanism $\displaystyle F$ is IC.

Appendix 0.C Reduction From the General to the Aligned Model

For $\displaystyle a+b\leq 1$, The mechanism $\displaystyle f$ would result in $\displaystyle c(a,b)=a$ and $\displaystyle d(a,b)=b$ according to its definition. We can match those $\displaystyle a,b$ the pair $\displaystyle A=[0,a],B=[1-b,1]$. Since $\displaystyle a+b\leq 1$, those interval are disjoint and from the non-wastefulness of $\displaystyle F$, $\displaystyle F(A,B)$ would result $\displaystyle C=[0,a],D=[1-b,1]$, therefore the condition is satisfied.

In a situation that player I demands the piece $\displaystyle A_{1}$ and player II wants a piece $\displaystyle B_{2}$, such that $\displaystyle|B_{2}|=b$ and $\displaystyle D_{1}=\setminus A_{1}\subset B_{2}$ (possible because $\displaystyle|A_{1}|=a$ and $\displaystyle b>1-a$). From incentive-compatibility, $\displaystyle|D_{2}|=|D_{1}|=1-a$. Since $\displaystyle|A_{1}\cup B_{2}|=1$, from non-wastefulness $\displaystyle|C_{2}|=1-|D_{2}|=a$.