Fairly taking turns. (English) Zbl 1530.91247
Summary: We investigate the fair division of a sequence of time slots when each agent is sufficiently patient. If agents have identical preferences, then we construct perfectly equitable and efficient allocations. Otherwise, (i) if there are two agents, then we construct envy-free allocations, (ii) if there are three agents, then we construct proportional allocations, and (iii) in general, we construct approximately fair allocations. Finally, we investigate achieving approximate fairness at each time period, strategy-proofness, and a notion of computational simplicity.
MSC:
| 91B32 | Resource and cost allocation (including fair division, apportionment, etc.) |
References:
| [1] | Abebe, Rediet; Cole, Richard; Gkatzelis, Vasilis; Hartline, Jason, A truthful cardinal mechanism for one-sided matching, 2096-2113 · Zbl 07304153 |
| [2] | Amanatidis, Georgios; Birmpas, Georgios; Christodoulou, George; Markakis, Evangelos, Truthful allocation mechanisms without payments: characterization and implications on fairness, 545-562 |
| [3] | Anbarcı, Nejat; Sun, Ching-Jun; Utku Ünver, M., Designing practical and fair sequential team contests: the case of penalty shootouts. Games Econ. Behav., 25-43 (2021) · Zbl 1478.91052 |
| [4] | Arrow, Kenneth; Debreu, Gerard, Existence of an equilibrium for a competitive economy. Econometrica, 265-290 (1954) · Zbl 0055.38007 |
| [5] | Austin, A. Keith, Sharing a cake. Math. Gaz., 212-215 (1982) |
| [6] | Aziz, Haris; Mackenzie, Simon, A discrete and bounded envy-free cake cutting protocol for any number of agents, 416-427 · Zbl 1373.68251 |
| [7] | Aziz, Haris; Ye, Chun, Cake cutting algorithms for piecewise constant and piecewise uniform valuations, 1-14 · Zbl 1406.91212 |
| [8] | Babaioff, Moshe; Tomer, Ezra; Feige, Uriel, Fair and truthful mechanisms for dichotomous valuations, 5119-5126 |
| [9] | Barman, Siddharth; Krishnamurthy, Sanath, On the proximity of markets with integral equilibria, 1748-1755 |
| [10] | Barman, Siddharth; Krishnamurthy, Sanath; Vaish, Rohit, Finding fair and efficient allocations, 557-574 |
| [11] | Barman, Siddharth; Verma, Paritosh, Truthful and fair mechanisms for matroid-rank valuations, 4801-4808 |
| [12] | Bei, Xiaohui; Chen, Ning; Huzhang, Guangda; Tao, Biaoshuai; Wu, Jiajun, Cake cutting: envy and truth, 3625-3631 |
| [13] | Bernstein, Sergei, Attempt at an axiomatic foundation of probability theory. Commun. Kharkov Math. Soc., 209-274 (1917), Translation |
| [14] | Bezáková, Ivona; Dani, Varsha, Allocating indivisible goods. ACM SIGecom Exch., 11-18 (2005) |
| [15] | Bilò, Vittorio; Caragiannis, Ioannis; Flammini, Michele; Igarashi, Ayumi; Monaco, Gianpiero; Peters, Dominik; Vinci, Cosimo; Zwicker, William, Almost envy-free allocations with connected bundles. Games Econ. Behav., 197-221 (2022) · Zbl 1483.91102 |
| [16] | Brams, Steven; Ismail, Mehmet, Making the rules of sports fairer. SIAM Rev., 181-202 (2018) · Zbl 1407.91010 |
| [17] | Brams, Steven; Ismail, Mehmet; Kilgour, D. Marc, Fairer Shootouts in Soccer: the m-n Rule (2023), Working paper |
| [18] | Brams, Steven; Ismail, Mehmet; Kilgour, D. Marc; Stromquist, Walter, Catch-up: a rule that makes service sports more competitive. Am. Math. Mon., 771-796 (2018) · Zbl 1402.60093 |
| [19] | Brams, Steven; Taylor, Alan, An envy-free cake division protocol. Am. Math. Mon., 9-18 (1995) · Zbl 0824.90142 |
| [20] | Brams, Steven; Taylor, Alan, The Win-Win Solution: Guaranteeing Fair Shares to Everybody (2000), W.W. Norton: W.W. Norton New York, New York |
| [21] | Brams, Steven; Taylor, Alan; Zwicker, William, Old and new moving-knife schemes. Math. Intell., 30-35 (1995) · Zbl 0837.90125 |
| [22] | Bu, Xiaolin; Song, Jiaxin; Tao, Biaoshuai, On existence of truthful fair cake cutting mechanisms. Artif. Intell. (2023) · Zbl 07702946 |
| [23] | Budish, Eric, The combinatorial assignment problem: approximate competitive equilibrium form equal incomes. J. Polit. Econ., 1061-1103 (2011) |
| [24] | Caragiannis, Ioannis; Kaklamanis, Christos; Kanellopoulos, Panagiotis; Kyropoulou, Maria, On low-envy truthful allocations, 111-119 · Zbl 1260.91129 |
| [25] | Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel; Shah, Nisarg; Wang, Junxing, The unreasonable fairness of maximum Nash welfare. ACM Trans. Econ. Comput. (2019) |
| [26] | Chambers, Christopher; Echenique, Federico, On multiple discount rates. Econometrica, 1325-1346 (2018) · Zbl 1396.91145 |
| [27] | Chateauneuf, Alain, On the existence of a probability measure compatible with a total preorder on a Boolean algebra. J. Math. Econ., 43-52 (1985) · Zbl 0575.90001 |
| [28] | Chen, Yiling; Lai, John; Parkes, David; Procaccia, Ariel, Truth, justice, and cake cutting. Games Econ. Behav., 284-297 (2013) · Zbl 1274.91262 |
| [29] | Chen, Bo; Takahashi, Satoru, A folk theorem for repeated games with unequal discounting. Games Econ. Behav., 571-581 (2012) · Zbl 1250.91016 |
| [30] | Cho, Wonki; Thomson, William, Strategy-Proofness in Private Good Economies with Linear Preferences: An Impossibility Result (2023), Working paper, SSRN · Zbl 1530.91242 |
| [31] | Chun, Youngsub, Fair Queueing (2016), Springer International Publishing: Springer International Publishing Cham, Switzerland · Zbl 1339.90003 |
| [32] | Cole, Richard; Gkatzelis, Vasilis; Goel, Gagan, Mechanism design for fair division: allocating divisible items without payments, 251-268 |
| [33] | Conitzer, Vincent; Freeman, Rupert; Shah, Nisarg, Fair public decision making, 629-646 |
| [34] | de Finetti, Bruno, La prévision: ses lois logiques, ses sources subjectives. Ann. Inst. Henri Poincaré, 1-68 (1937), [in French] · Zbl 0017.07602 |
| [35] | Descartes, René, Discours de la Méthode pour bien conduire sa raison, et chercher la vérité dans les sciences. Plus La Dioptrique. Les Météores. Et La Géométrie (1637), Jan Maire: Jan Maire Leiden, the Netherlands, [in French]; Descartes, René, The Geometry of René Descartes with a Facsimile of the First Edition (1954), Dover Publications, Inc.: Dover Publications, Inc. New York, New York, Translators: Smith, David and Marcia Latham |
| [36] | Dolan, Robert, Incentive mechanisms for priority queuing problems. Bell J. Econ., 421-436 (1978) |
| [37] | Dubins, Lester; Spanier, Edwin, Hot to cut a cake fairly. Am. Math. Mon., 1-17 (1961) · Zbl 0108.31601 |
| [38] | Eisenberg, Edmund; Gale, David, Consensus of subjective probabilities: the pari-mutuel method. Ann. Math. Stat., 165-168 (1959) · Zbl 0087.13805 |
| [39] | Erdős, Pál; Joó, István; Komornik, Vilmos, Characterization of the unique expansions \(1 = \sum_{i = 1}^\infty q^{- n_i}\) and related problems. Bull. Soc. Math. Fr., 377-390 (1990) · Zbl 0721.11005 |
| [40] | Foley, Duncan, Resource allocation and the public sector. Yale Econ. Essays, 45-98 (1967) |
| [41] | Fudenberg, Drew; Levine, David, Reputation and equilibrium selection in games with a patient player. Econometrica, 759-778 (1989) · Zbl 0693.90105 |
| [42] | Fudenberg, Drew; Maskin, Eric, On the dispensability of public randomization in discounted repeated games. J. Econ. Theory, 428-438 (1991) · Zbl 0719.90106 |
| [43] | Gale, David; Shapley, Lloyd, College admissions and the stability of marriage. Am. Math. Mon., 9-15 (1962) · Zbl 0109.24403 |
| [44] | Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia, Near fairness in matroids, 393-398 · Zbl 1366.91101 |
| [45] | Halpern, Daniel; Procaccia, Ariel; Psomas, Alexandros; Shah, Nisarg, Fair division with binary valuations: one rule to rule them all, 370-383 · Zbl 1533.91250 |
| [46] | Hill, Theodore, Partitioning general probability measures. Ann. Probab., 804-813 (1987) · Zbl 0625.60004 |
| [47] | Jackson, Matthew; Yariv, Leeat, Collective dynamic choice: the necessity of time inconsistency. Am. Econ. J. Microecon., 150-178 (2015) |
| [48] | Jones, Rafe, Achievement sets of sequences. Am. Math. Mon., 508-521 (2011) · Zbl 1270.40003 |
| [49] | Kakeya, Sōichi, On the set of partial sums of an infinite series. Proc. Tokyo Math.-Phys. Soc., 250-251 (1914) · JFM 45.0377.05 |
| [50] | Kakeya, Sōichi, On the partial sums of an infinite series. Sci. Rep. Tôhoku Imp. Univ., 159-163 (1915) · JFM 45.0377.06 |
| [51] | Kettering, Jeremy; Kochov, Asen, Consumption smoothing and discounting in infinite-horizon, discrete-choice problems. Math. Oper. Res., 1957-1969 (2021) · Zbl 1498.91137 |
| [52] | Klaus, Bettina; Miyagawa, Eiichi, Strategy-proofness, solidarity, and consistency for multiple assignment problems. Int. J. Game Theory, 421-435 (2001) · Zbl 1083.91046 |
| [53] | Kochov, Asen; Song, Yangwei, Intertemporal Hedging and Trade in Repeated Games with Recursive Utility (2023), Working paper, SSRN · Zbl 1541.91092 |
| [54] | Kolm, Serge-Christophe, Justice et Equité (1971), Centre d’Etudes Prospectives et d’Economie Mathématique Appliquées à la Planification: Centre d’Etudes Prospectives et d’Economie Mathématique Appliquées à la Planification Paris, France, [in French]; Kolm, Serge-Christophe, Justice and Equity (2002), The MIT Press: The MIT Press Cambridge, Massachusetts, Translator: Harold F. See |
| [55] | Komornik, Vilmos, Another short proof of Descartes’s rule of signs. Am. Math. Mon., 829-830 (2006) · Zbl 1215.12003 |
| [56] | Koopman, Bernard, The axioms and algebra of intuitive probability. Ann. Math., 269-292 (1940) · Zbl 0024.05001 |
| [57] | Koopmans, Tjalling, Stationary ordinal utility and impatience. Econometrica, 287-309 (1960) · Zbl 0149.38401 |
| [58] | Lehrer, Ehud; Pauzner, Ady, Repeated games with differential time preferences. Econometrica, 393-412 (1999) · Zbl 1020.91009 |
| [59] | Leo, Greg, Taking turns. Games Econ. Behav., 525-547 (2017) · Zbl 1409.91033 |
| [60] | Levmore, Saul; Cook, Elizabeth, Super Strategies for Puzzles and Games (1981), Doubleday and Company: Doubleday and Company Garden City, New York |
| [61] | Liapounoff, Aleksandr, Sur les fonctions-vecteurs complètement additives. Izv. Akad. Nauk SSSR, Ser. Mat., 465-478 (1940), [in Russian] · JFM 66.0219.02 |
| [62] | Lipton, Richard; Markakis, Evangelos; Mossel, Elchanan; Saberi, Amin, On approximately fair allocations of indivisible goods, 125-131 |
| [63] | Lowry, S. Todd, The Archaeology of Economic Ideas (1987), Duke University Press: Duke University Press Durham, North Carolina |
| [64] | Mackenzie, Andrew, A foundation for probabilistic beliefs with or without atoms. Theor. Econ., 709-778 (2019) · Zbl 1422.91201 |
| [65] | McKenzie, Lionel, On equilibrium in Graham’s model of world trade and other competitive systems. Econometrica, 147-161 (1954) · Zbl 0055.13702 |
| [66] | Mossel, Elchanan; Tamuz, Omer, Truthful fair division, 288-299 · Zbl 1310.91083 |
| [67] | Nash, John, The bargaining problem. Econometrica, 155-162 (1950) · Zbl 1202.91122 |
| [68] | Pazner, Elisha; Schmeidler, David, Egalitarian equivalent allocations: a new concept of economic equity. Q. J. Econ., 671-687 (1978) |
| [69] | Plaut, Benjamin; Roughgarden, Tim, Almost envy-freeness with general valuations. SIAM J. Discrete Math., 1039-1068 (2020) · Zbl 1437.91237 |
| [70] | Pólya, George; Szegö, Gabor, Aufgaben und Lehrsätze aus der Analysis (1925), Springer-Verlag: Springer-Verlag Berlin, Germany, [in German]; Pólya, George; Szegö, Gabor, Problems and Theorems in Analysis I (1925), Springer-Verlag: Springer-Verlag Berlin, Germany, Translator: Dorothee Aeppli · Zbl 1053.00002 |
| [71] | Rachmilevitz, Shiran, Endogenous bid rotation in repeated auctions. J. Econ. Theory, 1714-1725 (2013) · Zbl 1285.91052 |
| [72] | Rényi, Alfréd, Representations for real numbers and their ergodic properties. Acta Math. Hung., 477-493 (1957) · Zbl 0079.08901 |
| [73] | Rubinstein, Ariel, Perfect equilibrium in a bargaining model. Econometrica, 97-109 (1982) · Zbl 0474.90092 |
| [74] | Salonen, Hannu; Vartiainen, Hannu, Valuating payoff streams under unequal discount factors. Econ. Lett., 595-598 (2008) · Zbl 1255.91134 |
| [75] | Savage, Leonard, The Foundations of Statistics (1954), Dover Publications: Dover Publications Wiley, NY · Zbl 0055.12604 |
| [76] | Schummer, James, Strategy-proofness versus efficiency on restricted domains of exchange economies. Soc. Choice Welf., 47-56 (1997) · Zbl 0876.90011 |
| [77] | Sorin, Sylvain, On repeated games with complete information. Math. Oper. Res., 147-160 (1986) · Zbl 0655.90102 |
| [78] | Steinhaus, Hugo, The problem of fair division. Econometrica, 101-104 (1948) |
| [79] | Steinhaus, Hugo, Sur la division pragmatique. Econometrica, Supplement, 315-319 (1949) · Zbl 0039.34602 |
| [80] | Stromquist, Walter, How to cut a cake fairly. Am. Math. Mon., 613-614 (1981), Addendum: |
| [81] | Sugaya, Takuo, Characterizing the limit set of perfect and public equilibrium payoffs with unequal discounting. Theor. Econ., 691-717 (2015) · Zbl 1395.91048 |
| [82] | Suksumpong, Warut, Fairly allocating contiguous blocks of indivisible items. Discrete Appl. Math., 227-236 (2019) · Zbl 1411.91337 |
| [83] | Thomson, William, Children crying at birthday parties. Why?. Econ. Theory, 501-521 (2007) · Zbl 1114.91034 |
| [84] | Tinbergen, Jan, Redelijke Inkomensverdeling [Reasonable Income] (1946), De Gulden Pers: De Gulden Pers Haarlem, the Netherlands, [in Deutch] |
| [85] | Varian, Hal, Equity, envy and efficiency. J. Econ. Theory, 217-244 (1974) |
| [86] | Villegas, Cesareo, On quantitative probability \(σ\)-algebras. Ann. Math. Stat., 1787-1796 (1964) · Zbl 0127.34807 |
| [87] | Wang, Xiaoshen, A simple proof of Descartes’s rule of signs. Am. Math. Mon., 525-526 (2004) · Zbl 1080.26507 |
| [88] | Weitzman, Martin, Gamma discounting. Am. Econ. Rev., 260-271 (2001) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
