Answer: Exact optimal-threshold computation is polynomial-time solvable; the threshold-existence decision problem belongs to \(\mathrm{P}\).
Theorem 3.1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere exists a mechanism with REG(T) = O(min(K, log log T)) against myopic agent.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite solution menu including the null solution, a finite set of complete deterministic voter-task types with rational masses summing to one, and rational principal and agent utilities for every type-solution pair, choose one global threshold q. Each type submits its principal-favoring agent-utility-maximizing solution among those with principal utility at least q; maximize the mass-weighted principal utility and output an optimal q.
A society is given by its support: a list of \(\tau\) complete deterministic types with positive binary-rational masses \(w_i\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
The common solution menu is \(A=\{\bot,a_1,\ldots,a_m\}\). Every type \(i\) has explicitly given binary-rational principal and agent utilities \(x_{ia},y_{ia}\in[0,1]\), with \(x_{i\bot}=y_{i\bot}=0\).
Choose one global rational threshold \(q\in[0,1]\). Type \(i\) chooses from \(B_i(q)=\{\bot\}\cup\{a\in A\setminus\{\bot\}:x_{ia}\ge q\}\), maximizing agent utility, then principal utility; remaining ties use the listed menu order. Write this choice as \(b_i(q)\).
Maximize \(F(q)=\sum_{i=1}^{\tau}w_i x_{i,b_i(q)}\) and output an optimal threshold. Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Is exact optimal-threshold computation polynomial-time in \(m,\tau,L\), or is deciding whether \(\max_{q\in\mathbb{Q}\cap[0,1]}F(q)\ge r\), for an input binary-rational \(r\in[0,1]\), NP-hard?
For one fixed deterministic utility profile and a myopic agent, an online mechanism achieves cumulative regret \(O(\min\{m,\log\log T\})\) over \(T\) rounds ([source](https://arxiv.org/pdf/2310.04884)). This is a regret guarantee, rather than an offline complexity classification.
No result settling the exact explicitly supported mass problem above was located in the literature search.
Exact optimal-threshold computation is polynomial-time solvable for the explicitly supported society in the question.
Let \(N=m\tau\). An optimal threshold can be found using
\[ O\!\left((N+\tau+2)\log(N+2)L^2\right) \]
bit operations with schoolbook integer arithmetic. Consequently, the threshold-existence decision problem belongs to \(\mathrm{P}\); it can be NP-hard under polynomial-time many-one reductions only if \(\mathrm{P}=\mathrm{NP}\).
Define
\[ C=\{0,1\}\cup\{x_{ia}:1\le i\le\tau,\ a\in A\setminus\{\bot\}\}. \]
Thus \(|C|\le N+2\), and every element of \(C\) is an admissible rational threshold.
Lemma. For every \(q\in[0,1]\), there exists \(c\in C\) such that \(B_i(q)=B_i(c)\) for every type \(i\). Consequently, \(F(q)=F(c)\).
Proof. Set \(c=\min\{t\in C:t\ge q\}\). This minimum exists because \(1\in C\).
For any nonnull action \(a\) of any type \(i\), if \(x_{ia}\ge c\), then \(x_{ia}\ge q\). Conversely, if \(x_{ia}\ge q\), then \(x_{ia}\in C\) makes it a candidate in the minimum defining \(c\), so \(x_{ia}\ge c\). Therefore,
\[ x_{ia}\ge q\quad\Longleftrightarrow\quad x_{ia}\ge c. \]
The null action is always eligible. Hence all eligible sets agree. Because the tie-breaking rule is fixed, all choices and their weighted objective values agree. This proves the lemma.
In particular,
\[ \max_{q\in\mathbb{Q}\cap[0,1]}F(q)=\max_{c\in C}F(c). \]
This proves both that an optimum exists and that an optimal threshold has an input-sized rational representation.
Directly evaluating every candidate already gives a polynomial algorithm using \(O((N+2)\tau(m+1))\) rational operations. The following sweep improves that bound.
Let \(\operatorname{pos}(a)\) be the position of action \(a\) in the listed menu order. For each type \(i\), define a strict total preference order by lexicographically comparing
\[ \bigl(y_{ia},x_{ia},-\operatorname{pos}(a)\bigr), \]
with larger tuples preferred. This is exactly the specified choice rule.
Create one event \((x_{ia},i,a)\) for every nonnull action, and add endpoint markers at \(0\) and \(1\). Sort these records by decreasing threshold value, grouping equal values together.
Maintain a current choice \(h_i\) for each type and a current objective \(S\).
\[ S\leftarrow S+w_i\bigl(x_{ia}-x_{i,h_i^{\mathrm{old}}}\bigr). \]
The endpoint markers ensure that \(0\) and \(1\) are evaluated even when no action has that principal utility.
We prove that, immediately after processing the group at threshold \(t\),
\[ h_i=b_i(t)\quad\text{for every }i, \qquad S=F(t). \]
Initially, each current choice is the best action in the singleton set \(\{\bot\}\), and \(S\) is its weighted principal utility.
After processing the group at \(t\), the actions inserted for type \(i\) are exactly its nonnull actions satisfying \(x_{ia}\ge t\): all larger-value groups have already been processed, the equal-value group has just been processed, and smaller-value groups have not yet been processed. Together with the permanently present null action, these actions constitute \(B_i(t)\).
For a strict total order, the maximum of a set after inserting one new element is the preferred of its previous maximum and the new element. Applying this fact to each insertion shows that \(h_i\) is the maximum of \(B_i(t)\), namely \(b_i(t)\).
Each replacement changes exactly one summand of the objective. The stated update therefore preserves
\[ S=\sum_{i=1}^{\tau}w_i x_{i,h_i}. \]
This proves the invariant. Processing the whole equal-value group before evaluation is essential because actions with \(x_{ia}=t\) are eligible at threshold \(t\).
Thus the algorithm evaluates \(F(t)\) exactly at every \(t\in C\). By the candidate-threshold lemma, its returned threshold is globally optimal.
We now justify the bit complexity; counting rational operations alone would not suffice.
Write the input masses and nonnull principal utilities as
\[ w_i=\frac{u_i}{v_i}, \qquad x_{ia}=\frac{p_{ia}}{d_{ia}}, \]
with positive denominators encoded in binary. Define the positive integer
\[ D=\left(\prod_{i=1}^{\tau}v_i\right) \left(\prod_{i=1}^{\tau}\prod_{a\ne\bot}d_{ia}\right). \]
The sum of the encoded denominator lengths is at most \(L\), so \(D\) has \(O(L)\) bits. For every nonnull action, precompute the integer
\[ c_{ia}=u_i p_{ia}\frac{D}{v_i d_{ia}} =D w_i x_{ia}, \]
and set \(c_{i\bot}=0\). The division is exact because \(v_i d_{ia}\) divides the displayed product defining \(D\).
Maintain the integer objective numerator
\[ Z=\sum_i c_{i,h_i} \]
instead of \(S\). A replacement updates \(Z\) by subtracting the old coefficient and adding the new one. Since all utilities lie in \([0,1]\) and the masses sum to \(1\),
\[ 0\le Z=D\sum_i w_i x_{i,h_i}\le D. \]
Thus all maintained objective values have \(O(L)\) bits.
Constructing \(D\) and all coefficients requires \(O(N+\tau)\) arithmetic operations on \(O(L)\)-bit integers. Rational comparisons for sorting or preference comparisons use cross multiplication and also cost \(O(L^2)\) bit operations with schoolbook arithmetic.
Sorting takes \(O((N+2)\log(N+2))\) comparisons. The sweep processes \(N\) action events and at most \(N+2\) threshold groups. Including initialization and preprocessing, the total bound is therefore
\[ O\!\left((m\tau+\tau+2)\log(m\tau+2)L^2\right). \]
For the decision problem, write \(r=s/t\) with \(t>0\). If \(Z^\star\) is the maximum recorded numerator, decide by the exact integer comparison
\[ tZ^\star\ge sD. \]
This adds only \(O(L^2)\) bit operations.
If \(m=0\), every type always chooses \(\bot\); returning \(q=0\) is optimal. The algorithm and bound cover this case as well.
The proof uses the explicitly listed support of size \(\tau\), and its running time depends on that supplied support size. It does not require enumerating any additional possible types.
The online cumulative-regret result in the [supplied paper](https://arxiv.org/pdf/2310.04884) is a separate learning guarantee. The offline complexity classification above follows directly from the finite candidate set and exact sweep.
⟨structured verdict parsed — rendered above⟩
The prover’s output resolves the assigned problem correctly. The finite candidate set, sweep algorithm, and exact bit-complexity analysis are sound. I found no major or minor issues requiring repair.
The set \(C\) contains both endpoints and every nonnull principal utility, so \(|C|\le m\tau+2\). Every candidate is rational and lies in the permitted interval.
For any \(q\in[0,1]\), the stated minimum \(c=\min\{t\in C:t\ge q\}\) exists because \(1\in C\). Both directions of the eligibility equivalence are justified:
The null action remains eligible at both thresholds. Thus all eligible sets coincide. Since the choice rule is deterministic and depends only on the eligible actions and their fixed utilities and menu positions, all selected actions coincide as well.
This establishes the claimed equality of maxima. It also establishes attainment at a rational candidate with an input-sized representation. There is no missing compactness or continuity assumption.
The direct-evaluation count \(O((N+2)\tau(m+1))\) rational operations correctly accounts for scanning every type’s menu at each candidate.
The lexicographic tuple \((y_{ia},x_{ia},-\operatorname{pos}(a))\), with larger tuples preferred, implements the specified tie-breaking rule. Distinct menu positions make this a strict total order, including the null action.
Descending processing is consistent with eligibility: after processing threshold \(t\), precisely the nonnull actions with \(x_{ia}\ge t\) have been inserted. Endpoint markers add no actions and ensure both endpoint candidates are evaluated.
Comparing each newly inserted action with the current maximum correctly maintains the maximum under the fixed total order. Multiple events for one type at the same threshold cause no problem: the algorithm evaluates only after the entire group has been processed.
The objective update uses the old action’s principal utility and therefore changes exactly the affected summand. The notation \(h_i^{\mathrm{old}}\) adequately specifies which value must be used.
Initialization correctly represents the singleton eligible set consisting of the null action before any events are inserted.
The proof establishes both required invariants after each threshold group:
Every candidate in \(C\) is evaluated, and retaining a threshold attaining the largest recorded value is sufficient; ties between optimal thresholds need no additional rule. Combined with the candidate-threshold lemma, this proves global optimality over the requested rational thresholds.
The common denominator construction is valid. Each product \(v_i d_{ia}\) divides \(D\), since the corresponding denominator factors occur in the defining product. This remains true when denominator values coincide or share factors.
The total encoded denominator length bounds the bit length of their product by \(O(L)\). Consequently, \(D\), the coefficient-construction intermediates, and the relevant rational-comparison products all have \(O(L)\) bits.
Each coefficient satisfies the stated identity \(c_{ia}=D w_i x_{ia}\) and is an integer. The null coefficient is correctly set to zero.
The bound \(0\le Z\le D\) follows from the nonnegative utilities, their upper bound of \(1\), and the masses summing to \(1\). Thus objective comparisons and updates retain polynomial bit length throughout the sweep.
Constructing \(D\) and all coefficients requires \(O(N+\tau)\) integer arithmetic operations. Schoolbook multiplication and integer division on the stated operand lengths fit the \(O(L^2)\) per-operation upper bound.
Sorting requires \(O((N+2)\log(N+2))\) rational comparisons. Preference comparisons use the same cross-multiplication bound, with only a constant number of comparisons per event. Initialization, event processing, and threshold evaluation fit the additional linear terms.
Accordingly, the claimed total bound
\(O((m\tau+\tau+2)\log(m\tau+2)L^2)\)
is justified.
For the decision problem, \(tZ^\star\ge sD\) is equivalent to \(Z^\star/D\ge s/t\), because both denominators are positive. The additional \(O(L^2)\) bound is valid when \(L\) includes the decision input.
The conclusion concerning NP-hardness under polynomial-time many-one reductions is correct: a problem in \(\mathrm{P}\) can be NP-hard under those reductions only if \(\mathrm{P}=\mathrm{NP}\).
The argument covers \(q=0\), \(q=1\), utilities equal to either endpoint, repeated threshold values, and complete utility ties. Zero-utility nonnull actions cause no failure because menu order resolves their ties with the null action.
The \(m=0\) case is explicitly handled, and the bound remains valid there. Positive masses summing to \(1\) already exclude an empty support.
The algorithm uses only the explicitly supplied support. The online regret result is not used as an offline complexity argument, so no verification of that external result is needed to validate this proof.
No additional clarification or mathematical repair 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.