d4-conf-atal-2014-0102

NEW RESULT — continuous: polynomial-time · adversarial review: proved_with_minor_gaps

The anchor (named result in the paper)

statement extracted from the paper’s text layer; consult the paper for the exact wording

The continuous mirror question, as graded

Given a finite set of decisions $D$, goals $G$, and a rational-mass distribution $\mu$ over supported types $t$, where each type is a complete pair of decision frameworks with trust scores, compute all decisions $d$ for which no $d' \ne d$ has $q_\mu(d',g) \ge q_\mu(d,g)$ for every $g \in G$, with strict inequality for at least one goal, where $q_\mu(d,g)=\sum_t \mu_t v_{t,d,g}$ and $v_{t,d,g}=1$ exactly when $d$ meets $g$ in type $t$'s trust-resolved joint framework.

Packaged proof task (what the prover saw — nothing else)

Let $D$ and $G$ be nonempty finite sets, with $n=|D|$ and $k=|G|$. A society is given by its support: the list of the $\tau$ types with positive mass, each mass a binary rational $\mu_t$, with $\sum_t\mu_t=1$. Here $\tau$ is the support size, not the number of possible types.
Each type explicitly specifies two frameworks $F_{t,i}=(D_{t,i},A_{t,i},G_{t,i},B_{t,i},C_{t,i})$, for $i\in\{1,2\}$, with nonempty finite decision, attribute and goal sets, $D_{t,1}\cup D_{t,2}=D$, and $G_{t,1}\cup G_{t,2}=G$. Tables $B_{t,i}:D_{t,i}\times A_{t,i}\to\{0,1,u\}$ and $C_{t,i}:G_{t,i}\times A_{t,i}\to\{0,1,u\}$ respectively encode having an attribute and an attribute satisfying a goal; $u$ means unknown.
Each type also specifies binary-encoded integer trust scores $T_{t,1}>T_{t,2}\ge0$. Extend absent table cells by $u$. On the union domains, form joint tables $B_t,C_t$ by taking agent one's cell whenever it is $0$ or $1$, and agent two's cell otherwise.
Write $A_t=A_{t,1}\cup A_{t,2}$. Set $v_{t,d,g}=1$ exactly when some $a\in A_t$ satisfies $B_t(d,a)=C_t(g,a)=1$, and set it to $0$ otherwise. Define $q_\mu(d,g)=\sum_t\mu_t v_{t,d,g}$.
The required output is every $d\in D$ for which no $d'\in D\setminus\{d\}$ satisfies $q_\mu(d',g)\ge q_\mu(d,g)$ for every $g\in G$, with strict inequality for at least one goal. Include all decisions with tied undominated vectors. Let $m=\max_t|A_t|$ and let $L$ be the total binary input length; state running times in $n,k,m,\tau,L$.

Can this output be computed in polynomial time in $n,k,m,\tau,L$, or is the problem $\mathrm{NP}$-hard?

For two discrete agents, joint dominance—meeting every goal met by any decision—is equivalent to admissibility of the corresponding selection argument in their constructed joint ABA framework; this is a semantic equivalence, not a complexity classification. [Fan et al. (2014)](https://ifmas.csc.liv.ac.uk/Proceedings/aamas2014/aamas/p533.pdf)
That dominance condition is stronger than Pareto undominance. No result settling this exact rational-mass problem was located in the literature search.

Modeling choices made when packaging the task

Prover output (gpt-6.1-sol / high, Bolzano prover prompt)

Conclusion

The required output is computable in polynomial time. A conservative running-time bound, including exact arithmetic, is
\[ O\!\left(\tau nkmL+\tau L^2+n^2kL\right). \]
The algorithm computes each type’s Boolean satisfaction matrix, forms exact weighted scores, and checks every ordered pair of decisions for Pareto dominance.

1. Compute each type’s satisfaction matrix

For each supported type $t$, extend absent table cells by $u$, as stipulated. For every $d\in D$, $g\in G$, and $a\in A_t$, form
\[ B_t(d,a)= \begin{cases} B_{t,1}(d,a),&B_{t,1}(d,a)\in\{0,1\},\\ B_{t,2}(d,a),&B_{t,1}(d,a)=u, \end{cases} \]
and form $C_t(g,a)$ by the same rule.

This implements the specified priority exactly. The numerical magnitudes of the trust scores require no further computation: the input guarantees $T_{t,1}>T_{t,2}$.

Now compute
\[ v_{t,d,g} = \bigvee_{a\in A_t} \left(B_t(d,a)=1\ \text{and}\ C_t(g,a)=1\right). \]
Each entry takes at most $m$ attribute checks. Thus computing all satisfaction matrices uses $O(\tau nkm)$ checks. Constructing the joint tables uses $O(\tau(n+k)m)$ table operations, which is also $O(\tau nkm)$, because $n,k$ are positive.

These computations enumerate only the $\tau$ types explicitly supplied in the support.

2. Represent all weighted scores exactly

Write each input mass as $\mu_t=p_t/b_t$, where $p_t,b_t$ are positive binary-encoded integers. Reduction to lowest terms is unnecessary. Set
\[ Q=\prod_{t=1}^{\tau}b_t, \qquad w_t=p_t(Q/b_t). \]
Every $w_t$ is an integer, and
\[ \frac{w_t}{Q}=\mu_t, \qquad \sum_{t=1}^{\tau}w_t=Q. \]

For every decision and goal, compute the integer
\[ S(d,g)=\sum_{t=1}^{\tau}w_t v_{t,d,g}. \]
By definition,
\[ q_\mu(d,g)=\frac{S(d,g)}{Q}. \]
Since $Q>0$, comparisons of the required rational scores are exactly comparisons of these integers:
\[ q_\mu(d',g)\ge q_\mu(d,g) \quad\Longleftrightarrow\quad S(d',g)\ge S(d,g). \]
The same equivalence holds for strict inequalities.

The common denominator has polynomial bit length. Indeed,
\[ \log_2 Q=\sum_{t=1}^{\tau}\log_2 b_t, \]
and the total encoded length of the denominators is at most $L$. Consequently, $Q$ has $O(L)$ bits.

Furthermore, positivity of the weights and their sum imply
\[ 0\le w_t\le Q, \qquad 0\le S(d,g)\le Q. \]
Partial sums used to compute $S(d,g)$ also lie between zero and $Q$. Thus all score arithmetic uses $O(L)$-bit integers; there is no need for approximate arithmetic.

3. Extract precisely the requested decisions

Initially mark no decision as dominated. For each ordered pair $d,d'$ of distinct decisions, test both conditions
\[ S(d',g)\ge S(d,g)\quad\text{for every }g\in G, \]
and
\[ S(d',g)>S(d,g)\quad\text{for at least one }g\in G. \]
If both conditions hold, mark $d$ as dominated. After checking every pair, output all unmarked decisions.

Correctness. If a decision is marked, the comparisons in Section 2 show that the decision witnessing its mark satisfies exactly the dominance condition in the question. Therefore, every output decision is undominated.

Conversely, if $d$ is dominated according to the question, some distinct $d'$ satisfies those inequalities. The algorithm examines that ordered pair and marks $d$. Therefore, every undominated decision is output.

Finally, equal score vectors cannot satisfy the strict-inequality condition. Hence all decisions with tied undominated vectors are retained.

4. Running time and classification

Using elementary integer multiplication and division:

Computing $Q$ and all $w_t$ takes $O(\tau L^2)$ bit operations.
Accumulating all scores takes $O(\tau nkL)$ bit operations.
Checking all ordered pairs takes $O(n^2kL)$ bit operations.

Input labels can be converted to indices in $O(L^2)$ time. Conservatively charging $O(L)$ for table access and index manipulation, constructing the joint tables and satisfaction matrices takes $O(\tau nkmL)$ time. Because $\tau,m\ge1$, these bounds together give
\[ O\!\left(\tau nkmL+\tau L^2+n^2kL\right). \]

This is polynomial in the requested parameters. It is also polynomial in total input length, since the sets, attributes, and supported types are explicitly represented.

The supplied ABA semantic equivalence is unnecessary for this algorithm: the requested output follows directly from explicit Boolean witnesses, exact rational sums, and pairwise comparisons.

⟨structured verdict parsed — rendered above⟩

Adversarial review (gpt-6.1-sol / medium, Bolzano verifier prompt)

The prover resolves the requested problem in polynomial time. The algorithm and bit-complexity bound are sound. There is one minor issue: the two explanatory conclusions in the correctness paragraph are attached to the opposite implications. Both necessary implications are nevertheless established.

1. Scope and satisfaction matrices

The algorithm processes exactly the $\tau$ supported types, as required. It does not enumerate all possible types.

Extending absent cells by $u$ makes both agents’ tables available on the union domains. The displayed priority rule correctly selects agent one’s value whenever it is known, including when it is $0$, and selects agent two’s value otherwise. The trust scores require no additional numerical processing because their ordering is guaranteed by the input.

The Boolean expression defining $v_{t,d,g}$ exactly matches the required existential attribute witness. It does not mistakenly treat an unknown value as satisfaction.

Each of the $\tau nk$ entries requires at most $m$ attribute checks. Constructing the joint tables requires $O(\tau(n+k)m)$ operations. Since $n,k\ge1$, we have $n+k\le2nk$, so absorbing this cost into $O(\tau nkm)$ is valid.

Assessment: Correct.

2. Exact rational arithmetic

The representation $\mu_t=p_t/b_t$ with positive integers is consistent with positive rational masses. No reduction to lowest terms is needed.

Each $b_t$ divides $Q=\prod_t b_t$, so every $w_t=p_t(Q/b_t)$ is an integer. The identities
$$ w_t/Q=\mu_t,\qquad \sum_t w_t=Q $$
follow directly from the input’s normalization.

Consequently, $S(d,g)/Q=q_\mu(d,g)$. Because the same positive denominator applies to every score, the stated equivalences for both weak and strict comparisons are correct.

The denominator’s bit length is bounded by the sum of the input denominator lengths, up to a constant additive term. Thus $Q$ has $O(L)$ bits. Positivity and normalization give $0<w_t\le Q$ and $0\le S(d,g)\le Q$. Every partial score sum also stays within that interval. Intermediate quantities used in constructing the weights have $O(L)$ bits as well.

Assessment: Correct; no numerical approximation or uncontrolled denominator growth occurs.

3. Dominance test and correctness

The algorithm checks every ordered pair of distinct decisions. Its two tests reproduce exactly the required universal weak inequality and existential strict inequality.

The write-up establishes both necessary implications:

A marked decision has a valid dominance witness.
A decision dominated under the task’s definition is marked when its witnessing pair is examined.

Together, these establish that the marked decisions are precisely the dominated decisions.

Minor issue: The prose attaches the consequences to the wrong implications. “If a decision is marked” supports the conclusion that every undominated decision is output. Conversely, “if $d$ is dominated” supports the conclusion that every output decision is undominated. The write-up states these consequences in the opposite order.

Minimum clarification: Swap the two “Therefore” sentences, or place both conclusions after the two implications have been established. No additional mathematics is needed.

Equal vectors fail the strict-inequality test, so tied undominated decisions are retained. The case $n=1$ is also covered: there are no ordered pairs of distinct decisions, and the sole decision is output. The nonempty goal and attribute assumptions cover the other relevant domain restrictions.

Assessment: Sound in substance, with a minor exposition error.

4. Running time

The arithmetic bounds are valid using elementary multiplication and division:

Constructing $Q$ and all weights requires $O(\tau L^2)$ bit operations.
Accumulating scores requires $O(\tau nkL)$ bit operations.
Testing all ordered pairs requires $O(n^2kL)$ bit operations.

The conservative preprocessing and table-operation charges are compatible with the stated explicit input representation. Since $\tau,m\ge1$, the preprocessing cost and score-accumulation cost are absorbed into the displayed total:
$$ O\!\left(\tau nkmL+\tau L^2+n^2kL\right). $$

The explicitly represented sets and support also make the parameters polynomially bounded by input length. Thus the algorithm is polynomial in both the requested parameters and total input length.

The ABA equivalence is not used, so no external theorem application requires verification.

Assessment: The polynomial-time classification is established.