Answer: Both preference families are polynomial-time solvable with zero queries under the stated feasible set.
Proposition 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateRBLS and RBGA can be implemented in such way that they run in polynomial time and ask no more than a polynomial number of queries for OWA aggregators and Choquet integrals. We remark first that the number of iteration steps of the outer loop is polynomial (in the problem size) for both procedures, and this is also the case for the size of X∗at each iteration step.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given τ types with rational masses μ_t, costs w_t, contribution vectors a_t∈ℚ_{≥0}^n, and a per-capita budget B, let F={z: 0≤z_t≤μ_t, ∑_t w_tz_t≤B} and y(z)=∑_t z_ta_t. An unknown OWA or 2-additive Choquet preference ω is accessed through pairwise comparison queries, and Θ records the answers. Does there exist an interactive algorithm, polynomial in the input bit length and τ in time and queries, that returns z∈F with max_{z'=z+q(e_u-e_v)∈F, q≥0} max_{ω∈Ω_Θ}[f_ω(y(z'))-f_ω(y(z))]≤δ, whenever such an allocation is attainable?
A society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; let \(m\ge2\) be the number of objectives.
Each type has cost \(w_t\in\mathbb Q_{\ge0}\) and contribution vector \(a_t\in\mathbb Q_{\ge0}^m\); the per-capita budget is \(B\in\mathbb Q_{\ge0}\). Define \(F=\{z\in\mathbb R^\tau:0\le z_t\le\mu_t,\ \sum_t w_tz_t\le B\}\) and \(y(z)=\sum_tz_ta_t\).
The input specifies one preference family: OWA with arbitrary nonnegative weights summing to one, applied to coordinates sorted increasingly; or normalized monotone Choquet integrals with Möbius coefficients supported on singletons and pairs. In the latter family, coefficients may be signed, additive capacities are included, and belief-function restrictions are not imposed.
A fixed unknown parameter \(\omega^*\) belongs to the specified family. A query compares any two binary-rational profiles \(a,b\in\mathbb Q_{\ge0}^m\); the oracle truthfully returns a weakly preferred profile, choosing either on equality. An answer preferring \(a\) records \((a,b)\).
The input includes a finite initial transcript \(\Theta_0\) consistent with \(\omega^*\) and a binary-rational tolerance \(\delta\ge0\). For any accumulated transcript, define \(\Omega_\Theta=\{\omega:f_\omega(a)\ge f_\omega(b)\text{ for every }(a,b)\in\Theta\}\).
Writing \(e_t\) for a coordinate unit vector, define \(R(z,\Theta)=\max_{u,v\in\{1,\ldots,\tau\},\ q\in\mathbb R_{\ge0}:\ z+q(e_u-e_v)\in F}\max_{\omega\in\Omega_\Theta}[f_\omega(y(z+q(e_u-e_v)))-f_\omega(y(z))]\). Only these equal-mass swaps are permitted; there is no prescribed selected mass.
An allocation is attainable if some rational \(z\in F\) and some finite truthful query transcript extending \(\Theta_0\) satisfy \(R(z,\Theta)\le\delta\). Let \(L\) be the total binary input length, including \(\Theta_0\) and \(\delta\).
For each preference family, is finding such an allocation whenever attainable possible with time and query count polynomial in \(m,\tau,L\), or is this promised interactive search problem NP-hard?
For discrete item selection, RBLS with a polynomial iteration cap and RBGA admit polynomial-time implementations using polynomially many comparisons for OWA and 2-additive Choquet preferences; the cap does not guarantee that RBLS terminates with the local regret bound. [Source](https://cassandreleroy.github.io/link/ECAI2020.pdf).
No result settling exactly the continuous interactive search problem above was located.
For both preference families, the problem as defined is polynomial-time solvable with zero queries: return \(z=0\).
Indeed, \(0\in F\). If \(u\ne v\), feasibility of \(q(e_u-e_v)\) requires its \(v\)-coordinate, \(-q\), to be nonnegative; hence \(q=0\). If \(u=v\), the allocation does not change. Every feasible swap therefore has utility gain zero, so \(R(0,\Theta_0)=0\le\delta\). Consistency ensures \(\Omega_{\Theta_0}\ne\varnothing\).
Thus every stated instance is attainable, including when \(\delta=0\). Writing the allocation takes polynomial time.
To go beyond this degenerate witness, the following results address allocations with a prescribed positive selected mass, including the maximum feasible selected mass. These are additional restrictions, not replacements for the stated feasible set.
Proven theorem. Fix a rational \(s\) such that the set
\(F_s=\{z\in F:\sum_t z_t=s\}\)
is nonempty. For either preference family, a finite comparison procedure returns a rational \(z^\star\in F_s\) and a truthful transcript \(\Theta\supseteq\Theta_0\) satisfying
\(f_\omega(y(z^\star))\ge f_\omega(y(z))\quad\text{for every }z\in F_s\text{ and every }\omega\in\Omega_\Theta.\)
Consequently, \(R(z^\star,\Theta)=0\).
The procedure uses at most
\(\binom{\,2\tau+1+\binom m2\,}{\tau-1}-1\)
queries. Its running time is polynomial for every fixed \(\tau\). All queried profiles and the returned allocation have encoding length polynomial in the input length and the encoding length of \(s\).
Write \(y_i(z)=\sum_t z_t a_{t,i}\). For each permutation \(\pi\) of the objectives, define the possibly empty polytope
\(P_\pi=\{z\in F_s:y_{\pi(1)}(z)\le\cdots\le y_{\pi(m)}(z)\}.\)
These polytopes cover \(F_s\).
For OWA preferences, throughout \(P_\pi\),
\(f_\omega(y(z))=\sum_{r=1}^m\omega_r y_{\pi(r)}(z),\)
which is linear in \(z\).
For a Choquet integral with singleton and pair Möbius coefficients \(c_i,c_{ij}\),
\(f_c(x)=\sum_i c_i x_i+\sum_{i<j}c_{ij}\min(x_i,x_j).\)
On a fixed coordinate-order region, each minimum equals a designated coordinate. Thus this expression is also linear in \(z\), regardless of the signs of the pair coefficients. At coordinate ties, either choice gives the same value.
Let \(\mathcal H\) contain the hyperplanes
\(z_t=0,\qquad z_t=\mu_t,\qquad \sum_t w_tz_t=B,\qquad y_i(z)=y_j(z)\quad(i<j).\)
There are at most \(N=2\tau+1+\binom m2\) such hyperplanes.
For every choice of \(\tau-1\) hyperplanes from \(\mathcal H\), combine their equations with \(\sum_tz_t=s\). If the resulting system has a unique solution, retain that solution whenever it belongs to \(F_s\). Call the resulting set \(V\).
Every vertex of every nonempty \(P_\pi\) belongs to \(V\). To justify this, let \(v\) be such a vertex. The active constraint normals at \(v\), including the selected-mass equality, span the ambient space. Otherwise, there would be a nonzero direction orthogonal to every active normal; sufficiently small moves in both directions would remain feasible, contradicting that \(v\) is a vertex. Starting with the nonzero normal of \(\sum_tz_t=s\), select \(\tau-1\) active normals completing a basis. Their hyperplanes all belong to \(\mathcal H\).
Consequently, \(V\) is nonempty and \(|V|\le\binom N{\tau-1}\). Rational linear algebra gives polynomial encoding length for each candidate.
For any fixed parameter \(\omega\), the utility is linear on each bounded polytope \(P_\pi\), so its maximum there is attained at a vertex. Therefore
\(\max_{z\in F_s}f_\omega(y(z))=\max_{v\in V}f_\omega(y(v)).\)
Run a sequential tournament on the profiles \(\{y(v):v\in V\}\), recording every answer.
After each comparison, the current winner dominates every candidate already processed for every parameter consistent with the comparisons so far. This follows inductively:
This reasoning permits either oracle answer on equality.
Let \(z^\star\) be the final winner. For every \(\omega\in\Omega_\Theta\), it dominates every member of \(V\), and hence every allocation in \(F_s\) by Step 2. Every permitted swap preserves \(\sum_tz_t=s\), so its gain is nonpositive. The zero-length swap gives gain zero. Thus \(R(z^\star,\Theta)=0\).
The value
\(s_{\max}=\max_{z\in F}\sum_tz_t\)
and a feasible allocation attaining it can be computed by rational linear programming in polynomial time. The feasible set is nonempty and bounded, so the maximum exists; an optimal rational solution and \(s_{\max}\) have polynomial encoding length.
Applying the theorem with \(s=s_{\max}\) gives a finite procedure even under this substantive restriction. For fixed \(\tau\), that procedure is polynomial-time and uses polynomially many comparisons. If \(s_{\max}>0\), its output is nonzero.
For variable \(\tau\), the enumeration bound can be exponential. It does not establish polynomial-time solvability in that regime.
Proven theorem. Given rational \(z\in F\) and a finite consistent transcript \(\Theta\), the value \(R(z,\Theta)\) is computable in polynomial time for both specified families, measured in their total encoding length.
Fix \(u\ne v\). Its feasible amounts form the interval \([0,Q_{uv}]\), where
\(Q_{uv}=\min\{\mu_u-z_u,\ z_v\}\)
if \(w_u\le w_v\). If \(w_u>w_v\), also include
\(\dfrac{B-\sum_t w_tz_t}{w_u-w_v}\)
in this minimum.
Along this interval, coordinate \(i\) has the form
\(x_i(q)=y_i(z)+q(a_{u,i}-a_{v,i}).\)
Two nonidentical affine coordinate functions cross at most once. Partition the interval at all their crossing points lying in it, together with its two endpoints. There are at most \(\binom m2+2\) distinct partition points.
For every fixed parameter, utility is affine between consecutive partition points by the formulas in Section 2. Its maximum on each subinterval therefore occurs at an endpoint. Writing \(E_{uv}\) for the partition points gives
\(R(z,\Theta)=\max\left\{0,\ \max_{u\ne v}\max_{q\in E_{uv}}\max_{\omega\in\Omega_\Theta}\bigl[f_\omega(x(q))-f_\omega(y(z))\bigr]\right\}.\)
All these points are rational with polynomial encoding length. It remains to solve polynomially many fixed-profile parameter optimizations.
For fixed profiles, utility is linear in the weights. The constraints are
\(\omega_r\ge0,\qquad \sum_r\omega_r=1,\)
together with the transcript inequalities
\(\sum_r\omega_r\bigl(a_{(r)}-b_{(r)}\bigr)\ge0\quad((a,b)\in\Theta).\)
Each endpoint optimization is consequently a rational linear program of polynomial size.
Let the associated capacity be
\(\nu(S)=\sum_{i\in S}c_i+\sum_{\{i,j\}\subseteq S}c_{ij}.\)
Normalization requires
\(\sum_i c_i+\sum_{i<j}c_{ij}=1.\)
Monotonicity is equivalent to nonnegative increments when adding a single element:
\(c_i+\sum_{j\in S}c_{ij}\ge0\quad\text{for every }i\text{ and }S\subseteq\{1,\ldots,m\}\setminus\{i\}.\)
For fixed \(i\), the smallest increment is obtained by including precisely its negative pair coefficients. Thus these conditions are equivalent to
\(c_i+\sum_{j\ne i}\min(0,c_{ij})\ge0.\)
Introduce one auxiliary variable \(h_{ij}\) per unordered pair, with constraints
\(h_{ij}\le0,\qquad h_{ij}\le c_{ij},\qquad c_i+\sum_{j\ne i}h_{ij}\ge0.\)
This formulation is exact:
There are only quadratically many variables and constraints. Both transcript inequalities and the endpoint objective are linear, using
\(f_c(x)=\sum_i c_i x_i+\sum_{i<j}c_{ij}\min(x_i,x_j).\)
Hence these optimizations are polynomial-size rational linear programs as well.
The maxima exist: OWA parameters form a compact simplex, while normalized monotone capacities have values in \([0,1]\), which bound their singleton and pair Möbius coefficients. Their consistent parameter sets are closed and nonempty.
There is another useful boundary case.
Let \(A=\max_{t,i}a_{t,i}\). For any allocation of selected mass \(s\), every outcome coordinate belongs to \([0,sA]\). Both normalized preference families satisfy
\(0\le f_\omega(x)\le\max_i x_i\)
for nonnegative \(x\). For Choquet preferences this follows from monotonicity and normalization; for OWA it follows from the nonnegative weights summing to one.
Every permitted swap preserves \(s\). Therefore, uniformly over every consistent parameter,
\(R(z,\Theta)\le sA.\)
Suppose \(\delta>0\) and a nonzero feasible allocation exists. Some type \(t\) then admits a positive feasible allocation by itself. If \(A>0\), choose a positive rational \(s\) satisfying
\(s\le\mu_t,\qquad w_ts\le B,\qquad s\le\delta/A.\)
The allocation \(z=se_t\) is nonzero and satisfies \(R(z,\Theta_0)\le\delta\), without queries. If \(A=0\), every utility gain is zero.
Thus requiring merely positive selected mass does not remove the shortcut when tolerance is positive.
The stated problem is completely settled: both families admit a polynomial-time, zero-query algorithm.
Beyond that witness, the proofs above establish polynomial-time regret evaluation and polynomial-time interactive search for fixed support size, even with maximum feasible selected mass and zero tolerance. They do not settle search complexity with variable support size under that additional mass requirement.
The cited paper’s polynomial guarantee concerns its capped RBLS procedure; its termination rule does not establish that the returned allocation satisfies the requested local regret bound. [Benabbou, Leroy and Lust, Section 4.1](https://cassandreleroy.github.io/link/ECAI2020.pdf).
⟨structured verdict parsed — rendered above⟩
The prover resolves the stated task correctly for both preference families. I found no major or minor mathematical issues. The additional results are also sound within their stated scope.
The proposed algorithm returns \(z=0\) without making queries.
This argument handles \(\delta=0\), \(B=0\), zero costs, and support size one.
The zero allocation is a degenerate witness, but it is explicitly permitted by the task: there is no prescribed selected mass, and only equal-mass swaps are allowed. Consequently, this is a valid resolution of the intended formulation as supplied, rather than reliance on an unstated interpretation.
The regions \(P_\pi\) cover \(F_s\), including profiles with coordinate ties. Both displayed utility formulas are linear in the allocation on each region.
For signed singleton and pair Möbius coefficients, the displayed Choquet formula applies to the nonnegative profiles under consideration. Negative pair coefficients do not affect linearity within a region. Coordinate ties give identical values whichever tied coordinate represents the minimum.
Assessment: correct.
The listed hyperplanes include every possible active inequality boundary of \(P_\pi\). The active-normal argument correctly establishes that, at a vertex, these normals together with the selected-mass equality span the ambient space.
The argument also covers lower-dimensional feasible regions: failure to span would permit sufficiently small feasible displacements in both directions, contradicting extremality. Since the selected-mass normal is nonzero, it can be included in a basis completed by \(\tau-1\) active normals.
The enumeration therefore includes every required vertex. Additional retained points cause no problem because they also belong to \(F_s\).
The candidate-count bound is correct. For fixed \(\tau\), it is polynomial in \(m\). Solving the rational systems and checking feasibility take polynomial time per candidate, and standard rational linear algebra provides polynomial encoding lengths.
For \(\tau=1\), the enumeration selects zero hyperplanes and uses the selected-mass equality alone, as required.
Assessment: correct.
Every nonempty \(P_\pi\) is compact, so its linear utility attains a maximum at a vertex. This verifies the reduction to \(V\) for each parameter separately.
The tournament invariant is also valid. Each comparison shrinks the consistent parameter set, preserving previously established inequalities. A new winner dominates the incumbent throughout the new consistent set, and transitivity then preserves dominance over all previously processed candidates. Arbitrary tie answers remain compatible with these weak inequalities.
Thus the final winner simultaneously maximizes utility over \(F_s\) for every remaining consistent parameter. Feasible swaps preserve selected mass, and the zero-length swap supplies gain zero, yielding \(R(z^\star,\Theta)=0\).
The query bound of at most \(\binom N{\tau-1}-1\) follows.
Assessment: correct.
The invoked rational linear programming result applies: the feasible set is nonempty and bounded, and the constraints and objective are rational. An exact optimal rational allocation and value have polynomial encoding length and can be computed in polynomial time.
The subsequent enumeration is polynomial for fixed \(\tau\). The prover correctly refrains from claiming this bound is polynomial for variable \(\tau\).
Assessment: correct and appropriately scoped.
For distinct \(u,v\), the stated upper bounds account for the receiving coordinate’s remaining capacity, the donating coordinate’s available mass, and the budget.
When \(w_u\le w_v\), cost cannot increase along the swap. When \(w_u>w_v\), the displayed budget bound is necessary and sufficient. All numerators are nonnegative because the starting allocation is feasible.
Assessment: correct.
Each coordinate is affine in the swap amount. Nonidentical coordinate functions have at most one crossing; identical functions need no partition point. The stated bound of \(\binom m2+2\) partition points is valid.
For each fixed parameter, utility is affine between consecutive partition points. Subtracting the fixed starting utility preserves this property. Therefore maximizing over these endpoints suffices uniformly for every parameter, including signed Choquet coefficients.
Crossing points and endpoint profiles have polynomial rational encoding length.
Assessment: correct.
The simplex constraints describe exactly the specified OWA family. Sorting fixed profiles introduces no parameter dependence, so transcript inequalities and regret objectives are linear in the weights. The resulting programs have polynomial size.
Assessment: correct.
The single-element increment inequalities characterize capacity monotonicity. Minimizing such an increment over subsets selects precisely the negative incident pair coefficients, giving the stated equivalent condition.
The auxiliary-variable formulation is exact in both directions:
Sharing one auxiliary variable between the two endpoints of a pair causes no additional restriction: the explicit choice offered by the prover satisfies both rows whenever the capacity is monotone.
Normalization and transcript consistency are represented correctly. The formulation has polynomially many variables and constraints and does not impose belief-function restrictions.
The compactness claim concerns the actual capacity coefficients, not necessarily the auxiliary variables. Normalized monotone capacities have bounded coefficients, and their consistent sets are closed and nonempty. Thus the required maxima exist.
Assessment: correct.
The coordinate bound for an allocation of selected mass \(s\) follows from nonnegative contributions bounded by \(A\). The utility bounds used are valid for both specified normalized monotone families.
Since every swap preserves \(s\), the uniform regret bound \(R(z,\Theta)\le sA\) follows.
A nonzero feasible allocation has a positive coordinate whose isolated allocation remains feasible, because all costs are nonnegative. The subsequent choice of a sufficiently small positive rational mass is available when \(\delta>0\) and \(A>0\). The case \(A=0\) is handled separately.
Assessment: correct.
The description of capped RBLS is consistent with the cited algorithm: its iteration cap supplies a stopping condition independent of achieving the regret stopping criterion. It therefore does not supply the continuous search guarantee requested here. [Benabbou, Leroy and Lust, Section 4.1](https://cassandreleroy.github.io/link/ECAI2020.pdf).
No repairs or additional mathematical clarification are necessary. The fixed-mass results are supplementary; their limitation for variable support size does not weaken the complete zero-query resolution of the original task.
⟨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.