Thou Shalt Covet Thy Neighbor's Cake

1 Introduction

Imagine a cake topped with vanilla icings, chocolate chip cookie crumbs, toasted almonds, and strawberries. The cake must be divided between several hungry children. Alas, one of the children prefers the cookie crumbs, another is allergic to strawberries, and a third loudly insists on receiving the largest piece. How can the cake be divided fairly among the children?

Cake-cutting is often used as a metaphor for the division of a heterogeneous, divisible good among multiple agents that have different values for parts of the cake. A common example is dividing an inheritance among several inheritors, when the inheritance is not limited to money (which everyone values equally), but rather includes items that are of sentimental value to some of the inheritors. In the world of multiagent systems, it is possible to consider the allocation of processing time to agents, in a setting where the agents prefer specific time slots (e.g., early time slots or daytime slots). Generally speaking, fair cake-cutting is an important part of the field of fair division, which has many applications in multiagent resource allocation (MARA; see the survey by Chevaleyre et al. [2006]).

In mathematical terms, the cake is represented by the interval [0, 1], and the agents have well-behaved valuation functions on this interval. The problem is to find a partition of [0, 1] among the agents that is fair. Naturally, different fairness criteria can be, and have been, proposed. One example is proportionality: each of the n agents must receive at least 1/n of the cake according to its valuation function. Another example is envy-freeness: the value of an agent for its own piece of cake must be at least as great as its value for the piece of cake allocated to any other agent.

As is well-known to any person who grew up with one younger sibling, a fair algorithm for dividing a cake among two agents is the "cut-and-choose" algorithm, whereby one agent divides the cake into two equal pieces, according to its valuation, and the other chooses a (weakly) preferred piece. It is easy to see that this algorithm is both proportional and envy-free. In fact, it can be verified that, when there are exactly two agents, proportionality and envy-freeness are equivalent. For more agents proportionality is implied by envyfreeness, but not vice-versa.

Steinhaus [1948] observed that the cut-and-choose algorithm can be extended to a three-agent proportional cakecutting algorithm, which requires at most three cuts. A natural question was whether the simple cut-and-choose idea could be further extended to n agents for n > 3. This was answered in the affirmative by Banach and Knaster (as was also reported by Steinhaus); the algorithm they suggested might require Ω(n2 ) cuts. Some four decades later, Even and Paz [1984] presented a divide-and-conquer approach that yields a proportional solution with O(n log n) cuts.

A lower bound for proportional cake-cutting would have to wait for another two decades. While upper bounds are usually presented in a rather informal manner, a lower bound requires a precise definition of the operations that may be performed by the cake-cutting algorithm. A very appealing model was advocated by Robertson and Webb [1998]. Their model allows two types of queries: an evaluation query, by which the algorithm obtains information about the valuation of a given agent for a given subinterval; and a cut query, that asks a given agent to cut a piece of cake worth a given value. Roughly speaking, this model is powerful enough to capture all the existing discrete cake-cutting algorithms. While early work implicitly considered cuts to be more costly than evaluations, this does not seem to be a reasonable assumption, and indeed the two types of queries are given equal weight in the Robertson-Webb model. So, the Even-Paz algorithm can simply be seen as using O(n log n) queries.

An Ω(n log n) lower bound (in the Robertson-Web model) for proportional cake-cutting was established by Woeginger and Sgall [2007], by a reduction from sorting. However, their lower bound held only against algorithms that allocate a contiguous (that is, connected) piece to each agent. This assumption imposes a serious restriction; ultimately, Edmonds and Pruhs [2006] were recently able to prove a satisfying Ω(n logn) lower bound without any assumptions. Hence, proportional cake-cutting is, to all ends and purposes, completely understood.

Envy-free division, in stark contrast, is nothing if not enigmatic. The existence of envy-free allocations, even those that satisfy additional desiderata such as allocation of contiguous pieces, has been known since the 1940's (see, e.g., [Stromquist, 1980]). The first constructive solution to the envy-free cake-cutting problem, for exactly three players, was suggested around 1960 by Selfridge, and, independently, by Conway; the Selfridge-Conway algorithm requires at most five cut queries and a small number of evaluation queries, and is described in full in Section 2.

Despite numerous moving-knife schemes for envy-free cake-cutting that were suggested in the decades that followed the breakthrough of Selfridge and Conway (see, e.g., the work of Stromquist [1980]), a discrete algorithm that extends Selfridge-Conway for any number of agents was only devised in the 1990's by Brams and Taylor [1995]. Unfortunately, a curious property of the Brams-Taylor algorithm is that, even for four agents, the number of steps can be made arbitrarily large with a suitable choice of the agents' valuation functions. In fact, to this day there is no envy-free discrete cake-cutting algorithm that requires a bounded number of queries when n > 3. 1

Our result. In light of the discussion in the preceding paragraphs, the following question naturally arises: is it possible to prove a lower bound for envy-free cake-cutting? Since envy-freeness implies proportionality, the Ω(n logn) lower bound of Edmonds and Pruhs [2006] for proportional division also holds for envy-free division. In this paper, we seek to improve this lower bound.

The following theorem is our main result.

Theorem 3.1. The query complexity (in the Robertson-Webb model) of achieving an envy-free allocation is Ω(n2 ).

1 There is a moving knife solution to the four agent envy-free cake-cutting problem with a bounded number of cuts [Brams et al., 1997], but there is no bounded solution for n > 4 even if moving knives are allowed.

Notice that our result does not require any restrictions on the cake-cutting algorithm, apart from the implicit assumption that it is captured by the Robertson-Webb query model.

Since the algorithm of Even and Paz [1984] gives an O(n logn) upper bound for proportional division, our result establishes, for the first time, a gap between the complexity of proportional and envy-free division. This gap can be seen as providing a partial explanation for the difficulty of the envyfree cake-cutting problem with multiple agents. As with any lower bound, it can also be used to direct the search for upper bounds, that is, envy-free algorithms that require a bounded number of steps.

Related work. A very recent result that complements ours nicely was reported by Stromquist [2008]. Stromquist showed that any algorithm that requires a finite number of steps and allocates contiguous pieces of cake cannot be envyfree, for any number of agents n ≥ 3. Stromquist's assumptions on the allowed queries essentially reduce to the Robertson-Webb model. It is important to note that while existing envy-free algorithms require an unbounded number of queries, they are finite, i.e., they are guaranteed to terminate after a finite number of steps. Indeed, Stromquist's result does not hold with respect to the existing algorithms as they do not allocate contiguous pieces. Furthermore, for n = 3 there actually is an envy-free algorithm, namely SelfridgeConway, that does not allocate contiguous pieces and requires a bounded number of steps! Hence, the restriction to contiguous pieces is interesting but clearly very strong, and leaves plenty of room for the investigation of assumption-free lower bounds.

Busch et al. [2005] proved lower bounds of Ω(n2 ) for the number of cuts needed to achieve two stronger variations of envy-freeness: strong envy-freeness, namely each agent strictly prefers its own pieces to any other piece; and super envy-freeness, that is, each agent believes that every piece except its own is worth at most 1/n of the cake. These two stronger versions of envy-freeness are fundamentally different from regular envy-freeness, mainly since there does not necessarily exist an allocation that satisfies them for given valuation functions, and even when there is one, it might not be possible to allocate contiguous pieces. This facilitates quite straightforward proofs by constructing valuations that require allocating multiple disjoint intervals to each player in order to achieve strong or super envy-freeness. Our result implies, and is a significant improvement of, these lower bounds.

Short discussion. Our proof is based on defining a difficult problem that must be solved independently for many of the agents. This separation between the different agents allows for a mathematically clean Ω(n2 ) lower bound, but seems to hinder any attempts to raise the bound above n2 . Nevertheless, we believe it likely that the actual bound is higher, and that it might be possible to establish this by considering allocations to several agents simultaneously. Indeed, given an allocation of a piece to one agent, it is possible to set the valuation function of a different agent in a way that the latter envies the former. If one is careful not to over-constrain the valuations of the agents, this proof stub can possibly be built upon to yield an improved lower bound.

2 Preliminaries

We deal with a set of agents N = {1, . . . , n}. Each agent i ∈ N has a valuation function vi, that maps subintervals of [0, 1] to the value agent i assigns them. We simplify the notation by writing vi(x1, x2) instead of vi([x1, x2]) to denote the value of agent i for the interval [x1, x2]. We assume that for all i ∈ N, vi satisfies the following properties:

1. vi(0, 1) = 1.
2. Additivity: for every two disjoint subintervals I1 and I2, .

1. Divisibility: For every subinterval I ⊆ [0, 1] and 0 ≤ λ ≤ 1 there is I ′ ⊆ I such that vi(I ′ ) = λvi(I ).
2. For every subinterval I ⊆ [0, 1], vi(I ) ≥ 0.

It follows from the divisibility property that the functions v1, . . . , vn are nonatomic, i.e., for every x ∈ [0, 1], vi(x, x) = 0. Therefore, open and closed intervals have the same value, which allows us to disregard the boundaries of intervals. In particular, when we say "disjoint intervals" or write I1 ∩ I2 = ∅, this should be taken to mean that the interiors of the intervals do not intersect.

A piece of cake X is a finite union of disjoint intervals, X = ⋃k∈K Ik. By the additivity property, the value agent i ∈ N assigns to X is simply the sum of values of the subintervals, that is,

We deal with algorithms that assign a piece of cake Xi to each agent i ∈ N, such that X1, . . . ,Xn is a partition of [0, 1]. In this paper, the goal of the algorithm is to find an envy-free allocation: for all i, j ∈ N, vi(Xi) ≥ vi(Xj). Initially, the algorithm has no information about the valuations of the agents; it obtains this information using queries.

Before describing the query model that we deal with, it will prove instructive to first discuss a possibility result: the envy-free cake-cutting algorithm for n = 3 of Selfridge and Conway, circa 1960 (see the paper by Brams and Taylor [1995] for an excellent, full exposition of this algorithm and other prominent cake-cutting algorithms).

Stage 0.

1. Agent 1 divides the cake into three equal pieces according to v1.
2. Agent 2 trims the largest piece (that is, cuts off a slice) such that there is a tie between the two largest pieces according to v2. We call the original cake without the trimmings Cake 1, and we call the trimmings Cake 2.

Stage 1 (Division of Cake 1).

1. Agent 3 chooses one of the three pieces of Cake 1 (the largest according to v3).
2. If agent 3 did not choose the trimmed piece, Agent 2 is allocated the trimmed piece. Otherwise, Agent 2 chooses one of the two remaining pieces. Denote the agent i ∈ {2, 3} that received the trimmed piece by T, and the other agent by ¯ T .
3. Agent 1 is allocated the remaining (untrimmed) piece.

Note. The division of Cake 1 is envy-free: agent 3 received his preferred piece; agent 2 received one of the two pieces tied for largest according to v2; and agent 1 received an untrimmed piece worth 1/3 according to v1.

Stage 2 (Division of Cake 2).

1. ¯ T divides Cake 2 to three equal pieces according to v ¯ T .
2. Agents T, 1, and ¯ T choose the pieces of Cake 2, in that order.

Note. The division of Cake 2 is envy-free with respect to agents T and ¯ T, since T chooses first, and the three pieces are equal according to ¯ T. Further, agent 1 chooses a piece of Cake 2 before ¯ T, hence agent 1 does not envy ¯ T . Finally, agent 1 might prefer the piece of Cake 2 allocated to T; nevertheless, agent 1 cannot envy T overall, since the trimmed piece of Cake 1, combined with the entire Cake 2, is worth only 1/3 to agent 1.

There are seemingly many types of operations that are carried out in the execution of the Selfridge-Conway algorithm: dividing a cake into equal pieces, trimming pieces, and choosing a piece according to different criteria. Nevertheless, all these operations are captured by the two types of queries defined in the Robertson-Webb model [Robertson and Webb, 1998]:

1. evali(x1, x2): returns vi(x1, x2).
2. cuti(x1, α): returns x2 ∈ [0, 1] such that vi(x1, x2) = α, or announces that such an x2 does not exist.

For example, in order to simulate the trimming operation in step 0.2, the algorithm can first ask agent 2 to evaluate the three pieces. Say that v2(X1) ≥ v2(X2) ≥ v2(X3), and that X1 = [x1, x2]; the algorithm then submits a cut2(x1, v2(X2)) query. In general, as noted in the introduction, the RobertsonWebb model captures the existing discrete cake-cutting algorithms (that is, algorithms that do not require continuously moving knives or similar constructs), and was the model of choice in the previous papers about lower bounds for proportional division [Edmonds and Pruhs, 2006; Woeginger and Sgall, 2007].

Observe that the queries only provide the algorithm with information regarding the valuations of the agents, and do not produce an actual allocation. Once the algorithm has sufficient information to determine an envy-free allocation, it may output one "for free", that is, we are only interested in the number of queries, not the calculations required on the part of the algorithm to produce an envy-free allocation given sufficient information. The algorithmmay be adaptive, in the sense that each query may depend on the the answers of the agents to the previous queries. Finally, the query complexity of the algorithm (in the Robertson-Webb model) is the worstcase number of cut and eval queries that the algorithm requires in order to produce an envy-free allocation. The query complexity of the problem of envy-free cake-cutting is the query complexity of the best algorithm. The Robertson-Webb model is a model of concrete complexity, much like, e.g., the complexity of sorting in the comparison model [Cormen et al., 2001, Section 8.1].

Woeginger and Sgall [2007] raise some very interesting issues with the Robertson-Webb model. For example, there exists a one-to-one mapping from all possible valuation functions to [0, 1]. In response to, say, a cuti(0, 1/2) query, agent i can return a point x2 that encodes vi (disregarding the fact that x2 is supposed to satisfy vi(0, x2) = 1/2. Hence, after n queries, one to each agent, the algorithm has full information about the valuations of the agents, and can compute an envyfree allocation offline. In order to circumvent this difficulty, it is assumed that the agents must answer the queries truthfully.

3 A Lower Bound for Envy-Free cake-cutting

This section is devoted to proving our main result.

Theorem 3.1. The query complexity (in the Robertson-Webb model) of achieving an envy-free allocation is Ω(n2 ).

We first lay the notational and conceptual foundations for our proof. For an interval I = [x1, x2], we denote left(I ) = x1, right(I ) = x2, and |I| = x2 - x1. Similarly to Edmonds and Pruhs [2006], we say that a piece of cake (a union of disjoint intervals) X = ⋃k∈K Ik is light if its width is at most 2/n, that is,

A piece of cake is said to be heavy if it is not light.

Since we are dealing with a lower bound, we shall take the point of view of an adversary that is trying to answer the algorithm's queries in a confusing, albeit consistent, way. Curiously, it will prove useful to give the algorithm more information than it asks for. This only makes the algorithm's task, namely finding an envy-free allocation, easier. In other words, providing the algorithm with more information only makes the adversary's task harder, which is fine in the context of lower bounds. Specifically, given the query evali(x1, x2), we will provide the algorithm with the following values: vi(0, x1), vi(x1, x2), vi(x2, 1). Given the query cuti(x1, α), we will choose a point x2 such that vi(x1, x2) = α, and then provide the algorithm with the same values as above.

We will be interested in the information available to the algorithm in different stages of its execution, based on the adversary's answers (in their extended version, as given above). We refer to the point in time when t queries have been submitted by the algorithm as stage t. In order to analyze the information available to the algorithm after a given number of queries, we will associate with each agent i ∈ N and each stage t a set of disjoint intervals Πti that is a partition of [0, 1], i.e., ⋃I∈Πti I = [0, 1]. We say that an interval I ∈ Πti is active with respect to i at stage t.

The partition Πti is constructed inductively. We set Π0i = {[0, 1]} for all i ∈ N, that is, the only active interval with respect to i at stage 0 is [0, 1]. Now, assume that at stage t we have the partitions Πti for all i ∈ N. Further, suppose that query t+1 is submitted to agent i. For all j ̸= i, Πt+1 j = Πtj . We consider two cases, based on the type of query t + 1.

Case 1: the query is an evali(x1, x2) query. Let I1 ∈ Πti such that x1 ∈ I1, and I2 ∈ Πti such that x2 ∈ I2 (see Figure 1(a) for an illustration).

The first subcase is I1 ̸= I2; we let:

Less formally, I1 is partitioned into [left(I1), x1] and [x1, right(I1)], and I2 is partitioned into [left(I2), x2] and [x2, right(I2)], all of which are active with respect to i at stage t+1 (see Figure 1(b)). If one of these intervals is a singleton, it is not added to the partition.

The second subcase is when I1 = I2, and then:

Once again, a singleton interval is disregarded.

Case 2: The query is a cuti(x1, α) query. Let x2 ∈ [0, 1] such that vi(x1, x2) = α. We proceed exactly as in Case 1.

For example, assume that the first submitted query is evali(0, 1/2). This is the second subcase of the first case, with [left(I1), x1] a singleton. Then (regardless of the answer)

Taking the example one step further, assume the second query submitted by the algorithm is cuti(1/3, 1/2), and that the (partial) answer is 3/4, that is, vi(1/3, 3/4) = 1/2. Then

The following lemma, whose proof follows directly from the construction of Πt+1 i , will prove crucial in the sequel.

At this point, we wish to claim that, essentially, Πti is a partition of [0, 1] into (inclusion-) minimal intervals whose values are known.

Lemma 3.3. For every i ∈ N and stage t, Πti has the following properties:

1. For every I ∈ Πti , vi(I ) is known to the algorithm at stage t.
2. For every I ∈ Πti , I ′ ⊊ I, and 0 ≤ λ ≤ 1, it might be the case (based on the information available to the algorithm at stage t) that vi(I ′ ) = λvi(I ).

Proof sketch. Fix an agent i ∈ N. We prove the lemma by induction on t. For t = 0, Π0i = {[0, 1]}, and the two properties hold trivially.

Assume the two properties hold at stage t; we prove that they hold at stage t+1. This is straightforward if Πt+1 i = Πti , so assume this is not the case, i.e., query t+1 is submitted to i. Let x1, x2 ∈ [0, 1], I1, I2 ⊆ [0, 1] as in the construction of Πt+1 i . Assume that I1 ̸= I2 (the case I1 = I2 is very similar).

Concerning the first property, the value of all intervals in Πt+1 i ∩ Πti was known at stage t by the induction assumption, so we only need to verify that the property holds with respect to the intervals in Πt+1 i \Πti . Indeed, by the induction assumption vi(0, left(I1)) was known at stage t, since this interval can be partitioned into intervals in Πti . Since vi(0, x1) is revealed to the algorithm, the algorithm can calculate

Figure 1: The construction of the partition to active intervals: as a result of an evali(x1, x2) query, the partition changes from Πti , as shown in (a), to Πt+1 i , as shown in (b).

A symmetric argument for [left(I2), x2] and [x2, right(I2)] verifies the first property.

For the second property, by the induction assumption the algorithm had no information at stage t regarding the distribution of value inside the intervals in Πt+1 i ∩ Πti , and the answer to query t+1 clearly does not provide any such information. It can also be verified that the second property holds with respect to Πt+1 i \ Πti by the induction assumption with respect to I1 and I2.

From an evil adversary's point of view, the second property of active intervals is extremely useful. In particular, if I is active, vi(I ) can be concentrated in any arbitrarily small subinterval, and any strict subinterval can have value zero.

For a piece of cake X, let

Clearly vi(X) ≥ vt i (X). vt i (X) is, in a sense, the minimum value of X based on the information available to the algorithm at stage t. This notion will become more precise in the proof of Lemma 3.4.

The core of the proof is the notion of critical pieces. We say that a piece of cake X is critical with respect to i ∈ N at stage t if for every interval I ∈ Πti , vt i (X) ≥ vi(I ). In words, the minimum value of X is at least the value of any active interval. We shall demonstrate below that every agent i must be allocated a critical piece of cake, otherwise envy-freeness would be violated.

Lemma 3.4. Consider some algorithm for the envy-free allocation problem. Assume the algorithm outputs at stage t an allocation X1, . . . ,Xn. Then every Xi must be critical with respect to i at stage t.

Proof. Assume for contradiction that there exists i ∈ N such that Xi is not critical with respect to i at stage t. We will show that there is a valuation vi that is consistent with the information available to the algorithm at stage t such that i is envious.

First, we claim that we can set vi(Xi) = vt i (Xi). Indeed, for every I ∈ Πti such that I ⊈ Xi, set vi(Xi ∩ I ) = 0. If Xi ∩ I = ∅, this is trivially possible; otherwise, this is consistent with the information available at stage t since I is active, namely by Property 2 of Lemma 3.3. Moreover, since Πti is a partition of [0, 1], it holds that

Hence,

Now, by the assumption that Xi is not critical there exists some active interval I ∈ V t i such that vi(I ) > vt i (Xi) = vi(Xi); then it must be the case that I ⊈ Xi. Hence, there is some I ′ ⊆ I such that I ′ ∩Xi = ∅.

Next, we notice that a subinterval I ′′ of I ′ must be allocated to some agent, and the value of I might be concentrated in I ′′ . Formally, there exists j ∈ N such that Xj ∩ I ′ ̸= ∅. We let I ′′ = Xj ∩ I ′ . Since I is active, we can set

this is consistent with the information available to the algorithm at stage t. Hence,

We conclude that agent i envies agent j, in contradiction to the correctness of the algorithm.

At this point, we employ an idea used in the proof of Edmonds and Pruhs [2006] for proportional cake-cutting. Similarly to these authors, we wish to define a problem that is hard to solve with respect to one agent, and show that it must be solved with respect to many of the agents independently if an envy-free allocation is to be achieved. However, the problem that we deal with is harder than the one considered by Edmonds and Pruhs. We say that a piece is criticalight with respect to i at stage t if it is both light and critical with respect to i at stage t.

Lemma 3.5. If there is an adversary strategy such that at least T (n) queries are required to find a criticalight piece with respect to a given agent i ∈ N, then the query complexity of of envy-free cake-cutting is Ω(nT (n)).

Proof. We first observe that the answers to the queries submitted by the protocol to one agent i ∈ N cannot help the protocol find a criticalight piece with respect to another agent j ̸= i. Indeed, the property of being light is known in advance (i.e., does not depend on the valuations of the agents), and the property of being critical with respect to i only depends on the information available to the algorithm regarding vi. Therefore, in the context of finding criticalight pieces, we can separate the interaction of the algorithm with each agent. After the algorithm interacts with the agents, it must decide on an envy-free allocation. Now, it follows from our assumption that if an agent i receives less than T (n) queries, then it is possible to design vi (in a way that is consistent with the information available to the algorithm) such that the piece allocated to agent i is not criticalight with respect to i.

Let X1, . . . ,Xn be the allocation returned by the algorithm. By Lemma 3.4, for all i ∈ N we have that Xi is critical with respect to i. Now, assume for contradiction that more than n/2 pieces are heavy, that is, there exists a set N ′ ⊆ N, |N ′ | > n/2, such that for all i ∈ N ′ , |Xi| > 2/n. Since X1, . . . ,Xn are disjoint, it follows that

which cannot be true.

We conclude that at least n/2 of the Xi are light, and therefore (since X1, . . . ,Xn are all critical) at least n/2 of the pieces are criticalight. This means that the algorithm solved the problem of finding a criticalight piece with respect to at least n/2 agents, independently. Hence, the query complexity of the algorithm is at least

as required.

In order to complete the proof of Theorem 3.1, it only remains to prove that, given an agent, finding a criticalight piece is not a mundane task.

Proof of Theorem 3.1. By Lemma 3.5, it is sufficient to prove that there is an adversary strategy such that Ω(n) queries are required to find a criticalight piece with respect to a given agent i ∈ N.

Fix an agent i. We design a very simple adversary that answers the algorithm's queries with respect to agent i. The answer to the query eval(x1, x2) is that vi(0, x1) = x1, vi(x1, x2) = x2 - x1, and vi(x2, 1) = 1 - x2. The answer to the query cut(x1, α) is setting x2 = x1 + α and answering as above. In other words, the adversary always answers as if vi is uniformly distributed on [0, 1].

Let t∗ = n/4 - 1. It follows from Lemma 3.2 that for all t ≤ t∗ ,

It follows that there must be some active interval I ∗ at stage t with |I ∗ | > 2/n. The value of each active interval I is known to be |I|, thus vi(I ∗ ) = |I ∗ | > 2/n. Similarly, for any light piece of cake X, vt i (X) ≤ |X| ≤ 2/n < vi(I ∗ ). Therefore, no light piece of cake is critical with respect to i at any stage t ≤ t∗ , hence no piece of cake is criticalight with respect to i. We conclude that the number of queries required to find a criticalight piece is at least n/4 = Ω(n).

Acknowledgments

The author deeply thanks Felix Fischer for proofreading a draft of the paper. The author also thanks Ulle Endriss, Vangelis Markakis, J¨org Rothe, Michael Schapira, Moshe Tennenholtz, and Aviv Zohar for helpful discussions. Finally, the author thanks his brother Eviatar for introducing him to the cut-and-choose algorithm so early in life.