d4-conf-ijcai-2018-0698 (d4-conf-ijcai-2018-0698)

Given rational masses \(\mu_t\) over opponent types \(t\), labels \(b_t\) indicating whether the tagged target \(w\) beats type \(t\), and an integer budget \(\ell\), consider sequences of transitive tournaments on \(N\) entrants, where \(N\) tends to infinity through powers of two and the empirical opponent-type masses converge to \(\mu\). Does there exist such a sequence in which at most \(\ell\) match outcomes are reversed and a bracket makes \(w\) win?

A society is given by its support: the list of \(\tau\) opponent types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types. Each type has a label \(b_t\in\{0,1\}\), with \(b_t=1\) meaning that the distinguished entrant \(w\) beats every opponent of that type. The budget \(\ell\in\mathbb Z_{\ge0}\) is binary encoded; \(L\) is the total input bit length.
A realization has \(N=2^h\ge2\) distinct entrants: one \(w\) and \(N-1\) opponents assigned only listed types. Its original outcomes come from a strict total order of entrants, with the earlier entrant beating the later one, and must respect every \(b_t\). Opponent orders, including orders within types, are unrestricted subject to these requirements.
A manipulation reverses at most \(\ell\) pairwise outcomes, each at unit cost, with no restriction on their endpoints. Afterward, a seeding assigns all entrants bijectively to the leaves of a complete balanced binary knockout bracket; each match follows the resulting outcomes.
Call the input feasible if there exist realizations with \(N_j=2^{h_j}\to\infty\), type counts \(n_{j,t}\) satisfying \(n_{j,t}/(N_j-1)\to\mu_t\), and, for every \(j\), a manipulation and seeding making \(w\) win. The same budget \(\ell\) applies to every realization; exact finite proportions are not required.

Is deciding feasibility in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? State running times in \(\tau,L,\ell\); this model has no separate candidate-count parameter \(m\).

For finite transitive tournaments, feasibility is equivalent to \(\operatorname{victory}(w)\ge N/2^\ell-1\), where \(\operatorname{victory}(w)\) counts opponents originally beaten by \(w\); a winning manipulation and seeding can be constructed in polynomial time. [Gupta, Roy, Saurabh and Zehavi](https://www.ijcai.org/proceedings/2018/0039.pdf)
No result settling this exact limiting-sequence problem was located.

Result

The problem is in \(\mathrm P\). Define the total mass of opponents originally beaten by the distinguished entrant by
\[ \]
\(p:=\sum_{t:b_t=1}\mu_t.\)

Then the exact criterion is

\(\boxed{\text{The input is feasible if and only if }p\ge 2^{-\ell}.}\)

Equality is included. Using elementary integer arithmetic, feasibility can be decided in \(O(\tau L^2)\) bit operations and \(O(L)\) auxiliary space. The running time has no dependence on the numerical value of \(\ell\) beyond its encoding length.

1. Applying the finite theorem

Let \(G:=\{t:b_t=1\}\) and \(H:=\{t:b_t=0\}\). In any realization with type counts \(n_t\), the number of opponents originally beaten by the entrant is

\(B:=\sum_{t\in G}n_t.\)

Every permitted original tournament is transitive because its outcomes arise from a strict total order. Conversely, every vector of nonnegative integer counts summing to \(N-1\) admits such an order: put opponents of types in \(H\) first, then the distinguished entrant, then opponents of types in \(G\). Order entrants arbitrarily within these groups.

Consequently, the supplied finite theorem applies: a realization admits a winning manipulation with at most \(\ell\) reversals precisely when

\(B\ge N2^{-\ell}-1.\)

This is Theorem 2 of [Gupta, Roy, Saurabh and Zehavi](https://www.ijcai.org/proceedings/2018/0039.pdf). Its hypotheses match the present model: a transitive tournament, a balanced bracket with a power-of-two number of entrants, and unrestricted unit-cost outcome reversals.

2. Necessity

Suppose a witnessing sequence exists. Set

\(B_j:=\sum_{t\in G}n_{j,t}.\)

Because \(G\) is finite and each type proportion converges,

\(\displaystyle \frac{B_j}{N_j-1}\longrightarrow\sum_{t\in G}\mu_t=p.\)

Every realization in the sequence is winning, so the finite theorem gives

\(\displaystyle \frac{B_j}{N_j-1}\ge\frac{N_j2^{-\ell}-1}{N_j-1} =2^{-\ell}-\frac{1-2^{-\ell}}{N_j-1}.\)

Here \(\ell\) is fixed throughout the sequence. Taking limits as \(N_j\to\infty\) proves \(p\ge 2^{-\ell}\).

In particular, if \(p=0\), no finite budget permits a witnessing sequence.

3. Sufficiency, including equality

Assume \(p\ge 2^{-\ell}\). Since \(2^{-\ell}>0\), the set \(G\) is nonempty.

For any \(N=2^h\ge2\), write \(M:=N-1\), and prescribe the aggregate count

\(B:=\lceil Mp\rceil.\)

We construct type counts with this aggregate and with uniformly bounded rounding errors.

Initially set \(a_t:=\lfloor M\mu_t\rfloor\). Define the residuals

\(\displaystyle R_G:=B-\sum_{t\in G}a_t,\qquad R_H:=M-B-\sum_{t\in H}a_t.\)

Both residuals are nonnegative integers. Indeed,

\(\displaystyle \sum_{t\in G}\lfloor M\mu_t\rfloor\le\lfloor Mp\rfloor\le B,\)

and, since \(M\) is an integer,

\(\displaystyle M-B=\lfloor M(1-p)\rfloor \ge\sum_{t\in H}\lfloor M\mu_t\rfloor.\)

Moreover, writing \(f_t:=M\mu_t-\lfloor M\mu_t\rfloor\), so \(0\le f_t<1\), gives

\(\displaystyle R_G=\left\lceil\sum_{t\in G}f_t\right\rceil\le |G|,\qquad R_H=\left\lfloor\sum_{t\in H}f_t\right\rfloor\le |H|.\)

Choose one type in \(G\) and add \(R_G\) to its initial count. If \(H\) is nonempty, choose one type in \(H\) and add \(R_H\) to its initial count. If \(H\) is empty, then \(p=1\) and \(R_H=0\).

The resulting counts \(n_t\) satisfy

\(\displaystyle \sum_t n_t=M,\qquad \sum_{t\in G}n_t=B,\qquad |n_t-M\mu_t|\le\tau.\)

Thus, along any sequence of powers of two tending to infinity,

\(\displaystyle \left|\frac{n_t}{N-1}-\mu_t\right| \le\frac{\tau}{N-1}\longrightarrow0.\)

Every listed type also has positive count for all sufficiently large sizes, because its mass is positive.

It remains to verify the finite winning condition. Put \(q:=2^{-\ell}\). Since \(p\ge q\) and \(q\le1\),

\(\displaystyle B=\lceil (N-1)p\rceil \ge (N-1)p \ge (N-1)q =Nq-q \ge Nq-1.\)

For example, choose \(h_j:=\max\{1,\ell\}+j\) and \(N_j:=2^{h_j}\). Construct the counts above and a compatible total order for every \(j\). The finite theorem supplies a winning manipulation and seeding using at most the same budget \(\ell\) for each realization. These realizations constitute the required witnessing sequence.

This proves sufficiency even when \(p=2^{-\ell}\).

4. Exact algorithm and bit complexity

Write each mass as \(\mu_t=a_t/d_t\), with numerator and positive denominator encoded in binary. Compute \(p=A/D\) exactly, without requiring fraction reduction. Starting with \(A=0\) and \(D=1\), for each type in \(G\) update

\(\displaystyle (A,D)\leftarrow(Ad_t+a_tD,\;Dd_t),\)

using the old values on the right-hand side.

The denominator is a product of input denominators, so its bit length is \(O(L)\). Every partial mass sum lies in \([0,1]\), hence \(0\le A\le D\); the numerator and temporary arithmetic values also have \(O(L)\) bits. Elementary multiplication therefore gives an \(O(\tau L^2)\) bound for this accumulation.

The remaining test is \(A2^\ell\ge D\), performed as follows:

• If \(A=0\), reject.
• Otherwise let \(k\) be the bit length of \(D\). If \(\ell\ge k\), accept: \(A\ge1\) implies \(A2^\ell\ge2^k>D\).
• If \(\ell<k\), shift \(A\) left by \(\ell\) bits and compare it with \(D\).

In the last case, \(\ell<k=O(L)\), so the shifted integer still has \(O(L)\) bits. Comparing the binary encoded budget with \(k\) takes \(O(L)\) bit operations, even when its numerical value is enormous.

Thus the complete decision algorithm uses \(O(\tau L^2)\) bit operations and \(O(L)\) auxiliary space. It examines only the listed support and does not construct a finite realization or introduce a separate candidate-count parameter.

⟨structured verdict parsed — rendered above⟩

The prover’s output resolves the task correctly. The limiting criterion, inclusion of equality, and polynomial bit complexity are all justified. No major or minor mathematical gaps were found.

1. Application of the finite theorem

The prover correctly identifies the original victory count as
\[ B=\sum_{t\in G}n_t, \]
where \(G\) contains precisely the types beaten by \(w\).

Every allowed original tournament is transitive. Conversely, the proposed order—opponents in \(H\), then \(w\), then opponents in \(G\)—realizes every nonnegative integer count vector totaling \(N-1\), while respecting every label. No additional restrictions on opponent orders or within-type orders are imposed by the task.

The cited Theorem 2 does state that an acyclic tournament admits a winning manipulation precisely when its victory count is at least \(N/2^\ell-1\), and that a solution can be constructed in polynomial time. The paper’s manipulation model allows at most \(\ell\) unrestricted arc reversals, matching the task. Its tournament framework matches the balanced knockout model used here. Thus the theorem is stated accurately and its hypotheses are satisfied. [Gupta, Roy, Saurabh and Zehavi, Theorem 2](https://www.ijcai.org/proceedings/2018/0039.pdf)

2. Necessity

The passage from individual type convergence to
\[ \frac{B_j}{N_j-1}\longrightarrow p \]
is valid because the support, and hence \(G\), is finite and fixed.

The finite inequality is normalized correctly:
\[ \frac{N_j2^{-\ell}-1}{N_j-1} = 2^{-\ell}-\frac{1-2^{-\ell}}{N_j-1}. \]
Since the budget is fixed throughout the sequence and \(N_j\) tends to infinity, the right-hand side converges to \(2^{-\ell}\). Therefore necessity establishes
\[ p\ge 2^{-\ell}. \]

The stated consequence for \(p=0\) is correct: every permitted budget is a finite nonnegative integer, so \(2^{-\ell}>0\).

3. Sufficiency and rounding

The prescribed aggregate \(B=\lceil Mp\rceil\) is an integer between zero and \(M\). Under the sufficiency assumption, \(G\) is nonempty, so the designated type receiving its residual exists.

Both residuals are correctly shown to be nonnegative integers. In particular,
\[ M-\lceil Mp\rceil=\lfloor M(1-p)\rfloor \]
holds because \(M\) is an integer. This justifies the residual calculation for \(H\), including when the aggregate is rounded upward.

The fractional-part formulas
\[ R_G=\left\lceil\sum_{t\in G}f_t\right\rceil, \qquad R_H=\left\lfloor\sum_{t\in H}f_t\right\rfloor \]
are correct. Their stated bounds follow from \(0\le f_t<1\).

Adding each residual to one type preserves nonnegativity, achieves both required aggregate totals, and gives the claimed error bound
\[ |n_t-M\mu_t|\le\tau. \]
For an unchanged count, the error is less than one; for a changed count, the error is \(R_G-f_t\) or \(R_H-f_t\), whose absolute value satisfies the stated bound.

The empty-\(H\) case is explicitly handled: normalization forces \(p=1\), and its residual is zero. Dividing the uniform rounding bound by \(M\) proves convergence for every listed type. The assertion of eventual positive counts also follows from positive masses and bounded rounding errors.

4. Winning condition and sequence quantifiers

Every inequality in
\[ B\ge (N-1)p\ge (N-1)q=Nq-q\ge Nq-1 \]
is valid, with \(q=2^{-\ell}\) and \(0<q\le1\). This establishes the finite winning condition even at equality \(p=q\).

The specified heights are integers, produce powers of two at least two, and tend to infinity. The construction supplies counts and a compatible original order for every member of the sequence; the finite theorem supplies a winning manipulation and seeding with the same budget throughout.

The edge case \(\ell=0\) is covered: the criterion requires \(p=1\), and the construction assigns every opponent to a type beaten by \(w\). Neither empty label class nor equality creates an exception.

5. Exact arithmetic and complexity

The rational accumulation update uses the old numerator and denominator correctly and computes the exact sum without reduction.

The denominator’s bit length is bounded by the sum of the input denominator lengths, hence is \(O(L)\). Since each partial sum lies in \([0,1]\), its numerator is no larger than its denominator. Intermediate products and sums also have \(O(L)\) bits. Consequently, elementary arithmetic supports the stated \(O(\tau L^2)\) accumulation bound and \(O(L)\) auxiliary space.

The comparison procedure is correct:

• A zero numerator must be rejected.
• If \(\ell\) is at least the denominator’s bit length \(k\), then \(A2^\ell\ge2^k>D\).
• Otherwise, the shift length is \(O(L)\), so the shifted numerator and comparison remain within \(O(L)\) bits.

The binary budget is compared before any potentially enormous shift. Thus the algorithm has no dependence on the numerical value of \(\ell\) beyond its encoding length. It uses only the supplied support and introduces no candidate-count parameter.

No repair or additional mathematical clarification is required.

⟨structured verdict parsed — rendered above⟩