d4-conf-wine-2024-0025 (d4-conf-wine-2024-0025)

Given a finite transaction set \(X\) and a finite-support rational distribution over pairs of true and reported strict orders, with at most mass \(\varepsilon\) on pairs that disagree, compute an ordering \(\pi\) using the reported-order marginal. Require that for every \(\gamma \in (1/2,1]\), if true-order mass at least \(\gamma\) ranks \(x\) before \(y\) but \(\pi\) reverses them, then \(\pi\) contains a reverse path from \(y\) to \(x\) whose every step has true-order mass at least \(\gamma-2\varepsilon\).

Let \(X\) be a finite transaction set of size \(m\geq 1\). A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Here a type is a pair \((T,R)\) of complete strict orders on \(X\), respectively true and reported. Masses sum to \(1\).
Let \(\varepsilon\in[0,1]\) be rational, with \(\Pr[T\neq R]\leq\varepsilon\), and let \(L\) be the total binary input length. Write \(p(x,y)=\Pr[x\prec_T y]\).
Compute a deterministic strict order \(\pi\) of all of \(X\) using only the reported-order marginal: the output must be identical for all societies with that marginal, independently of their true orders and of \(\varepsilon\).
For every admissible society and every real \(\gamma\in(1/2,1]\), require that if \(p(x,y)\geq\gamma\) and \(y\prec_\pi x\), there exist \(k\geq 1\) and distinct transactions \(y=z_0\prec_\pi z_1\prec_\pi\cdots\prec_\pi z_k=x\) with \(p(z_i,z_{i+1})\geq\gamma-2\varepsilon\) for every \(0\leq i<k\).

Can such an ordering rule be computed in time polynomial in \(m,\tau,L\), or is this continuous ordering problem NP-hard?

For \(n\) equally weighted replicas with complete votes and \(f\) faulty replicas, [Ranked Pairs achieves this guarantee](https://arxiv.org/html/2304.02730v4#S4) simultaneously for every \(\gamma\in(1/2,1]\), with error parameter \(f/n\), in polynomial time without knowing \(f\).
No result settling the exact rational-support mass formulation was located in the literature search.

Proven result

The problem is polynomial-time solvable. Exact rational weights can be used directly in Ranked Pairs, without expanding the society into equally weighted replicas. The resulting order depends only on the reported-order marginal and satisfies the requirement simultaneously for every allowed \(\gamma\) and \(\varepsilon\).

1. Construction using only reported orders

For distinct \(u,v\in X\), define the reported pairwise probability
\( q(u,v)=\Pr[u\prec_R v]. \)
This is determined by the reported-order marginal.

Fix a canonical order on the transaction identifiers, independent of the society. Use it to break all ties deterministically.

Apply the descending-weight locking procedure described in [Section 4 of the supplied paper](https://arxiv.org/html/2304.02730v4#S4):

• List all \(m(m-1)\) directed edges \((u,v)\), with weight \(q(u,v)\).
• Sort them by nonincreasing weight, breaking equal-weight ties canonically.
• Start with the empty directed graph \(H\) on \(X\). Process each edge in this sequence, adding it precisely when its addition would not create a directed cycle.
• Output a topological order \(\pi\) of the final graph, choosing the canonically first available vertex whenever necessary.

Processing all directed edges, including weights at most \(1/2\), will ensure the proof applies even when \(\gamma-\varepsilon\leq 1/2\).

The graph remains acyclic by construction, so a topological order exists and includes every transaction. All decisions depend only on \(q\) and the fixed transaction identifiers. Consequently, societies with the same reported-order marginal produce identical output, regardless of their true orders, support decompositions, or values of \(\varepsilon\).

For \(m=1\), the construction outputs the unique order and the guarantee is vacuous.

2. The reverse-path property

We prove a property of the construction that holds for every distinct pair \(x,y\):

If \(y\prec_\pi x\), then there is a directed path in the final graph \(H\) from \(y\) to \(x\), every edge of which has weight at least \(q(x,y)\).

To prove this, consider the moment when \((x,y)\) was processed. It cannot have been accepted: an accepted edge remains in the final graph, and every topological order would then put \(x\) before \(y\), contradicting \(y\prec_\pi x\).

Thus \((x,y)\) was rejected. Let \(H_{\mathrm{old}}\) be the graph immediately before that rejection. It was acyclic, whereas adding \((x,y)\) would create a directed cycle. Any such cycle must contain the new edge, since \(H_{\mathrm{old}}\) itself has no cycle. Removing the new edge from this cycle gives a directed path
\( y=z_0\longrightarrow z_1\longrightarrow\cdots\longrightarrow z_k=x \)
in \(H_{\mathrm{old}}\), with \(k\geq 1\).

Every edge of this path was processed before \((x,y)\). The processing sequence is nonincreasing in weight, so
\( q(z_i,z_{i+1})\geq q(x,y) \)
for every \(0\leq i<k\).

Accepted edges are never removed, so the path persists in the final graph. Its vertices are distinct because the graph is acyclic. Finally, every path edge is respected by the topological order, giving
\( y=z_0\prec_\pi z_1\prec_\pi\cdots\prec_\pi z_k=x. \)
This proves the property, including the required monotonicity in the output order.

3. Transfer from reported probabilities to true probabilities

Let \(\delta=\Pr[T\neq R]\), so that \(\delta\leq\varepsilon\). For any distinct \(u,v\), the indicators of \(u\prec_T v\) and \(u\prec_R v\) agree whenever \(T=R\). Therefore
\( \begin{aligned} |p(u,v)-q(u,v)| &=\left|\mathbb{E}\!\left[\mathbf{1}_{\{u\prec_T v\}}-\mathbf{1}_{\{u\prec_R v\}}\right]\right|\\ &\leq\mathbb{E}\!\left[\left|\mathbf{1}_{\{u\prec_T v\}}-\mathbf{1}_{\{u\prec_R v\}}\right|\right]\\ &\leq\Pr[T\neq R]\\ &\leq\varepsilon. \end{aligned} \)

Now fix any real \(\gamma\in(1/2,1]\) and distinct \(x,y\) satisfying \(p(x,y)\geq\gamma\) and \(y\prec_\pi x\).

The reverse-path property supplies distinct transactions
\( y=z_0\prec_\pi z_1\prec_\pi\cdots\prec_\pi z_k=x \)
such that, for every \(0\leq i<k\),
\( \begin{aligned} p(z_i,z_{i+1}) &\geq q(z_i,z_{i+1})-\varepsilon\\ &\geq q(x,y)-\varepsilon\\ &\geq p(x,y)-2\varepsilon\\ &\geq\gamma-2\varepsilon. \end{aligned} \)

This is exactly the requested guarantee. The construction never uses \(\gamma\) or \(\varepsilon\), and the argument holds for every allowed choice of them. Thus the guarantee is simultaneous over the entire specified continuum of thresholds.

4. Polynomial bit complexity

Write the support masses as \(a_s/b_s\), for \(1\leq s\leq\tau\), with positive integers \(a_s,b_s\) encoded in binary. Set
\( D=\prod_{s=1}^{\tau}b_s, \qquad c_s=a_s(D/b_s). \)

The bit length of \(D\) is at most \(1+\sum_s\log_2 b_s\), hence is \(O(L)\). The normalization of the masses gives
\( \sum_{s=1}^{\tau}c_s=D. \)

For each directed pair, compute
\( A(u,v)=\sum_{\{s:\,u\prec_{R_s}v\}}c_s. \)
Then \(q(u,v)=A(u,v)/D\), and \(0\leq A(u,v)\leq D\). Every weight numerator therefore has \(O(L)\) bits. Although the numerical value of \(D\) can be exponentially large, its binary representation has polynomial length.

Using rank positions in each reported order, all numerators can be computed with \(O(\tau m^2)\) integer additions. Sorting requires \(O(m^2\log(m+1))\) comparisons of these numerators; their denominator is common.

For each candidate edge \((u,v)\), a graph search tests whether the current graph contains a path from \(v\) to \(u\). Such a path exists exactly when adding \((u,v)\) would create a cycle. Each search takes \(O(m^2)\) graph operations, so processing all edges takes \(O(m^4)\) graph operations. Topological sorting is polynomial as well.

All integer arithmetic uses polynomially many bits, and standard exact arithmetic therefore gives total running time polynomial in \(m,\tau,L\). Neither replica expansion nor enumeration of threshold values is required.

⟨structured verdict parsed — rendered above⟩

The prover resolves the rational-support formulation correctly. The construction, guarantee, and polynomial bit complexity are all justified. I found no major or minor issues.

• Construction and dependence on the reported marginal.

Each \(q(u,v)\) is determined by the reported-order marginal. Sorting these probabilities with fixed canonical tie-breaking, locking edges, and choosing a canonical topological order therefore produce identical outputs whenever that marginal is identical.

Different support decompositions may change the arithmetic representation of the probabilities, but exact comparisons preserve their ordering and equality. Neither true orders nor \(\varepsilon\) affect any algorithmic decision.

The finite graph remains acyclic because an edge is accepted only when it preserves acyclicity. Consequently, a topological order exists and gives a strict order of all transactions.

The cited description of Ranked Pairs agrees with the descending-weight, cycle-avoiding construction. The rational-weight guarantee is proved directly in the output, so it does not depend on extending the paper’s replica theorem without justification. [Section 4 of the supplied paper](https://arxiv.org/html/2304.02730v4#S4).

• Reverse-path property.

Fix distinct \(x,y\) with \(y\prec_\pi x\). The edge \((x,y)\) was processed because the algorithm processes every directed pair. It cannot have been accepted: accepted edges persist, and every topological order respects them.

Its rejection therefore means that adding it to the current acyclic graph would create a cycle. Such a cycle must contain the new edge; removing that edge yields the asserted path from \(y\) to \(x\).

Every path edge was accepted earlier. Nonincreasing processing order implies that its weight is at least \(q(x,y)\), including when weights are tied. Those edges persist, and the final topological order respects every consecutive pair on the path. Acyclicity ensures distinct path vertices, and distinct endpoints ensure \(k\geq1\).

Thus the reverse-path property, including monotonicity in \(\pi\), is fully established. Processing all edges makes the argument valid without a restriction on \(q(x,y)\).

• Transfer to true probabilities.

The indicator comparison is correct: disagreement on a pair can occur only on the event \(T\neq R\). Hence, for every distinct \(u,v\),
\[ |p(u,v)-q(u,v)|\leq\Pr[T\neq R]\leq\varepsilon. \]

Every inequality in the subsequent chain has the correct direction:
\[ p(z_i,z_{i+1}) \geq q(z_i,z_{i+1})-\varepsilon \geq q(x,y)-\varepsilon \geq p(x,y)-2\varepsilon \geq\gamma-2\varepsilon. \]

The path has exactly the endpoints, distinctness, and output-order monotonicity required by the task.

• Quantifiers and edge cases.

The proof fixes an arbitrary admissible society and arbitrary real \(\gamma\in(1/2,1]\), while the algorithm uses neither \(\gamma\) nor \(\varepsilon\). This establishes the simultaneous guarantee; no threshold enumeration is needed.

The stated treatment of \(m=1\) is correct. The reasoning also covers \(\varepsilon=0\), \(\varepsilon=1\), \(\gamma=1\), tied probabilities, zero-weight edges, and nonpositive required path thresholds. None requires an additional argument.

• Exact arithmetic and runtime.

The common denominator \(D=\prod_s b_s\) has \(O(L)\) bits. Each \(c_s=a_s(D/b_s)\) is an integer, and normalization gives \(\sum_s c_s=D\). Consequently, every computed numerator \(A(u,v)\) lies between zero and \(D\), so it also has \(O(L)\) bits.

Constructing these integers uses polynomially many exact multiplications and divisions on polynomial-length operands. The stated \(O(\tau m^2)\) additions and \(O(m^2\log(m+1))\) weight comparisons are valid.

Cycle testing by reverse reachability is correct under the maintained acyclicity invariant. Each search requires \(O(m^2)\) graph operations, giving \(O(m^4)\) operations over all candidate edges. Canonical topological sorting is polynomial as well.

The numerical magnitude of \(D\) therefore causes no exponential runtime: the algorithm manipulates its binary representation and never expands it into replicas.

No repair or additional clarification is needed. The output establishes a deterministic polynomial-time ordering rule for the exact input representation specified in the task.

⟨structured verdict parsed — rendered above⟩