## Weitere Artikel dieser Ausgabe durch Wischen aufrufen

Erschienen in:

16.11.2021 | Original Paper

# Fair cake-cutting for imitative agents

verfasst von: Eleonora Cresto, Diego Tajer

Erschienen in: Social Choice and Welfare | Ausgabe 4/2022

Einloggen, um Zugang zu erhalten

## Abstract

We investigate cases of preference change in the context of cake-cutting problems. In some circumstances, believing that some other player can be credited with a particular preference structure triggers a preference shift by imitation. As a result of this, players may experience regret. However, in typical examples the extent of the change (and the ensuing regret) cannot be anticipated, so players cannot adjust their behavior beforehand. Our goal is to describe the phenomenon, provide a formal model for it, and explore circumstances and allocation procedures that may alleviate some of its negative consequences. In the face of utility shifts we propose a new criterion for fairness, which we dub Ratifiability; in a ratifiable allocation rational players are happy to stick to their choices, in spite of the changes in utilities they may experience. We argue that this embodies a sense of fairness that is not captured by other properties of fair allocation.

### Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

• über 69.000 Bücher
• über 500 Zeitschriften

aus folgenden Fachgebieten:

• Automobil + Motoren
• Bauwesen + Immobilien
• Elektrotechnik + Elektronik
• Energie + Nachhaltigkeit
• Finance + Banking
• Management + Führung
• Marketing + Vertrieb
• Maschinenbau + Werkstoffe
• Versicherung + Risiko

Jetzt 90 Tage mit der neuen Mini-Lizenz testen!

### Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

• über 58.000 Bücher
• über 300 Zeitschriften

aus folgenden Fachgebieten:

• Bauwesen + Immobilien
• Finance + Banking
• Management + Führung
• Marketing + Vertrieb
• Versicherung + Risiko

Jetzt 90 Tage mit der neuen Mini-Lizenz testen!

Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
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.

2
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).

3
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.

4
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.

5
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.

6
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.

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

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

9
The definition asks us to consider the expected utility of the future pieces that would be obtained by a re-application that takes place right after the (first) procedure ends—where a re-application of a given procedure may involve once again several rounds.

10
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).

11
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.

12
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.

13
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.

14
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.

15
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.

16
Utility functions are already temporally indexed, which spares us the need to include the number of rounds elapsed as a second argument of d.

17
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.

18
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.

19
Note that assuming extreme risk aversion instead of truthfulness is sufficient to prove Proposition 3 (for fully myopic agents with a linear discount); for Proposition 4 (for myopic agents with linear discount) we need common knowledge of extreme risk aversion.

20
See the discussion at the end of Sect. 3

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

22
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.

23
Thanks to an anonymous referee for raising this concern.

24
Thanks to an anonymous reviewer for pointing out this implication.

25
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.

26
Isn’t extreme risk aversion always the rational attitude to hold, when information is scarce? (for example, for myopic players who are aware of possible shifts, but have no credences for that?) Not necessarily. If you know nothing (and this includes: if you have no positive probability for your being systematically prone to imitative utility changes) you may as well decide to keep playing now and hope to stop the next time, and hence benefit from the opportunity to make up for what went wrong in this round.

27
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).

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

29
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.

30
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).

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

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

Literatur
Ariel P et al (2016) Cake cutting algorithms. In: Felix B (ed) Handbook of computational social choice. Cambridge University Press, Cambridge, pp 311–330
Austin AK (1982) “Sharing a Cake”. In: The mathematical gazette 66.437, pp 212–215
Aziz H, Ye C (2014) Cake Cutting algorithms for piecewise constant and piecewise uniform valuations. In: Ye Y, Liu TY, Qi Q (eds) Web and internet economics. WINE 2014. lecture notes in computer science, vol 8877. Springer, pp 1–14
Barbanel JB (2005) The geometry of efficient fair division. Cambridge University Press, Cambridge CrossRef
Bell DE (1982) Regret in decision making under uncertainty. Oper Res 30(5):961–981 CrossRef
Brams Steven J (2006) Fair division. In: Weingast BR, Wittman Donald A (eds) Oxford handbook of political economy. Oxford University Press, Oxford, pp 425–437
Brams S, Jones MA, Klamler C (2013) N-person cake-cutting: there may be no perfect division. Am Math Mon 120(1):35–47 CrossRef
Brams SJ, Taylor AD (1996) Fair division: from cake-cutting to dispute resolution. Cambridge University Press, Cambridge CrossRef
Brams SJ, Marc Kilgour D, Klamler C (2012) The undercut procedure: an algorithm for the envy-free division of indivisible items. Soc Choice Welf 39:615–631 CrossRef
Brian H (2009) Three analyzes of sour grapes. In: Change P (ed) Till Grüne–Yanoff and Sven Ove Hansson. Springer, Berlin, pp 27–56
Cseh A, Fleiner T (2018) The complexity of cake cutting with unequal shares. In: Xiaotie D (ed) Algorithmic game theory. Springer, Berlin, pp 19–31 CrossRef
Delgosha P, Gohari A (2017) Information theoretic cutting of a cake. IEEE Trans Inf Theory 63(11):6950–6978 CrossRef
Derek P (1973) Later selves and moral principles. In: Montefiore A (ed) Philosophy and personal relations. Routledge and Kegan Paul, London, pp 137–169
Douglas G (1996) What have we learned from social learning. Eur Econ Rev 40:617–628 CrossRef
Dubins LE, Spanier EH (1961) How to cut a cake fairly. Am Math Mon 68(1):1. https://​doi.​org/​10.​2307/​2311357 CrossRef
Dupuis-Roy N, Gosselin F (2009) An empirical evaluation of fair-division algorithm. In: Proceedings of the annual meeting of the cognitive science society, pp 2681–2686
Edmonds J, Pruhs K (2011) Cake cutting really is not a piece of cake. ACM Trans Algorithms 7(4):1–12 CrossRef
Elster J (1983) Sour Grapes: studies in the subversion of rationality. Cambridge University Press, Cambridge CrossRef
Han B, Peter W (2015) Regret theory: a bold alternative to the alternatives. Econ J 125(583):493–511 CrossRef
Hevé M (2003) Fair division and collective welfare. The MIT Press, Cambridge
Jack R, William W (1998) Cake-cutting algorithms. AK Peters, Natick
Jeffrey R (ed) (1965) The logic of decision. University of Chicago Press, Chicago
Kyropoulou M, Ortega J, Segal-Halevet E (2019) Fair cake-cutting in practice. In: Proceedings of the 2019 ACM conference on economics and computation, pp 547–548
Loewenstein G, Angner E (2003) Predicting and indulging changing preferences. In: George L, Daniel R, Roy B (eds) Time and decision. Economic and psychological perspectives on intertemporal choice. Russell Sage Foundation, New York, pp 351–391
Loomes G, Sudgen R (1982) Regret theory: an alternative theory of rational choice under uncertainty. Econ J 92(368):805–882 CrossRef
Manabe Y, Okamoto T (2010) Meta-envy-free cake-cutting protocols. In: Petr H, Antonin K (eds) Mathematical foundations of computer science. Springer, Berlin, pp 501–512
Nicolò A, Yu Y (2008) Strategic divide and choose. https://​doi.​org/​10.​1016/​j.​geb.​2008.​01.​006
Paul Laurie A (2014) Transformative experience. Oxford University Press, Oxford CrossRef
Richard B (2017) Decision theory with a human face. Cambridge University Press, Cambridge
Richard P (2020) Choosing for changing selves. Oxford University Press, Oxford
Tamuz O, Vardi S, Ziani J (2018) Non-exploitable protocols for repeated cake cutting. In: The thirty-second AAAI conference on artificial intelligence, pp 1226–1233
Woeginger GJ, Sgall J (2007) On the complexity of cake cutting. Discrete Optm 4(2):213–220 CrossRef
Zeelenberg M, Pieters R (2007) A theory of regret regulation 10. J Consum Psychol 17(1):3–18 CrossRef
Titel
Fair cake-cutting for imitative agents
verfasst von
Eleonora Cresto
Diego Tajer
Publikationsdatum
16.11.2021
Verlag
Springer Berlin Heidelberg
Erschienen in
Social Choice and Welfare / Ausgabe 4/2022
Print ISSN: 0176-1714
Elektronische ISSN: 1432-217X
DOI
https://doi.org/10.1007/s00355-021-01375-2

Zur Ausgabe