Two's Company, Three's a Crowd: Consensus-Halving for a Constant Number of Agents

Introduction

The topic of fair division, founded in the work of Steinhaus , has been in the centre of the literature in economics, mathematics, and more recently computer science and artificial intelligence. Classic examples include the well-known fair cake cutting problem for the division of divisible resources (e.g., see [Gamow and Stern, 1958], [Brams and Taylor, 1996] or [Procaccia, 2013]), as well as the fair division of indivisible resources (e.g., see [Bouveret et al., 2016]). The earlier works in economics and mathematics were mainly concerned with the questions of whether fair solutions exist, and whether they can be found constructively, i.e., via finite-time protocols. In the more recent literature in computer science, a plethora of works have been concerned with the computational complexity of finding such solutions, either by providing polynomial-time algorithms, or by proving computational hardness results. Currently, it would be no exaggeration to say that fair division is one of the most vibrant and important topics in the intersection of these areas.

Besides the classic fair division settings mentioned above, another well-known problem is the Consensus-Halving problem, whose origins date back to the 1940s and the work of Neyman . In this problem, a set of $n$ agents with different and heterogeneous valuation functions over the unit interval $$aim at finding a partition of the interval into pieces labelled either “$+$” or “$-$” using at most$n$cuts, such that the total value of every agent for the portion labelled “$+$” and for the portion labelled “$-$” is the same. Very much like other well-known problems in fair division, the existence of a solution can be proven via fixed-point theorems, in particular the Borsuk-Ulam theorem [Borsuk, 1933], and can also be seen as a generalisation of the Hobby-Rice Theorem [Hobby and Rice, 1965].

The problem has applications in the context of the well-known Necklace Splitting problem of Alon and was studied in conjunction with this latter problem [Goldberg and West, 1985; Alon and West, 1986]. Other applications were highlighted by Simmons and Su , who were the first to study the problem in isolation. For example, consider two families that are dividing a piece of land into two regions, such that every member of each family considers the split to be equal. Another example is the 1994 Convention of the Law of the Sea (see [Brams and Taylor, 1996]), which regards the protection of developing countries in the event that an industrialised nation is planning to mine resources in international waters. In such cases, a representative of the developing nations reserves half of the seabed for future use by them, and a consensus-halving solution would correspond to a partition of the seabed into two portions that all the developing nations consider to be of equal value.

Simmons and Su in fact studied the approximate version of Consensus-Halving, coined the $\varepsilon$-Consensus-Halving problem, where the requirement is that the total value of every agent for the portion labelled “$+$” and for the portion labelled “$-$” is approximately the same, up to an additive parameter $\varepsilon$. For this version, Simmons and Su provided a constructive solution via an exponential-time algorithm. The $\varepsilon$-Consensus-Halving problem received considerable attention in the literature of computer science over the past few years, as it was proven to be the first “natural” PPA-complete problem [Filos-Ratsikas and Goldberg, 2018], i.e., a problem that does not have a polynomial-sized circuit explicitly in its definition, answering a decade-old open question [Papadimitriou, 1994; Grigni, 2001]. Additionally, Filos-Ratsikas and Goldberg , reduced from this problem to establish the PPA-completeness of Necklace Splitting with two thieves; these PPA-completeness results provided the first definitive evidence of intractability for these two classic problems, establishing for instance that solving them is at least as hard as finding a Nash equilibrium of a strategic game [Daskalakis et al., 2009; Chen et al., 2009]. Filos-Ratsikas et al. improved on the results for the $\varepsilon$-Consensus-Halving problem, by showing that the problem remains PPA-complete, even if one restricts the attention to very small classes of agents’ valuations, namely piecewise uniform valuations with only two valuation blocks. Very recently, the $\varepsilon$-Consensus-Halving problem was shown to be PPA-complete even for constant $\varepsilon$, namely any $\varepsilon<1/5$ [Deligkas et al., 2022a].

This latter result falls under the general umbrella of imposing restrictions on the structure of the problem, to explore if the computational hardness persists or whether we can obtain polynomial-time algorithms. Filos-Ratsikas et al. applied this approach along the axis of the valuation functions, while considering a general number of agents, similarly to [Filos-Ratsikas and Goldberg, 2018, 2019]. In this paper, we take a different approach, and we restrict the number of agents to be constant. This is in line with most of the theoretical work on fair division, which is also concerned with solutions for a small number of agentsFor example, the existence of bounded protocols for cake-cutting for more than $3$ agents was not known until very recently [Aziz and Mackenzie, 2016a, b], but such protocols for $2$ and $3$ agents were known since the 1960s (see [Brams and Taylor, 1996; Robertson and Webb, 1998]). and it is also quite relevant from a practical standpoint, as fair division among a few participants is quite common. We believe that such investigations are necessary in order to truly understand the computational complexity of the problem. To this end, we state our first main question:

What is the computational complexity of $\varepsilon$-Consensus-Halving for a constant number of agents?

Since the number of agents is now fixed, any type of computational hardness must originate from the structure of the valuation functions. We remark that the existence results for $\varepsilon$-Consensus-Halving are fairly general, and in particular do not require assumptions like additivity or monotonicity of the valuation functions. For this reason, the sensible approach is to start from valuations that are as general as possible (for which hardness is easier to establish), and gradually constrain the domain to more specific classes, until eventually polynomial-time solvability becomes possible. Indeed, in a paper that is conceptually similar to ours, Deng et al. studied the computational complexity of the contiguous envy-free cake-cutting problemThis version of the classic envy-free cake-cutting problem requires that every agent receives a single, connected piece. and proved that the problem is PPAD-complete, even for three agents, when agents have ordinal preferences over the possible pieces. These types of preferences induce no structure on the valuation functions and are therefore as general as possible. In contrast, the authors showed that for three agents and monotone valuations, the problem becomes polynomial-time solvable, leaving the case of four or more agents as an open problem. We adopt a similar approach in this paper for $\varepsilon$-Consensus-Halving, and we manage to completely settle the complexity of the problem when the agents have monotone valuations, among other results, which are highlighted in Section 1.1.

Another relevant question that has been surprisingly overlooked in the related literature is the query complexity of the problem. In this regime, the algorithm interacts with the agents via queries, asking them to provide their values for different parts of the interval $$, and the complexity is measured by the number of queries required to find an$\varepsilon$-approximate solution. This brings us to our second main question:

What is the query complexity of $\varepsilon$-Consensus-Halving for a constant number of agents?

We develop appropriate machinery that allows us to answer both of our main questions at the same time. In a nutshell, for the positive results, we design algorithms that run in polynomial time and can be recast as query-based algorithms that only use a polynomial number of queries. For the negative results, we construct reductions from “hard” computational problems which allow us to simultaneously obtain computational hardness results and query complexity lower bounds.

In this section, we list our main results regarding the computational complexity and the query complexity of the $\varepsilon$-Consensus-Halving problem.

Computational Complexity: We start from the computational complexity of the problem for a constant number of agents. We prove the following main results, parameterised by (a) the number of agents and (b) the structure of the valuation functions.

Finally, the $\varepsilon$-Consensus-Halving problem with $2$ agents coincides with the well-known $\varepsilon$-Perfect Division problem for cake-cutting (e.g., see [Brânzei and Nisan, 2017, 2019]), and thus naturally our results imply that $\varepsilon$-Perfect Division with $2$ agents with monotone valuations can be done in polynomial time, whereas it becomes PPA-complete for $2$ agents with general valuations.

Before we proceed, we offer a brief discussion on the different cases that are covered by our results. The distinction on the number of agents is straightforward. For the valuation functions, we consider mainly general valuations and monotone valuations. Note that neither of these functions is additive, meaning that the value that an agent has for the union of two disjoint intervals $[a,b]$ and $[c,d]$ is not necessarily the sum of her values for the two intervals. For monotone valuations, the requirement is that for any two subsets $I$ and $I^{\prime}$ of $$such that$I\subseteq I^{\prime}$, the agent values$I^{\prime}$at least as much as$I$, whereas for general valuations there is no such requirement.

We remark that for agents with piecewise constant valuations (i.e., the valuations used in [Filos-Ratsikas and Goldberg, 2018] to obtain the PPA-completeness of the problem for many agents), the problem can be solved rather straightforwardly in polynomial time for a constant number of agents, using linear programming (see Appendix A). In terms of the classification of the complexity of the problem in order of increasing generality of the valuation functions, this observation provides the “lower bound” whereas our PPA-hardness results for monotone valuations provide the “upper bound”, see Figure 1. While the precise point of the phase transition has not yet been identified, our results make considerable progress towards this goal.

Query Complexity: Besides the computational complexity of the problem, we are also interested in its query complexity. In this setting, one can envision an algorithm which interacts with the agents via a set of queries, and aims to compute a solution to $\varepsilon$-Consensus-Halving using the minimum number of queries possible. In particular, a query is a question from the algorithm to an agent about a subset of $$, who then responds with her value for that set. We provide the following results, where$L$ denotes the Lipschitz parameter of the valuation functions:

To put these results into context, we remark that when studying the query complexity of the problem, the input consists of the error parameter $\varepsilon$ and the Lipschitz parameter $L$, given by their binary representation. In that sense, for some constant $k$, a $\Theta(\log^{k}(L/\varepsilon))$ number of queries is polynomial in the size of the input. On the contrary, a $\Theta(L/\varepsilon)$ number of queries is exponential in the size of the input. Not surprisingly, our PPA-hardness results give rise to exponential query complexity lower bounds, whereas our algorithms can be transformed into query-based algorithms of polynomial query complexity. We remark however that beyond this connection, our query complexity analysis is in fact quantitative, as we provide tight or almost tight bounds on the query complexity as a function of the number of agents $n$, for both general and monotone valuation functions.

Finally, for the case of monotone valuations, we consider a more expressive query model, which is an appropriate extension of the well-known Robertson-Webb query model [Robertson and Webb, 1998; Woeginger and Sgall, 2007], the predominant query model in the literature of fair cake-cutting [Brams and Taylor, 1996]; we refer to this extension as the Generalised Robertson-Webb (GRW) query model. We show that our bounds extend to this model as well, up to logarithmic factors.

2 Related Work

As we mentioned in the introduction, the origins of the Consensus-Halving problem can be traced back to the 1940s and the work of Neyman , who studied a generalisation of the problem with $k$ labels instead of two (“$+$”, “$-$”), and proved the existence of a solution when the valuation functions are probability measures and there is no constraint on the number of cuts used to obtain the solution. The existence theorem for two labels is known as the Hobby-Rice Theorem [Hobby and Rice, 1965] and has been studied rather extensively in the context of the famous Necklace Splitting problem [Goldberg and West, 1985; Alon and West, 1986; Alon, 1987]. In fact, most of the proofs of existence for Necklace Splitting (with two thieves) were established via the Consensus-Halving problem, which was at the time referred to as Continuous Necklace Splitting [Alon, 1987]. The term “Consensus-Halving” was coined by Simmons and Su , who studied the continuous problem in isolation, and provided a constructive proof of existence which holds for very general valuation functions, including all of the valuation functions that we consider in this paper. Interestingly, the proof of Simmons and Su reduces the problem to finding edges of complementary labels on a triangulated $n$-sphere, labelled as prescribed by Tucker’s lemma, a fundamental result in topology.

While not strictly a reduction in the sense of computational complexity, the ideas of [Simmons and Su, 2003] certainly paved the way for subsequent work on the problem in computer science. The first computational results were obtained by Filos-Ratsikas et al. , who proved that the associated computational problem, $\varepsilon$-Consensus-Halving, lies in PPA (adapting the constructive proof of Simmons and Su ) and that the problem is PPAD-hard, for $n$ agents with piecewise constant valuation functions. Filos-Ratsikas and Goldberg proved that the problem is in fact PPA-complete, establishing for the first time the existence of a “natural” problem complete for PPA, i.e., a problem that does not contain a polynomial-sized circuit explicitly in its definition, answering a long-standing open question of Papadimitriou . In a follow-up paper, [Filos-Ratsikas and Goldberg, 2019] used the PPA-completeness of Consensus-Halving to prove that the Necklace Splitting problem with two thieves is also PPA-complete. Very recently, Filos-Ratsikas et al. strengthened the PPA-hardness result to the case of very simple valuation functions, namely piecewise constant valuations with at most two blocks of value. Deligkas et al. studied the computational complexity of the exact version of the problem, and obtained among other results its membership in a newly introduced class BU (for “Borsuk-Ulam” [Borsuk, 1933]) and its computational hardness for the well-known class FIXP of Etessami and Yannakakis . Batziou et al. showed that the corresponding strong approximation problem (with measures represented by algebraic circuits) is complete for BU. A version of Consensus-Halving with divisible items was studied by Goldberg et al. , who proved that the problem is polynomial-time solvable for additive utilities, but PPAD-hard for slightly more general utilities. Very recently, Deligkas et al. [2022b] showed the PPA-completeness of the related Pizza Sharing problem [Karasev et al., 2016], via a reduction from Consensus-Halving.

Importantly, none of the aforementioned results apply to the case of a constant number of agents, which was prior to this paper completely unexplored. Additionally, none of these works consider the query complexity of the problem. A recent work [Alon and Graur, 2021] studies $\varepsilon$-Consensus-Halving in a hybrid computational model (see the full version of their paper) which includes query access to the valuations, but contrary to our paper, their investigations are not targeted towards a constant number of agents, and the agents have additive valuation functions.

A relevant line of work is concerned with the query complexity of fair cake-cutting [Brams and Taylor, 1996; Procaccia, 2016], a related but markedly different fair-division problem. Conceptually closest to ours is the paper by Deng et al. , who study both the computational complexity and the query complexity of contiguous envy-free cake-cutting, for agents with either generalMore accurately, Deng et al. prove their impossibility results for ordinal preferences, where for each possible division of the cake, the agent specifies the piece that she prefers. In particular, if one were to define valuation functions consistent with these preferences, the value of an agent for a piece would have to depend also on the way the rest of the cake is divided among the agents. or monotone valuations. For the latter case, the authors obtain a polynomial-time algorithm for three agents, and leave open the complexity of the problem for four or more agents. In our case, for $\varepsilon$-Consensus-Halving, we completely settle the computational complexity of the problem for agents with monotone valuations.

In the literature of fair cake-cutting, most of the related research (e.g., see [Brams and Taylor, 1996; Aziz and Mackenzie, 2016a, b; Amanatidis et al., 2018; Brânzei and Nisan, 2017]) has focused on the well-known Robertson-Webb (RW) query model, in which agents interact with the protocol via two types of queries, evaluation queries (eval) and cut queries (cut). As the name suggests, this query model is due to Robertson and Webb , but the work of Woeginger and Sgall has been rather instrumental in formalising it in the form that it is being used today. Given the conceptual similarity of fair cake-cutting with Consensus-Halving, it certainly makes sense to study the latter problem under this query model as well, and in fact, the queries used by Alon and Graur are essentially RW queries. As we show in Section 6, our bounds are qualitatively robust when migrating to this more expressive model, i.e., they are preserved up to logarithmic factors.

Related to our investigation is also the work of Brânzei and Nisan , who among other settings study the problem of $\varepsilon$-Perfect Division, which stipulates a partition of the cake into $n$ pieces, such that each of the $n$ agents interprets all pieces to be of approximate equal value (up to $\varepsilon$). For the case of $n=2$, this problem coincides with $\varepsilon$-Consensus-Halving, and thus one can interpret our results for $n=2$ as extensions of the results in [Brânzei and Nisan, 2017] (which are only for additive valuations) to the case of monotone valuations (for which the problem is solvable with polynomially-many queries) and to the case of general valuations (for which the problem admits exponential query complexity lower bounds). Besides the aforementioned results, there is a plethora of works in computer science and artificial intelligence related to computational aspects of fair cake cutting and fair division in general, e.g., see [Elkind et al., 2021; Segal-Halevi, 2022; Bei et al., 2017, 2012, 2022; Bei and Suksompong, 2021; Goldberg et al., 2020; Balkanski et al., 2014; Alijani et al., 2017; Kurokawa et al., 2013; Brânzei et al., 2016; Cohler et al., 2011; Hosseini et al., 2020].

Preliminaries

In the $\varepsilon$-Consensus-Halving problem, there is a set of $n$ agents with valuation functions $v_{i}$ (or simply valuations) over the interval $$, and the goal is to find a partition of the interval into subintervals labelled either “$+$” or “$-$”, using at most$n$cuts. This partition should satisfy that for every agent$i$, the total value for the union of subintervals$\mathcal{I}^{+}$labelled “$+$” and the total value for the union of subintervals$\mathcal{I}^{-}$labelled “$-$” is the same up to$\varepsilon$, i.e.,$|v_{i}(\mathcal{I}^{+})-v_{i}(\mathcal{I}^{-})|\leq\varepsilon$. In this paper we will assume$n$to be a constant and therefore the inputs to the problem will only be$\varepsilon$and the valuation functions$v_{i}$.

Valuation Classes: We will be particularly interested in the following three valuation classes, in terms of decreasing generality:

General valuations, in which there is no further restriction to the functions $v_{i}$.

Monotone valuations, in which $v_{i}(A)\leq v_{i}(A^{\prime})$ for any two Lebesgue-measurable subsets $A$ and $A^{\prime}$ such that $A\subseteq A^{\prime}$. Intuitively, for this type of function, when comparing two sets such that one is a subset of the other, an agent cannot have a smaller value for the set that contains the other.

Normalisation: We will also be interested in valuation functions that satisfy some standard normalisation properties. A valuation function $v_{i}$ is normalised, if the following properties hold:

In other words, we require the agents’ values to lie in $$and that their value for the whole interval is normalised to$1$. These are the standard assumptions in the literature of the problem for additive valuations [Alon, 1987], as well as in the related problem of fair cake-cutting [Procaccia, 2016]. We will only consider normalised valuation functions for our lower bounds and hardness results, whereas for the upper bounds and polynomial-time algorithms we will not impose any normalisation; this only makes both sets of results even stronger.

With regard to the valuation classes defined above, we will often be referring to their normalised versions as well, e.g., normalised general valuations or normalised monotone valuations.

Input models: Given the fairly general nature of the valuation functions, we need to specify the manner in which they will be accessed by an algorithm for $\varepsilon$-Consensus-Halving. Since we are interested in both the computational complexity and the query complexity of the problem, we will assume the following standard two ways of accessing these functions.

We will also consider the following weaker version of the black-box model, which we will use in our query complexity upper bounds, thus making them stronger: In the weak black-box model the input to a valuation function $v_{i}$ is some set $\mathcal{I}$ of intervals, obtained by using at most $n$ cuts, where $n$ is the number of agents.

In the white-box model, the valuation functions $v_{i}$ are polynomial-time algorithms, mapping sets of intervals to non-negative rational numbers. These polynomial-time algorithms are given explicitly as part of the input, including the Lipschitz parameter $L$.To avoid introducing too many technical details here, we refer to Appendix B for the fully formal definition. This input model is appropriate for studying the computational complexity of the problem, where the complexity is measured as usual by the running time of the algorithm.

We now provide the formal definitions of the problem in the black-box and the white-box model. Note that the Lipschitz-parameter $L$ is part of the input of the problem and thus will appear in the bounds we obtain. Some of the previous works take $L$ to be bounded by a constant, and as a result it does not appear in their bounds.

\mathcal{I}^{+} and $\mathcal{I}^{-}$ such that for each agent $i$, it holds that $|v_{i}(\mathcal{I}^{+})-v_{i}(\mathcal{I}^{-})|\leq\varepsilon$, using at most $n$ cuts. Definition 2 ($\varepsilon$-Consensus-Halving (white-box model)). For any constant $n\geq 1$, the problem $\varepsilon$-Consensus-Halving with $n$ agents is defined as follows: - Input: $\varepsilon>0$, the Lipschitz parameter $L$, polynomial-time algorithms $v_{i}$. - Output: A partition of $$into two sets of intervals$\mathcal{I}^{+}$and$\mathcal{I}^{-}$such that for each agent$i$, it holds that$|v_{i}(\mathcal{I}^{+})-v_{i}(\mathcal{I}^{-})|\leq\varepsilon$, using at most$n$cuts. Terminology: When the valuation functions are normalised, we will refer to the problem as$\varepsilon$-Consensus-Halving with$n$normalised agents. When the valuation functions are monotone, we will refer to the problem as$\varepsilon$-Consensus-Halving with$n$monotone agents. If both conditions are true, we will use the term$\varepsilon$-Consensus-Halving with$n$ normalised monotone agents.

In the black-box version of $nD$-Borsuk-Ulam, we can query the value of the function $F$ at any point $x\in B^{n+1}$. In the white-box version of this problem, we are given a polynomial-time algorithm that computes $F$. Since the number of inputs of $F$ is fixed, we can assume that we are given an arithmetic circuit with $n+1$ inputs and $n$ outputs that computes $F$. Following the related literature [Daskalakis and Papadimitriou, 2011], we will consider circuits that use the arithmetic gates $+,-,\times,\max,\min,<$ and rational constants.Formally speaking these circuits also need to be well-behaved in a certain sense (see [Fearnley et al., 2021]). It is easy to check that the circuits we construct in this paper all have this property.

Another related problem that will be of interest to us is the computational version of Tucker’s Lemma [Tucker, 1945]. Tucker’s lemma is a discrete analogue of the Borsuk-Ulam theorem, and its computational counterpart, $nD$-Tucker, is defined below.

In the white-box model, $nD$-Tucker was recently proven to be PPA-hard for any $n\geq 2$, by Aisenberg et al. ; the membership of the problem in PPA was known by [Papadimitriou, 1994].

For any constant $n\geq 2$, $nD$-Tucker is PPA-complete.

The computational class PPA was defined by Papadimitriou , among several subclasses of the class TFNP [Megiddo and Papadimitriou, 1991], the class of problems with a guaranteed solution which is verifiable in polynomial time. PPA is defined with respect to a graph of exponential size, which is given implicitly as input, via the use of a circuit that outputs the neighbours of a given vertex, and the goal is to find a vertex of odd degree, given another such vertex as input.

Given the close connection between Tucker’s Lemma and the Borsuk-Ulam Theorem, the PPA-hardness of some appropriate computational version of Borsuk-Ulam follows as well [Aisenberg et al., 2020]. However, this does not apply to the version of $nD$-Borsuk-Ulam defined above, especially when one considers the additional properties of the function $F$ required for normalisation and monotonicity, as discussed earlier. We will reduce from $nD$-Tucker to our version of $nD$-Borsuk-Ulam, to obtain its PPA-hardness (even for the normalised monotone version), which will then imply the PPA-hardness of $\varepsilon$-Consensus-Halving, via our main reduction in Section 3.

In the black-box model, Deng et al. , building on the results of Chen and Deng , proved both query complexity lower bounds and upper bounds for $nD$-Tucker.

For any constant $n\geq 2$, the query complexity of $nD$-Tucker is $\Theta\left(N^{n-1}\right)$.

We remark that Deng et al. use a version of $nD$-Tucker that is slightly different from the one that we defined above, but their results apply to this version as well.

Some connections between the aforementioned problems, namely $nD$-Borsuk-Ulam, $nD$-Tucker, and $\varepsilon$-Consensus-Halving are known from the previous literature. First, $nD$-Borsuk-Ulam and $nD$-Tucker are known to be computationally equivalent due to Papadimitriou and Aisenberg et al. , although, technically speaking, none of the aforementioned papers proved this result formally, or even defined $nD$-Borsuk-Ulam formally. Yet, even the implicit reduction between those problems is insufficient for our purposes, because, in order to achieve our results for Consensus-Halving, we need a version of $nD$-Borsuk-Ulam that exhibits several properties, as described in Definition 3 (namely, normalisation and primarily monotonicity). Indeed, proving the PPA-completeness of monotone $nD$-Borsuk-Ulam is the main technical result of our work.

In terms of the completeness of Consensus-Halving, the works of Filos-Ratsikas and Goldberg indeed establish reductions from $nD$-Tucker, but crucially, these reductions are white-box, i.e., they have access to the Boolean circuit that encodes the labelling function. On the contrary, our reductions are black-box (see Section 2.2 below), which allows us to obtain both computational complexity results and query complexity bounds at the same time. Also, quite importantly, all the previous reductions do not work when there is a constant number of agents.

2 Efficient Black-Box Reductions

The reductions that we will construct (from $nD$-Tucker to $nD$-Borsuk-Ulam to $\varepsilon$-Consensus-Halving) will be black-box reductions, and therefore they will also allow us to obtain query complexity lower bounds for $\varepsilon$-Consensus-Halving in the black-box model, given the corresponding lower bounds of Theorem 2.2. For the upper bounds, we will reduce directly from $\varepsilon$-Consensus-Halving to $nD$-Tucker, again via a black-box reduction.

Roughly speaking,To keep the exposition clean, we do not provide formal definitions of these concepts here, as they are rather standard; we refer the reader to the related works of [Beame et al., 1998; Komargodski et al., 2019] for more details. a black-box reduction from Problem A to Problem B is a procedure by which we can answer oracle calls (queries) for an instance of Problem B by using an oracle for some instance of Problem A, such that a solution to the instance of Problem B yields a solution to the instance of Problem A. For example, a black-box reduction from $nD$-Borsuk-Ulam to $\varepsilon$-Consensus-Halving is a procedure that simulates an instance for the latter problem by accessing the function $F$ of the former problem a number of times, and such that a solution of $\varepsilon$-Consensus-Halving can easily be translated to a solution of $nD$-Borsuk-Ulam. The name “black-box” comes from the fact that this type of reduction does not need to know the structure of the functions $v_{i}$ of $\varepsilon$-Consensus-Halving or $F$ of $nD$-Borsuk-Ulam.

In order to prove lower bounds on the query complexity of some Problem B, it suffices to construct a black-box reduction from some Problem A, for which query complexity lower bounds are known; the obtained bounds will depend on the number $k$ of oracle calls to the input of Problem A that are needed to answer an oracle call to the input of Problem B. A black-box reduction is efficient if $k$ is a constant, and therefore the query complexity lower bounds of Problems A and B are of the same asymptotic order. To obtain upper bounds on the query complexity, we can construct a reduction in the opposite direction (from Problem B to Problem A), assuming that query complexity upper bounds for Problem A are known.

Ideally, we would like to use the same reduction to also obtain computational complexity results in the white-box model. For this to be possible, the procedure described above should actually be a polynomial-time algorithm. Slightly abusing terminology, we will use the term “efficient” to describe such a reduction in the white-box model as well.

We say that a black-box reduction from Problem A to Problem B is efficient if:

in the black-box model, it uses a constant number of queries (oracle calls) to the function (oracle) of Problem A, for each query (oracle call) to the function of Problem B;

in the white-box model, the condition above holds, and the reduction is also a polynomial-time algorithm.

Concretely for our case, all of our reductions will be efficient black-box reductions, thus allowing us to obtain both PPA-completeness results and query complexity bounds matching those of the problems that we reduce from/to. We remark that the reductions constructed for proving the PPA-hardness of the problem in previous works (for a non-constant number of agents) [Filos-Ratsikas and Goldberg, 2018, 2019; Filos-Ratsikas et al., 2020] are not black-box reductions, and therefore have no implications on the query complexity of the problem.

Black-Box Reductions to and from Consensus-Halving

In this section we develop our main machinery for proving both PPA-completeness results and query complexity upper and lower bounds for $\varepsilon$-Consensus-Halving. We summarise our general approach for obtaining positive and negative results below.

For our impossibility results (i.e., computational hardness results in the white-box model and query complexity lower bounds in the black-box model), we will construct an efficient black-box reduction from $nD$-Borsuk-Ulam to $\varepsilon$-Consensus-Halving with $n$ agents (Proposition 3.1). This reduction will preserve the optional properties of Definition 3, meaning that if the instance of $nD$-Borsuk-Ulam is normalised (respectively monotone), the valuation functions of the corresponding instance of $\varepsilon$-Consensus-Halving will be normalised (respectively monotone) as well. This will allow us in subsequent sections to reduce the problem of proving impossibility results for $\varepsilon$-Consensus-Halving to proving impossibility results for the versions of $nD$-Borsuk-Ulam with those properties. We will obtain these latter results via reductions from $nD$-Tucker, which for $n\geq 2$ is known to be PPA-hard (Theorem 2.1) and admit exponential query complexity lower bounds (Theorem 2.2).

For our positive results (i.e., membership in PPA in the white-box model and query complexity upper bounds in the black-box model), we will construct an efficient black-box reduction from $\varepsilon$-Consensus-Halving to $nD$-Tucker (Proposition 3.2). We remark here that a similar reduction already exists in the related literature [Filos-Ratsikas et al., 2021], but only applied to the case of additive valuation functions. The extension to the case of general valuations follows along the same lines, and we provide it here for completeness. We also note that some of our positive results, namely the results for one general agent and two monotone agents, will not be obtained via reductions, but rather directly via the design of polynomial-time algorithms in the white-box model or algorithms of polynomial query complexity in the black-box model.

Related to the discussion above, we have the following two propositions. Their proofs are presented in the sections below.

There is an efficient black-box reduction from (normalised, monotone) $nD$-Borsuk-Ulam to (normalised, monotone) $\varepsilon$-Consensus-Halving.

There is an efficient black-box reduction from $\varepsilon$-Consensus-Halving to $nD$-Tucker.

Description of the reduction. Let $n\geq 1$ be a fixed integer. Let $\varepsilon>0$ and let $F:B^{n+1}\to B^{n}$ be a Lipschitz-continuous function with Lipschitz parameter $L$. We now construct valuation functions $v_{1},\dots,v_{n}$ for a Consensus-Halving instance.

Let $R_{1},R_{2},\dots,R_{n+1}$ denote the partition of interval $$into$n+1$subintervals of equal length, i.e.,$R_{j}=[\frac{j-1}{n+1},\frac{j}{n+1}]$for$j\in[n+1]$. For any$A\in\Lambda()$, we define$x(A)\in B^{n+1}=^{n+1}$ by

for all $j\in[n+1]$. Recall that $\lambda$ denotes the Lebesgue measure on the interval $$. Note that since$\lambda(A\cap R_{j})\in[0,\frac{1}{n+1}]$, we indeed have$[x(A)]_{j}\in$; see Figure 2 for a visualisation.

For $i\in[n]$, the valuation function $v_{i}$ of the $i$th agent is defined as

for any $A\in\Lambda()$, where $F_{i}:B^{n+1}\to$ is the $i$th output of $F$. Note that $v_{i}(A)\in$, since $F_{i}(x(A))\in$.

Lipschitz-continuity. For any $A,B\in\Lambda()$ it holds that

Thus, $v_{i}$ is Lipschitz-continuous with Lipschitz parameter $(n+1)\cdot L$.

Letting $y=x(\mathcal{I}^{+})\in\partial(B^{n+1})$, we have that for any $i\in[n]$

Thus, $y$ is a solution to the original $nD$-Borsuk-Ulam instance.

White-box model. This reduction yields a polynomial-time many-one reduction from $nD$-Borsuk-Ulam to $\varepsilon$-Consensus-Halving with $n$ agents. Thus, if we show that $nD$-Borsuk-Ulam is PPA-hard for some $n$, then we immediately obtain that $\varepsilon$-Consensus-Halving with $n$ agents is also PPA-hard.

Black-box model. It is easy to see that this is a black-box reduction. It can be formulated as follows: given access to an oracle for an instance of $nD$-Borsuk-Ulam with parameters $(\varepsilon,L)$ we can simulate an oracle for an instance of $\varepsilon$-Consensus-Halving (with $n$ agents) with parameters $(\varepsilon/2,(n+1)L)$ such that any solution of the latter yields a solution to the former. Furthermore, in order to answer a query to some $v_{i}$, we only need to perform a single query to $F$. Thus, we obtain the following query lower bound: solving an instance of $\varepsilon$-Consensus-Halving (with $n$ agents) with parameters $(\varepsilon,L)$ requires at least as many queries as solving an instance of $nD$-Borsuk-Ulam with parameters $(\varepsilon^{\prime},L^{\prime})=(2\varepsilon,\frac{L}{n+1})$. This means that if $nD$-Borsuk-Ulam has a query lower bound of $\Omega((\frac{L^{\prime}}{\varepsilon^{\prime}})^{n-1})$ for some $n$, then $\varepsilon$-Consensus-Halving (with $n$ agents) has a query lower bound of $\Omega((\frac{L}{2\varepsilon(n+1)})^{n-1})=\Omega((\frac{L}{\varepsilon})^{n-1})$, since $n$ is constant.

Additional properties of the reduction. Some properties of the Borsuk-Ulam function $F$ carry over to the valuation functions $v_{1},\dots,v_{n}$. In particular, the following properties are of interest to us:

If $F$ is monotone, then $v_{1},\dots,v_{n}$ are monotone. Indeed, consider $A,B\in\Lambda()$ with $A\subseteq B$. Then, it holds that $\lambda(A\cap R_{j})\leq\lambda(B\cap R_{j})$ for all $j\in[n+1]$, and as a result $x(A)\leq x(B)$ (coordinate-wise). By monotonicity of $F$, it follows that $F_{i}(x(A))\leq F_{i}(x(B))$, and thus $v_{i}(A)\leq v_{i}(B)$ for all $i\in[n]$.

If $F$ is normalised, then $v_{1},\dots,v_{n}$ are normalised. As noted earlier, we already have that $v_{i}(A)\in$ for all $A\in\Lambda()$. Thus, it remains to prove that $v_{i}(\emptyset)=0$ and $v_{i}()=1$. It is easy to see that $x()=(1,1,\dots,1)$ and thus $F(x())=(1,1,\dots,1)$ since $F$ is normalised, which yields $v_{i}()=1$. On the other hand, we have $x(\emptyset)=(-1,-1,\dots,-1)$ and thus $F(x(\emptyset))=-F(-x(\emptyset))=-F(1,1,\dots,1)=(-1,-1,\dots,-1)$, which yields $v_{i}(\emptyset)=0$. Here we also used the fact $F$ is an odd function, since it is normalised. In fact, since $F$ is odd, we also obtain that $v_{i}(A)+v_{i}(A^{c})=1$ for all $A\in\Lambda()$, where $A^{c}=\setminus A$ denotes the complement of $A$. This can be shown by noting that $x(A^{c})=-x(A)$ (by using the same argument as for $\mathcal{I}^{+}$ and $\mathcal{I}^{-}$ above) and then using the fact that $F(x(A^{c}))=-F(x(A))$.

This means that if we are able to show (white- or black-box) hardness of $nD$-Borsuk-Ulam where $F$ has additional properties, then the hardness will also hold for $\varepsilon$-Consensus-Halving with $n$ agents that have the corresponding properties.

Furthermore, note that if $F$ is a normalised $nD$-Borsuk-Ulam function, then an $\varepsilon$-approximate Consensus-Halving for $v_{1},\dots,v_{n}$ (i.e., $|v_{i}(\mathcal{I}^{+})-v_{i}(\mathcal{I}^{-})|\leq\varepsilon$), yields an $\varepsilon$-approximate solution to $F$, in the sense that $\|F(x(\mathcal{I}^{+}))\|_{\infty}\leq\varepsilon$. This is due to the fact that, by definition, $F$ is an odd function, if it is normalised.

2 Proof of Proposition 3.2

The reduction presented in this section is based on a proof of existence for a generalization of Consensus-Halving with general valuations given in [Filos-Ratsikas et al., 2021]. This existence proof was also used in [Filos-Ratsikas et al., 2021] to provide a reduction for additive valuations. It can easily be extended to work for general valuations as well. We include the full reduction here for completeness.

Description of the reduction. Consider an instance of $\varepsilon$-Consensus-Halving with $n$ agents with parameters $\varepsilon$, $L$. Let $v_{1},\dots,v_{n}$ denote the valuations of the agents. We consider the domain $K_{m}^{n}$, where $K_{m}=\{-1,-(m-1)/m,\dots,-1/m,0,1/m,2/m,\dots,(m-1)/m,1\}$, for $m=\lceil 2nL/\varepsilon\rceil$. A point in $K_{m}^{n}$ corresponds to a way to partition the interval $$into two sets$\mathcal{I}^{+},\mathcal{I}^{-}$using at most$n$cuts. A very similar encoding was also used by Meunier for the Necklace Splitting problem. A point$x\in K_{m}^{n}$corresponds to the partition$\mathcal{I}^{+}(x),\mathcal{I}^{-}(x)$ obtained as follows.

Provisionally put the label “$+$” on the whole interval $$

Note that subsequent assignments of a label to an interval, “overwrite” previous assignments. One way of thinking about it, is that we are applying a coat of paint on the interval $$. Initially the whole interval is painted with colour “$+$”, and as the procedure is executed, various subintervals will be painted over with colour “$-$” or “$+$”. It is easy to check that the final partition into$\mathcal{I}^{+}(x),\mathcal{I}^{-}(x)$that is obtained, uses at most$n$cuts. Furthermore, for any$x\in\partial K_{m}^{n}$, the partition$\mathcal{I}^{+}(-x),\mathcal{I}^{-}(-x)$obtained from$-x$corresponds to the partition$\mathcal{I}^{+}(x),\mathcal{I}^{-}(x)$with labels “$+$” and “$-$” switched. In other words,$\mathcal{I}^{+}(-x)=\mathcal{I}^{-}(x)$and$\mathcal{I}^{-}(-x)=\mathcal{I}^{+}(x)$. For a more formal definition of this encoding, see [Filos-Ratsikas et al., 2021].

Let $i\in[n]$ be the agent that sees the largest difference between $v_{i}(\mathcal{I}^{+}(x))$ and $v_{i}(\mathcal{I}^{-}(x))$, i.e., $i=\arg\max_{i\in[n]}|v_{i}(\mathcal{I}^{+}(x))-v_{i}(\mathcal{I}^{-}(x))|$, where we break ties by picking the smallest such $i$.

Pick a sign $s\in\{+,-\}$ as follows. If $v_{i}(\mathcal{I}^{+}(x))>v_{i}(\mathcal{I}^{-}(x))$, then let $s=+$. If $v_{i}(\mathcal{I}^{+}(x))<v_{i}(\mathcal{I}^{-}(x))$, then let $s=-$. If $v_{i}(\mathcal{I}^{+}(x))=v_{i}(\mathcal{I}^{-}(x))$, then pick $s$ such that $\mathcal{I}^{s}$ contains the left end of the interval $$.

and the same bound also holds for $\lambda(\mathcal{I}^{-}(x)\triangle~{}\mathcal{I}^{-}(y))$. Since $v_{i}$ is Lipschitz-continuous with parameter $L$, it follows that

and similarly for $|v_{i}(\mathcal{I}^{-}(x))-v_{i}(\mathcal{I}^{-}(y))|$.

This means that $\mathcal{I}^{+}(x),\mathcal{I}^{-}(x)$ yields a solution to the original $\varepsilon$-Consensus-Halving instance.

General Valuations

We are now ready to prove our main results for the $\varepsilon$-Consensus-Halving problem, starting from the case of general valuations. First, for a single agent with a general valuation function, a simple binary search procedure is sufficient to solve $\varepsilon$-Consensus-Halving with a polynomial number of queries and in polynomial time, therefore obtaining an efficient algorithm both in the white-box and in the black-box model. We have the following theorem.

For one agent with a general valuation function (or multiple agents with identical general valuations), $\varepsilon$-Consensus-Halving is solvable in polynomial time and has query complexity $\Theta\left(\log\frac{L}{\varepsilon}\right)$.

We will prove the theorem for the case of $n=1$, as a solution to $\varepsilon$-Consensus-Halving for this case is also straightforwardly a solution to the problem with multiple agents with identical valuations. Our algorithm essentially simulates binary search. We say that the label of a cut $x\in$ is “$+$”, if $v([0,x])>v([x,1])+\varepsilon$. Respectively, the label of cut $x$ is “$-$”, if $v([x,1])>v([0,x])+\varepsilon$. In any other case, the label of the cut is 0; if a cut has label 0, then it is a solution to $\varepsilon$-Consensus-Halving. Observe that in order for an interval $[a,b]\subseteq$ to contain a solution, it suffices that the label of $a$ be “$-$” and the label of $b$ be “$+$” (or vice-versa); then there is definitely a point $x\in[a,b]$ where the label is 0 (by continuity of $v$).

Now let $a=0$ and $b=1$. If $a$ or $b$ has label 0, then we have immediately found a solution. Otherwise, note that if $a$ has label “$-$”, then $b$ must have label “$+$”, and vice-versa. For convenience, in what follows, we assume that $a$ has label “$-$” and $b$ has label “$+$”. Our algorithm proceeds as follows in every iteration. Given an interval $[a,b]$ with label “$-$” for $a$ and label “$+$” for $b$, it computes the label of $\frac{a+b}{2}$. This can be done via two eval queries. Then, if the label of $\frac{a+b}{2}$ is “$+$”, it sets $b=\frac{a+b}{2}$; if the label is “$-$”, it sets $a=\frac{a+b}{2}$; and if the label is 0 it outputs this cut.

We claim that the algorithm will always find a cut with label 0 after at most $\log\frac{L}{\varepsilon}$ iterations. For the sake of contradiction, assume that there is no such cut after $\log\frac{L}{\varepsilon}$ iterations. Observe that the length of $[a,b]$ in this case will be $\frac{\varepsilon}{L}$. In addition, we know the labels of $a$ and $b$. Cut $a$ has label “$-$”, thus $v([a,1])>v([0,a])+\varepsilon$, and cut $b$ has label “$+$”, i.e., $v([0,b])>v([b,1])+\varepsilon$. Since $|b-a|\leq\frac{\varepsilon}{L}$ and $v$ is $L$-Lipschitz-continuous, it follows that

and similarly $|v([0,a])-v([0,b])|\leq\varepsilon$. Putting everything together, we obtain that

which contradicts the assumption that cut $b$ has label “$+$”.

Since a polynomial-time algorithm which queries the polynomial-time algorithm of the input $O\left(\log\frac{L}{\varepsilon}\right)$ times is a polynomial-time algorithm, we immediately obtain the polynomial-time upper bound for the white-box model.

For the black-box model, the algorithm immediately gives us the upper bound, whereas the lower bound follows from our general reduction from $nD$-Borsuk-Ulam (Proposition 3.1), and the query lower bounds for the latter problem obtained through Lemma 4.2 below. In more detail, $1D$-Borsuk-Ulam (and thus $\varepsilon$-Consensus-Halving with a single agent) inherits its query complexity lower bounds from $1D$-Tucker, which can be easily seen to require at least $\Omega(\log N)$ queries in the worst-case. The latter bound naturally translates to a $\Omega(\log(L/\varepsilon))$ bound for $\varepsilon$-Consensus-Halving. We also remark that the upper bound holds for any version of the problem with general valuations, even in the weak black-box model, whereas the lower bound holds even for normalised general valuations and for the standard black-box model. ∎

We now move to our results for two or more agents with general valuations. Here we obtain a PPA-completeness result for $\varepsilon$-Consensus-Halving, as well as exponential bounds on the query complexity of the problem. Our results demonstrate that for general valuations, even in the case of two agents, the problem is intractable in both the black-box and the white-box model. The main technical result of the section is the following pivotal lemma, proved at the end of this section.

For any constant $n\geq 1$, $nD$-Tucker reduces to normalised $nD$-Borsuk-Ulam, via an efficient black-box reduction.

Now we state our main theorem about the computational/query complexity of the $\varepsilon$-Consensus-Halving problem, as well as a corresponding theorem for $nD$-Borsuk-Ulam. The proofs follow from Theorems 2.1 and 2.2 characterising the complexity of $nD$-Tucker and the following chain of reductions (where “$\leq$” denotes an efficient black-box reduction from the problem on the left-hand side to the problem on the right-hand side).

The specific parameters that appear in the bounds below follow from the proof of Lemma 4.2.

$\varepsilon$-Consensus-Halving with $n$ normalised general agents is PPA-complete. This remains the case, even if (a) we fix $\varepsilon\in(0,1)$, or (b) we fix $L\geq 3(n+1)$;

there exists a constant $c>0$ such that for any $\varepsilon\in(0,1)$ and any $L\geq 3(n+1)$ with $L/\varepsilon\geq c$, the query complexity of $\varepsilon$-Consensus-Halving with $n$ normalised general agents is $\Theta((L/\varepsilon)^{n-1})$.

normalised $nD$-Borsuk-Ulam is PPA-complete. This remains the case, even if (a) we fix $\varepsilon\in(0,1)$, or (b) we fix $L\geq 3$;

there exists a constant $c>0$ such that for any $\varepsilon\in(0,1)$ and any $L\geq 3$ with $L/\varepsilon\geq c$, the query complexity of normalised $nD$-Borsuk-Ulam is $\Theta((L/\varepsilon)^{n-1})$.

In both cases, the lower bounds hold even for the normalised versions of the problems, while the upper bounds hold even for the more general, non-normalised, versions.

The remainder of the proof will proceed in three steps: In Step 1, we will interpolate the $nD$-Tucker instance, to obtain a continuous function on $[-1/2,1/2]^{n}$, in Step 2, we extend this function to the whole domain $^{n}$, and in Step 3 we further extend to $^{n+1}$, to obtain an instance of the normalised $nD$-Borsuk-Ulam problem.

We embed the grid $[N]^{n}$ in $[-1/2,1/2]^{n}$ in a straightforward way, namely $p\in[N]^{n}$ corresponds to $\widehat{p}\in[-1/2,1/2]^{n}$ such that $\widehat{p}_{j}=-1/2+(p_{j}-1)/(N-1)$ for all $j\in[n]$. Note that antipodal grid points exactly correspond to antipodal points in $[-1/2,1/2]^{n}$. In other words, $p$ and $q$ are antipodal on the grid, if and only if $\widehat{p}=-\widehat{q}$.

Next we define the value of the function $f:[-1/2,1/2]^{n}\to[-\delta\cdot n,\delta\cdot n]$ at the embedded grid points as follows

$f$ is antipodally anti-symmetric on the boundary of $[-1/2,1/2]^{n}$, i.e., $f(-x)=-f(x)$ for all $x\in\partial([-1/2,1/2]^{n})$.

$f$ is Lipschitz-continuous with Lipschitz parameter $2n^{2}(N-1)\delta$, since the grid size is $1/(N-1)$ and $\|f(\widehat{p})\|_{\infty}\leq\delta\cdot n$ for all $p\in[N]^{n}$.

$f(1/2,1/2,\dots,1/2)=\delta\cdot n\cdot e_{+1}=(\delta\cdot n,0,0,\dots,0)$.

Now, we define $g:[-1/2,1/2]^{n}\to[-\delta,\delta]^{n}$ to be the truncation of $f$ to $[-\delta,\delta]^{n}$, namely

It is not hard to see that $g$ is also antipodally anti-symmetric, Lipschitz-continuous with Lipschitz parameter $2n^{2}(N-1)\delta$ and $g(1/2,1/2,\dots,1/2)=\delta\cdot e_{+1}$. Furthermore, if $x\in[-1/2,1/2]^{n}$ is such that $\|g(x)\|_{\infty}\leq\varepsilon$, then, since $\varepsilon<\delta$, $\|f(x)\|_{\infty}\leq\varepsilon$, and thus $x$ again yields a solution to the $nD$-Tucker instance.

Step 2: Extending to $\bm{^{n}}$. The goal of the next step is to define a function $h:^{n}\to^{n}$ that extends $g$ and ensures that $h(1,1,\dots,1)=(1,1,\dots,1)$, while maintaining its other properties. For $x\in^{n}$ we let $T(x)\in[-1/2,1/2]^{n}$ denote its truncation to $[-1/2,1/2]^{n}$, i.e., $[T(x)]_{i}=\min\{1/2,\max\{-1/2,x_{i}\}\}$ for all $i\in[n]$. The function $h:^{n}\to^{n}$ is defined as

so $\|h(x)\|_{\infty}>\varepsilon$. By the same argument, if $x_{i}<-1/2$ for all $i$, then we also have $\|h(x)\|_{\infty}>\varepsilon$.

Since $g(1/2,1/2,\dots,1/2)=\delta\cdot e_{+1}$ and $g(-1/2,-1/2,\dots,-1/2)=\delta\cdot e_{-1}$, it is easy to see that $h$ is continuous. Furthermore, since for any $x,y\in^{n}$ it holds that $\|T(x)-T(y)\|_{\infty}\leq\|x-y\|_{\infty}$, it is easy to see that $h$ is $2n^{2}(N-1)\delta$-Lipschitz-continuous outside of $\{x\in^{n}|x_{i}\geq 1/2\text{ for all }i\in[n]\}\cup\{x\in^{n}|x_{i}\leq-1/2\text{ for all }i\in[n]\}$. For any $y,z\in\{x\in^{n}|x_{i}\geq 1/2\text{ for all }i\in[n]\}$, it holds that $|h_{i}(y)-h_{i}(z)|=2|\min_{j}y_{j}-\min_{j}z_{j}|\leq 2\|y-z\|_{\infty}$ for $i>1$, and $|h_{1}(y)-h_{1}(z)|=2(1-\delta)|\min_{j}y_{j}-\min_{j}z_{j}|\leq 2\|y-z\|_{\infty}$. Thus, $h$ is $2$-Lipschitz-continuous on $\{x\in^{n}|x_{i}\geq 1/2\text{ for all }i\in[n]\}$ and, by the same argument, also on $\{x\in^{n}|x_{i}\leq-1/2\text{ for all }i\in[n]\}$.

As a result, $h$ is Lipschitz-continuous on $^{n}$ with Lipschitz parameter $\max\{2,2n^{2}(N-1)\delta\}$. Indeed, consider any $x,y\in^{n}$. If $x_{i}\geq 1/2$ and $y_{i}\leq-1/2$ for all $i$, then $\|x-y\|_{\infty}\geq 1$, and thus $\|h(x)-h(y)\|_{\infty}\leq 2\leq 2\|x-y\|_{\infty}$. By symmetry, the only remaining case that we need to check is when $x_{i}\geq 1/2$ for all $i$, and $y$ is such that there exists $i$ with $y_{i}<1/2$ and there exists $i$ with $y_{i}>-1/2$. In that case, we consider the segment $[x,y]$ from $x$ to $y$, and let $z\in[x,y]$ be the point that is the furthest away from $x$ but such that $z_{i}\geq 1/2$ for all $i$. Note that there must exist $i$ such that $z_{i}=1/2$. This means $h(z)=g(T(z))$ and thus $\|h(z)-h(y)\|_{\infty}\leq 2n^{2}(N-1)\delta\|z-y\|_{\infty}$. On the other hand, we have $\|h(x)-h(z)\|_{\infty}\leq 2\|x-z\|_{\infty}$. Putting these two expressions together, we obtain that $\|h(x)-h(y)\|_{\infty}\leq\max\{2,2n^{2}(N-1)\delta\}(\|x-z\|_{\infty}+\|z-y\|_{\infty})=\max\{2,2n^{2}(N-1)\delta\}\|x-y\|_{\infty}$. Here we used the fact that $z\in[x,y]$, which means that there exists $t\in$ such that $z=x+t(y-x)$ and thus

Step 3: Extending to $\bm{^{n+1}}$. The final step is to define a normalised $nD$-Borsuk-Ulam function $F:^{n+1}\to^{n}$ such that any $x\in\partial(^{n+1})$ with $\|F(x)\|_{\infty}\leq\varepsilon$ yields a solution to the $nD$-Tucker instance. For $x\in^{n+1}$ we write $x=(x^{\prime},x_{n+1})$, where $x^{\prime}\in^{n}$. We define

Consider any $x=(x^{\prime},x_{n+1})\in\partial(^{n+1})$ with $\|F(x)\|_{\infty}\leq\varepsilon$. Since $F$ is an odd function, we can assume that $x_{n+1}\geq 0$ (otherwise just use $-x$ instead of $x$). If $x_{n+1}=1$, then $F(x^{\prime},x_{n+1})=h(x^{\prime})$, and thus $\|h(x^{\prime})\|_{\infty}\leq\varepsilon$, which yields a solution to the $nD$-Tucker instance. If $x_{n+1}\in[0,1)$, then $x^{\prime}\in\partial(^{n})$ and thus $h(x^{\prime})=-h(-x^{\prime})$. This implies that $F(x^{\prime},x_{n+1})=h(x^{\prime})$ in this case too.

Finally, let us determine the Lipschitz parameter of $F$. Let $x,y\in^{n+1}$. We have

Putting these two expressions together, it follows that

Note that $\max\{3,2n^{2}(N-1)\delta+1\}\leq\max\{3,4n^{2}(N-1)\varepsilon+1\}$.