d4-conf-atal-2017-0283 (d4-conf-atal-2017-0283)

Given candidates \(C\), tree order \(k\), and a support of ballot types \(t\) with rational masses \(\mu_t\), compute the restricted Markov tree’s maximum-likelihood transition table. For each context \(S\) and eligible next candidate \(c\), use the total mass \(W_{S,c}\) of ballots contributing the transition \(S\to c\) and the context mass \(W_S=\sum_c W_{S,c}\), returning \(\hat\theta_{S,c}=W_{S,c}/W_S\) when \(W_S>0\), with the model’s fixed default distribution otherwise.

Given a candidate set \(C\) with \(m=|C|\geq 1\) and an integer order \(1\leq k\leq m\), a society is given by its support: the list of \(\tau\) ballot types with positive binary rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
A ballot type records disjoint ordered blocks of distinct candidates certified to occupy consecutive positions in an incomplete ranking; at most one block is marked as beginning at the first position. Unspecified positions and comparisons remain unknown. Complete rankings and strict top orders are included.
Contexts \(S\) are ordered sequences of distinct candidates with \(0\leq |S|\leq k\) and \(|S|<m\); eligible successors are \(c\in C\setminus S\). From a marked initial block, extract each prefix transition whose context has length less than \(k\), including the empty-context transition. From every block, extract every consecutive window of length \(k+1\), using its first \(k\) candidates as context and its last as successor; pool these observations across positions.
Let \(a_t(S,c)\) count these occurrences in type \(t\), \(W_{S,c}=\sum_t\mu_t a_t(S,c)\), and \(W_S=\sum_{c\in C\setminus S}W_{S,c}\). Compute the exact table \(\hat\theta_{S,c}=W_{S,c}/W_S\) when \(W_S>0\), and \(\hat\theta_{S,c}=1/(m-|S|)\) otherwise. Maximum likelihood refers to the extracted categorical training observations, with no smoothing. Represent the table by its observed-context rows and an implicit uniform default for all other contexts.
Is this exact transition-table computation solvable in polynomial time in \(m,\tau,L,k\), or is it NP-hard?
Known discrete results give a finite-sample parameter-error bound for rankings drawn from the same model and claim estimation time linear in the total length of supplied training subsequences, using an implicit-default representation. [Doucette and Cohen (2017)](https://www.ifaamas.org/Proceedings/aamas2017/pdfs/p893.pdf).
No published result addressing exactly this rational-mass formulation was located.

Claim and scope. The exact transition table is computable in deterministic polynomial time in \(m,\tau,L,k\), with the stipulated representation by observed rows and an implicit uniform default. This holds for variable \(k\), including \(k=m\).

The proof uses precisely the extracted categorical observations specified in the question.

1. Bounding the number of observations.

Let \(B_t\) be the total number of candidate occurrences listed in the blocks of ballot type \(t\), and let \(N_t\) be its number of extracted transition occurrences. Because the blocks are disjoint and contain distinct candidates, \(B_t\leq m\).

An unmarked block of length \(r\) contributes \(\max\{r-k,0\}\) windows of length \(k+1\), hence at most \(r\) observations.

A marked initial block of length \(r\) contributes:

• \(\min\{k,r\}\) prefix transitions, whose context lengths run from \(0\) through \(\min\{k,r\}-1\);
• \(\max\{r-k,0\}\) windows with context length \(k\).

Their sum is exactly \(r\). Thus, writing \(N\) for the total number of extracted occurrences and \(R\) for the number of distinct observed contexts, we obtain

\(R\leq N=\sum_{t=1}^{\tau}N_t\leq\sum_{t=1}^{\tau}B_t\leq\tau m.\)

Every extracted transition is eligible: its context and successor are distinct candidates in the same block. Prefix contexts have length less than \(k\) and less than \(m\). A window can exist only if \(k+1\leq m\), so its context also has length less than \(m\).

Consequently, explicitly listing all eligible successor probabilities in the observed rows requires at most \(Rm\leq\tau m^2\) entries. The algorithm need not enumerate unobserved contexts.

2. Clearing denominators without expanding the society.

Write each supplied mass as \(\mu_t=p_t/q_t\), where \(p_t,q_t\) are positive integers represented in binary. Define

\(D=\prod_{t=1}^{\tau}q_t,\qquad x_t=p_t(D/q_t).\)

Each \(x_t\) is a positive integer. The normalization of the input masses gives

\(\sum_{t=1}^{\tau}x_t=D\sum_{t=1}^{\tau}\mu_t=D.\)

For each extracted occurrence of \((S,c)\) in type \(t\), add \(x_t\) to an integer accumulator \(A_{S,c}\). After processing all occurrences, define \(A_S=\sum_{c\in C\setminus S}A_{S,c}\). Then

\(A_{S,c}=\sum_t x_ta_t(S,c)=DW_{S,c},\qquad A_S=DW_S.\)

Therefore, whenever \(A_S>0\),

\(\hat\theta_{S,c}=A_{S,c}/A_S=W_{S,c}/W_S.\)

Because all masses are positive, \(A_S>0\) holds exactly for contexts that occur in the extracted data. Store those rows, assigning zero to eligible successors with no occurrence. For every other context, store the single default rule \(\hat\theta_{S,c}=1/(m-|S|)\).

The integers \(x_t\) serve only as arithmetic weights; the algorithm never creates \(x_t\) copies of a ballot.

3. Exact arithmetic and bit complexity.

The sum of the binary lengths of the supplied denominators is at most \(L\). Consequently,

\(\log_2D=\sum_t\log_2q_t\leq L.\)

Furthermore, the sum of all integer observation weights satisfies

\(\sum_{S,c}A_{S,c}=\sum_t x_tN_t\leq m\sum_t x_t=mD.\)

All accumulators, including every \(A_S\), therefore have \(O(L+\log(m+1))\) bits. Reducing \(A_{S,c}/A_S\) by their greatest common divisor cannot increase this bound.

For a deterministic implementation, first label candidates by integers from \(1\) through \(m\). Generate the \(N\) occurrence records, retaining their ballot-type indices, and sort them lexicographically by the ordered context and successor. Each key contains at most \(k+1\) candidate indices, so has \(O((k+1)\log(m+1))\) bits. Sorting and grouping these records takes polynomial time.

Computing \(D\) and the \(x_t\), accumulating grouped weights, computing row totals, and reducing output fractions requires \(O(\tau+N+Rm)\) calls to integer arithmetic and greatest-common-divisor routines. Their operands have polynomial bit length, and these routines admit polynomial-time algorithms.

Including context keys, the output has size at most

\(O\!\left(R(k+1)\log(m+1)+Rm\bigl(L+\log(m+1)\bigr)\right).\)

Since \(R\leq\tau m\), this size and the entire running time are polynomial in the requested parameters.

4. Verification of the maximum-likelihood interpretation.

For completeness, consider one observed context \(S\), and put \(p_c=W_{S,c}/W_S\). Let \(I=\{c:W_{S,c}>0\}\). Its contribution to the weighted categorical log-likelihood is

\(\ell_S(\theta)=\sum_{c\in I}W_{S,c}\log\theta_{S,c},\)

subject to nonnegative probabilities summing to one over \(C\setminus S\).

If any \(\theta_{S,c}=0\) for \(c\in I\), its log-likelihood is negative infinity and cannot maximize the objective. Otherwise, using \(\log u\leq u-1\) for \(u>0\),

\(\ell_S(\theta)-\ell_S(p)=W_S\sum_{c\in I}p_c\log(\theta_{S,c}/p_c)\leq W_S\left(\sum_{c\in I}\theta_{S,c}-1\right)\leq0.\)

Equality requires \(\theta_{S,c}=p_c\) for every \(c\in I\); these probabilities already sum to one, forcing zero on the remaining successors. Thus the computed observed row is the unique maximizer.

For an unobserved context, all weights vanish and the likelihood is independent of that row. The prescribed uniform default is therefore a valid maximizing choice. Since the extracted categorical objective separates over contexts, these rowwise choices maximize the full objective.

5. Relation to the cited work and boundary cases.

[Doucette and Cohen (2017), Section 3.2](https://www.ifaamas.org/Proceedings/aamas2017/pdfs/p893.pdf) discusses a finite-sample parameter-error bound and estimation using lazily constructed maps with uniform defaults. The proof above independently establishes the additional exact rational-arithmetic and output-size bounds needed for this formulation; it requires no assumption that the input society was sampled from a model.

If no observations are extracted, the output consists entirely of the uniform-default rule. For \(k=m\), there are no windows of length \(k+1\), and the prefix argument still applies. For \(m=1\), the only context is empty and its sole probability is one. Thus the proof covers every allowed input.

⟨structured verdict parsed — rendered above⟩

Verdict

The proof is correct and resolves the assigned computation problem. It establishes deterministic polynomial time in \(m,\tau,L,k\) for the required representation, including variable \(k\). No major or minor mathematical issues were found.

Step-by-step verification

1. Number and validity of extracted observations

The bound \(B_t\leq m\) follows from the stated disjointness of blocks and distinctness of their candidates.

For an unmarked block of length \(r\), the number of consecutive windows of length \(k+1\) is exactly \(\max\{r-k,0\}\).

For a marked initial block, the prefix count \(\min\{k,r\}\) is correct: the context lengths are exactly \(0,\ldots,\min\{k,r\}-1\). Its windows have context length \(k\), so they do not duplicate the shorter-context prefix transitions. The identity
\[ \min\{k,r\}+\max\{r-k,0\}=r \]
holds both when \(r\leq k\) and when \(r>k\).

Consequently, \(N_t\leq B_t\), and the asserted bound \(R\leq N\leq\tau m\) is valid. Each observed context contains at least one occurrence, which justifies \(R\leq N\).

The eligibility checks are also correct. Prefix contexts have length less than both \(k\) and \(m\). Windows exist only when \(k+1\leq m\), so their contexts have length less than \(m\). Distinct candidates within each block ensure that the successor is outside its context.

Each observed row has at most \(m\) eligible successors. Thus the bound \(Rm\leq\tau m^2\) on explicitly listed probabilities is valid.

2. Clearing denominators and computing the prescribed table

The product \(D=\prod_t q_t\) is divisible by every \(q_t\), so every weight \(x_t=p_t(D/q_t)\) is a positive integer. Reduced input fractions are unnecessary.

The normalization identity \(\sum_t x_t=D\) follows directly from \(\sum_t\mu_t=1\).

Adding \(x_t\) once for every extracted occurrence correctly accounts for the multiplicity \(a_t(S,c)\). Therefore the identities \(A_{S,c}=DW_{S,c}\) and \(A_S=DW_S\) hold exactly, and taking their ratio gives the required probability.

Strict positivity of the masses ensures that a context has positive total weight exactly when it appears among the extracted observations. This justifies storing precisely the observed rows. Assigning zero to unobserved successors within such a row is required by the formula.

For every other context, the default denominator \(m-|S|\) is positive by the task’s restriction \(|S|<m\). The default rule is therefore well-defined.

No expansion into a society of \(D\) ballots occurs.

3. Bit complexity and deterministic implementation

The denominator bound \(\log_2D\leq L\) is valid because the total binary encoding length of the denominators is at most \(L\).

The calculation
\[ \sum_{S,c}A_{S,c}=\sum_t x_tN_t\leq m\sum_t x_t=mD \]
is correct. All terms are nonnegative, so it bounds every individual accumulator and every row total. Their binary lengths are consequently \(O(L+\log(m+1))\).

The arithmetic used to form \(x_t\) also has polynomial-size operands: both \(p_t\) and \(D/q_t\) have at most \(O(L)\) bits, so their product has at most \(O(L)\) bits. Fraction reduction cannot enlarge the numerator or denominator.

The sorting implementation preserves ordered contexts rather than identifying contexts with their underlying candidate sets. Its keys contain at most \(k+1\) candidate indices and have the claimed polynomial length. Lexicographic sorting and grouping are deterministic polynomial-time operations.

The stated count \(O(\tau+N+Rm)\) of arithmetic and greatest-common-divisor calls is consistent with denominator construction, weight construction, accumulation, row totals, and output reduction. Standard binary integer arithmetic and greatest-common-divisor algorithms apply to the bounded operands.

The output-size bound accounts for context keys and explicitly listed rational probabilities. Together with \(R\leq\tau m\), it establishes polynomial output size and running time. When \(R=0\), the remaining default rule has constant descriptive size; this causes no complexity problem.

4. Maximum-likelihood interpretation

For an observed context, \(W_S>0\), and the probabilities \(p_c=W_{S,c}/W_S\) are positive on \(I\) and sum to one there. Thus the proposed row has finite log-likelihood.

Any row assigning zero probability to a positively weighted successor has log-likelihood negative infinity and cannot maximize it.

For all remaining rows, the application of \(\log u\leq u-1\) satisfies its hypothesis because \(\theta_{S,c}/p_c>0\) on \(I\). Both displayed inequalities follow correctly. Equality in the first requires \(\theta_{S,c}=p_c\) for every \(c\in I\), since every corresponding weight is positive. These probabilities exhaust the row total, forcing all other successor probabilities to zero. The uniqueness claim is justified.

An unobserved row contributes no terms to the extracted categorical objective, so its uniform default is a maximizing choice. The task imposes independent categorical row constraints, making the separation over contexts valid.

5. Citation and boundary cases

The description of the cited paper is accurate: Section 3.2 discusses the parameter-error bound, lazy maps, uniform defaults, and the claimed training-time bound. [Doucette and Cohen (2017), Section 3.2](https://www.ifaamas.org/Proceedings/aamas2017/pdfs/p893.pdf).

The prover does not use that paper’s statistical theorem to establish the rational-mass complexity result. Its hypotheses therefore do not constitute an unverified dependency of this proof.

All stated boundary cases are covered:

• With no extracted observations, the implicit default specifies the entire table.
• With \(k=m\), no length-\(k+1\) window exists, while all permitted marked-prefix transitions remain covered.
• With \(m=1\), the only allowed context is empty, and its sole successor has probability one whether the row is observed or uses the default.

Issues and repair feedback

No unjustified nontrivial step, false assertion, missing hypothesis, or blocking gap was identified. No additional clarification is needed to verify the polynomial-time claim.

⟨structured verdict parsed — rendered above⟩