Fair cake-cutting for imitative agents

A few words on our use of this expression. In some cultural backgrounds, where everyday concepts and language are heavily permeated by a psychoanalytic tradition, mostly everybody would recognize himself or herself as neurotic to a certain degree; even if the speaker does not take psychoanalytic theory seriously, it is still in the language—much in the way expressions such as “the sun rises” superseded their pre-Copernican origin. In this line, we would like to stress that by ‘neurosis’ we do not mean to point to a mental illness or to a mental disorder, but to a state of mind in which the person does not know exactly what s/he wants.

Other cases of uncertainty of preferences in cake-cutting contexts are mentioned in Woeginger and Sgall (2007), Edmonds and Pruhs (2011), or Aziz and Ye (2014).

A correct assessment of the extent to which dissatisfaction with standard algorithms is due to Preference-Shift Regret requires empirical testing. There might be circumstances that bolster preference changes by imitation, while other circumstances might help prevent this from happening. We hope to address these problems in a future paper. In any case, regardless of how common the phenomenon actually is, we believe there are paradigmatic examples of Preference-Shift Regret that merit theoretical analysis.

Sometimes a distinction is drawn between a piece of cake and a portion of cake (where a piece refers to a connected subset of the cake, and a portion of cake is a collection of pieces). We will not make use of that distinction here; the algorithms we will favor will assume a single cut.

Sometimes assessments of further potential applications of a given procedure are made only subjunctively or even counterfactually—say, with the purpose of evaluating the gain that a player could obtain if the cake were to be reassembled and divided again at \(t_{n+1}\) (which, depending on the circumstances, may or may not be actually feasible). Related to this, we will not make provisions on how players might come to think of re-applying a procedure; this could well be the task of a third party agent. A third party agent may be in charge of making sure the players follow a given procedure in the first place, and, eventually, she may offer them to re-apply it. Actually, we need not cast it as an “offer” at all. Applying, or re-applying a given procedure need not be the result of a decision made by the players; we may think of it as a given feature of the situation they are in.

Strictly speaking, the change is assumed to occur with every behavioral trigger. However, as a matter of fact we will not deal with procedures that allow players to perform more than one action per round, hence we will not need to consider more than one utility shift per round. This can be easily fixed, if needed. In Sect. 5 we offer computer simulations that show how such a \(u^{*}\) can be generated.

Just to clarify: our model is tailored to take care of utility changes by imitation; the way utility shifts are assumed to work helps us circumscribe our object study. Of course other types of shifts are logically possible, but fall outside the scope of the paper. In particular, if players were to change preferences by moving away from the perceived utilities of the other player, they will not feel Preference-Shift Regret in the first place. We come back to this point in further sections.

Cf. Brams et al. (2013). For an overview of procedures and properties cf. Brams (2006), or Procaccia (2016), among others.

In Austin’s moving knife procedure, for example, the player who yells “stop!” may have decided to take a fifty-fifty chance to obtain a much valuable piece (assuming the pieces are assigned by tossing a fair coin); cf. Austin (1982).

Exact and Non-manipulable explicit allocation procedures are trivially ratifiable also under the assumption that the cake loses part of its value as time goes by, as is obvious.

An interesting work on sequential cut and choose can be found in Nicolò and Yu (2008), although it is not designed to take care of shifting preferences.

Some of the results we discuss below can also be obtained by assuming that players are extremely risk averse, rather than truthful—with some caveats. We go back to the relation between risk aversion and truthfulness in the next pages.

The last expression is needed for coherence reasons, to make sure that, for every partition of the cake, the sum of the new values of the pieces adds up to the new value of the whole cake.

We do not intend to say that Minimality is a reasonable constraint for every time discount function in every possible context, but that it certainly makes sense in a cake-cutting scenario. Minimal discounts might be just linear, or exponential up to a certain point (where the value becomes zero), among other possibilities.

Conservative players do not act out of spite. For example, suppose i’s current gain at round n is 0; i also believes that j’s piece at n has positive value, but that the whole cake will be worthless for both players at \(n+1\). Our conservative principle tells us that, if it is up to i to decide whether to stop or to go on, i will stop at n.

By ‘linear’ we mean that there is a fixed discount \(\delta\) such that, for every round n, the value of the cake C is \(1-\delta (n-1)\). Then the values of the pieces are proportionally adjusted: the utility \(u_{i,n+1}(X_i)\) of piece \(X_i\) in round \(n+1\) would be \((u^{*}_{n,i}(X)/u_{n,i}(C)) (1 - \delta (n-1))\). Given that \(\delta\) is fixed, the value of the cake will be zero at some point.

See the discussion at the end of Sect. 3

See the Appendix for a summary of the different procedures mentioned in this paper.

GI does not generalize easily to more than two players, as in such settings it is no longer well defined what a utility change by imitation is. We hope to address generalizations to more than 2 people in future work.

Thanks to an anonymous referee for raising this concern.

Thanks to an anonymous reviewer for pointing out this implication.

Myopic players need not be completely unaware of the fact that they may experience new shifts in the future, but they may choose not to pay attention to that possibility, in the absence of more concrete information.

We ran identical simulations with exponential discounts, 0.95 and 0.97, with very similar results. An interesting question is whether there are ratifiable algorithms for which the probability to stop in the first round is positive even when the discount is small or zero (thanks to an anonymous referee for raising this question). To this effect we run simulations for an iterated version of Symmetric Cut and Choose. For one set of simulations we assumed that agents were fully myopic; for a second set of simulations we assumed myopia, but not full myopia. If Player 1 is fully myopic she believes that, in the next round, Player 2 will cut by the same point as he did before. Hence, once Player 1 experiences a utility shift, she can get a larger piece by approaching Player 2’s cutting point; in this scenario, when the discount is zero, agents will always prefer to try another round. The situation changes, however, when agents are just myopic: Player 1 fears that Player 2 may shift his cutting point by approaching Player 1’s previous cut, and hence Player 1 may end with a smaller piece of cake. In this case, even with a zero discount, agents stopped in the first round with probability \(\approx\)0.6. A similar phenomenon applies when the discount is positive. For example, when the discount is 4, the agents will stop with probability larger than 0.95 (compared to \(\approx\)0.2 in the original ICC).

Arguably, in such scenarios utility changes can always be traced back to changes of credences, but this is not our problem here.

This also holds for irrational changes of credences, of course; there is a vast literature that addresses this problem, which is only tangentially related to ours.

In Parfit’s classical example, a Russian noble tells his wife that, were he to change his mind in the future on giving the land to the peasants, she should consider that the person she now loves and regards as her husband is already dead; cf. Parfit (1973). On this cf. also Pettigrew (2020).

We could also explore a modification of the so called undercut procedure described in Brams et al. (2012).

Thanks to an anonymous referee for suggesting us to consider this procedure.