On the Complexity of Chore Division

1 Introduction

The chore division problem is the problem of fairly allocating a divisible undesirable object among n players. Imagine that we want to divide up a job among some players. There are many ways to assign this job to them, especially when players have a different evaluation of cost for each part of the job. For example, one might prefer doing certain tasks and other may not be good at them. This gives rise to an important question: How can one fairly assign a task to others?

The problem of fairly allocating an undesirable object, called chore, was first introduced by [Gardner, 1978] in the 1970s. Many definitions of fairness have been proposed for the chore division. The most important ones are proportionality and envy-freeness. An allocation of the chore is proportional if everyone receives at most 1/n of the chore in his perspective. The other definition of fairness is envy-freeness. An allocation is envy-free if each player receives a part that he thinks is the smallest.

The chore division is the dual problem of the well-studied cake cutting problem in which we want to fairly allocate a divisible good among players. This problem was introduced in the 1940s, and popularized by [Robertson and Webb, 1998]. The same criteria of fairness can also be defined for this problem. For the case of two players, the simple cut-and-choose protocol provides both proportionality and envy-freeness. In this protocol, one player cuts the cake into two equally preferred pieces, and the other chooses the best piece.

∗ Supported in part by NSF CAREER award CCF-1053605, NSF BIGDATA grant IIS-1546108, NSF AF:Medium grant CCF1161365, DARPA GRAPHS/AFOSR grant FA9550-12-1-0423, and another DARPA SIMPLEX grant.

Despite the simple algorithm for the two-player proportional allocation, finding a fair allocation for more players is more challenging. In 1948, [Steinhaus, 1948] proposed a proportional protocol for three players. Later, Banach, Knaster, and Steinhaus proposed an O(n2 ) protocol inspired by the cut-and-choose protocol for proportional allocation among n players. [Even and Paz, 1984] improved this result by providing an O(n log n) divide and conquer protocol. Also, they showed that no protocol can proportionally allocate the cake using less than n cuts; however this lower bound was not tight. The main difficulty of obtaining any lower bound for the cake cutting problem was the lack of any formal way to represent protocols. Finally, [Robertson and Webb, 1998] gave a formal model for cake cutting protocols. Their model covers almost all discrete cake cutting protocols. Later, [Edmonds and Pruhs, 2006] provided an Ω(n log n) lower bound for the proportional cake cutting. Their result shows that the proportional protocol by Even and Paz is asymptotically tight.

However, finding an envy-free allocation seems to be much harder. For a long time, the only known discrete and bounded envy-free protocols were for n ≤ 3. Every other protocol required an unbounded number of queries [Brams and Taylor, 1995; Pikhurko, 2000]. In a recent work, [Procaccia, 2009] proved an Ω(n2 ) lower bound for envy-free allocation which shows that finding an envy-free allocation is truly harder than proportional allocation. In a recent breakthrough, [Aziz and Mackenzie, 2016b; 2016a] provided the first discrete and bounded protocol for envy-free allocation. Their protocol requires nnnnnn queries in the worst case.

Despite all the studies in the cake cutting, the results known for the chore division are very limited. The same divide and conquer algorithm by Even and Paz, finds a proportional allocation using O(n log n) queries. However, no lower bound was known for this problem. For the envy-free chore division, [Peterson and Su, 2009] gave an envy-free protocol for n players, although their protocol is unbounded. Another protocol by [Peterson and Su, 2002] finds an envy-free allocation for 4 players using moving-knife procedure. However, the moving-knife procedure is not discrete and could not be captured using any discrete protocol. Only recently, a protocol by [Dehghani et al., 2018] provides the first discrete and bounded protocol for the envy-free chore division.

In this paper, we give an Ω(n logn) lower bound for the proportional chore division. Our method shows a close relation between chore division and cake cutting. We introduce a subproblem similar to thin-rich game introduced in [Edmonds and Pruhs, 2006], and show that solving both proportional cake cutting and proportional chore division requires solving this problem, and solving this problem is hard. Our method can also be seen roughly as a reduction from proportional chore division to proportional cake cutting. We introduce the notion of dual of a valuation function, and we show that how we can use dual functions to reduce some problems in chore division to similar problems in cake cutting. Since envy-freeness implies proportionality, our result also shows that any envy-free chore division protocol requires at least Ω(n log n) queries.

2 Preliminaries

In chore division (resp. cake cutting) problem, we are asked to partition a divisible undesirable (resp. desirable) object, usually modeled by the interval [0, 1], among n players. Let N = {1, 2, . . . , n} be the set of players. Each player i has a valuation function vi that indicates, given a subinterval I ⊆ [0, 1], the cost (resp. profit) of that interval for the player i. For an interval [x, y], we use vi(x, y) to denote the player i's valuation for this interval. We assume that valuation functions are non-negative, additive, divisible and normalized, in other words, for each player i, his valuation function vi satisfies the following properties:

• Non-negative: vi(I) ≥ 0 for every subinterval I in [0, 1].
• Additive: vi(I1 ∪ I2) = vi(I1) + vi(I2) for all disjoint intervals I1 and I2.
• Divisible: for every interval I and 0 ≤ λ ≤ 1, there exists an interval I ′ ⊆ I such that vi(I ′ ) = λvi(I).
• Normalized: vi(0, 1) = 1.

For an interval I = [x, y], we denote Left(I) = x and Right(I) = y. Also, we use |I| = y - x to denote the width of I. We say that an interval I is non-empty if |I| > 0.

We say that P is a piece of the chore if it is union of finite disjoint intervals, i.e., P = ∪ki=1 Ii. For a piece P , we use |P | to denote its width which is

Similarly, we use v(P) to denote the value of the function v for P. It follows from additivity of valuation functions that

Also, we use Dv(P ) = v(P )/|P | to denote the density of P . The complexity of a protocol is the number of queries it makes. We use the standard Robertson and Webb query model which allows two types of queries on a valuation function v.

• EVALv(x, y) : returns v(x, y).
• CUTv(x, r) : returns y ∈ [0, 1] such that v(x, y) = r or declares that answer does not exist.

An allocation X = (X1,X2, · · · ,Xn) is a partitioning of chore into n parts X1,X2, · · · ,Xn such that each player i receives Xi. We say that an allocation X = (X1,X2, · · · ,Xn) is proportional if vi(Xi) ≤ 1/n for every player i.

3 Lower Bound on Chore Division

In this section we provide an Ω(n logn) lower bound for the proportional chore division. In the cake cutting, [Edmonds and Pruhs, 2006] presents an Ω(n log n) lower bound by showing that finding a dense part for an arbitrary valuation function is hard and a protocol must use at least Ω(log n) queries. Later, they show that any proportional protocol for cake cutting finds a dense part for at least Ω(n) of n arbitrary valuation functions.

For the chore division problem, we consider a special type of valuation functions in which density of each piece of the chore is at least 1/2. Then, we represent a mapping from these valuation functions to low-density valuation functions, and show that finding any dense piece in low-density valuation functions requires Ω(logn) number of queries. Finally, we provide a lower-bound for the proportional chore division by showing that using any protocol for this problem, we can find a dense piece for at least Ω(n) of n arbitrary low-density valuation functions.

Definition 3.1. Given values α and β such that 0 ≤ α ≤ 1 ≤ β, we say that a valuation function v is (α, β)-dense if α ≤ Dv(I) ≤ β for every non-empty subinterval I in [0, 1]. Moreover, a valuation function v is positive if Dv(I) > 0 for every non-empty subinterval I in [0, 1].

An example of (α, β)-dense valuation functions is uniform functions. Since density of every interval in a uniform valuation function is 1, these valuation functions are (1, 1)-dense.

For an arbitrary positive valuation function v, we define its dual function and show that every query on the dual function can be answered using O(1) queries on the v. Later, we show that the dual function is an appropriate mapping from highdensity functions to low-density functions.

Definition 3.2. For a positive valuation function v, we use v∗ to denote its dual function and define it as follows.

for every subinterval [x, y] in [0, 1]

Note that in a positive valuation function, every CUTv(x, y) query has a unique answer, therefore the function above is well-defined for positive functions.

Lemma 3.3. For a positive valuation function v and its dual function v∗ the following holds.

• EVALv∗ (x, y) = CUTv(0, y) - CUTv(0, x)
• CUTv∗ (x, r) = EVALv(0, CUTv(0, x) + r)

So we can answer each query on v∗ using O(1) queries on v.

Proof. Based on definition of the dual function, we have:

For the cut query, it should return a y such that v∗ (x, y) = r. We complete the proof by showing that v∗ (x, EVALv(0,CUTv(0, x) + r)) = r. By the definition of dual function, we have v∗ (x, EVALv(0, CUTv(0, x) + r))

Note that for any positive valuation function v, and 0 ≤ x ≤ 1, we have CUTv(0, EVALv(0, x)) = x. Therefore,

In the following observation, we show that for a valuation function v, dual function of v∗ is v.

Observation 3.4. Let v be a positive valuation function and v∗ be its dual function, then dual of v∗ is v.

Proof. Let function u be the dual of v∗ , then the valuation of u for an interval [x, y] is

Since v∗ is the dual of v, by Lemma 3.3 we have,

Therefore, valuation of u for any interval is the same as valuation of v; hence, u = v. ✷

We introduce high-density and low-density pieces. [Edmonds and Pruhs, 2006] showed that a protocol must use at least Ω(logn) queries in order to find a high-density piece for an arbitrary valuation function. We expand their result by showing that finding a high-density piece for a positive (0, 2)-dense valuation function is still hard.

Definition 3.5. A piece X is heavy with respect to valuation function v if its width is at most 1/n and the valuation of v on this piece be at least 1/2n, i.e., |X| ≤ 1/n and v(X) ≥ 1/2n.

Similarly, a piece is light with respect to v if |X| ≥ 1/2n and v(X) ≤ 1/n.

Note that heavy and light pieces are not exclusive, and a piece can be both heavy and light.

Theorem 3.6. Any protocol that finds a heavy piece for an arbitrary positive (0, 2)-dense valuation function requires Ω(log n) queries in the worst case.

This theorem is our main tool to obtain a lower-bound for proportional chore division. First we show how we can use this theorem to prove the Ω(n logn) lower bound for chore division, and then in the next section we provide a proof for this theorem.

We show that any protocol for this chore division problem requires Ω(n logn) queries even if all the players' valuation functions are (1/2,∞)-dense. Specifically, we show that given n arbitrary positive (0, 2)-dense valuation functions, one can use their dual functions and any proportional chore division protocol to find a heavy piece for at least Ω(n) of them. First we show that if a valuation function v is positive and (0, 2)-dense, then its dual is (1/2,∞)-dense.

Lemma 3.7. The dual of a positive (0, 2)-dense valuation function is positive and (1/2,∞)-dense.

Proof. Suppose that v is a positive (0, 2)-dense valuation function. Let [x, y] be a non-empty subinterval in [0, 1]. We show that the density of the interval [x, y] is at least 1/2 with respect to v∗ . For an interval [x, y] we have v∗ (x, y) = CUTv(0, y) - CUTv(0, x). Therefore, we have

Note that x = EVALv(0,CUTv(0, x)), and y = EVALv(0,CUTv(0, y)). Therefore, by setting l = CUTv(0, x), and r = CUTv(0, y), we have x = EVALv(0, l) and y = EVALv(0, r). Therefore,

Since v is positive (0, 2)-dense, we have 0 < Dv(l, r) ≤ 2, therefore,

Now, we show that if n players all have a (1/2,∞)-dense valuation functions, then in any proportional allocation of chore to these players, at least n/3 of allocated pieces are light.

Lemma 3.8. Given n players with (1/2,∞)-dense valuation functions u1, · · · , un, let X1,X2, · · · ,Xn be any proportional allocation of the chore to the players such that Xi is allocated to the player i, then at least n/3 of the allocated pieces are light for their owners.

Proof. For each player i, we use wi to denote the width of the piece allocated to player i, i.e., wi = |Xi|. Therefore, ∑ni=1 wi = 1. Since the allocation is proportional we have ui(Xi) ≤ 1/n for every ui. Also, Since the valuation functions are (1/2,∞)-dense, we have ui(Xi) ≥ wi/2 for every player i, therefore wi ≤ 2ui(Xi) ≤ 2/n. Now assume that t is the number of pieces with the width less than 1/2n. Since the width of every other piece is at most 2/n, the following holds.

Therefore at least n - t ≥ n/3 of the wi are at least 1/2n, and the width of at least n/3 of the Xi are at least 1/2n. Note that because of the proportionality, the value of each of these pieces is at most 1/n for its owner. Therefore these pieces are light. ✷

Now we present a mapping from light pieces to heavy pieces in the dual of the valuation function.

Definition 3.9. For an interval I = [a, b] and a positive valuation function v, we define the dual of this interval with respect to v as I ∗ v = [EVALv(0, a), EVALv(0, b)].

For a part P which is union of finite disjoint intervals I1, · · · , Ik, we define the dual of P as P ∗ v = ∪ki=1 Ii ∗v .

Lemma 3.10. Let P be a light piece with respect to v where v is a positive valuation function, then P ∗ v is heavy with respect to v∗ .

Proof. Suppose that P = ∪ki=1 Ii, then P ∗ v = ∪ki=1 Ii ∗v . It follows that

Also, for an interval I = [a, b], we have,

Therefore,

This completes the proof.

✷

Now we are ready to prove that complexity of any proportional chore division protocol is at least Ω(n log n)

Theorem 3.11. Any protocol for the proportional chore division makes at least Ω(n log n) queries in the worst case.

Proof. Suppose that the query complexity of a chore division protocol is T(n). Consider n arbitrary positive (0, 2)- dense valuation functions v1, v2, · · · , vn, and solve the proportional chore division problem for their dual functions v∗ 1 , v∗ 2 , · · · , v∗n . Let X1,X2, · · · ,Xn be the pieces allocated to the players respectively. For every v∗ i , by Lemma 3.3, we can answer each query on this function by making O(1) queries on vi. Therefore, we can find the proportional chore division for the dual valuation functions v∗ 1 , v∗ 2 , · · · , v∗n using O(T (n)) queries.

According to the Lemma 3.7, valuation functions v∗ 1 , v∗ 2 , · · · , v∗n are (1/2,∞)-dense. Therefore, by Lemma 3.8, at least n/3 of the X1,X2, · · · ,Xn are light with respect to the dual valuation functions. Let Y1, Y2, · · · , Yn be the dual of pieces, where Yi is the dual of Xi with respect to v∗ i , i.e., Yi = X∗ i v∗ i . Since the dual of v∗ i is vi, applying Lemma 3.10 implies that at least n/3 of the dual pieces Y1, Y2, · · · , Yn are heavy for the valuation functions v1, v2, · · · , vn. Since the protocol makes at most O(T(n)) queries, the pieces returned by this protocol are at most union of O(T(n)) intervals, so we can calculate the dual of all these pieces using O(T(n)) queries. Therefore we can find heavy piece for at least n/3 of the valuation functions using O(T(n)) queries. This along with Lemma 3.6 implies that T(n) = Ω(n log n). Note that pieces Y1, Y2, · · · , Yn are not necessarily disjoint. However, we only want to find a heavy piece for Ω(n) of valuation functions, and since this is not an allocation, Y1, Y2, · · · , Yn can intersect.

✷

4 Lower Bound on Finding a Heavy Piece

In this section we prove Theorem 3.6 and give an Ω(logn) lower bound for finding a heavy piece in positive (0, 2)-dense valuation functions. We introduce special types of valuation functions, called balanced-value-trees, and present an adversarial strategy that gives an Ω(log n) lower bound for finding a heavy piece on balanced-value-trees. Balanced-value-trees are very similar to value trees valuation functions introduced in [Edmonds and Pruhs, 2006], but value trees cannot be used for our problem since these valuation functions are not necessarily (0, 2)-dense.

Assume that n ≥ 311 is a power of three. A balancedvalue-tree is a ternary balanced tree with n leaves and depth d = log3 n. Each non-leaf node v in the tree has three children, we use l(u), m(u) and r(u) to denote its left, middle, and right child. Each node in the tree corresponds to an interval in [0, 1]. For each node u, we use Iu to denote the interval that corresponds to u, and we use V (u) and D(u) to denote the value and the density of the interval Iu. Let r be the root of the tree, then |Ir| = 1 and V (r) = 1. For every non-leaf node u, its children partition the interval corresponding to u into three disjoint intervals with the equal width, i.e., Iu = Il(u) ∪ Im(u) ∪ Ir(u) and |Il(u)| = |Im(u)| = |Ir(u)| = |Iu|/3. It follows that width of every leaf in the tree is 1/n. We call a node u critical if D(u) × β > 2 where β = 26/ ln(n) .

We label each edge in the tree such that the value of every node u be the product of the label of edges along the path from the root to u. For a non-leaf critical node u, the label of edges between this node and its children are 1/3 . Every other non-leaf node has an edge with label β/3 called a heavy edge, and the label of its two other edges which we call them light are 1/2 - β/6. Since n ≥ 311 , we have 1/3 ≤ β/3 < 1/2, i.e., the value of every heavy edge is between 1/3 and 1/2. Also, the value of every light edge is between 1/4 and 1/3. We assume that the valuation of every leaf in the tree is uniform, this means that for every leaf u, and an interval I ⊆ Iu, we have V (I) = V (u)|I|

valuation of an arbitrary interval using the tree. Note that, it follows from the definition of critical nodes and our labeling that all children of a critical node are also critical.

Lemma 4.1. In a balanced-value-tree, the value of every non-leaf node is the sum of the values of its children.

Proof. Consider a non-leaf node u, if node u is critical then all its edges to its children are labeled 1/3, therefore V (l(u)) + V (m(u)) + V (r(u)) = (V (u)/3 + V (u)/3 + V (u)/3) = V (u). The lemma holds in this case.

Otherwise, we suppose that a node u is not critical, therefore V (l(u)) + V (m(u)) + V (r(u)) = V (u)(β/3 + 1/2 - β/6+1/2-β/6) = V (u). This completes the proof. ✷

For a node u, we use h(u), q(u) and z(u) to denote respectively the number of heavy, light, and other edges along the path from the root to u. In the following lemma we show that how we can compute the density of node u from h(u), q(u) and z(u).

Lemma 4.2. In a balanced-value-tree we have D(u) = βh(u) (3/2 - β/2)q(u) for every node u in the tree.

Proof. By the definition of balanced-value-trees we have

Now we are ready to show that balanced-value-trees are positive and (0, 2)-dense.

Lemma 4.3. Consider any balanced-value-tree, the valuation that this tree represents is positive and (0, 2)-dense.

Proof. Our goal is to show that density of every non-empty interval I is at most 2 and greater than 0. By the definition of the balanced-value-tree, the valuation for every interval I is greater than zero, so as its density.

Now it remains to show that density of every interval is at most 2. Assume for the sake of contradiction that there is an interval with density greater than 2, it follows that there is at least one leaf in the tree with the density greater than 2. Let u be this leaf. Consider the case that u is a critical leaf, let u1, u2, · · · , uk be the path from the root to u where u1 = r and uk = u. Let ut be the first node in this sequence that is critical. t is larger than one, since the root is not critical. It follows from the definition of the balanced-value-trees that D(u) = D(ut) ≤ βD(ut-1). Since ut-1 is not critical, it implies that βD(ut-1) ≤ 2, therefore D(u) ≤ 2 which is a contradiction.

Otherwise, suppose that u is not critical, therefore D(u) < βD(u) ≤ 2, thus we have the contradiction for both cases. ✷

We say that a non-critical leaf u in the tree is rich if D(u) ≥ 1/2. The following lemma shows that we can use any protocol that finds a heavy piece to find either a rich or a critical leaf in a balanced-value-tree.

Lemma 4.4. If a protocol finds a heavy piece in positive (0, 2)-dense valuation functions with at most T(n) queries, then using O(T(n)) queries we can find either a rich or a critical leaf in a balanced-value-tree.

Proof. Consider the valuation function derived from the balanced-value-tree. Let piece P be the output of the protocol for this valuation function. Since P is heavy, we have |P| ≤ 1/n and V (P) ≥ 1/2n. Therefore, D(P) ≥ 1/2. Since P is the union of at most O(T(n)) intervals, there is an interval I with the density at least 1/2. We can find this interval with O(T(n)) queries. Since |I| ≤ |P| ≤ 1/n, the interval I overlaps with at most two leaves, and one of these leaves has a density at least 1/2 which can be found with O(1) queries. The density of this leaf is at least 1/2, thus it is either critical or rich. ✷

For the rest of the section, our goal is to show that any protocol for finding a leaf which is either rich or critical must make Ω(log n) queries in the worst case. To this end, we first show that h(u) = Ω(log n) for critical and rich leaves.

Lemma 4.5. Let u be a leaf which is either rich or critical, then h(u) > (ln n)/6 - 1.

Proof. First, we assume that u is a critical leaf, therefore βD(u) > 2 ⇒D(u) > 2/β. It implies from lemma 4.2 that

Therefore,

Otherwise, suppose that u is a rich leaf, therefore D(u) ≥ 1/2. Since u is a leaf and is not critical, we have h(u) + q(u) = d = log3 n. We complete the proof by showing that h(u) must be greater than (ln n)/6. For the sake of contradiction suppose that h(u) ≤ (lnn)/6, therefore the maximum density that u can have is

Let denote f(n) to be the function above.

It is easy to verify that function f is an increasing function in n. Therefore,

which is a contradiction. Thus, for this case h(u) > (ln n)/6. ✷

We now show that any protocol that finds either a critical or a rich leaf must make Ω(logn) quries in the worst case. We give an adversarial strategy very similar to the strategy represented in [Edmonds and Pruhs, 2006] which prevents any protocol to find a critical or a rich leaf with less than Ω(logn) queries. Consider a balanced-value-tree. At the beginning, the label of each edge is unknown to the protocol. However, after each query instead of answering the query, we reveal the label of some edges in the tree such that the answer of the query can uniquely be determined from the revealed edges. Let u be a node in the tree and u1, u2, · · · , uk be the path from the root to u where u1 = r and uk = u. We say that node u is revealed if for every 1 ≤ i ≤ k, all labels of node ui to its children are revealed. The following lemma shows the information that a player can get from the revealed labels.

Lemma 4.6. (Lemma 2.2 in [Edmonds and Pruhs, 2006])

• For any revealed node u, the value of V (u) can be determined.
• For any revealed node u, values V (0,Left(Iu)) and V (0, Right(Iu)) can be computed.

• Let u, v be two revealed leaves, and x ∈ Iu and y ∈ Iv, then values V (0, x) and V (x, y) can be computed.
• Let u be a revealed leaf, x ∈ Iu, α be a value and v be the leaf that contains a point y such that V (x, y) = α, then the least common ancestor of u and v can be computed.

We are now ready to provide an adversarial strategy against finding a critical or a rich leaf.

Lemma 4.7. The query complexity of any protocol that finds either a critical or a rich leaf in a balanced-value-tree is Ω(log n).

Proof. We follow the following strategy for the first ⌊((ln n)/6-1)/2⌋ queries. The strategy is very similar to the one in [Edmonds and Pruhs, 2006] with some minor changes, and we just highlight the main ideas in this strategy and the details of it can be found in the original paper. The strategy reveals the label of some edges after each query such that the answer of the query can be computed and keeps the following invariants. First, for each node in the tree either none or all of its edges to its children are revealed. Second, after m queries, in any path from the root to a leaf at most 2m heavy edges are revealed. Three, all the revealed nodes form a connected component in the tree. Now we show that how we reveal the label of edges for each query.

• For EVAL(x, y) query, let uk be the leaf containing x, u1, u2, · · · , uk be the path from the root to u, and ul be the first unrevealed node. For each ui, l ≤ i < k, we reveal the label of ui to its children such that the edge between ui and ui+1 be light, and ui has exactly two light edges and one heavy edge. Similarly, we reveal the edges in the same way for the point y. Lemma 4.6 shows that the answer of this query can be computed using these edges.
• For CUT(x, α) query, we reveal the edges in the same way as the last case for the point x. Let y be a point such that V (x, y) = α. Using Lemma 4.6, we can find the least common ancestor of leaves containing x and y. Let u be this node. Let u′ be the first unrevealed node from u towards the leaf containing y. Let γ be the value that we must find in the subtree with the root u′ . Recall that label of heavy edges are 1/3 ≤ β/3 < 1/2. If γ > β/3, then we reveal the label of the first children to be heavy, and two others to be light. Otherwise, we reveal the first two edges to be light and the last one to be heavy. Since β/3 < 1/2, the edge between u′ and its child that contains y is always light. We reveal the edges in the same way for the child which contains y and do the same thing until we reveal the leaf containing y.

We follow this strategy for the first ⌊((lnn)/6 - 1)/2⌋ queries. Since n ≥ 311 , we have ((ln n)/6-1)/2 > 0. After these queries, at most (lnn)/6 - 1 heavy edges are revealed in any path from the root to a leaf. By lemma 4.5, any critical or rich leaf must have more than (ln n)/6 - 1 heavy edges in its path to the root. Therefore, the protocol could not be sure about any critical or rich leaf. After these queries, the density of no interval is greater than 2, since every critical node should have more than (ln n)/6-1 heavy edges in its path to the root and no node is revealed to be critical. Therefore, this is a valid labeling of a balanced-value-tree, and no protocol can find a critical or a rich leaf against this strategy with less than ⌊((ln n)/6-1)/2⌋ queries; hence, the query complexity of any protocol is Ω(log n). ✷

Now we can prove Theorem 3.6.

Theorem 3.6. Any protocol that finds a heavy piece for an arbitrary positive (0, 2)-dense valuation function requires Ω(log n) queries in the worst case.

Proof. Let T(n) be the query complexity of a protocol that finds a heavy piece. By Lemma 4.4, we can find either a critical or a rich leaf using O(T(n)) queries. Since query complexity of finding a critical or a rich leaf is Ω(logn), we have T (n) = Ω(log n). ✷

Acknowledgments

We thank the anonymous reviewers for their careful reading of our manuscript and their many insightful comments and suggestions.