Maximal Number of Points in Co-Pareto-Front

Question

Let $n \in \mathbb{N}$ be some big number and $d \in \mathbb{N}_{\geq 1}$ be a number of dimensions. Let furthermore $f : (\{0, \ldots, n\})^d \rightarrow \mathbb{B}$ be some monotone oracle function, i.e., such that for each $\vec x, \vec x' \in (\{0, \ldots, n\})^d$ with $\vec x \leq_d \vec x'$ with $f(\vec x)=\mathbf{true}$, we have $f(\vec x')=\mathbf{true}$, where $\leq_d$ is the product order over elements from $(\{0, \ldots, n\})^d$.

We say that some point $\vec x$ is a Pareto point for $f$ if $f(x)=\mathbf{true}$ and for no $\vec x \neq \vec x'$, we have $\vec x' \leq_d \vec x$ and $f(x)=\mathbf{true}$.

Likewise, a co-Pareto point is some point $\vec x$ with $f(x)=\mathbf{false}$ and for no $\vec x \neq \vec x'$, we have $\vec x \leq_d \vec x'$ and $f(x)=\mathbf{false}$.

By these definitions, every oracle function $f$ has a fixed number of Pareto points $c_p(f)$ and co-Pareto points $c_c(f)$.

Question: How many co-Pareto points can a function $f$ have at most have for a given number of Pareto points $c_p(f)$ and for a given number of dimensions $d \in \mathbb{N}$?

More precisely, I am searching for an as-simple-as-possible representation of a function $g : \mathbb{N}_{\geq 1} \times \mathbb{N}_{\geq 1} \rightarrow \mathbb{N}$ such that for every $(d, c) \in \mathbb{N}_{\geq 1}^2 $, we have:

$$ g(d,c) = \max_{n \in \mathbb{N}, f : (\{0, \ldots, n\})^d \rightarrow \mathbb{B}, f \text{ is monotone}, c_p(f) = c} c_c(f) $$

Background: This question is rooted in multicriterial optimization over a discrete space of potential solutions. For instance, let $d = 2$ and $f$ be a function that maps from a number of bread rolls and a number of cabbages to whether there is some recipe for making dinner for a football team with these ingredients. If we have a combination of bread rolls and cabbages that is suitable for making dinner, then adding more bread rolls or adding cabbages will not change this. Hence, $f$ is monotone. For some fixed upper bound $n$, we can draw the values of $f$ into a diagram as follows:

Here, the dark green cells represent the Pareto points, i.e., the smallest combinations of resources suitable for making dinner. The dark blue cells, on the other hand, represent the co-Pareto points, i.e., the largest combinations of resources not suitable for making dinner.

In can be seen that for the function $f$ depicted in the Figure, we have $c_p(f)=4$, and $c_c(f)=5$. For $d=2$, it should be relatively easy to show that indeed the worst-case number of co-Pareto points is always the number of Pareto points plus one. Hence, we should have

$$ g(2,c) = c+1 $$

But for higher number of dimensions, the shape of $g$ is unknown. I acknowledge that I may simply have the wrong search terms to find a publication with a suitable result.

Known Lower Bound: For even $d = c$, we have that $g(d,c) \geq 3^{(c/2)}$. To see this, consider the set of Pareto points of the following form (for $0 \leq i < c/2-1$):

$$ (\underbrace{0,0,\ldots}_{2i \text{ many } 0s},1,2,\underbrace{\ldots,0,0}_{(c-2i-2) \text{ many } 0s}) $$ and $$ (\underbrace{0,0,\ldots}_{2i \text{ many } 0s},2,1,\underbrace{\ldots,0,0}_{(c-2i-2) \text{ many } 0s}) $$

The co-Pareto points in this case are arbitrary concatenations of $c/2$ many elements from of $\{(0,n), (1,1), (n,0)\}$, such as:

• $(0,n,0,n,\ldots,0,n)$
• $(0,n,0,n,\ldots,1,1)$
• $(0,n,0,n,\ldots,n,0)$
• $\ldots$
• $(n,0,n,0,\ldots,n,0)$

Answer 1

Here’s an upper bound of $g(d, c) = O(c^{\lfloor d/2\rfloor})$ for each fixed $d$:

Let the $i$th Pareto point be $\vec p_i = (p_{i1}, p_{i2}, \dotsc, p_{id})$ for each $1 \le i \le c$, and define $p_{0k} = n + 1$ for convenience, so that any co-Pareto point is described by $(p_{i_11} - 1, p_{i_22} - 1, \dotsc, p_{i_dd} - 1)$ for some $0 \le i_1, i_2, \dotsc, i_d \le c$. Perform the following procedure:

• Initialize $j_1 \leftarrow i_1, j_2 \leftarrow i_2, \dotsc, j_d \leftarrow i_d$.
• Initialize $h_1 \leftarrow 1, h_2 \leftarrow 1, \dotsc, h_d \leftarrow 1$.
• For each $k \leftarrow 1, 2, \dotsc, d$:
  • If $p_{j_k k} \ne p_{j_\ell k}$ for all $\ell \ne k$:
    • Choose $\ell \ne k$ to maximize $p_{j_\ell k}$ with $j_\ell \ne 0$.
    • Assign $j_k \leftarrow j_\ell$ and $h_k \leftarrow 0$.

This loop maintains the invariant that $(p_{i_11} - h_1, p_{i_22} - h_2, \dotsc, p_{i_dd} - h_d)$ is co-Pareto within the $(d - k)$-dimensional slice defined by fixing the first $k$ coordinates after step $k$.

The result is a tuple $(j_1, j_2, \dotsc, j_d)$ where every element occurs at least twice (there are $O(c^{\lfloor d/2\rfloor})$ such tuples for fixed $d$), and a tuple $(h_1, h_2, \dotsc, h_d)$ of bits (there are $O(1)$ such tuples for fixed $d$). Given these tuples, we can uniquely recover the original co-Pareto point:

• Initialize $i_1 \leftarrow j_1, i_2 \leftarrow j_2, \dotsc, i_d \leftarrow j_d$.
• For each $k \leftarrow d, d - 1, \dotsc, 1$:
  • If $h_k = 0$:
    • Assign $h_k = 1$.
    • Assign $i_k$ to minimize $p_{i_k k}$ such that $f(p_{i_11} - h_1, p_{i_22} - h_2, \dotsc, p_{i_dd} - h_d) = \mathbf{false}$.

Therefore, there are $O(c^{\lfloor d/2\rfloor})$ co-Pareto points.