Answer: The decision problem is \(\mathrm{NP}\)-complete, and exact optimization is \(\mathrm{NP}\)-hard, even with binary catalogue coordinates, equal masses, and uncertainty polytopes of dimension \(p-1\).
Lemma 3.2 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateLet 𝑟 be an upper bound of SMMR𝑘 W (A), W′ ⊆W and B ⊆A. For 𝑤∈W, let Γ𝑤 be the set of 𝛼∈A such that ValA(𝑤) −𝑢𝑤(𝛼) < 𝑟. Then SMRW′(B, A) < 𝑟 if and only if for all 𝑤∈W′, there exists 𝛼∈B such that 𝛼∈Γ𝑤.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a rational catalogue \(A\subseteq\mathbb{Q}^p\), a shortlist size \(k\), and \(\tau\) preference types with rational masses \(\mu_t\geq 0\), \(\sum_t\mu_t=1\), and nonempty rational uncertainty polytopes \(W_t\subseteq\{w\in\mathbb{R}^p:w_i\geq0,\sum_i w_i=1\}\), find a common \(k\)-item shortlist \(B\subseteq A\) minimizing \(R_\mu(B)=\max_{(w_t)\in\prod_t W_t}\sum_t\mu_t\bigl(\max_{a\in A}a\cdot w_t-\max_{b\in B}b\cdot w_t\bigr)\), and compute its exact value.
An explicitly listed catalogue is \(A\subseteq\mathbb{Q}^{p}\), with \(m=|A|\geq1\), \(p\geq1\), arbitrary signed coordinates, and integer \(1\leq k\leq m\).
A society is given by its support: a list of \(\tau\) types with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
Each type has a nonempty uncertainty polytope \(W_t\subseteq\{w\in\mathbb{R}^{p}:w_i\geq0,\ \sum_iw_i=1\}\), given by an explicit system of weak rational linear inequalities; lower-dimensional polytopes are allowed.
Utility is \(a\cdot w\), with larger values preferred. Each type chooses a utility-maximizing item from the common shortlist; ties have no effect on regret.
For \(B\subseteq A\) with \( |B|=k\), define \(R_\mu(B)=\max_{(w_t)\in\prod_tW_t}\sum_{t=1}^{\tau}\mu_t\bigl(\max_{a\in A}a\cdot w_t-\max_{b\in B}b\cdot w_t\bigr)\). The optimization problem asks for a minimizing shortlist and its exact value.
Let \(L\) be the total binary input length, including all polytope descriptions and any rational threshold \(q\); state running times in \(m,\tau,p,k,L\).
Is exact optimization of \(R_\mu(B)\) polynomial-time solvable, or is its decision version—whether some \(B\subseteq A\) with \( |B|=k\) satisfies \(R_\mu(B)\leq q\)—NP-hard?
For a finite nonempty scenario set \(S\), the known discrete equivalence is \(\max_{w\in S}(\max_{a\in A}a\cdot w-\max_{b\in B}b\cdot w)<r\) if and only if every \(w\in S\) has some \(b\in B\) satisfying \(\max_{a\in A}a\cdot w-b\cdot w<r\); this supports exact search with cardinality-constrained SAT pruning. [Toffano, Viappiani and Wilson](https://ifaamas.csc.liv.ac.uk/Proceedings/aamas2021/pdfs/p1326.pdf)
No result settling exactly the mass-weighted optimization problem above was located.
The decision problem is \(\mathrm{NP}\)-complete. Consequently, computing an optimal shortlist and its exact value is \(\mathrm{NP}\)-hard and has no polynomial-time algorithm unless \(\mathrm{P}=\mathrm{NP}\).
Hardness holds even when all catalogue coordinates are binary, all masses are equal, and every uncertainty polytope has dimension \(p-1\), the full dimension of the simplex. Thus the conclusion does not depend on allowing singleton uncertainty sets.
For a prescribed shortlist, however, its exact regret is polynomial-time computable.
Write \(\Delta_p=\{w\in\mathbb{R}^p:w_i\geq0,\ \sum_iw_i=1\}\). For a nonempty \(B\subseteq A\), define
\(g_B(w)=\max_{a\in A}a\cdot w-\max_{b\in B}b\cdot w\), and \(r_t(B)=\max_{w\in W_t}g_B(w)\).
Each \(W_t\) is nonempty and compact: its weak inequalities define a closed set, and it lies in the bounded simplex. The function \(g_B\) is continuous, so every maximum defining \(r_t(B)\) is attained.
Because the types’ uncertainty choices are independent,
\(R_\mu(B)=\sum_{t=1}^{\tau}\mu_t r_t(B)\).
Indeed, every feasible tuple gives a sum at most the right-hand side. Choosing a maximizing \(w_t\) for each type simultaneously attains equality.
For each \(t\) and \(a\in A\), let
\(v_{t,a}(B)=\max\{z:w\in W_t,\ z\leq(a-b)\cdot w\text{ for every }b\in B\}\).
For fixed \(w\), the largest feasible \(z\) equals
\(\min_{b\in B}(a-b)\cdot w=a\cdot w-\max_{b\in B}b\cdot w\).
Interchanging the two maxima, one over a finite set and the other over a compact set, therefore gives
\(r_t(B)=\max_{a\in A}v_{t,a}(B)\).
Thus evaluation requires exactly \(m\tau\) rational linear programs, each with \(p+1\) variables and \(k\) additional shortlist inequalities.
To check boundedness explicitly, set \(M=\max_{a\in A,\ i}|a_i|\). Since every feasible \(w\) belongs to \(\Delta_p\), one has \(|(a-b)\cdot w|\leq2M\). We may therefore add \(-2M\leq z\leq2M\) without changing the optimum. The resulting feasible region is a nonempty bounded rational polytope, even if \(W_t\) is lower-dimensional.
We use the standard rational linear programming theorem: an explicitly encoded rational linear program can be solved in time polynomial in its binary encoding length, with an exact rational optimum when finite. This is the polynomial-time linear programming result originating with [Khachiyan](https://www.mathnet.ru/eng/dan42319). The hypotheses hold here: every coefficient is rational, the constraints are explicit, and the preceding bounds establish feasibility and boundedness.
Every constructed program has encoding length polynomial in \(p,k,L\). Its optimum has polynomial binary length, and taking maxima and forming the mass-weighted sum preserves polynomial binary length. Hence, for some fixed polynomial \(P\), exact evaluation takes time
\(O\!\left(m\tau P(p,k,L)\right)\).
A certificate for the decision problem is a list of \(k\) distinct catalogue indices. Checking the indices, computing the exact regret, and comparing it with \(q\) are polynomial-time operations. Therefore the decision problem belongs to \(\mathrm{NP}\).
We reduce from the standard \(\mathrm{NP}\)-complete satisfiability problem for formulas whose clauses contain at most three literals, listed in [Karp’s original paper](https://www2.seas.gwu.edu/~simhaweb/champalg/tsp/papers/KarpOriginal.pdf).
Let the source formula have variables \(x_1,\ldots,x_n\) and nonempty clauses \(C_1,\ldots,C_c\), with \(n,c\geq1\). These restrictions preserve hardness: formulas with an empty clause or no clauses can be replaced, respectively, by a fixed unsatisfiable or satisfiable formula satisfying the restrictions.
Set \(N=n+c\). We construct
\(m=2n,\qquad k=n,\qquad \tau=N,\qquad p=N+2n=3n+c\).
Label the coordinates as follows:
For each literal \(\ell\), construct an item \(a^\ell\in\{0,1\}^p\) by the rules:
All remaining entries are zero. The private coordinates ensure that all \(2n\) items are distinct, as required for a catalogue defined as a set.
Call the variable and clause coordinates the test coordinates. Every test coordinate has catalogue maximum \(1\): both literals of a variable have value \(1\) at its variable coordinate, and every clause is nonempty.
Say that \(B\) covers a test coordinate \(j\) if some \(b\in B\) has \(b_j=1\).
There is one type for each test coordinate \(j\), with mass
\(\mu_j=1/N\).
Set \(\varepsilon=1/(2N)\), and define
\(W_j=\{w\in\Delta_p:w_j\geq1-\varepsilon\},\qquad q=\varepsilon\).
These polytopes have explicit weak rational descriptions. They are nonempty because \(e_j\in W_j\).
They also have dimension \(p-1\). To verify this, consider the point with
\(w_j=1-\varepsilon/2,\qquad w_i=\varepsilon/(2(p-1))\quad(i\neq j)\).
Every coordinate is strictly positive and \(w_j>1-\varepsilon\). Consequently, a sufficiently small neighborhood of this point within the hyperplane \(\sum_iw_i=1\) remains in \(W_j\).
The catalogue has \(2np\) binary entries. Each polytope uses \(p\) nonnegativity inequalities, two inequalities for the simplex equality, and one additional inequality. Masses and thresholds have binary length \(O(\log N)\). The entire construction therefore has size, and can be produced in time, polynomial in the source input length.
Fix a type \(j\), and choose \(b\in B\) with \(b_j=1\). For every \(w\in W_j\), binary nonnegative catalogue coordinates imply
\(\max_{a\in A}a\cdot w\leq1\),
whereas
\(\max_{b'\in B}b'\cdot w\geq b\cdot w\geq w_j\geq1-\varepsilon\).
Thus \(g_B(w)\leq\varepsilon\), so \(r_j(B)\leq\varepsilon\). Summing over the equal masses gives
\(R_\mu(B)\leq\sum_{j=1}^{N}(1/N)\varepsilon=\varepsilon=q\).
Suppose \(j\) is uncovered. At the feasible point \(w=e_j\), every selected item has utility \(0\), while the catalogue maximum is \(1\). Hence \(r_j(B)\geq1\).
All type regrets are nonnegative because \(B\subseteq A\). Therefore
\(R_\mu(B)\geq\mu_jr_j(B)\geq1/N>1/(2N)=q\).
We have proved the exact equivalence
\(R_\mu(B)\leq q\quad\Longleftrightarrow\quad B\text{ covers every test coordinate}\).
Suppose the formula is satisfiable. Select the item corresponding to the true literal of each variable. This produces exactly \(n=k\) items and covers every variable coordinate. Every clause has a true literal, so every clause coordinate is also covered. Section 3 gives \(R_\mu(B)\leq q\).
Conversely, suppose a shortlist of exactly \(n\) items satisfies \(R_\mu(B)\leq q\). It covers all test coordinates.
Only \(a^{x_i}\) and \(a^{\neg x_i}\) cover variable coordinate \(v_i\). Thus the shortlist must contain at least one item from each of the \(n\) disjoint literal pairs. Since it contains exactly \(n\) items, it contains exactly one item from each pair.
Assign \(x_i\) true precisely when \(a^{x_i}\) is selected. Every clause coordinate is covered by a selected literal occurring in that clause. That literal is true under the assignment, so every clause is satisfied.
This proves a polynomial many-one reduction and establishes \(\mathrm{NP}\)-hardness. Together with Section 1, it proves \(\mathrm{NP}\)-completeness.
An exact optimization algorithm would decide the decision problem by comparing its returned value with \(q\). Exact optimization is therefore \(\mathrm{NP}\)-hard.
There is nevertheless an exact exhaustive algorithm: enumerate all shortlists of size \(k\), evaluate each by Section 1, and retain one with minimum value. Its running time is
\(O\!\left(\binom{m}{k}\,m\tau P(p,k,L)\right)\).
In particular, this is at most \(O\!\left(m^{k+1}\tau P(p,k,L)\right)\), so optimization is polynomial-time solvable for every fixed \(k\). For \(k=m\), the optimum is immediately \(0\).
The finite-scenario SAT equivalence mentioned in the question concerns a common maximum-regret threshold, as developed by [Toffano, Viappiani and Wilson](https://ifaamas.csc.liv.ac.uk/Proceedings/aamas2021/pdfs/p1326.pdf). The proof above directly handles the mass-weighted objective: independence permits exact evaluation by separate linear programs, while the constructed threshold gap makes shortlist selection \(\mathrm{NP}\)-complete.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly. The decision problem is \(\mathrm{NP}\)-complete, and exact optimization is \(\mathrm{NP}\)-hard, including under the stated restrictions to binary catalogue coordinates, equal masses, and uncertainty polytopes of full simplex dimension. I found no major or minor mathematical issues.
Each \(W_t\) is closed, bounded, and nonempty under the task’s assumptions, hence compact. Both catalogue and shortlist maxima are continuous functions of \(w\), since they are maxima of finitely many linear functions. Their difference \(g_B\) is therefore continuous and attains its maximum on each \(W_t\).
The equality
\[
R_\mu(B)=\sum_{t=1}^{\tau}\mu_t r_t(B)
\]
is justified by the argument given. Positive masses yield the upper bound for every feasible tuple, and independently chosen typewise maximizers attain that bound simultaneously. No common uncertainty choice or coupling constraint is silently introduced.
For fixed \(a\) and \(w\), the inequalities on \(z\) give exactly
\[
\max z=\min_{b\in B}(a-b)\cdot w
=a\cdot w-\max_{b\in B}b\cdot w.
\]
Thus each program computes the maximum of the indicated function over \(W_t\).
Taking the maximum over \(a\in A\) then recovers \(r_t(B)\). The exchange involves two maximizations, over a finite catalogue and a compact uncertainty set; it is valid and requires no minimax theorem. In particular, the prover does not incorrectly interchange a maximum with the minimum over \(B\).
The bound \(\lvert(a-b)\cdot w\rvert\leq2M\) is valid for arbitrary signed catalogue coordinates because \(w\) has nonnegative coordinates summing to one. Consequently, the added bounds on \(z\) preserve the optimum. The bounded program remains nonempty: every feasible \(w\) admits \(z=-2M\).
These arguments also cover \(M=0\), \(p=1\), and lower-dimensional uncertainty polytopes. No interior-point assumption is needed.
The stated rational linear programming theorem applies to explicit rational constraints and provides polynomial-time exact optimization in the binary encoding model. The feasibility-to-optimization framework is documented in the [MIT linear programming notes](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf).
Coefficient differences and the added bounds have polynomial encoding length. Exact optimal values have polynomial binary length; taking finite maxima and summing the explicitly listed rational mass-weighted values preserves a polynomial bound. Therefore the evaluation time
\[
O\!\left(m\tau P(p,k,L)\right)
\]
is justified. The polytope constraint counts and coefficient lengths are included in \(L\).
A shortlist certificate consists of \(k\) distinct catalogue indices and has polynomial length. The verifier can check cardinality, compute its exact regret using the preceding algorithm, and compare it with the rational threshold.
This establishes membership in \(\mathrm{NP}\), despite the continuous uncertainty sets. Exact comparison also handles equality at the threshold and negative thresholds.
Satisfiability with at most three literals per clause is a valid \(\mathrm{NP}\)-complete source problem, as stated in [Karp’s paper](https://www2.seas.gwu.edu/~simhaweb/champalg/tsp/papers/KarpOriginal.pdf). The restrictions to nonempty clauses and positive variable and clause counts preserve hardness through the stated treatment of trivial source instances.
The dimensions and counts are internally consistent:
\[
m=2n,\qquad k=n,\qquad \tau=n+c,\qquad p=3n+c.
\]
In particular, the constructed shortlist size satisfies the target’s required range. Private coordinates distinguish all catalogue items. Every test coordinate has catalogue maximum one, including clause coordinates because clauses are nonempty.
There are exactly \(N\) positive masses, each equal to \(1/N\), so they sum to one. The output descriptions and their rational coefficients have polynomial total encoding length.
Every \(W_j\) contains \(e_j\), proving nonemptiness. The displayed interior point has coordinates summing to one, all strictly positive, and satisfies the extra inequality strictly.
Here \(N\geq2\) and \(p\geq4\), so all denominators are valid. A sufficiently small neighborhood within the simplex’s affine hyperplane remains feasible. This establishes dimension \(p-1\), exactly as claimed.
For a covered coordinate \(j\), the selected covering item has utility at least \(w_j\), while every catalogue item has utility at most one. Hence the regret is at most \(\varepsilon\) throughout \(W_j\), and covering all test coordinates gives weighted regret at most \(q=\varepsilon\).
For an uncovered coordinate, the feasible point \(e_j\) gives regret one. Other type regrets cannot cancel this contribution because \(B\subseteq A\) makes them nonnegative. Therefore
\[
R_\mu(B)\geq\frac1N>\frac1{2N}=q.
\]
The strict gap is correct and proves both directions of the claimed coverage equivalence for the weak decision threshold.
A satisfying assignment selects one true literal per variable, producing exactly \(n\) distinct items and covering every variable and clause coordinate.
Conversely, covering all variable coordinates requires at least one item from each of \(n\) disjoint literal pairs. Exact shortlist cardinality forces exactly one from each pair. Under the stated assignment, every selected literal is true, so coverage of each clause coordinate implies satisfaction of that clause.
Neither direction assumes distinct literals within clauses or excludes tautological clauses.
Exact optimization would decide the threshold problem by comparing its returned value with \(q\), so the hardness conclusion follows. Exhaustive enumeration evaluates every feasible shortlist and returns a minimizing shortlist and its exact value within
\[
O\!\left(\binom{m}{k}m\tau P(p,k,L)\right).
\]
The upper bound using \(m^k\), polynomial-time solvability for each fixed \(k\), and zero optimum for \(k=m\) are all correct.
The final discussion accurately distinguishes the weighted objective from the finite-scenario maximum-regret setting in [Toffano, Viappiani and Wilson](https://ifaamas.csc.liv.ac.uk/Proceedings/aamas2021/pdfs/p1326.pdf). The new complexity conclusion rests on the supplied reduction, not on that paper.
No repair or additional clarification is required.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.