2484:, the protocol can ask either Alice or George to cut a certain piece to two pieces. Suppose w.l.o.g. that the cutter is George and that he cuts piece X to two sub-pieces: X1 and X2. Now, the total number of subsets is 2: half of them already existed and by assumption they are not exact, so the protocol's only chance of finding an exact subset is to look at the new subsets. Each new subset is made of an old subset in which the piece X has been replaced with either X1 or X2. Since George is the cutter, he can cut in a way which makes one of these subsets an exact subset for him (e.g. if a certain subset containing piece X had a value of 3/4, George can cut X such that X1 has a value of 1/4 in his opinion, so that the new subset has a value of exactly 1/2). But, George does not know Alice's valuation and cannot take it into account when cutting. Therefore, there is an uncountable infinity of different values that the pieces X1 and X2 can have for Alice. Since the number of new subsets is finite, there is an infinite number of cases in which no new subset has a value of 1/2 for Alice, hence no new subset is exact.
2499:
The simplest case is when the weights are 1/2, i.e. they want to cut a piece that both of them agree to be half the cake value. This is done as follows. One agent moves two knives over the cake from left to right, always keeping the value between the knives as exactly 1/2. It is possible to prove (by
2065:
Although the agents' preferences are modeled with measures, the proofs do not require the value functions to be positive or additive over subsets; they may be any continuous set functions defined on the Borel sigma-algebra. Thus it is not required that partners' valuations over subsets of the cake be
1590:
union of intervals. Intuition: consider the division procedure for piecewise-homogeneous cakes described above. In general, the cake is not piecewise-homogeneous. However, because the value measures are continuous, it is possible to divide the cake to smaller and smaller regions such that the regions
5762:
The simplest truthful division mechanism is: select a single partner at random (with probabilities determined by the weights) and give him the entire cake. This mechanism is trivially truthful because it asks no questions. Moreover, it is consensus in expectation: the expected value of each partner
1464:
regions, such that all agents agree that the value-density in each region is uniform. For example, consider a circular cake in which each of its 4 quarters has a different topping. The agents may value each of the toppings differently, but do not distinguish between different pieces having the same
46:
people with different tastes agree on the value of each of the pieces. For example, consider a cake which is half chocolate and half vanilla. Alice values only the chocolate and George values only the vanilla. The cake is divided into three pieces: one piece contains 20% of the chocolate and 20% of
2869:
Otherwise (the value in the bowl is less than 1/2 to both partners), if the value in the bowl is larger for Alice than for George, then find a crumb whose value for George is more than its value for Alice (such a crumb must exist because the sum of values of all crumbs is 1 both for Alice and for
2538:
A better way to achieve a consensus division is to identify the two endpoints of the cake and treat it like a circle. I.e, when the right knife gets to the right side, it immediately goes to the left side, and the piece-between-the-knives is now actually the union of the piece to the right of the
2476:
pieces. Without loss of generality, we may assume that each piece has a non-zero value to both partners. This is because, if Alice (for example) cuts a piece which she values as 0, it is possible that George also values the same piece as 0, so we can discard this piece and continue with the other
2464:
Initially, there is only one piece which both partners value as 1, so there is obviously no exact subset. After one step, at most one partner (say, Alice) has had an option to cut the cake. Even if Alice cuts the cake to two pieces that are equal in her opinion, they may be different in George's
5627:
An exact division with different weights is not necessarily fair. Going back to the opening example, if the 20% piece is given to Alice and the other two pieces (of 50% and 30%) are given to George, this is obviously unfair to Alice. But such divisions can be used as subroutines for
5754:
Any algorithm for consensus division relies on the value measures reported by the partners. If the partners know how the algorithm works, they may have an incentive to lie about their value measures in order to receive more than their weight. In order to prevent this, a
295:
are finite, Consensus divisions always exist. However, they cannot be found by discrete protocols (with a finite number of queries). In some cases, exact divisions can be found by moving-knife protocols. Near-exact divisions can be found by discrete protocols.
3023:. This holds even for arbitrary bounded and non-atomic valuations. However, the run-time of this algorithm may be exponential in the problem parameters. In fact, consensus halving is computationally hard in several respects.
2407:
The original version of this theorem works only if the number of dimensions of the cake is equal to the number of partners. E.g, it is not possible to use this theorem to divide a 3-dimensional sandwich to 4 or more partners.
7309:
Pre-requisites on the value functions of the partners. Less pre-requisites mean that the result is more general. Con=Continuous is the most general; Con+Add=Additive is less general; Con+Add+Pwl=Piecewise-linear is the least
3473:-approximate consensus-halving is polynomial-time equivalent to computing an approximation to an exact solution of the Borsuk-Ulam search problem. This means that it is complete for the complexity class BU – a superclass of
3212:
is a constant, two types of approximations can be computed in polynomial time. The algorithms work for general additive valuations (not necessarily piecewise-constant); the valuations are accessed using queries in the
3929:
3394:
3839:
7157:
Filos-Ratsikas, Aris; Hollender, Alexandros; Sotiraki, Katerina; Zampetakis, Manolis (2021-01-01), "A Topological
Characterization of Modulo-p Arguments and Implications for Necklace Splitting",
2778:
1077:
3325:
531:
3979:
4439:
1617:, this process converges to a consensus division. However, the number of required cuts in the limit is infinite. Fremlin later showed that it is possible to construct such a division as a
1908:
5796:
regardless of the reported value function, so the mechanism is still truthful – no partner can gain anything from lying. Moreover, a truthful partner is guaranteed a value of exactly 1/
4316:
1002:
475:
361:
2949:
1440:
1224:
885:
707:
5486:
5385:
5277:
5199:
5121:
4618:
4517:
4093:
2504:) that at some point, the value of the piece between the knives to the other partner will also be exactly 1/2. The other agent calls "stop!" at that point and the piece is cut.
598:
2675:
920:
150:
2372:
1329:
793:
1762:
3508:
It is NP-hard to compute a consensus halving with the optimal number of cuts for a given instance. Moreover, it is NP-hard to compute a consensus halving with at most OPT+
2695:
2535:. By combining several such pieces, it is possible to achieve a consensus division with any ratios that are rational numbers. But this may require a large number of cuts.
2160:
2013:
1677:
1615:
1352:
1247:
1158:
1134:
940:
263:
240:
214:
190:
170:
122:
55: = 2), as both Alice and George value the three pieces as 20%, 50% and 30% respectively. Several common variants and special cases are known by different terms:
5596:, since in many cases it is possible to take advantage of the subjective valuations and divide the resources such that all partners receive more than their fair share of
4838:
4745:
4180:
3058:. The input to the problem contains, for each agent, the endpoints and values of his piecewise-constant valuation; and all numbers (including the approximation accuracy
4357:
6470:
1551:
4677:
4234:
3619:
3593:
2797:: the goal is to cut the cake to tiny bits ("crumbs") such that each partner assigns a sufficiently small value to each crumb. This is done in the following way. Let
6053:
5904:
5523:
4383:
3758:
3696:
3567:
2629:
2262:
2059:
2575:
2227:
1857:
1506:
1114:
636:
404:
6109:
4649:
1941:
6667:
5622:
5572:
5055:
4773:
4208:
2533:
2398:
1824:
1718:
1380:
1275:
825:
739:
5410:
4863:
5444:
5343:
5299:
5221:
5143:
5023:
4989:
4963:
4925:
4899:
4807:
4714:
4576:
4539:
4475:
4274:
4149:
4115:
4051:
3251:
3101:
with only two blocks (However, when agents have piecewise-uniform valuations with a single block, the problem can be solved in parametrized-polynomial time for
2200:
2180:
2127:
2107:
1798:
3525:
For agents with non-additive monotone utilities, consensus halving is still PPAD-hard, but there are polynomial-time algorithms for a fixed number of agents.
6669:
for him. But this is not a consensus division, because the partners may not agree on the value of the other pieces besides the piece allocated to them. See
1687:
exists a consensus division with this exact number of cuts. This question was studied extensively, focusing mainly on a one-dimensional cake (an interval).
47:
the vanilla, the second contains 50% of the chocolate and 50% of the vanilla, and the third contains the rest of the cake. This is an exact division (with
3709:
can be improved. Particularly, it is open whether there is an efficient (online or offline) algorithm such that each agent values each part at least 1/
6462:
2411:
However, there are generalizations that enable such a division. They do not use a hyperplane knife but rather a more complicated polynomial surface.
7002:
Filos-Ratsikas, Aris; Frederiksen, Soren
Kristoffer Stiil; Goldberg, Paul W.; Zhang, Jie (2018-08-08). "Hardness Results for Consensus-Halving".
5763:
is exactly its weight, and this is true according to all value measures. However, the resulting division is of course not a consensus division.
2889:
Formally, each piece can be represented as a vector of values, one per partner. The length of each vector is bounded, i.e. for each such vector
7109:
Goldberg, Paul W.; Hollender, Alexandros; Igarashi, Ayumi; Manurangsi, Pasin; Suksompong, Warut (2022). "Consensus
Halving for Sets of Items".
3848:
2866:
If the value in the bowl becomes more than 1/2 to either partner, give the bowl to that partner and give the other crumbs to the other partner.
2400:
dimensional hyperplane, then there is a half-space whose value is exactly 1/2 to each partner. Hence there exists a consensus division using a
2109:
different measures on the interval, all absolutely continuous with respect to length. The measure of the entire necklace, according to measure
7286:
7176:
6965:
6895:
6821:
6771:
6715:
6228:
2291:. The number of cuts is essentially optimal for general weights. This theorem can be applied recursively to obtain an exact division for any
7088:
Batziou, Eleni; Hansen, Kristoffer
Arnsfelt; Høgh, Kasper (2021-03-07). "Strong Approximate Consensus Halving and the Borsuk-Ulam Theorem".
2874:
It is possible to prove by induction, that the difference in the valuation of the bowl between Alice and George is always at most 1/
3334:
3776:
2581:. It is possible to prove that at some point, the value of the piece between the knives to the other partner will also be exactly
3652:
3214:
2435:=2 pieces the weights equal 1/2. This means that the best we can achieve using a discrete algorithm is a near-exact division.
2288:
6670:
5800:
with probability 1 (not only in expectation). Hence the partners have an incentive to reveal their true value functions.
2711:
2493:
1010:
2539:
right knife and the piece to the left of the left knife. This way, it is possible to find a consensus division for every
3055:
1457:
3934:
It is open whether the numbers of cuts can be improved. For online algorithms, a lower bound on the number of cuts for
3263:
1829:
Every element of the vector can be either positive (if it belongs to piece #1) or negative (if it belongs to piece #2).
1683:
pieces which are equal in the eyes of the partner that values this district. This raises the question of whether there
1572:
484:
3941:
3445:
problem – each one can be reduced to the other in polynomial time (this implies that necklace splitting is PPAD hard).
3098:
2856:. Here is an intuitive explanation of the packing step for two partners (Alice and George) when the weights are 1/2.
5735:-1) cuts, and that finding an approximate unanimous-proportional division is in PPA. The number of cuts is tight for
4402:
5665:
2501:
2086:
1558:
3145:
2677:, one can give each partner a piece such that all partners believe that the values they have differ by less than
1865:
4281:
3481:
When the resource to divide is not a cake but rather a set of divisible resources, the problem becomes easier:
3120:
The number of agents is a constant and at least 3 (However, with 2 agents it can be solved in polynomial time).
2480:
The total number of different subsets now is 2, and by the induction assumption none of them is exact. At step
948:
421:
307:
2308:
6957:
5700:
pieces (and equal weights). In particular, it implies that unanimous-proportional division requires at least
2896:
1385:
1169:
830:
652:
6576:
2981:
6269:
Simmons, Forest W.; Su, Francis Edward (2003). "Consensus-halving via theorems of Borsuk-Ulam and Tucker".
1769:
6278:
5582:
3155:
It is allowed to use a constant number of additional cuts (that is, we search for a consensus halving for
2985:
2577:. One agent moves the knives cyclically around the cake, always keeping the value between them at exactly
6803:
5451:
5350:
5242:
5164:
5086:
4583:
4482:
4058:
2453:– a subset of the pieces which both partners value as exactly 1/2. We are going to prove that, for every
7325:
5804:
5576:
3063:
2427:
It is impossible to compute an exact division with a finite number of queries, even when there are only
2327:
547:
152:, the agents may disagree on the pieces values, but the difference between the values should be at most
3466:
2878:. Hence, when one of the partners receives the bowl, its value for both partners is between than 1/2-1/
2654:
899:
129:
7029:
2348:
1280:
744:
6283:
3534:
From a computational perspective, not much is known about the computation of an exact division with
2964:. To do this, we have to divide the vectors to subsets, such that the sum of vectors in each subset
1723:
6856:
Filos-Ratsikas, Aris; Hollender, Alexandros; Sotiraki, Katerina; Zampetakis, Manolis (2020-07-13).
6187:
3016:
2019:
1773:
271:
3522:
necessary for consensus halving when agents' utilities are drawn from probabilistic distributions.
2680:
2132:
1965:
1644:
1594:
1337:
1232:
1143:
1119:
925:
248:
225:
199:
175:
155:
107:
7292:
7264:
7241:
7215:
7182:
7136:
7118:
7089:
7067:
7041:
7003:
6971:
6935:
6901:
6865:
6827:
6777:
6749:
6585:
6364:
6317:
5756:
5727:
families. In particular, it implies that exact unanimous-proportional division can be done with (
5588:
3442:
2588:
By repeatedly applying the above procedure, it is possible to achieve a consensus division among
2585:. The other agent calls "stop!" at that point and the piece is cut. This requires only two cuts.
1565:
279:
7028:
Deligkas, Argyrios; Fearnley, John; Melissourgos, Themistoklis; Spirakis, Paul G. (2021-05-01).
6526:
5788:
Perform a random permutation on the consensus partition and give each partner one of the pieces.
4814:
4721:
4156:
4323:
7282:
7233:
7172:
7059:
6961:
6891:
6817:
6767:
6711:
6234:
6224:
5629:
3397:
3012:
2507:
The same protocol can be used to cut a piece that both agents agree that its value is exactly
1568:
1530:
407:
35:
4656:
4213:
3598:
3572:
3477:
that involves solutions to problems whose existence is guaranteed by the Borsuk-Ulam theorem.
2182:
parts (not necessarily contiguous), such that the measure of each part, according to measure
7274:
7225:
7162:
7128:
7051:
6953:
6945:
6883:
6875:
6809:
6759:
6595:
6542:
6508:
6479:
6443:
6414:
6356:
6288:
6023:
5874:
5593:
5493:
4362:
3842:
3728:
3699:
3666:
3537:
3486:
3328:
3020:
2599:
2232:
2029:
6556:
5723:
pieces implies a solution to unanimous-proportional division among n+1 agents grouped into
2542:
2205:
1835:
1586:
Woodall showed that it is possible to construct an exact division of an interval cake as a
1484:
1092:
614:
382:
6552:
6242:
6085:
5770:, can be built given any existing algorithm (or oracle) for finding a consensus division:
5656:
pieces and allocate one piece per family. A natural fairness criterion in this setting is
4625:
3474:
2999:
Most results for bounded number of cuts focus on the case in which the weights are equal.
1917:
6644:
5599:
5549:
5034:
4752:
4187:
2991:
A different explanation of the crumb-and-pack procedure is provided by Brams and Taylor.
2510:
2377:
1803:
1697:
1359:
1254:
804:
718:
5392:
4845:
97:– the number of pieces equals the number of agents: the cake should be partitioned into
6808:. STOC 2019. New York, NY, USA: Association for Computing Machinery. pp. 638–649.
5429:
5328:
5284:
5206:
5128:
5008:
4974:
4948:
4910:
4884:
4792:
4699:
4561:
4524:
4460:
4259:
4134:
4100:
4036:
3236:
2185:
2165:
2112:
2092:
1783:
6484:
6292:
3489:, there is a polynomial-time algorithm for computing a consensus halving with at most
7319:
7186:
7140:
7071:
6975:
6905:
6748:. STOC 2018. New York, NY, USA: Association for Computing Machinery. pp. 51–64.
6512:
6419:
6402:
6344:
5704:-1 cuts, and that finding an approximate unanimous-proportional division is PPA-hard.
5660:, which means that all members in all families value their family's share at least 1/
3519:
3137:
1587:
283:– the resource to divide is made of a finite number of indivisible objects ("beads").
7296:
6934:. EC '21. New York, NY, USA: Association for Computing Machinery. pp. 347–368.
6864:. EC '20. New York, NY, USA: Association for Computing Machinery. pp. 381–399.
6831:
3019:. An adaptation of this algorithm shows that the problem is in the complexity class
1637:
partners values only a single district. Then, a consensus division of the cake into
7245:
7161:, Proceedings, Society for Industrial and Applied Mathematics, pp. 2615–2634,
6928:"Two's Company, Three's a Crowd: Consensus-Halving for a Constant Number of Agents"
6781:
6368:
3621:, since we are allowed to use a larger number of cuts. What is currently known is:
3047:
2461:
there is no exact subset, and hence the protocol might have to continue endlessly.
1580:
1469:
they get from each region. An exact division can be achieved in the following way:
3140:, which is theoretically weaker than PPA-hard. The proof is by reduction from the
7278:
6499:
Stromquist, Walter; Woodall, D.R (1985). "Sets on which several measures agree".
5766:
A better truthful mechanism, which works for the case in which all weights are 1/
172:. Similarly, the approximate variants of the above-mentioned problems are called
7167:
6434:
Goldberg, Charles H.; West, Douglas B. (1985). "Bisection of Circle
Colorings".
6340:
2275:
weights. Stromquist and
Woodall proved that there exists an exact division of a
7229:
7055:
6316:; Graur, Andrei (2020-06-30). "Efficient Splitting of Measures and Necklaces".
2634:
As of 2015, there is no known generalization of this moving-knife procedure to
2061:. In that partition, all partners value piece #1 (and piece #2) at exactly 1/2.
6926:
Deligkas, Argyrios; Filos-Ratsikas, Aris; Hollender, Alexandros (2021-07-18).
6600:
6571:
6360:
2339:
2315:
17:
7237:
7203:
7063:
6547:
6530:
3182:-approximate consensus-halving is PPA-hard (which is stronger than PPAD-hard)
7030:"Computing exact solutions of consensus halving and the Borsuk-Ulam theorem"
6949:
6879:
6813:
6763:
6313:
2323:
2082:
1947:-th element is the value of piece #1 in that partition according to partner
1456:
It is easy to prove the existence of an exact division when the agents have
7132:
6616:
6246:
2326:
space, it is possible to divide all of them in half (with respect to their
6927:
6857:
6805:
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of
Computing
6799:
6746:
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of
Computing
6741:
1564:
An exact division exists in the more general setting in which agents have
6887:
3924:{\displaystyle n\cdot (k-1)\cdot \lceil 2+\log _{2}(3k/\epsilon )\rceil }
3454:
solution, then consensus halving is much harder: finding a solution with
1583:). However, this theorem says nothing about the number of required cuts.
1082:
That is, there is a consensus among all partners that the value of piece
7159:
Proceedings of the 2021 ACM-SIAM Symposium on
Discrete Algorithms (SODA)
3011:-approximate consensus halving can be computed by an algorithm based on
2984:. The latter protocol generates a division which is both near-exact and
2414:
There are also discrete adaptations of these multi-dimensional results.
66: = 2), and all agents agree that the pieces have equal values.
7263:. Lecture Notes in Computer Science. Vol. 6386. pp. 288–299.
5777:
Use the existing algorithm/oracle to generate a partition in which all
5668:). The problem is equivalent to exact division in the following sense:
3651:
Two types of approximations can be computed using polynomial number of
2374:, and the value measures of the partners are finite and vanish on any
607:, since there is a consensus among all agents that the value of piece
6590:
3659:
Finding a partition such that each agent values each part at least 1/
3458:
cuts is FIXP-hard, and deciding whether there exists a solution with
3229:
Finding a partition such that each agent values each part at least 1/
6800:"The complexity of splitting necklaces and bisecting ham sandwiches"
6447:
3441:-approximate consensus-halving is computationally equivalent to the
7220:
7123:
7094:
7046:
7008:
6940:
6932:
Proceedings of the 22nd ACM Conference on
Economics and Computation
6870:
6862:
Proceedings of the 21st ACM Conference on Economics and Computation
6754:
6531:"Partitions of mass–distributions and convex bodies by hyperplanes"
6322:
3256:
Finding a partition such that each agent values each part at 1/2 ±
1465:
topping: the value of each piece to each agent only depends on the
7269:
3512:-1 cuts, where OPT is the optimal number of cuts for the instance.
2303:
Multi-dimensional cake, many partners, many subsets, equal weights
2642:
Computation of near-exact divisions with unbounded number of cuts
7259:
Mossel, Elchanan; Tamuz, Omer (2010). "Truthful Fair Division".
6617:"Consensus division of a cake to two people in arbitrary ratios"
6238:
3201:
3050:. Hardness holds even with the following additional conditions:
2449:
pieces. To provide an exact division, the protocol must find an
2276:
101:
pieces, and all agents agrees that all pieces have equal values.
3765:
Finding a partition such that each agent values each part at 1/
2995:
Computation of near-exact divisions with bounded number of cuts
1557:
is the number of regions. This algorithm can be generalized to
84:
pieces, and all agents agree that the pieces have equal values.
6343:; Lai, John K.; Parkes, David C.; Procaccia, Ariel D. (2013).
6683:
V. Bergström (1930). "Zwei Sätze über ebene Vectorpolygone".
3389:{\displaystyle n\cdot \lceil 2+\log _{2}(1/\epsilon )\rceil }
3071:
The number of pieces in the piecewise-constant valuations is
2817:. These new pieces of course still have a value of at most 1/
1826:, in which the elements are the lengths of the sub-intervals.
1720:
and equal weights. The lower bound on the number of cuts is
3834:{\displaystyle O({\frac {kn\log {(kn)}}{\varepsilon ^{2}}})}
3595:. Note that the problem is not necessarily harder than for
5785:
according to the value functions reported by the partners.
3225:
valuations. The following approximations can be attained:
6382:
Neyman, Jerzy (January 1946). "Un théoreme d'existence".
2968:
is sufficiently close to a vector all whose elements are
2870:
George). Add this crumb to the bowl and return to step 2.
2809:. Ask partner #2 to trim pieces as needed (using at most
1832:
The set of all partitions is homeomorphic to the sphere
80: > 1 – the cake should be partitioned into
2977:. This is possible thanks to a theorem by V.Bergström,
2813:-1 cuts) such that each piece has a value of at most 1/
2279:(a circular cake) in which each piece contains at most
6798:
Filos-Ratsikas, Aris; Goldberg, Paul W. (2019-06-23).
6740:
Filos-Ratsikas, Aris; Goldberg, Paul W. (2018-06-20).
5680:, a solution to unanimous-proportional division among
2801:
be a certain constant. Ask partner #1 cut the cake to
1768:
cuts always exists. This is a direct corollary of the
6710:]. Cambridge University Press. pp. 131–133.
6647:
6088:
6026:
5877:
5602:
5552:
5496:
5454:
5432:
5395:
5353:
5331:
5287:
5245:
5209:
5167:
5131:
5089:
5037:
5011:
4977:
4951:
4913:
4887:
4848:
4817:
4795:
4755:
4724:
4702:
4659:
4628:
4586:
4564:
4527:
4485:
4463:
4405:
4365:
4326:
4284:
4262:
4216:
4190:
4159:
4137:
4103:
4061:
4039:
3944:
3851:
3779:
3731:
3669:
3601:
3575:
3540:
3337:
3266:
3239:
2899:
2714:
2683:
2657:
2602:
2545:
2513:
2380:
2351:
2235:
2208:
2188:
2168:
2162:. Then it is possible to partition the interval into
2135:
2115:
2095:
2032:
1968:
1920:
1868:
1838:
1806:
1786:
1726:
1700:
1647:
1597:
1533:
1487:
1388:
1362:
1340:
1283:
1257:
1235:
1172:
1146:
1122:
1095:
1013:
951:
928:
902:
833:
807:
747:
721:
655:
617:
550:
487:
424:
385:
310:
251:
228:
202:
178:
158:
132:
110:
6463:"The Borsuk-Ulam theorem and bisection of necklaces"
5792:
Here, the expected value of each partner is still 1/
5692:
families implies a solution to exact division among
3148:. Hardness holds even in the following conditions:
2980:
The Crumb-and-Pack procedure is a subroutine in the
2843:
subsets, such that the sum of values in each subset
2773:{\displaystyle |V_{i}(X_{j})-w_{j}|<\varepsilon }
1072:{\displaystyle |V_{i}(X_{j})-w_{j}|<\varepsilon }
3403:Note that there is a gap between PPAD-hardness for
2821:
for partner #1. Continue with partners #3, #4, …, #
1679:cuts, since each of the districts must be cut into
1573:
a corollary of the Dubins–Spanier convexity theorem
1460:. This means that the cake can be partitioned into
6661:
6570:de Longueville, Mark; Živaljević, Rade T. (2008).
6103:
6047:
5898:
5616:
5566:
5517:
5480:
5438:
5404:
5379:
5337:
5293:
5271:
5215:
5193:
5137:
5115:
5049:
5017:
4983:
4957:
4919:
4893:
4857:
4832:
4801:
4767:
4739:
4708:
4671:
4643:
4612:
4570:
4533:
4511:
4469:
4433:
4377:
4351:
4310:
4268:
4228:
4202:
4174:
4143:
4109:
4087:
4045:
3973:
3923:
3833:
3752:
3690:
3613:
3587:
3561:
3388:
3319:
3245:
2943:
2772:
2689:
2669:
2623:
2569:
2527:
2492:Two agents can achieve a consensus division using
2392:
2366:
2256:
2221:
2194:
2174:
2154:
2121:
2101:
2053:
2007:
1935:
1902:
1851:
1818:
1792:
1756:
1712:
1671:
1609:
1545:
1500:
1434:
1374:
1346:
1323:
1269:
1241:
1218:
1152:
1128:
1108:
1071:
996:
934:
914:
879:
819:
787:
733:
701:
630:
592:
525:
469:
398:
355:
257:
234:
208:
184:
164:
144:
116:
62:– the cake should be partitioned into two pieces (
7202:Segal-Halevi, Erel; Nitzan, Shmuel (2019-12-01).
6958:20.500.11820/f92c933a-c6bd-4f93-b56f-de38970860e7
6501:Journal of Mathematical Analysis and Applications
6407:Journal of Mathematical Analysis and Applications
3320:{\displaystyle O((n\log {n})/(\varepsilon ^{2}))}
2829:partners value each resulting crumb as at most 1/
2783:The near-exact division procedure has two steps:
526:{\displaystyle C=X_{1}\sqcup \cdots \sqcup X_{k}}
6471:Proceedings of the American Mathematical Society
3974:{\displaystyle O({\frac {n}{\varepsilon ^{2}}})}
5652:families; the goal is to partition a cake into
6637:There is a generalization which gives each of
6436:SIAM Journal on Algebraic and Discrete Methods
5664:(for other criteria and related problems, see
4434:{\displaystyle \varepsilon \in \Omega (2^{n})}
3200:is a constant. The proof is by reduction from
2839:: the goal here is to partition the crumbs to
1800:cuts can be represented as a vector of length
6858:"Consensus-Halving: Does It Ever Get Easier?"
6264:
6262:
6260:
6258:
6256:
5774:Ask each partner to report his value measure.
5640:In the problem of cake-cutting among families
4447:PPA-hard for piecewise-constant valuations ).
3079:(the values themselves may be exponential in
2345:Stated differently: if the cake is the space
34:, is a partition of a continuous resource ("
8:
6671:Austin moving-knife procedures#Many partners
3918:
3876:
3383:
3344:
2951:. Our goal is to create, for each partner
2465:opinion, so again there is no exact subset.
6221:Cake-Cutting Algorithms: Be Fair If You Can
3465:When agents' valuations are represented by
1903:{\displaystyle V:S^{n}\to \mathbb {R} ^{n}}
1764:. Indeed, a consensus halving with at most
1633:districts (sub-intervals), and each of the
6702:Brams, Steven J.; Taylor, Alan D. (1996).
1910:in the following way: for every partition
7268:
7219:
7166:
7122:
7093:
7045:
7007:
6939:
6869:
6753:
6651:
6646:
6599:
6589:
6546:
6483:
6418:
6384:Comptes Rendus de l'Académie des Sciences
6321:
6282:
6087:
6025:
5876:
5606:
5601:
5556:
5551:
5495:
5461:
5453:
5431:
5394:
5360:
5352:
5330:
5307:PPA-hard; At least exponential #queries.
5286:
5252:
5244:
5229:PPA-hard; At least exponential #queries.
5208:
5174:
5166:
5130:
5096:
5088:
5036:
5010:
4976:
4950:
4912:
4886:
4847:
4816:
4794:
4754:
4723:
4701:
4658:
4627:
4593:
4585:
4563:
4526:
4492:
4484:
4462:
4422:
4404:
4364:
4337:
4325:
4311:{\displaystyle \Omega ({\text{poly}}(n))}
4291:
4283:
4261:
4215:
4189:
4158:
4136:
4102:
4068:
4060:
4038:
3960:
3951:
3943:
3907:
3889:
3850:
3820:
3801:
3786:
3778:
3730:
3668:
3600:
3574:
3539:
3415:, and the polynomial-time algorithm for 2
3372:
3357:
3336:
3305:
3293:
3285:
3265:
3238:
2933:
2926:
2918:
2913:
2905:
2900:
2898:
2759:
2753:
2737:
2724:
2715:
2713:
2682:
2656:
2601:
2544:
2517:
2512:
2379:
2358:
2354:
2353:
2350:
2234:
2213:
2207:
2187:
2167:
2146:
2134:
2114:
2094:
2089:, proved the following result. There are
2031:
1967:
1919:
1894:
1890:
1889:
1879:
1867:
1843:
1837:
1805:
1785:
1725:
1699:
1646:
1596:
1532:
1492:
1486:
1424:
1412:
1393:
1387:
1361:
1339:
1313:
1301:
1288:
1282:
1256:
1234:
1208:
1196:
1177:
1171:
1145:
1121:
1100:
1094:
1058:
1052:
1036:
1023:
1014:
1012:
997:{\displaystyle w_{1},w_{2},\ldots ,w_{k}}
988:
969:
956:
950:
927:
901:
869:
857:
838:
832:
806:
777:
765:
752:
746:
720:
691:
679:
660:
654:
622:
616:
584:
568:
555:
549:
517:
498:
486:
470:{\displaystyle w_{1},w_{2},\ldots ,w_{k}}
461:
442:
429:
423:
390:
384:
367:weights whose sum is 1. Assume there are
356:{\displaystyle w_{1},w_{2},\ldots ,w_{k}}
347:
328:
315:
309:
250:
227:
201:
177:
157:
131:
109:
6335:
6333:
5814:
3986:
3030:is allowed to be inverse-exponential in
2457:, there are situations in which at step
1629:Suppose the cake is an interval made of
7034:Journal of Computer and System Sciences
6708:From cake-cutting to dispute resolution
6223:. Natick, Massachusetts: A. K. Peters.
6219:Robertson, Jack; Webb, William (1998).
6198:
6063:
3188:Also, deciding whether there exists an
3090:is allowed to be inverse-polynomial in
2955:, a vector all whose elements are near
2944:{\displaystyle ||v||\leq {\sqrt {n}}/k}
2863:Insert into the bowl one of the crumbs.
2423:Impossibility using discrete procedures
1591:become more and more homogeneous. When
1435:{\displaystyle w_{1}=\cdots =w_{n}=1/n}
1219:{\displaystyle w_{1}=\cdots =w_{n}=1/k}
880:{\displaystyle w_{1}=\cdots =w_{n}=1/n}
702:{\displaystyle w_{1}=\cdots =w_{n}=1/k}
7197:
7195:
6572:"Splitting multidimensional necklaces"
6214:
6212:
6210:
6208:
6206:
6204:
6202:
5546:An exact division with equal weights (
3152:The valuations are piecewise-constant;
2264:cuts are needed, and this is optimal.
7152:
7150:
7083:
7081:
7023:
7021:
7019:
6997:
6995:
6993:
6991:
6989:
6987:
6985:
6921:
6919:
6917:
6915:
6851:
6849:
6847:
6845:
6843:
6841:
6793:
6791:
6735:
6733:
6731:
6729:
6727:
6461:Alon, Noga; West, Douglas B. (1986).
5715:, a solution to exact-division among
3530:Many subsets (consensus 1/k-division)
3433:is constant or inverse-polynomial in
2596:>1 subsets. The number of cuts is
1780:Every partition of an interval using
7:
6308:
6306:
6304:
6302:
3493:cuts, and for computing a consensus
3192:-approximate consensus halving with
1116:, where the difference is less than
6742:"Consensus halving is PPA-complete"
6152:
5942:
5481:{\displaystyle O({\text{poly}}(n))}
5380:{\displaystyle O({\text{poly}}(n))}
5272:{\displaystyle O({\text{poly}}(n))}
5194:{\displaystyle O({\text{poly}}(n))}
5116:{\displaystyle O({\text{poly}}(n))}
4613:{\displaystyle O({\text{poly}}(n))}
4512:{\displaystyle O({\text{poly}}(n))}
4088:{\displaystyle O({\text{poly}}(n))}
3992:-approximate consensus-halving for
3450:If we are interested in finding an
3015:, which is the discrete version of
371:agents, all of whom value the cake
275:– there are infinitely many agents.
7204:"Fair cake-cutting among families"
7111:Mathematics of Operations Research
6345:"Truth, justice, and cake cutting"
5063:ETR-complete to decide existence.
4818:
4725:
4412:
4285:
4160:
3717:), where c(k) is some function of
3644:may be an exponential function of
3178:is a constant, it is open whether
3136:-approximate consensus-halving is
3128:is a constant (does not depend on
3105:cuts, and in polynomial time for 2
3046:-approximate consensus-halving is
1772:. It can also be proved using the
1604:
1579:-division was previously noted by
1477:sub-regions, such that sub-region
593:{\displaystyle V_{i}(X_{j})=w_{j}}
25:
6485:10.1090/s0002-9939-1986-0861764-9
5592:. However, it is not necessarily
5151:Polynomial; Polynomial #queries.
2670:{\displaystyle \varepsilon >0}
2445:, it has a collection of at most
1958:is continuous. Moreover, for all
915:{\displaystyle \varepsilon >0}
375:as 1. The value measure of agent
145:{\displaystyle \varepsilon >0}
6641:partners, a piece worth exactly
6119:
3981:, so there is a logarithmic gap.
2468:Suppose now that we are at step
2367:{\displaystyle \mathbb {R} ^{n}}
1575:(the existence of a consensus 1/
477:is a partition of the cake into
3003:Two subsets (consensus halving)
2441:: When the protocol is at step
2295:>1 and any weights, using O(
1527:The number of required cuts is
1324:{\displaystyle w_{1}=w_{2}=1/2}
788:{\displaystyle w_{1}=w_{2}=1/2}
6042:
6030:
5914:
5893:
5881:
5542:Comparison with other criteria
5509:
5497:
5475:
5472:
5466:
5458:
5374:
5371:
5365:
5357:
5266:
5263:
5257:
5249:
5188:
5185:
5179:
5171:
5110:
5107:
5101:
5093:
4827:
4821:
4734:
4728:
4607:
4604:
4598:
4590:
4506:
4503:
4497:
4489:
4428:
4415:
4305:
4302:
4296:
4288:
4169:
4163:
4082:
4079:
4073:
4065:
3968:
3948:
3915:
3898:
3870:
3858:
3828:
3811:
3802:
3783:
3744:
3732:
3682:
3670:
3553:
3541:
3380:
3366:
3314:
3311:
3298:
3290:
3273:
3270:
3038:is an exponential function of
2919:
2914:
2906:
2901:
2760:
2743:
2730:
2716:
2618:
2606:
2564:
2552:
2418:Computation of exact divisions
2283:-1 intervals; hence, at most 2
2248:
2236:
2085:, in his 1987 paper about the
2042:
2036:
1996:
1987:
1978:
1972:
1930:
1924:
1885:
1757:{\displaystyle n\cdot (k-1)=n}
1745:
1733:
1666:
1654:
1601:
1059:
1042:
1029:
1015:
574:
561:
1:
6293:10.1016/S0165-4896(02)00087-2
6001:
4781:NP-hard to decide existence.
3196:-1 cuts is NP-hard even when
3056:piecewise-constant valuations
2494:Austin moving-knife procedure
2330:, i.e. volume) with a single
1458:piecewise-constant valuations
7279:10.1007/978-3-642-16170-4_25
6513:10.1016/0022-247x(85)90021-6
6420:10.1016/0022-247x(80)90225-5
6271:Mathematical Social Sciences
5970:
3636:The problem is PPA-hard for
2690:{\displaystyle \varepsilon }
2155:{\displaystyle k\cdot a_{i}}
2008:{\displaystyle V(x)+V(-x)=0}
1672:{\displaystyle n\cdot (k-1)}
1610:{\displaystyle R\to \infty }
1356:– the special case in which
1347:{\displaystyle \varepsilon }
1251:– the special case in which
1242:{\displaystyle \varepsilon }
1166:– the special case in which
1153:{\displaystyle \varepsilon }
1129:{\displaystyle \varepsilon }
935:{\displaystyle \varepsilon }
801:– the special case in which
715:– the special case in which
649:– the special case in which
533:, such that for every agent
258:{\displaystyle \varepsilon }
235:{\displaystyle \varepsilon }
209:{\displaystyle \varepsilon }
185:{\displaystyle \varepsilon }
165:{\displaystyle \varepsilon }
117:{\displaystyle \varepsilon }
7168:10.1137/1.9781611976465.155
6349:Games and Economic Behavior
5852:
3146:Generalised Circuit problem
3097:The agents' valuations are
2805:pieces that he values as 1/
1559:piecewise-linear valuations
1136:. Some special cases are:
7342:
7230:10.1007/s00355-019-01210-9
7056:10.1016/j.jcss.2020.10.006
6111:(optimal for some weights)
5688:-1)+1 agents grouped into
5666:fair division among groups
5574:) is, in particular, also
4933:Strong approximation is BU
4833:{\displaystyle \Omega (1)}
4740:{\displaystyle \Omega (1)}
4175:{\displaystyle \Omega (1)}
3988:Computational results for
3215:Robertson–Webb query model
2502:intermediate value theorem
2289:Stromquist–Woodall theorem
2087:necklace splitting problem
638:. Some special cases are:
42:pieces, such that each of
7208:Social Choice and Welfare
6685:Hamburgische Abhandlungen
6601:10.1016/j.aim.2008.02.003
6361:10.1016/j.geb.2012.10.009
5658:unanimous proportionality
5636:Unanimous proportionality
5311:
5067:
4550:Parametrized polynomial.
4352:{\displaystyle n+n^{1-d}}
3705:It is open whether the 1/
3221:-query to the sum of all
3086:The approximation factor
2081:>1 and equal weights.
6548:10.2140/pjm.1960.10.1257
6403:"Dividing a cake fairly"
5739:=2 families but not for
3497:-division with at most (
3462:-1 cuts is ETR-complete.
3167:cuts, for some constant
2647:Crumb-and-pack procedure
2287:-2 cuts are needed. See
1546:{\displaystyle k\cdot R}
1473:Divide each region into
1452:Unbounded number of cuts
1004:is a division in which:
406:. It is assumed to be a
7261:Algorithmic Game Theory
6950:10.1145/3465456.3467625
6880:10.1145/3391403.3399527
6814:10.1145/3313276.3316334
6764:10.1145/3188745.3188880
6577:Advances in Mathematics
4672:{\displaystyle d\geq 0}
4229:{\displaystyle d\geq 0}
3614:{\displaystyle k\geq 2}
3588:{\displaystyle k\geq 3}
2982:Robertson-Webb protocol
2488:Moving-knife procedures
1519:-th sub-regions in all
7133:10.1287/moor.2021.1249
6663:
6105:
6049:
6048:{\displaystyle n(k-1)}
5900:
5899:{\displaystyle 2(k-1)}
5857:Moving-knife procedure
5618:
5568:
5519:
5518:{\displaystyle (k-1)n}
5482:
5440:
5406:
5381:
5339:
5295:
5273:
5217:
5195:
5139:
5117:
5051:
5019:
4985:
4959:
4921:
4895:
4859:
4834:
4803:
4769:
4741:
4710:
4673:
4645:
4614:
4572:
4535:
4513:
4471:
4435:
4379:
4378:{\displaystyle d>0}
4353:
4312:
4270:
4230:
4204:
4176:
4145:
4111:
4089:
4047:
3975:
3925:
3835:
3754:
3753:{\displaystyle (k-1)n}
3692:
3691:{\displaystyle (k-1)n}
3653:Robertson-Webb queries
3625:The problem is in PPA-
3615:
3589:
3563:
3562:{\displaystyle (k-1)n}
3411:cuts for any constant
3390:
3321:
3247:
3113:cuts for any constant
2986:envy-free cake-cutting
2945:
2774:
2691:
2671:
2625:
2624:{\displaystyle 2(k-1)}
2571:
2529:
2394:
2368:
2267:Consider now the case
2258:
2257:{\displaystyle (k-1)n}
2223:
2196:
2176:
2156:
2123:
2103:
2066:additively separable.
2055:
2054:{\displaystyle V(x)=0}
2009:
1937:
1904:
1853:
1820:
1794:
1758:
1714:
1673:
1625:Bounded number of cuts
1611:
1547:
1502:
1436:
1376:
1348:
1325:
1271:
1243:
1220:
1154:
1130:
1110:
1073:
998:
936:
916:
881:
821:
789:
735:
703:
632:
594:
527:
471:
400:
357:
259:
236:
210:
186:
166:
146:
118:
6664:
6401:Woodall, D.R (1980).
6106:
6050:
5922:Piecewise-homogeneous
5915:Piecewise-homogeneous
5901:
5805:truthful cake-cutting
5781:pieces are exactly 1/
5619:
5569:
5520:
5483:
5441:
5407:
5382:
5340:
5296:
5274:
5218:
5196:
5140:
5118:
5052:
5020:
4986:
4960:
4922:
4896:
4860:
4835:
4804:
4770:
4742:
4711:
4674:
4646:
4615:
4573:
4536:
4514:
4472:
4436:
4380:
4354:
4313:
4271:
4231:
4205:
4177:
4146:
4112:
4090:
4048:
3976:
3926:
3836:
3755:
3693:
3616:
3590:
3564:
3391:
3322:
3248:
3062:) are represented in
2946:
2775:
2692:
2672:
2626:
2572:
2570:{\displaystyle p\in }
2530:
2395:
2369:
2259:
2224:
2222:{\displaystyle a_{i}}
2197:
2177:
2157:
2124:
2104:
2056:
2010:
1938:
1905:
1854:
1852:{\displaystyle S^{n}}
1821:
1795:
1759:
1715:
1674:
1612:
1548:
1503:
1501:{\displaystyle w_{j}}
1437:
1377:
1349:
1326:
1272:
1244:
1221:
1155:
1131:
1111:
1109:{\displaystyle w_{j}}
1074:
999:
937:
917:
882:
822:
790:
736:
704:
633:
631:{\displaystyle w_{j}}
595:
528:
472:
401:
399:{\displaystyle V_{i}}
358:
260:
243:-consensus-splitting,
237:
211:
187:
167:
147:
119:
6645:
6157:Near-exact procedure
6104:{\displaystyle 2n-2}
6086:
6024:
5875:
5648:agents grouped into
5600:
5550:
5494:
5452:
5430:
5393:
5351:
5329:
5285:
5243:
5207:
5165:
5129:
5087:
5035:
5009:
4975:
4949:
4911:
4885:
4846:
4815:
4793:
4753:
4722:
4700:
4657:
4644:{\displaystyle 2n-d}
4626:
4584:
4562:
4525:
4483:
4461:
4403:
4363:
4324:
4282:
4260:
4214:
4188:
4157:
4135:
4101:
4059:
4037:
3942:
3849:
3777:
3729:
3667:
3599:
3573:
3538:
3335:
3264:
3237:
3132:). Then, finding an
3042:). Then, finding an
3026:First, assumed that
2897:
2712:
2681:
2655:
2600:
2592:=2 partners and any
2543:
2511:
2378:
2349:
2233:
2206:
2186:
2166:
2133:
2113:
2093:
2030:
1966:
1936:{\displaystyle V(x)}
1918:
1866:
1836:
1804:
1784:
1724:
1698:
1645:
1621:union of intervals.
1595:
1531:
1515:be the union of the
1485:
1386:
1360:
1338:
1281:
1255:
1233:
1170:
1144:
1120:
1093:
1011:
949:
943:-near-exact division
926:
900:
831:
805:
745:
719:
653:
615:
603:It is also called a
548:
485:
422:
383:
308:
249:
226:
200:
176:
156:
130:
124:-near-exact division
108:
6662:{\displaystyle 1/n}
6188:Problem of the Nile
5750:Truthful mechanisms
5617:{\displaystyle 1/n}
5567:{\displaystyle 1/n}
5528:piecewise-constant
5415:piecewise-constant
5060:algebraic circuits
5050:{\displaystyle n-1}
4994:algebraic circuits
4930:algebraic circuits
4868:piecewise-constant
4778:piecewise-constant
4768:{\displaystyle n-1}
4239:piecewise-constant
4203:{\displaystyle n+d}
3997:
3017:Borsuk-Ulam theorem
2528:{\displaystyle 1/n}
2393:{\displaystyle n-1}
2309:Stone–Tukey theorem
2020:Borsuk-Ulam theorem
1819:{\displaystyle n+1}
1774:Borsuk-Ulam theorem
1713:{\displaystyle k=2}
1690:Consider first the
1375:{\displaystyle k=n}
1270:{\displaystyle k=2}
892:Near-exact division
820:{\displaystyle k=n}
734:{\displaystyle k=2}
272:Problem of the Nile
126:, for any constant
89:consensus splitting
76:, for any constant
51: = 3 and
28:Consensus splitting
6659:
6101:
6064:Stromquist-Woodall
6045:
6002:Necklace-splitting
5975:Infinite procedure
5919:Discrete procedure
5896:
5757:truthful mechanism
5614:
5564:
5515:
5478:
5436:
5405:{\displaystyle 2n}
5402:
5377:
5335:
5291:
5269:
5213:
5191:
5135:
5113:
5047:
5015:
4981:
4955:
4917:
4891:
4858:{\displaystyle 2n}
4855:
4830:
4799:
4765:
4737:
4706:
4682:piecewise-uniform
4669:
4641:
4610:
4568:
4544:piecewise-uniform
4531:
4509:
4467:
4431:
4388:piecewise-uniform
4375:
4349:
4308:
4266:
4247:whether PPA-hard.
4226:
4200:
4172:
4141:
4107:
4085:
4043:
3987:
3971:
3921:
3831:
3750:
3688:
3611:
3585:
3559:
3487:additive utilities
3467:algebraic circuits
3443:necklace splitting
3386:
3317:
3243:
3124:Next, assume that
2941:
2860:Get an empty bowl.
2770:
2697:, i.e., for every
2687:
2667:
2621:
2567:
2525:
2390:
2364:
2311:states that given
2254:
2219:
2192:
2172:
2152:
2119:
2099:
2051:
2022:, there exists an
2005:
1943:is a vector whose
1933:
1900:
1862:Define a function
1849:
1816:
1790:
1770:Hobby–Rice theorem
1754:
1710:
1669:
1607:
1569:nonatomic measures
1566:countably-additive
1543:
1498:
1432:
1372:
1344:
1321:
1267:
1249:-consensus halving
1239:
1216:
1150:
1126:
1106:
1069:
994:
932:
912:
877:
817:
785:
731:
699:
628:
605:consensus division
590:
523:
467:
396:
353:
280:Necklace splitting
266:-perfect-division.
255:
232:
206:
193:-consensus-halving
182:
162:
142:
114:
7288:978-3-642-16169-8
7178:978-1-61197-646-5
6967:978-1-4503-8554-1
6897:978-1-4503-7975-5
6823:978-1-4503-6705-9
6773:978-1-4503-5559-9
6717:978-0-521-55644-6
6615:Fischer, Daniel.
6230:978-1-56881-076-8
6179:
6178:
5971:Consensus-halving
5934:Num. of districts
5630:fair cake-cutting
5539:
5538:
5464:
5439:{\displaystyle n}
5363:
5338:{\displaystyle n}
5294:{\displaystyle n}
5255:
5216:{\displaystyle n}
5177:
5138:{\displaystyle n}
5099:
5018:{\displaystyle n}
4984:{\displaystyle n}
4958:{\displaystyle n}
4920:{\displaystyle n}
4894:{\displaystyle n}
4802:{\displaystyle n}
4709:{\displaystyle n}
4596:
4571:{\displaystyle n}
4534:{\displaystyle n}
4495:
4470:{\displaystyle n}
4294:
4269:{\displaystyle n}
4144:{\displaystyle n}
4110:{\displaystyle n}
4071:
4046:{\displaystyle n}
3966:
3826:
3398:offline algorithm
3246:{\displaystyle n}
3099:piecewise-uniform
2931:
2195:{\displaystyle i}
2175:{\displaystyle k}
2122:{\displaystyle i}
2102:{\displaystyle n}
2069:Consider now the
1793:{\displaystyle n}
1692:consensus halving
1641:subsets requires
1481:contains exactly
1354:-perfect division
713:Consensus halving
408:nonatomic measure
60:Consensus halving
16:(Redirected from
7333:
7311:
7307:
7301:
7300:
7272:
7256:
7250:
7249:
7223:
7199:
7190:
7189:
7170:
7154:
7145:
7144:
7126:
7117:(4): 3357–3379.
7106:
7100:
7099:
7097:
7085:
7076:
7075:
7049:
7025:
7014:
7013:
7011:
6999:
6980:
6979:
6943:
6923:
6910:
6909:
6873:
6853:
6836:
6835:
6795:
6786:
6785:
6757:
6737:
6722:
6721:
6699:
6693:
6692:
6680:
6674:
6668:
6666:
6665:
6660:
6655:
6635:
6629:
6628:
6626:
6624:
6612:
6606:
6605:
6603:
6593:
6567:
6561:
6560:
6550:
6541:(4): 1257–1261.
6523:
6517:
6516:
6496:
6490:
6489:
6487:
6467:
6458:
6452:
6451:
6431:
6425:
6424:
6422:
6398:
6392:
6391:
6379:
6373:
6372:
6337:
6328:
6327:
6325:
6310:
6297:
6296:
6286:
6266:
6251:
6250:
6216:
6138:
6129:
6110:
6108:
6107:
6102:
6054:
6052:
6051:
6046:
5992:
5905:
5903:
5902:
5897:
5840:
5833:
5815:
5759:should be used.
5623:
5621:
5620:
5615:
5610:
5594:Pareto efficient
5573:
5571:
5570:
5565:
5560:
5524:
5522:
5521:
5516:
5487:
5485:
5484:
5479:
5465:
5462:
5445:
5443:
5442:
5437:
5411:
5409:
5408:
5403:
5386:
5384:
5383:
5378:
5364:
5361:
5344:
5342:
5341:
5336:
5300:
5298:
5297:
5292:
5278:
5276:
5275:
5270:
5256:
5253:
5222:
5220:
5219:
5214:
5200:
5198:
5197:
5192:
5178:
5175:
5144:
5142:
5141:
5136:
5122:
5120:
5119:
5114:
5100:
5097:
5056:
5054:
5053:
5048:
5024:
5022:
5021:
5016:
4990:
4988:
4987:
4982:
4964:
4962:
4961:
4956:
4926:
4924:
4923:
4918:
4900:
4898:
4897:
4892:
4864:
4862:
4861:
4856:
4839:
4837:
4836:
4831:
4808:
4806:
4805:
4800:
4774:
4772:
4771:
4766:
4746:
4744:
4743:
4738:
4715:
4713:
4712:
4707:
4678:
4676:
4675:
4670:
4650:
4648:
4647:
4642:
4619:
4617:
4616:
4611:
4597:
4594:
4577:
4575:
4574:
4569:
4540:
4538:
4537:
4532:
4518:
4516:
4515:
4510:
4496:
4493:
4476:
4474:
4473:
4468:
4440:
4438:
4437:
4432:
4427:
4426:
4384:
4382:
4381:
4376:
4358:
4356:
4355:
4350:
4348:
4347:
4317:
4315:
4314:
4309:
4295:
4292:
4275:
4273:
4272:
4267:
4235:
4233:
4232:
4227:
4209:
4207:
4206:
4201:
4181:
4179:
4178:
4173:
4150:
4148:
4147:
4142:
4116:
4114:
4113:
4108:
4094:
4092:
4091:
4086:
4072:
4069:
4052:
4050:
4049:
4044:
3998:
3980:
3978:
3977:
3972:
3967:
3965:
3964:
3952:
3930:
3928:
3927:
3922:
3911:
3894:
3893:
3843:online algorithm
3840:
3838:
3837:
3832:
3827:
3825:
3824:
3815:
3814:
3787:
3759:
3757:
3756:
3751:
3721:(independent of
3700:online algorithm
3697:
3695:
3694:
3689:
3620:
3618:
3617:
3612:
3594:
3592:
3591:
3586:
3568:
3566:
3565:
3560:
3485:For agents with
3395:
3393:
3392:
3387:
3376:
3362:
3361:
3329:online algorithm
3326:
3324:
3323:
3318:
3310:
3309:
3297:
3289:
3252:
3250:
3249:
3244:
2950:
2948:
2947:
2942:
2937:
2932:
2927:
2922:
2917:
2909:
2904:
2779:
2777:
2776:
2771:
2763:
2758:
2757:
2742:
2741:
2729:
2728:
2719:
2696:
2694:
2693:
2688:
2676:
2674:
2673:
2668:
2630:
2628:
2627:
2622:
2576:
2574:
2573:
2568:
2534:
2532:
2531:
2526:
2521:
2399:
2397:
2396:
2391:
2373:
2371:
2370:
2365:
2363:
2362:
2357:
2337:
2321:
2314:
2263:
2261:
2260:
2255:
2228:
2226:
2225:
2220:
2218:
2217:
2201:
2199:
2198:
2193:
2181:
2179:
2178:
2173:
2161:
2159:
2158:
2153:
2151:
2150:
2128:
2126:
2125:
2120:
2108:
2106:
2105:
2100:
2060:
2058:
2057:
2052:
2025:
2014:
2012:
2011:
2006:
1961:
1957:
1950:
1946:
1942:
1940:
1939:
1934:
1913:
1909:
1907:
1906:
1901:
1899:
1898:
1893:
1884:
1883:
1858:
1856:
1855:
1850:
1848:
1847:
1825:
1823:
1822:
1817:
1799:
1797:
1796:
1791:
1763:
1761:
1760:
1755:
1719:
1717:
1716:
1711:
1678:
1676:
1675:
1670:
1616:
1614:
1613:
1608:
1552:
1550:
1549:
1544:
1507:
1505:
1504:
1499:
1497:
1496:
1441:
1439:
1438:
1433:
1428:
1417:
1416:
1398:
1397:
1381:
1379:
1378:
1373:
1353:
1351:
1350:
1345:
1330:
1328:
1327:
1322:
1317:
1306:
1305:
1293:
1292:
1276:
1274:
1273:
1268:
1248:
1246:
1245:
1240:
1225:
1223:
1222:
1217:
1212:
1201:
1200:
1182:
1181:
1159:
1157:
1156:
1151:
1135:
1133:
1132:
1127:
1115:
1113:
1112:
1107:
1105:
1104:
1078:
1076:
1075:
1070:
1062:
1057:
1056:
1041:
1040:
1028:
1027:
1018:
1003:
1001:
1000:
995:
993:
992:
974:
973:
961:
960:
941:
939:
938:
933:
921:
919:
918:
913:
886:
884:
883:
878:
873:
862:
861:
843:
842:
826:
824:
823:
818:
799:Perfect division
794:
792:
791:
786:
781:
770:
769:
757:
756:
740:
738:
737:
732:
708:
706:
705:
700:
695:
684:
683:
665:
664:
637:
635:
634:
629:
627:
626:
599:
597:
596:
591:
589:
588:
573:
572:
560:
559:
537:and every piece
532:
530:
529:
524:
522:
521:
503:
502:
476:
474:
473:
468:
466:
465:
447:
446:
434:
433:
405:
403:
402:
397:
395:
394:
362:
360:
359:
354:
352:
351:
333:
332:
320:
319:
264:
262:
261:
256:
241:
239:
238:
233:
215:
213:
212:
207:
191:
189:
188:
183:
171:
169:
168:
163:
151:
149:
148:
143:
123:
121:
120:
115:
95:Perfect division
87:Another term is
21:
7341:
7340:
7336:
7335:
7334:
7332:
7331:
7330:
7316:
7315:
7314:
7308:
7304:
7289:
7258:
7257:
7253:
7201:
7200:
7193:
7179:
7156:
7155:
7148:
7108:
7107:
7103:
7087:
7086:
7079:
7027:
7026:
7017:
7001:
7000:
6983:
6968:
6925:
6924:
6913:
6898:
6855:
6854:
6839:
6824:
6797:
6796:
6789:
6774:
6739:
6738:
6725:
6718:
6701:
6700:
6696:
6682:
6681:
6677:
6643:
6642:
6636:
6632:
6622:
6620:
6614:
6613:
6609:
6569:
6568:
6564:
6535:Pacific J. Math
6525:
6524:
6520:
6498:
6497:
6493:
6465:
6460:
6459:
6455:
6448:10.1137/0606010
6433:
6432:
6428:
6400:
6399:
6395:
6381:
6380:
6376:
6339:
6338:
6331:
6312:
6311:
6300:
6284:10.1.1.203.1189
6268:
6267:
6254:
6231:
6218:
6217:
6200:
6196:
6184:
6136:
6127:
6124:Existence proof
6084:
6083:
6068:Existence proof
6022:
6021:
6006:Existence proof
5990:
5947:Existence proof
5873:
5872:
5838:
5831:
5813:
5752:
5638:
5598:
5597:
5548:
5547:
5544:
5492:
5491:
5450:
5449:
5428:
5427:
5391:
5390:
5349:
5348:
5327:
5326:
5283:
5282:
5241:
5240:
5205:
5204:
5163:
5162:
5127:
5126:
5085:
5084:
5033:
5032:
5007:
5006:
4973:
4972:
4947:
4946:
4936:
4909:
4908:
4883:
4882:
4844:
4843:
4813:
4812:
4791:
4790:
4751:
4750:
4720:
4719:
4698:
4697:
4655:
4654:
4624:
4623:
4582:
4581:
4560:
4559:
4523:
4522:
4481:
4480:
4459:
4458:
4448:
4444:
4418:
4401:
4400:
4397:
4361:
4360:
4333:
4322:
4321:
4280:
4279:
4258:
4257:
4212:
4211:
4186:
4185:
4155:
4154:
4133:
4132:
4120:any continuous
4099:
4098:
4057:
4056:
4035:
4034:
3956:
3940:
3939:
3885:
3847:
3846:
3816:
3788:
3775:
3774:
3727:
3726:
3665:
3664:
3597:
3596:
3571:
3570:
3536:
3535:
3532:
3353:
3333:
3332:
3301:
3262:
3261:
3235:
3234:
3005:
2997:
2976:
2963:
2895:
2894:
2855:
2749:
2733:
2720:
2710:
2709:
2679:
2678:
2653:
2652:
2649:
2644:
2598:
2597:
2541:
2540:
2509:
2508:
2490:
2425:
2420:
2376:
2375:
2352:
2347:
2346:
2331:
2319:
2312:
2305:
2231:
2230:
2209:
2204:
2203:
2184:
2183:
2164:
2163:
2142:
2131:
2130:
2111:
2110:
2091:
2090:
2028:
2027:
2023:
1964:
1963:
1959:
1955:
1948:
1944:
1916:
1915:
1911:
1888:
1875:
1864:
1863:
1839:
1834:
1833:
1802:
1801:
1782:
1781:
1722:
1721:
1696:
1695:
1643:
1642:
1627:
1593:
1592:
1529:
1528:
1508:of the regions.
1488:
1483:
1482:
1454:
1449:
1408:
1389:
1384:
1383:
1358:
1357:
1336:
1335:
1297:
1284:
1279:
1278:
1253:
1252:
1231:
1230:
1192:
1173:
1168:
1167:
1142:
1141:
1118:
1117:
1096:
1091:
1090:
1048:
1032:
1019:
1009:
1008:
984:
965:
952:
947:
946:
924:
923:
898:
897:
894:
853:
834:
829:
828:
803:
802:
761:
748:
743:
742:
717:
716:
675:
656:
651:
650:
618:
613:
612:
580:
564:
551:
546:
545:
513:
494:
483:
482:
457:
438:
425:
420:
419:
386:
381:
380:
343:
324:
311:
306:
305:
302:
247:
246:
224:
223:
198:
197:
174:
173:
154:
153:
128:
127:
106:
105:
23:
22:
15:
12:
11:
5:
7339:
7337:
7329:
7328:
7318:
7317:
7313:
7312:
7302:
7287:
7251:
7214:(4): 709–740.
7191:
7177:
7146:
7101:
7077:
7015:
6981:
6966:
6911:
6896:
6837:
6822:
6787:
6772:
6723:
6716:
6694:
6675:
6658:
6654:
6650:
6630:
6607:
6584:(3): 926–939.
6562:
6518:
6491:
6453:
6426:
6393:
6374:
6355:(1): 284–297.
6329:
6298:
6252:
6229:
6197:
6195:
6192:
6191:
6190:
6183:
6180:
6177:
6176:
6173:
6170:
6167:
6164:
6161:
6158:
6155:
6153:Crumb-and-pack
6149:
6148:
6145:
6142:
6139:
6134:
6131:
6125:
6122:
6116:
6115:
6112:
6100:
6097:
6094:
6091:
6081:
6078:
6075:
6072:
6069:
6066:
6060:
6059:
6056:
6044:
6041:
6038:
6035:
6032:
6029:
6019:
6016:
6013:
6010:
6007:
6004:
5998:
5997:
5994:
5988:
5985:
5982:
5979:
5976:
5973:
5967:
5966:
5963:
5960:
5957:
5954:
5951:
5948:
5945:
5943:Dubins–Spanier
5939:
5938:
5935:
5932:
5929:
5926:
5923:
5920:
5917:
5911:
5910:
5907:
5895:
5892:
5889:
5886:
5883:
5880:
5870:
5867:
5864:
5861:
5858:
5855:
5849:
5848:
5845:
5842:
5835:
5828:
5825:
5822:
5819:
5812:
5809:
5790:
5789:
5786:
5775:
5751:
5748:
5747:
5746:
5705:
5637:
5634:
5613:
5609:
5605:
5563:
5559:
5555:
5543:
5540:
5537:
5536:
5529:
5526:
5514:
5511:
5508:
5505:
5502:
5499:
5488:
5477:
5474:
5471:
5468:
5460:
5457:
5447:
5435:
5424:
5420:
5419:
5416:
5413:
5401:
5398:
5387:
5376:
5373:
5370:
5367:
5359:
5356:
5346:
5334:
5323:
5319:
5318:
5309:
5308:
5305:
5302:
5290:
5279:
5268:
5265:
5262:
5259:
5251:
5248:
5238:
5235:
5231:
5230:
5227:
5224:
5212:
5201:
5190:
5187:
5184:
5181:
5173:
5170:
5160:
5157:
5153:
5152:
5149:
5146:
5134:
5123:
5112:
5109:
5106:
5103:
5095:
5092:
5082:
5079:
5075:
5074:
5065:
5064:
5061:
5058:
5046:
5043:
5040:
5029:
5026:
5014:
5003:
4999:
4998:
4995:
4992:
4980:
4969:
4966:
4954:
4943:
4939:
4938:
4934:
4931:
4928:
4916:
4905:
4902:
4890:
4879:
4875:
4874:
4869:
4866:
4854:
4851:
4840:
4829:
4826:
4823:
4820:
4810:
4798:
4787:
4783:
4782:
4779:
4776:
4764:
4761:
4758:
4747:
4736:
4733:
4730:
4727:
4717:
4705:
4694:
4690:
4689:
4686:
4680:
4668:
4665:
4662:
4640:
4637:
4634:
4631:
4620:
4609:
4606:
4603:
4600:
4592:
4589:
4579:
4567:
4556:
4552:
4551:
4548:
4542:
4530:
4519:
4508:
4505:
4502:
4499:
4491:
4488:
4478:
4466:
4455:
4451:
4450:
4446:
4430:
4425:
4421:
4417:
4414:
4411:
4408:
4398:
4395:
4392:
4390:with 2 blocks
4386:
4374:
4371:
4368:
4346:
4343:
4340:
4336:
4332:
4329:
4318:
4307:
4304:
4301:
4298:
4290:
4287:
4277:
4265:
4254:
4250:
4249:
4240:
4237:
4225:
4222:
4219:
4199:
4196:
4193:
4182:
4171:
4168:
4165:
4162:
4152:
4140:
4129:
4125:
4124:
4121:
4118:
4106:
4095:
4084:
4081:
4078:
4075:
4067:
4064:
4054:
4042:
4031:
4027:
4026:
4023:
4020:
4017:
4011:
4005:
3985:
3984:
3983:
3982:
3970:
3963:
3959:
3955:
3950:
3947:
3920:
3917:
3914:
3910:
3906:
3903:
3900:
3897:
3892:
3888:
3884:
3881:
3878:
3875:
3872:
3869:
3866:
3863:
3860:
3857:
3854:
3830:
3823:
3819:
3813:
3810:
3807:
3804:
3800:
3797:
3794:
3791:
3785:
3782:
3763:
3762:
3761:
3749:
3746:
3743:
3740:
3737:
3734:
3687:
3684:
3681:
3678:
3675:
3672:
3649:
3648:
3634:
3610:
3607:
3604:
3584:
3581:
3578:
3558:
3555:
3552:
3549:
3546:
3543:
3531:
3528:
3527:
3526:
3523:
3513:
3506:
3479:
3478:
3463:
3448:
3426:
3425:
3424:
3423:
3385:
3382:
3379:
3375:
3371:
3368:
3365:
3360:
3356:
3352:
3349:
3346:
3343:
3340:
3316:
3313:
3308:
3304:
3300:
3296:
3292:
3288:
3284:
3281:
3278:
3275:
3272:
3269:
3254:
3242:
3217:, including a
3206:
3205:
3186:
3172:
3153:
3122:
3121:
3118:
3095:
3084:
3068:
3067:
3013:Tucker's lemma
3004:
3001:
2996:
2993:
2972:
2959:
2940:
2936:
2930:
2925:
2921:
2916:
2912:
2908:
2903:
2872:
2871:
2867:
2864:
2861:
2851:
2825:. Finally all
2781:
2780:
2769:
2766:
2762:
2756:
2752:
2748:
2745:
2740:
2736:
2732:
2727:
2723:
2718:
2686:
2666:
2663:
2660:
2651:For any given
2648:
2645:
2643:
2640:
2638:>2 agents.
2620:
2617:
2614:
2611:
2608:
2605:
2566:
2563:
2560:
2557:
2554:
2551:
2548:
2524:
2520:
2516:
2489:
2486:
2472:and there are
2431:=2 agents and
2424:
2421:
2419:
2416:
2389:
2386:
2383:
2361:
2356:
2304:
2301:
2253:
2250:
2247:
2244:
2241:
2238:
2216:
2212:
2191:
2171:
2149:
2145:
2141:
2138:
2118:
2098:
2063:
2062:
2050:
2047:
2044:
2041:
2038:
2035:
2018:Hence, by the
2016:
2004:
2001:
1998:
1995:
1992:
1989:
1986:
1983:
1980:
1977:
1974:
1971:
1952:
1932:
1929:
1926:
1923:
1897:
1892:
1887:
1882:
1878:
1874:
1871:
1860:
1846:
1842:
1830:
1827:
1815:
1812:
1809:
1789:
1753:
1750:
1747:
1744:
1741:
1738:
1735:
1732:
1729:
1709:
1706:
1703:
1668:
1665:
1662:
1659:
1656:
1653:
1650:
1626:
1623:
1606:
1603:
1600:
1542:
1539:
1536:
1525:
1524:
1509:
1495:
1491:
1453:
1450:
1448:
1445:
1444:
1443:
1431:
1427:
1423:
1420:
1415:
1411:
1407:
1404:
1401:
1396:
1392:
1371:
1368:
1365:
1343:
1332:
1320:
1316:
1312:
1309:
1304:
1300:
1296:
1291:
1287:
1266:
1263:
1260:
1238:
1227:
1215:
1211:
1207:
1204:
1199:
1195:
1191:
1188:
1185:
1180:
1176:
1149:
1125:
1103:
1099:
1088:nearly-exactly
1080:
1079:
1068:
1065:
1061:
1055:
1051:
1047:
1044:
1039:
1035:
1031:
1026:
1022:
1017:
991:
987:
983:
980:
977:
972:
968:
964:
959:
955:
945:in the ratios
931:
911:
908:
905:
893:
890:
889:
888:
876:
872:
868:
865:
860:
856:
852:
849:
846:
841:
837:
816:
813:
810:
796:
784:
780:
776:
773:
768:
764:
760:
755:
751:
730:
727:
724:
710:
698:
694:
690:
687:
682:
678:
674:
671:
668:
663:
659:
625:
621:
601:
600:
587:
583:
579:
576:
571:
567:
563:
558:
554:
520:
516:
512:
509:
506:
501:
497:
493:
490:
464:
460:
456:
453:
450:
445:
441:
437:
432:
428:
418:in the ratios
416:exact division
393:
389:
379:is denoted by
350:
346:
342:
339:
336:
331:
327:
323:
318:
314:
301:
298:
285:
284:
276:
268:
254:
231:
205:
181:
161:
141:
138:
135:
113:
102:
92:
67:
32:exact division
30:, also called
24:
18:Exact division
14:
13:
10:
9:
6:
4:
3:
2:
7338:
7327:
7324:
7323:
7321:
7306:
7303:
7298:
7294:
7290:
7284:
7280:
7276:
7271:
7266:
7262:
7255:
7252:
7247:
7243:
7239:
7235:
7231:
7227:
7222:
7217:
7213:
7209:
7205:
7198:
7196:
7192:
7188:
7184:
7180:
7174:
7169:
7164:
7160:
7153:
7151:
7147:
7142:
7138:
7134:
7130:
7125:
7120:
7116:
7112:
7105:
7102:
7096:
7091:
7084:
7082:
7078:
7073:
7069:
7065:
7061:
7057:
7053:
7048:
7043:
7039:
7035:
7031:
7024:
7022:
7020:
7016:
7010:
7005:
6998:
6996:
6994:
6992:
6990:
6988:
6986:
6982:
6977:
6973:
6969:
6963:
6959:
6955:
6951:
6947:
6942:
6937:
6933:
6929:
6922:
6920:
6918:
6916:
6912:
6907:
6903:
6899:
6893:
6889:
6888:1721.1/146185
6885:
6881:
6877:
6872:
6867:
6863:
6859:
6852:
6850:
6848:
6846:
6844:
6842:
6838:
6833:
6829:
6825:
6819:
6815:
6811:
6807:
6806:
6801:
6794:
6792:
6788:
6783:
6779:
6775:
6769:
6765:
6761:
6756:
6751:
6747:
6743:
6736:
6734:
6732:
6730:
6728:
6724:
6719:
6713:
6709:
6705:
6704:Fair Division
6698:
6695:
6690:
6686:
6679:
6676:
6672:
6656:
6652:
6648:
6640:
6634:
6631:
6618:
6611:
6608:
6602:
6597:
6592:
6587:
6583:
6579:
6578:
6573:
6566:
6563:
6558:
6554:
6549:
6544:
6540:
6536:
6532:
6528:
6522:
6519:
6514:
6510:
6506:
6502:
6495:
6492:
6486:
6481:
6477:
6473:
6472:
6464:
6457:
6454:
6449:
6445:
6441:
6437:
6430:
6427:
6421:
6416:
6412:
6408:
6404:
6397:
6394:
6389:
6385:
6378:
6375:
6370:
6366:
6362:
6358:
6354:
6350:
6346:
6342:
6336:
6334:
6330:
6324:
6319:
6315:
6309:
6307:
6305:
6303:
6299:
6294:
6290:
6285:
6280:
6276:
6272:
6265:
6263:
6261:
6259:
6257:
6253:
6248:
6244:
6240:
6236:
6232:
6226:
6222:
6215:
6213:
6211:
6209:
6207:
6205:
6203:
6199:
6193:
6189:
6186:
6185:
6181:
6174:
6171:
6168:
6165:
6162:
6159:
6156:
6154:
6151:
6150:
6146:
6143:
6140:
6135:
6132:
6126:
6123:
6121:
6118:
6117:
6113:
6098:
6095:
6092:
6089:
6082:
6079:
6076:
6073:
6070:
6067:
6065:
6062:
6061:
6057:
6039:
6036:
6033:
6027:
6020:
6017:
6014:
6011:
6008:
6005:
6003:
6000:
5999:
5995:
5989:
5986:
5983:
5980:
5977:
5974:
5972:
5969:
5968:
5964:
5961:
5958:
5955:
5952:
5949:
5946:
5944:
5941:
5940:
5936:
5933:
5930:
5927:
5924:
5921:
5918:
5916:
5913:
5912:
5908:
5890:
5887:
5884:
5878:
5871:
5868:
5865:
5862:
5859:
5856:
5854:
5851:
5850:
5846:
5843:
5836:
5829:
5826:
5823:
5820:
5817:
5816:
5811:Summary table
5810:
5808:
5806:
5801:
5799:
5795:
5787:
5784:
5780:
5776:
5773:
5772:
5771:
5769:
5764:
5760:
5758:
5749:
5745:
5742:
5738:
5734:
5730:
5726:
5722:
5718:
5714:
5710:
5706:
5703:
5699:
5695:
5691:
5687:
5683:
5679:
5675:
5671:
5670:
5669:
5667:
5663:
5659:
5655:
5651:
5647:
5643:
5635:
5633:
5631:
5625:
5611:
5607:
5603:
5595:
5591:
5590:
5585:
5584:
5579:
5578:
5561:
5557:
5553:
5541:
5534:
5530:
5527:
5525:
5512:
5506:
5503:
5500:
5489:
5469:
5455:
5448:
5446:
5433:
5425:
5422:
5421:
5417:
5414:
5412:
5399:
5396:
5388:
5368:
5354:
5347:
5345:
5332:
5324:
5321:
5320:
5317:
5315:
5310:
5306:
5303:
5301:
5288:
5280:
5260:
5246:
5239:
5236:
5233:
5232:
5228:
5225:
5223:
5210:
5202:
5182:
5168:
5161:
5158:
5155:
5154:
5150:
5147:
5145:
5132:
5124:
5104:
5090:
5083:
5080:
5077:
5076:
5073:
5071:
5066:
5062:
5059:
5057:
5044:
5041:
5038:
5030:
5027:
5025:
5012:
5004:
5001:
5000:
4996:
4993:
4991:
4978:
4970:
4967:
4965:
4952:
4944:
4941:
4940:
4932:
4929:
4927:
4914:
4906:
4903:
4901:
4888:
4880:
4877:
4876:
4873:
4870:
4867:
4865:
4852:
4849:
4841:
4824:
4811:
4809:
4796:
4788:
4785:
4784:
4780:
4777:
4775:
4762:
4759:
4756:
4748:
4731:
4718:
4716:
4703:
4695:
4692:
4691:
4687:
4685:
4684:with 1 block
4681:
4679:
4666:
4663:
4660:
4651:
4638:
4635:
4632:
4629:
4621:
4601:
4587:
4580:
4578:
4565:
4557:
4554:
4553:
4549:
4547:
4546:with 1 block
4543:
4541:
4528:
4520:
4500:
4486:
4479:
4477:
4464:
4456:
4453:
4452:
4449:
4443:
4423:
4419:
4409:
4406:
4399:PPA-hard for
4393:
4391:
4387:
4385:
4372:
4369:
4366:
4344:
4341:
4338:
4334:
4330:
4327:
4319:
4299:
4278:
4276:
4263:
4255:
4252:
4251:
4248:
4246:
4241:
4238:
4236:
4223:
4220:
4217:
4197:
4194:
4191:
4183:
4166:
4153:
4151:
4138:
4130:
4127:
4126:
4122:
4119:
4117:
4104:
4096:
4076:
4062:
4055:
4053:
4040:
4032:
4029:
4028:
4024:
4021:
4018:
4016:
4012:
4010:
4006:
4004:
4000:
3999:
3995:
3991:
3961:
3957:
3953:
3945:
3937:
3933:
3932:
3912:
3908:
3904:
3901:
3895:
3890:
3886:
3882:
3879:
3873:
3867:
3864:
3861:
3855:
3852:
3844:
3821:
3817:
3808:
3805:
3798:
3795:
3792:
3789:
3780:
3772:
3768:
3764:
3747:
3741:
3738:
3735:
3724:
3720:
3716:
3712:
3708:
3704:
3703:
3701:
3685:
3679:
3676:
3673:
3662:
3658:
3657:
3656:
3654:
3647:
3643:
3639:
3635:
3632:
3628:
3624:
3623:
3622:
3608:
3605:
3602:
3582:
3579:
3576:
3556:
3550:
3547:
3544:
3529:
3524:
3521:
3520:almost surely
3517:
3514:
3511:
3507:
3504:
3500:
3496:
3492:
3488:
3484:
3483:
3482:
3476:
3472:
3468:
3464:
3461:
3457:
3453:
3449:
3447:
3444:
3440:
3436:
3432:
3428:
3427:
3422:
3418:
3414:
3410:
3406:
3402:
3401:
3399:
3377:
3373:
3369:
3363:
3358:
3354:
3350:
3347:
3341:
3338:
3330:
3306:
3302:
3294:
3286:
3282:
3279:
3276:
3267:
3259:
3255:
3240:
3232:
3228:
3227:
3226:
3224:
3220:
3216:
3211:
3203:
3199:
3195:
3191:
3187:
3185:
3181:
3177:
3173:
3170:
3166:
3162:
3159:agents using
3158:
3154:
3151:
3150:
3149:
3147:
3144:-approximate
3143:
3139:
3135:
3131:
3127:
3119:
3116:
3112:
3108:
3104:
3100:
3096:
3093:
3089:
3085:
3082:
3078:
3074:
3070:
3069:
3065:
3061:
3057:
3053:
3052:
3051:
3049:
3045:
3041:
3037:
3033:
3029:
3024:
3022:
3018:
3014:
3010:
3002:
3000:
2994:
2992:
2989:
2987:
2983:
2978:
2975:
2971:
2967:
2962:
2958:
2954:
2938:
2934:
2928:
2923:
2910:
2892:
2887:
2885:
2881:
2877:
2868:
2865:
2862:
2859:
2858:
2857:
2854:
2850:
2846:
2842:
2838:
2834:
2832:
2828:
2824:
2820:
2816:
2812:
2808:
2804:
2800:
2796:
2795:Crumbing step
2792:
2790:
2786:
2767:
2764:
2754:
2750:
2746:
2738:
2734:
2725:
2721:
2708:
2707:
2706:
2704:
2700:
2684:
2664:
2661:
2658:
2646:
2641:
2639:
2637:
2632:
2615:
2612:
2609:
2603:
2595:
2591:
2586:
2584:
2580:
2561:
2558:
2555:
2549:
2546:
2536:
2522:
2518:
2514:
2505:
2503:
2497:
2495:
2487:
2485:
2483:
2478:
2475:
2471:
2466:
2462:
2460:
2456:
2452:
2448:
2444:
2440:
2436:
2434:
2430:
2422:
2417:
2415:
2412:
2409:
2405:
2403:
2387:
2384:
2381:
2359:
2343:
2341:
2338:-dimensional
2335:
2329:
2325:
2318:"objects" in
2317:
2310:
2302:
2300:
2298:
2294:
2290:
2286:
2282:
2278:
2274:
2270:
2265:
2251:
2245:
2242:
2239:
2214:
2210:
2202:, is exactly
2189:
2169:
2147:
2143:
2139:
2136:
2116:
2096:
2088:
2084:
2080:
2076:
2074:
2067:
2048:
2045:
2039:
2033:
2021:
2017:
2002:
1999:
1993:
1990:
1984:
1981:
1975:
1969:
1954:The function
1953:
1927:
1921:
1895:
1880:
1876:
1872:
1869:
1861:
1844:
1840:
1831:
1828:
1813:
1810:
1807:
1787:
1779:
1778:
1777:
1775:
1771:
1767:
1751:
1748:
1742:
1739:
1736:
1730:
1727:
1707:
1704:
1701:
1693:
1688:
1686:
1682:
1663:
1660:
1657:
1651:
1648:
1640:
1636:
1632:
1624:
1622:
1620:
1598:
1589:
1584:
1582:
1578:
1574:
1570:
1567:
1562:
1560:
1556:
1540:
1537:
1534:
1522:
1518:
1514:
1510:
1493:
1489:
1480:
1476:
1472:
1471:
1470:
1468:
1463:
1459:
1451:
1446:
1429:
1425:
1421:
1418:
1413:
1409:
1405:
1402:
1399:
1394:
1390:
1369:
1366:
1363:
1355:
1341:
1333:
1318:
1314:
1310:
1307:
1302:
1298:
1294:
1289:
1285:
1264:
1261:
1258:
1250:
1236:
1228:
1213:
1209:
1205:
1202:
1197:
1193:
1189:
1186:
1183:
1178:
1174:
1165:
1163:
1160:-consensus 1/
1147:
1139:
1138:
1137:
1123:
1101:
1097:
1089:
1085:
1066:
1063:
1053:
1049:
1045:
1037:
1033:
1024:
1020:
1007:
1006:
1005:
989:
985:
981:
978:
975:
970:
966:
962:
957:
953:
944:
929:
909:
906:
903:
891:
874:
870:
866:
863:
858:
854:
850:
847:
844:
839:
835:
814:
811:
808:
800:
797:
782:
778:
774:
771:
766:
762:
758:
753:
749:
728:
725:
722:
714:
711:
696:
692:
688:
685:
680:
676:
672:
669:
666:
661:
657:
648:
646:
641:
640:
639:
623:
619:
610:
606:
585:
581:
577:
569:
565:
556:
552:
544:
543:
542:
540:
536:
518:
514:
510:
507:
504:
499:
495:
491:
488:
480:
462:
458:
454:
451:
448:
443:
439:
435:
430:
426:
417:
413:
409:
391:
387:
378:
374:
370:
366:
348:
344:
340:
337:
334:
329:
325:
321:
316:
312:
299:
297:
294:
290:
282:
281:
277:
274:
273:
269:
267:
252:
244:
229:
221:
219:
216:-consensus 1/
203:
194:
179:
159:
139:
136:
133:
125:
111:
103:
100:
96:
93:
90:
86:
83:
79:
75:
73:
68:
65:
61:
58:
57:
56:
54:
50:
45:
41:
38:") into some
37:
33:
29:
19:
7326:Cake-cutting
7305:
7260:
7254:
7211:
7207:
7158:
7114:
7110:
7104:
7037:
7033:
6931:
6861:
6804:
6745:
6707:
6703:
6697:
6688:
6684:
6678:
6638:
6633:
6621:. Retrieved
6610:
6591:math/0610800
6581:
6575:
6565:
6538:
6534:
6521:
6504:
6500:
6494:
6475:
6469:
6456:
6439:
6435:
6429:
6410:
6406:
6396:
6387:
6383:
6377:
6352:
6348:
6341:Chen, Yiling
6274:
6270:
6220:
6144:1 half-plane
6130:-dimensional
5802:
5797:
5793:
5791:
5782:
5778:
5767:
5765:
5761:
5753:
5744:
5740:
5736:
5732:
5728:
5724:
5720:
5716:
5712:
5708:
5701:
5697:
5696:agents with
5693:
5689:
5685:
5681:
5677:
5673:
5661:
5657:
5653:
5649:
5645:
5641:
5639:
5626:
5587:
5581:
5577:proportional
5575:
5545:
5532:
5490:
5426:
5423:prime power
5389:
5325:
5313:
5312:
5281:
5203:
5125:
5069:
5068:
5031:
5005:
4971:
4945:
4907:
4881:
4871:
4842:
4789:
4749:
4696:
4688:Polynomial.
4683:
4653:
4622:
4558:
4545:
4521:
4457:
4445:
4442:
4389:
4320:
4256:
4244:
4243:
4184:
4131:
4097:
4033:
4014:
4008:
4002:
3993:
3989:
3935:
3770:
3766:
3722:
3718:
3714:
3710:
3706:
3698:cuts, in an
3660:
3650:
3645:
3641:
3637:
3630:
3626:
3533:
3515:
3509:
3502:
3498:
3494:
3490:
3480:
3470:
3459:
3455:
3451:
3446:
3438:
3434:
3430:
3420:
3416:
3412:
3408:
3404:
3257:
3230:
3222:
3218:
3209:
3207:
3197:
3193:
3189:
3183:
3179:
3175:
3168:
3164:
3160:
3156:
3141:
3133:
3129:
3125:
3123:
3114:
3110:
3106:
3102:
3091:
3087:
3080:
3076:
3072:
3059:
3054:Agents have
3043:
3039:
3035:
3034:(that is, 1/
3031:
3027:
3025:
3008:
3006:
2998:
2990:
2979:
2973:
2969:
2965:
2960:
2956:
2952:
2890:
2888:
2883:
2879:
2875:
2873:
2852:
2848:
2844:
2840:
2837:Packing step
2836:
2835:
2830:
2826:
2822:
2818:
2814:
2810:
2806:
2802:
2798:
2794:
2793:
2788:
2784:
2782:
2702:
2698:
2650:
2635:
2633:
2593:
2589:
2587:
2582:
2578:
2537:
2506:
2498:
2491:
2481:
2479:
2473:
2469:
2467:
2463:
2458:
2454:
2451:exact subset
2450:
2446:
2442:
2438:
2437:
2432:
2428:
2426:
2413:
2410:
2406:
2401:
2344:
2333:
2306:
2296:
2292:
2284:
2280:
2272:
2268:
2266:
2078:
2072:
2071:consensus 1/
2070:
2068:
2064:
1951:, minus 1/2.
1765:
1691:
1689:
1684:
1680:
1638:
1634:
1630:
1628:
1618:
1585:
1581:Jerzy Neyman
1576:
1563:
1554:
1526:
1520:
1516:
1512:
1478:
1474:
1466:
1461:
1455:
1334:
1229:
1161:
1140:
1087:
1083:
1081:
942:
895:
798:
712:
644:
643:Consensus 1/
642:
608:
604:
602:
538:
534:
478:
415:
411:
376:
372:
368:
364:
303:
292:
288:
286:
278:
270:
265:
242:
217:
196:
192:
104:
98:
94:
88:
85:
81:
77:
71:
70:Consensus 1/
69:
63:
59:
52:
48:
43:
39:
31:
27:
26:
6527:B. Grünbaum
6507:: 241–248.
6413:: 233–247.
6120:Stone–Tukey
5925:Con+Add+Pwl
5830:#partners (
5719:agents and
5418:PPAD-hard.
4997:FIXP-hard.
4937:-complete.
4396:(PPAD-hard;
4242:PPAD-hard;
4022:Valuations
4013:Accuracy 1/
3845:, or using
3841:cuts in an
3640:=3, when 1/
3396:cuts in an
3331:, or using
3327:cuts in an
2324:dimensional
611:is exactly
300:Definitions
7221:1510.03903
7124:2007.06754
7095:2103.04452
7047:1903.03101
7009:1609.05136
6941:2007.15125
6871:2002.11437
6755:1711.04503
6691:: 205–219.
6478:(4): 623.
6442:: 93–106.
6390:: 843–845.
6323:2006.16613
6314:Alon, Noga
6194:References
6133:Con(+Add?)
6012:Con(+Add?)
5837:#subsets (
5827:Valuations
5803:See also:
5707:For every
5672:For every
5644:there are
4394:PPA-hard.
3073:polynomial
2882:and 1/2+1/
2701:and every
2340:hyperplane
2316:measurable
2229:. At most
2077:case: any
2026:such that
1571:. This is
1511:Let piece
896:For every
287:When both
7270:1003.5480
7238:1432-217X
7187:214667000
7141:246764981
7072:228908526
7064:0022-0000
7040:: 75–98.
6976:220871193
6906:211505917
6619:. Math.SE
6279:CiteSeerX
6277:: 15–25.
6172:Unbounded
6096:−
6055:(optimal)
6037:−
5993:(optimal)
5962:Unbounded
5906:(optimal)
5888:−
5589:equitable
5583:envy-free
5504:−
5226:monotone
5148:monotone
5042:−
4819:Ω
4760:−
4726:Ω
4664:≥
4636:−
4413:Ω
4410:∈
4407:ε
4342:−
4286:Ω
4221:≥
4161:Ω
4007:# agents
3958:ε
3919:⌉
3913:ϵ
3896:
3877:⌈
3874:⋅
3865:−
3856:⋅
3818:ε
3799:
3739:−
3725:), using
3677:−
3606:≥
3580:≥
3569:cuts for
3548:−
3518:cuts are
3384:⌉
3378:ϵ
3364:
3345:⌈
3342:⋅
3303:ε
3283:
3138:PPAD-hard
2924:≤
2768:ε
2747:−
2685:ε
2659:ε
2613:−
2550:∈
2385:−
2273:arbitrary
2243:−
2140:⋅
2083:Noga Alon
2075:-division
1991:−
1886:→
1740:−
1731:⋅
1661:−
1652:⋅
1605:∞
1602:→
1588:countable
1538:⋅
1447:Existence
1403:⋯
1342:ε
1237:ε
1187:⋯
1148:ε
1124:ε
1067:ε
1046:−
979:…
930:ε
904:ε
848:⋯
670:⋯
511:⊔
508:⋯
505:⊔
452:…
338:…
253:ε
230:ε
220:-division
204:ε
180:ε
160:ε
134:ε
112:ε
74:-division
7320:Category
7310:general.
7297:11732339
6832:44085263
6529:(1960).
6247:2730675W
6239:97041258
6182:See also
6009:Interval
5978:Interval
5860:Interval
5847:weights
5304:general
4123:In PPA.
4001:#pieces
3773:, using
3663:, using
3629:for any
3260:, using
3233:, using
3048:PPA-hard
2847:is near
2785:crumbing
2477:pieces.
2299:) cuts.
1553:, where
1523:regions.
1164:division
647:division
481:pieces:
7246:1602396
6782:8111195
6623:23 June
6557:0124818
6369:2096977
6163:Con+Add
6074:Con+Add
5953:Con+Add
5531:In PPA-
4025:Status
4019:# cuts
3996:agents
3419:+O(log(
2789:packing
2328:measure
2271:=2 and
7295:
7285:
7244:
7236:
7185:
7175:
7139:
7070:
7062:
6974:
6964:
6904:
6894:
6830:
6820:
6780:
6770:
6714:
6555:
6367:
6281:
6245:
6237:
6227:
6147:Equal
6071:Circle
6058:Equal
5996:Equal
5853:Austin
5743:>2.
5316:>2:
5072:fixed:
3938:=2 is
3931:cuts.
3064:binary
2402:single
1694:case:
1685:always
1619:finite
1467:amount
7293:S2CID
7265:arXiv
7242:S2CID
7216:arXiv
7183:S2CID
7137:S2CID
7119:arXiv
7090:arXiv
7068:S2CID
7042:arXiv
7004:arXiv
6972:S2CID
6936:arXiv
6902:S2CID
6866:arXiv
6828:S2CID
6778:S2CID
6750:arXiv
6706:[
6586:arXiv
6466:(PDF)
6365:S2CID
6318:arXiv
5844:#cuts
4872:Open.
3760:cuts.
3452:exact
3429:When
3253:cuts.
3208:When
3174:When
2439:Proof
2404:cut.
2129:, is
922:, An
414:. An
7283:ISBN
7234:ISSN
7173:ISBN
7060:ISSN
6962:ISBN
6892:ISBN
6818:ISBN
6768:ISBN
6712:ISBN
6625:2015
6235:LCCN
6225:ISBN
6175:Any
6169:Many
6166:Many
6114:Any
6077:Many
6018:Many
6015:Many
5984:Many
5965:Any
5959:Many
5956:Many
5937:Any
5931:Many
5928:Many
5909:Any
5869:Many
5824:Cake
5821:Type
5818:Name
5731:-1)(
5711:and
5676:and
5586:and
5463:poly
5362:poly
5254:poly
5176:poly
5098:poly
4595:poly
4494:poly
4370:>
4293:poly
4245:Open
4070:poly
3505:cuts
3475:FIXP
3421:ε)).
3219:mark
3202:3SAT
2787:and
2765:<
2662:>
2500:the
2336:− 1)
2307:The
1382:and
1277:and
1064:<
907:>
827:and
741:and
304:Let
291:and
245:and
137:>
36:cake
7275:doi
7226:doi
7163:doi
7129:doi
7052:doi
7038:117
6954:hdl
6946:doi
6884:hdl
6876:doi
6810:doi
6760:doi
6596:doi
6582:218
6543:doi
6509:doi
6505:108
6480:doi
6444:doi
6415:doi
6388:222
6357:doi
6289:doi
6160:Any
5981:Con
5950:Any
5863:Con
5028:∞
4968:∞
3887:log
3796:log
3501:-1)
3355:log
3280:log
3075:in
3021:PPA
3007:An
2297:n k
2277:pie
1561:.
1086:is
410:on
363:be
222:or
7322::
7291:.
7281:.
7273:.
7240:.
7232:.
7224:.
7212:53
7210:.
7206:.
7194:^
7181:,
7171:,
7149:^
7135:.
7127:.
7115:47
7113:.
7080:^
7066:.
7058:.
7050:.
7036:.
7032:.
7018:^
6984:^
6970:.
6960:.
6952:.
6944:.
6930:.
6914:^
6900:.
6890:.
6882:.
6874:.
6860:.
6840:^
6826:.
6816:.
6802:.
6790:^
6776:.
6766:.
6758:.
6744:.
6726:^
6687:.
6594:.
6580:.
6574:.
6553:MR
6551:.
6539:10
6537:.
6533:.
6503:.
6476:98
6474:.
6468:.
6438:.
6411:78
6409:.
6405:.
6386:.
6363:.
6353:77
6351:.
6347:.
6332:^
6301:^
6287:.
6275:45
6273:.
6255:^
6243:OL
6241:.
6233:.
6201:^
5807:.
5632:.
5624:.
5580:,
5535:.
5322:3
5237:2
5234:2
5159:3
5156:2
5081:2
5078:2
5002:2
4942:2
4904:?
4878:2
4786:2
4693:2
4652:,
4555:2
4454:2
4359:,
4253:2
4210:,
4128:2
4030:2
3769:±
3707:kn
3702:.
3661:kn
3655::
3646:n.
3469:,
3437:,
3400:.
3231:2n
3171:).
3115:d)
3083:).
2988:.
2893::
2886:.
2833:.
2791:.
2705::
2631:.
2496:.
2342:.
1962:,
1914:,
1776::
541::
195:,
7299:.
7277::
7267::
7248:.
7228::
7218::
7165::
7143:.
7131::
7121::
7098:.
7092::
7074:.
7054::
7044::
7012:.
7006::
6978:.
6956::
6948::
6938::
6908:.
6886::
6878::
6868::
6834:.
6812::
6784:.
6762::
6752::
6720:.
6689:8
6673:.
6657:n
6653:/
6649:1
6639:n
6627:.
6604:.
6598::
6588::
6559:.
6545::
6515:.
6511::
6488:.
6482::
6450:.
6446::
6440:6
6423:.
6417::
6371:.
6359::
6326:.
6320::
6295:.
6291::
6249:.
6141:2
6137:n
6128:n
6099:2
6093:n
6090:2
6080:2
6043:)
6040:1
6034:k
6031:(
6028:n
5991:n
5987:2
5894:)
5891:1
5885:k
5882:(
5879:2
5866:2
5841:)
5839:k
5834:)
5832:n
5798:n
5794:n
5783:n
5779:n
5768:n
5741:k
5737:k
5733:k
5729:n
5725:k
5721:k
5717:n
5713:k
5709:n
5702:n
5698:k
5694:n
5690:k
5686:k
5684:(
5682:n
5678:k
5674:n
5662:k
5654:k
5650:k
5646:n
5642:,
5612:n
5608:/
5604:1
5562:n
5558:/
5554:1
5533:k
5513:n
5510:)
5507:1
5501:k
5498:(
5476:)
5473:)
5470:n
5467:(
5459:(
5456:O
5434:n
5400:n
5397:2
5375:)
5372:)
5369:n
5366:(
5358:(
5355:O
5333:n
5314:k
5289:n
5267:)
5264:)
5261:n
5258:(
5250:(
5247:O
5211:n
5189:)
5186:)
5183:n
5180:(
5172:(
5169:O
5133:n
5111:)
5108:)
5105:n
5102:(
5094:(
5091:O
5070:n
5045:1
5039:n
5013:n
4979:n
4953:n
4935:a
4915:n
4889:n
4853:n
4850:2
4828:)
4825:1
4822:(
4797:n
4763:1
4757:n
4735:)
4732:1
4729:(
4704:n
4667:0
4661:d
4639:d
4633:n
4630:2
4608:)
4605:)
4602:n
4599:(
4591:(
4588:O
4566:n
4529:n
4507:)
4504:)
4501:n
4498:(
4490:(
4487:O
4465:n
4441:;
4429:)
4424:n
4420:2
4416:(
4373:0
4367:d
4345:d
4339:1
4335:n
4331:+
4328:n
4306:)
4303:)
4300:n
4297:(
4289:(
4264:n
4224:0
4218:d
4198:d
4195:+
4192:n
4170:)
4167:1
4164:(
4139:n
4105:n
4083:)
4080:)
4077:n
4074:(
4066:(
4063:O
4041:n
4015:ε
4009:n
4003:k
3994:n
3990:ε
3969:)
3962:2
3954:n
3949:(
3946:O
3936:k
3916:)
3909:/
3905:k
3902:3
3899:(
3891:2
3883:+
3880:2
3871:)
3868:1
3862:k
3859:(
3853:n
3829:)
3822:2
3812:)
3809:n
3806:k
3803:(
3793:n
3790:k
3784:(
3781:O
3771:ε
3767:k
3748:n
3745:)
3742:1
3736:k
3733:(
3723:n
3719:k
3715:k
3713:(
3711:c
3686:n
3683:)
3680:1
3674:k
3671:(
3642:ε
3638:k
3633:.
3631:k
3627:k
3609:2
3603:k
3583:3
3577:k
3557:n
3554:)
3551:1
3545:k
3542:(
3516:n
3510:n
3503:n
3499:k
3495:k
3491:n
3471:ε
3460:n
3456:n
3439:ε
3435:n
3431:ε
3417:n
3413:d
3409:d
3407:+
3405:n
3381:)
3374:/
3370:1
3367:(
3359:2
3351:+
3348:2
3339:n
3315:)
3312:)
3307:2
3299:(
3295:/
3291:)
3287:n
3277:n
3274:(
3271:(
3268:O
3258:ε
3241:n
3223:n
3210:ε
3204:.
3198:ε
3194:n
3190:ε
3184:.
3180:ε
3176:ε
3169:d
3165:d
3163:+
3161:n
3157:n
3142:ε
3134:ε
3130:n
3126:ε
3117:.
3111:d
3109:-
3107:n
3103:n
3094:.
3092:n
3088:ε
3081:n
3077:n
3066:.
3060:ε
3044:ε
3040:n
3036:ε
3032:n
3028:ε
3009:ε
2974:j
2970:w
2966:j
2961:j
2957:w
2953:j
2939:k
2935:/
2929:n
2920:|
2915:|
2911:v
2907:|
2902:|
2891:v
2884:k
2880:k
2876:k
2853:j
2849:w
2845:j
2841:n
2831:k
2827:n
2823:n
2819:k
2815:k
2811:k
2807:k
2803:k
2799:k
2761:|
2755:j
2751:w
2744:)
2739:j
2735:X
2731:(
2726:i
2722:V
2717:|
2703:j
2699:i
2665:0
2636:n
2619:)
2616:1
2610:k
2607:(
2604:2
2594:k
2590:n
2583:p
2579:p
2565:]
2562:1
2559:,
2556:0
2553:[
2547:p
2523:n
2519:/
2515:1
2482:k
2474:k
2470:k
2459:k
2455:k
2447:k
2443:k
2433:k
2429:n
2388:1
2382:n
2360:n
2355:R
2334:n
2332:(
2322:-
2320:n
2313:n
2293:k
2285:n
2281:n
2269:k
2252:n
2249:)
2246:1
2240:k
2237:(
2215:i
2211:a
2190:i
2170:k
2148:i
2144:a
2137:k
2117:i
2097:n
2079:k
2073:k
2049:0
2046:=
2043:)
2040:x
2037:(
2034:V
2024:x
2015:.
2003:0
2000:=
1997:)
1994:x
1988:(
1985:V
1982:+
1979:)
1976:x
1973:(
1970:V
1960:x
1956:V
1949:i
1945:i
1931:)
1928:x
1925:(
1922:V
1912:x
1896:n
1891:R
1881:n
1877:S
1873::
1870:V
1859:.
1845:n
1841:S
1814:1
1811:+
1808:n
1788:n
1766:n
1752:n
1749:=
1746:)
1743:1
1737:k
1734:(
1728:n
1708:2
1705:=
1702:k
1681:k
1667:)
1664:1
1658:k
1655:(
1649:n
1639:k
1635:n
1631:n
1599:R
1577:k
1555:R
1541:R
1535:k
1521:R
1517:j
1513:j
1494:j
1490:w
1479:j
1475:k
1462:R
1442:.
1430:n
1426:/
1422:1
1419:=
1414:n
1410:w
1406:=
1400:=
1395:1
1391:w
1370:n
1367:=
1364:k
1331:.
1319:2
1315:/
1311:1
1308:=
1303:2
1299:w
1295:=
1290:1
1286:w
1265:2
1262:=
1259:k
1226:.
1214:k
1210:/
1206:1
1203:=
1198:n
1194:w
1190:=
1184:=
1179:1
1175:w
1162:k
1102:j
1098:w
1084:j
1060:|
1054:j
1050:w
1043:)
1038:j
1034:X
1030:(
1025:i
1021:V
1016:|
990:k
986:w
982:,
976:,
971:2
967:w
963:,
958:1
954:w
910:0
887:.
875:n
871:/
867:1
864:=
859:n
855:w
851:=
845:=
840:1
836:w
815:n
812:=
809:k
795:.
783:2
779:/
775:1
772:=
767:2
763:w
759:=
754:1
750:w
729:2
726:=
723:k
709:.
697:k
693:/
689:1
686:=
681:n
677:w
673:=
667:=
662:1
658:w
645:k
624:j
620:w
609:j
586:j
582:w
578:=
575:)
570:j
566:X
562:(
557:i
553:V
539:j
535:i
519:k
515:X
500:1
496:X
492:=
489:C
479:k
463:k
459:w
455:,
449:,
444:2
440:w
436:,
431:1
427:w
412:C
392:i
388:V
377:i
373:C
369:n
365:k
349:k
345:w
341:,
335:,
330:2
326:w
322:,
317:1
313:w
293:k
289:n
218:k
140:0
99:n
91:.
82:k
78:k
72:k
64:k
53:n
49:k
44:n
40:k
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.