Answer: Polynomial-time solvable: in \(\mathrm P\).
Proposition 1 — class: other
Let \(\mathcal C_n\) be the polytope of Choquet capacities and \(T=\operatorname{ext}(\mathcal C_n)\) its extreme capacities, treated as voter types. Given rational alternatives \(X\subseteq[0,1]^n\) and aggregate elicitation statements \(P\) that constrain \(\bar v_\mu(A)=\sum_{t\in T}\mu_t v^t(A)\), where \(\mu\) is an unknown society distribution over \(T\), choose \(x\in X\) minimizing \(\max_{\mu\text{ consistent with }P}\max_{y\in X}\bigl(C_{\bar v_\mu}(y)-C_{\bar v_\mu}(x)\bigr)\).
Let \(N=\{1,\ldots,m\}\), where \(m=n\geq1\). Let \(\mathcal C_m\) consist of capacities \(v:2^N\to[0,1]\) satisfying \(v(\varnothing)=0\), \(v(N)=1\), and \(v(A)\leq v(B)\) whenever \(A\subseteq B\); types are \(T=\operatorname{ext}(\mathcal C_m)\). Write \(C_v\) for the standard Choquet integral.
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. \(\tau\) is the support size, not the number of possible types. Masses sum to \(1\), and \(\bar v_\mu(A)=\sum_{t\in\operatorname{supp}(\mu)}\mu_t v^t(A)\).
Here the society is unknown: neither its support nor its masses are supplied or bounded; admissible societies range over all rational distributions on \(T\).
The input is a nonempty explicit set \(X\subseteq[0,1]^m\) of rational alternatives, a finite list \(P\) of weak bounds \(\bar v_\mu(A)\geq\lambda\) or \(\bar v_\mu(A)\leq\lambda\), and a rational threshold \(r\in[0,1]\). Each coalition is encoded by its incidence vector and each \(\lambda\in[0,1]\) is rational; promise that some society satisfies \(P\).
A lower bound on \(A\) also applies to every superset, and an upper bound applies to every subset. Include the fixed endpoint values in the resulting intervals \([l_A,u_A]\).
Define \(R(X,P)=\min_{x\in X}\max_{\mu\models P}\max_{y\in X}\bigl(C_{\bar v_\mu}(y)-C_{\bar v_\mu}(x)\bigr)\); any minimizing alternative may be chosen.
Is deciding whether \(R(X,P)\leq r\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
State running times in \(m\), \(k=|X|\), \(p=|P|\), and total input bit length \(L\); any dependence on an explicitly represented society uses its actual support size \(\tau\), while the decision input contains no society.
For a single unknown capacity, any partial assignment satisfying the propagated intervals and inclusion monotonicity extends to a compatible capacity; the associated finite-alternative minimax-regret problem has a polynomial-size linear programming formulation. [Capacity elicitation results](https://doi.org/10.3233/978-1-61499-419-0-87).
The [extended treatment](https://hal.sorbonne-universite.fr/hal-01480147v3/document) also establishes this extension property. No result specifically treating the unknown society distribution above was verified.
The decision problem is in \(\mathrm P\). The key point is that unrestricted rational distributions on the extreme capacities produce exactly all rational capacities. The unknown society therefore introduces no additional restriction on its mean capacity.
Below is a self-contained proof, including the finite LP construction and its running time.
Call a capacity Boolean if all its values belong to \(\{0,1\}\).
Lemma 1. The extreme points of \(\mathcal C_m\) are exactly the Boolean capacities. Every rational capacity is the mean of a rational distribution on these extreme points.
Proof. First, let \(w\) be a Boolean capacity and suppose
\(w=\theta u+(1-\theta)v\),
where \(u,v\in\mathcal C_m\) and \(0<\theta<1\). At any coalition \(A\), both \(u(A)\) and \(v(A)\) lie in \([0,1]\). If \(w(A)=0\), the displayed equality forces \(u(A)=v(A)=0\). If \(w(A)=1\), it forces \(u(A)=v(A)=1\). Thus \(u=v=w\), proving that \(w\) is extreme.
Now take any capacity \(v\). List its distinct positive values as
\(0=a_0<a_1<\cdots<a_s=1\).
For each \(j\in\{1,\ldots,s\}\), define
\(w^j(A)=\mathbf 1\{v(A)\geq a_j\}\).
Each \(w^j\) is a Boolean capacity: monotonicity follows from that of \(v\), and its endpoint values are \(0\) and \(1\). Moreover,
\(v=\sum_{j=1}^s(a_j-a_{j-1})w^j\).
Indeed, if \(v(A)=a_h\), the right-hand side at \(A\) is \(\sum_{j=1}^h(a_j-a_{j-1})=a_h\); if \(v(A)=0\), it is zero. The weights are positive and sum to \(1\).
If \(v\) is not Boolean, then \(s\geq2\). At a coalition satisfying \(v(A)=a_1\), we have \(w^1(A)=1\) and \(w^j(A)=0\) for every \(j\geq2\). Consequently, the decomposition expresses \(v\) as a nontrivial convex combination of \(w^1\) and another capacity distinct from \(w^1\). Hence \(v\) is not extreme.
Finally, if \(v\) is rational, all the weights \(a_j-a_{j-1}\) are rational. Conversely, a rational distribution on Boolean capacities has rational mean values and its mean is a capacity. This proves both assertions. \(\square\)
Let \(\mathcal F_{\mathbb Q}(P)\) denote the rational capacities satisfying \(P\). Lemma 1 gives the exact equality
\(\{\bar v_\mu:\mu\text{ is an admissible rational society satisfying }P\}=\mathcal F_{\mathbb Q}(P)\).
This equality uses the absence of restrictions on society support or mass denominators.
For an alternative \(x\), choose a permutation \(\pi_x\) such that
\(x_{\pi_x(1)}\leq\cdots\leq x_{\pi_x(m)}\),
and put \(x_{\pi_x(0)}=0\). Define the tail coalitions
\(A_i^x=\{\pi_x(i),\ldots,\pi_x(m)\}\).
The standard Choquet formula on nonnegative alternatives is
\(C_v(x)=\sum_{i=1}^m\bigl(x_{\pi_x(i)}-x_{\pi_x(i-1)}\bigr)v(A_i^x)\).
Ties cause no difficulty because the corresponding increments are zero.
Fix an ordered pair \((x,y)\in X^2\). Let \(\mathcal S_{xy}\) contain:
Write \(q_{xy}=|\mathcal S_{xy}|\). Then
\(q_{xy}\leq Q:=2m+p+2\).
Only values on this set are needed to evaluate \(C_v(y)-C_v(x)\).
For completeness, the propagated intervals can be calculated without enumerating all coalitions. Augment the lower-bound list by \((\varnothing,0)\) and \((N,1)\), and augment the upper-bound list by the same endpoint bounds. Then, for any queried coalition \(A\),
\(l_A=\max\{\lambda:(B,\lambda)\text{ is an augmented lower bound and }B\subseteq A\}\),
\(u_A=\min\{\lambda:(B,\lambda)\text{ is an augmented upper bound and }A\subseteq B\}\).
The augmented lists make both extrema well-defined. Every compatible capacity satisfies these intervals by monotonicity.
Consider variables \(z_A\), indexed by \(A\in\mathcal S_{xy}\), with constraints
\(l_A\leq z_A\leq u_A\quad\text{for every }A\in\mathcal S_{xy}\),
\(z_A\leq z_B\quad\text{whenever }A,B\in\mathcal S_{xy}\text{ and }A\subseteq B\).
Denote the resulting polytope by \(H_{xy}\).
Lemma 2. Every point of \(H_{xy}\) extends to a capacity satisfying \(P\). Every rational point extends to a rational capacity satisfying \(P\). Conversely, restricting any capacity satisfying \(P\) to \(\mathcal S_{xy}\) gives a point of \(H_{xy}\).
Proof. The converse follows directly from monotonicity and propagated bounds.
For the extension, given \(z\in H_{xy}\), define on every coalition \(D\subseteq N\)
\(\widehat v(D)=\max\{z_A:A\in\mathcal S_{xy},\ A\subseteq D\}\).
The set in this maximum is nonempty because \(\varnothing\in\mathcal S_{xy}\).
If \(D\in\mathcal S_{xy}\), inclusion monotonicity of the assigned values gives \(z_A\leq z_D\) for every indexed \(A\subseteq D\). Since \(D\) itself is eligible in the maximum, \(\widehat v(D)=z_D\). Thus the extension agrees with every assigned value.
If \(D\subseteq E\), the eligible coalitions for \(D\) form a subset of those for \(E\), so \(\widehat v(D)\leq\widehat v(E)\). Every assigned value lies in \([0,1]\), and the endpoint intervals force \(z_\varnothing=0\) and \(z_N=1\). Therefore \(\widehat v\in\mathcal C_m\).
Every coalition mentioned in \(P\) belongs to \(\mathcal S_{xy}\). Its assigned interval includes its original bound, so the extension satisfies \(P\). If all assigned values are rational, every extension value, being a maximum of finitely many such values, is rational. \(\square\)
Thus the finite constraints are sufficient; no omitted coalition introduces a further restriction.
For the ordered pair \((x,y)\), solve the LP with feasible polytope \(H_{xy}\) and objective
\(\max_{z\in H_{xy}}\left[\sum_{i=1}^m\bigl(y_{\pi_y(i)}-y_{\pi_y(i-1)}\bigr)z_{A_i^y}-\sum_{i=1}^m\bigl(x_{\pi_x(i)}-x_{\pi_x(i-1)}\bigr)z_{A_i^x}\right]\).
Call its optimal value \(D_{xy}\).
Lemma 3. This LP optimum is attained by an admissible rational society, and
\(D_{xy}=\max_{\mu\models P}\bigl(C_{\bar v_\mu}(y)-C_{\bar v_\mu}(x)\bigr)\).
Proof. By the feasibility promise, some compatible society exists. Its mean restricts to a feasible point of \(H_{xy}\), so this polytope is nonempty. It is closed and contained in \([0,1]^{q_{xy}}\), hence compact.
Every admissible society supplies a feasible point with the same objective value, so its pairwise regret is at most \(D_{xy}\).
The LP has rational constraints and a rational objective. A linear objective on a nonempty compact polytope attains its maximum at a vertex. Every vertex of a rational polytope is rational: it is the unique solution of a full-rank subsystem of tight rational constraints, and rational Gaussian elimination gives rational coordinates.
Choose such a rational optimal vertex \(z^*\). Lemma 2 extends it to a rational compatible capacity \(\widehat v\), and Lemma 1 represents \(\widehat v\) as the mean of an admissible rational society. The Choquet formulas depend only on the assigned values, so this society attains \(D_{xy}\). \(\square\)
In particular, restricting societies to rational distributions does not merely preserve a supremum: the pairwise maxima are attained.
The construction also gives a support bound for an attaining society. The extension in Lemma 2 takes values only among the assigned \(z_A^*\). Since \(z_\varnothing^*=0\), it has at most \(q_{xy}-1\) distinct positive values. The threshold decomposition in Lemma 1 therefore uses at most \(q_{xy}-1\) types. This is an existence result; the algorithm does not need to represent those types.
For a fixed \(x\), finiteness of \(X\) and Lemma 3 imply
\(\max_{\mu\models P}\max_{y\in X}\bigl(C_{\bar v_\mu}(y)-C_{\bar v_\mu}(x)\bigr)=\max_{y\in X}D_{xy}\).
To check both inequalities explicitly, every pairwise regret under every society is bounded by the corresponding \(D_{xy}\), giving the upper bound. For the lower bound, choose \(y\) attaining \(\max_yD_{xy}\) and a society attaining that pair’s optimum. Under that society, the maximum over all alternatives is at least \(D_{xy}\).
Consequently,
\(R(X,P)=\min_{x\in X}\max_{y\in X}D_{xy}\).
The algorithm solves the \(k^2\) pairwise LPs, computes each row maximum and then their minimum, and compares the resulting rational number with \(r\). Any alternative attaining the minimum is a valid minimax-regret choice.
The following bounds use bit complexity, with \(L\) the total input bit length and \(Q=2m+p+2\).
Sorting all alternatives requires \(O(km\log(m+1))\) rational comparisons. Each pairwise LP has at most \(Q\) variables and \(O(Q^2)\) constraints.
For each pair:
Polynomial-time rational linear programming therefore solves each LP exactly in time polynomial in \(Q\) and \(L\). The optimum values have polynomial bit length, so the final comparisons also take polynomial time. Altogether, the running time is
\(O\!\left(km\log(m+1)\operatorname{poly}(L)+k^2\operatorname{poly}(m+p,L)\right)\).
There is no dependence on \(\tau\), because the decision input contains no represented society and the algorithm never enumerates types or society supports.
Thus the requested decision problem is polynomial-time solvable.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned decision problem correctly. The reduction, finite LP formulation, attainment argument, and polynomial bit-complexity bound all stand. No major or minor issues were found.
Lemma 1 correctly identifies the extreme points as Boolean capacities. A convex combination yielding a Boolean value at any coalition forces both constituent values to equal that value, proving extremality.
The threshold decomposition is valid: each threshold function is monotone, has the required endpoint values, and the weights are positive and telescope to the original capacity values. For a non-Boolean capacity, \(0<a_1<1\), and the coalition with value \(a_1\) distinguishes the first threshold capacity from the convex combination of the remaining ones. Thus the decomposition genuinely establishes non-extremality.
Rational capacities yield rational weights, and rational distributions on Boolean capacities yield rational capacities. Consequently, the stated equality between admissible society means and rational compatible capacities is exact. It uses precisely the task’s absence of support and denominator restrictions.
The displayed Choquet formula is correct for alternatives in \([0,1]^m\). Sorting coordinates in ascending order and using tail coalitions gives the stated increments. Equal coordinates introduce zero increments, so arbitrary ordering within ties is harmless.
The set \(\mathcal S_{xy}\) contains every coalition needed by the objective, every explicitly constrained coalition, and both endpoints. Its cardinality satisfies \(q_{xy}\leq 2m+p+2\), including when coalitions coincide.
The formulas propagate lower bounds to supersets and upper bounds to subsets in the correct directions. The added lower bound at \(\varnothing\) and upper bound at \(N\) make the extrema well-defined and enforce values in \([0,1]\). The other endpoint bounds force the endpoint values themselves.
Every capacity satisfying \(P\) satisfies these intervals. The feasibility promise rules out conflicting bounds.
Lemma 2 is correct. The maximum defining \(\widehat v(D)\) is always over a nonempty finite set. At an indexed coalition \(D\), the inclusion constraints bound every eligible value by \(z_D\), while \(z_D\) itself is eligible; hence the extension agrees with the assignment.
Inclusion of coalitions enlarges the eligible set, establishing monotonicity. The interval constraints and indexed endpoints give the required range and normalization.
Every original bound is satisfied because its coalition is indexed and its propagated interval enforces that bound. Rational assigned values produce rational extension values. The converse restriction statement also follows directly from the constraints.
The feasible polytope is nonempty by the promise, closed, and bounded. The vertex-attainment theorem applies to its linear objective. The rationality argument for vertices is valid, including for a lower-dimensional polytope: a full-rank subsystem of tight constraints determines each vertex.
The optimal rational assignment therefore extends to a rational compatible capacity and then to an admissible rational society. Its objective agrees with the LP objective because all required tail coalitions are indexed.
This establishes an attained maximum over rational societies, rather than merely equality of suprema. The stated support bound is also valid: the extension introduces no values outside the assigned values, leaving at most \(q_{xy}-1\) distinct positive values.
The exchange of the two maxima is justified explicitly. Every society’s regret against any alternative is bounded by the corresponding pairwise optimum. Conversely, an alternative attaining the largest pairwise optimum has an attaining society by Lemma 3.
Thus the formula \(R(X,P)=\min_{x\in X}\max_{y\in X}D_{xy}\) follows. It does not require one society to attain every pairwise optimum simultaneously. The argument covers \(k=1\), and any minimizing alternative is permitted by the task.
Each LP has at most \(Q=2m+p+2\) variables and \(O(Q^2)\) constraints. The stated coalition construction, inclusion-testing, and interval-comparison counts are valid.
Each objective variable receives at most one contribution from each alternative’s strictly nested tail chain. Consequently, combining its coefficients uses only a constant number of coordinate differences, as claimed. Numerical coefficient lengths are \(O(L)\), and the dense encoding bound \(O(Q^3+QL)\) is consistent with the constraint matrix, bounds, and objective.
Polynomial-time rational LP optimization applies to these feasible bounded instances and permits exact comparison with \(r\). Solving \(k^2\) such LPs gives the claimed polynomial running time in \(m,k,p,L\). No represented society is processed, so no dependence on \(\tau\) is required.
No additional clarification is needed to make the argument verifiable.
⟨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.