Answer: Yes. The required family exists with \(c=\tfrac13\) for every \(m\geq3\), with \(\mathbb E_{D_m}[\mathrm{OPT}]=1\).
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThere exists an instance distribution of the on- line feedback arc set problem where vertices arrive in ad- versarial order such that any randomized algorithm has a competitive ratio Ω(n), where n is the number of vertices.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) alternatives and a rational distribution \(\mu\) over complete rankings, reveal alternatives in adversarial order and, at each arrival, reveal only the majority comparisons between the new alternative and those already arrived. The algorithm must maintain an ordering without changing the relative order of previously arrived alternatives. Is there a distribution over such societies and arrival orders for which every randomized strategy has expected backward-edge cost at least \(\Omega(m)\) times the offline optimum?
Let \(m\geq 3\) alternatives have a society \(\mu\) over strict complete rankings, with positive rational masses summing to \(1\). A society is represented by its support: the list of its \(\tau\) positive-mass types, each mass encoded as a binary rational; \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total encoding length; measure running times in \(m,\tau,L\).
Assume no pairwise majority ties. Direct \(a\to b\) exactly when \(\mu\) assigns mass greater than \(\tfrac12\) to rankings placing \(a\) before \(b\). For an ordering \(\pi\), let \(C_\mu(\pi)\) count these edges whose head precedes their tail, each with unit cost, and let \(\mathrm{OPT}(\mu)=\min_\pi C_\mu(\pi)\).
The online algorithm knows \(m\) and the alternative labels, but receives no society or initial sample. Alternatives arrive one at a time; each arrival reveals only the majority-edge directions to earlier arrivals. The algorithm inserts the new alternative into its maintained ordering without changing the relative order of earlier alternatives. Strategies may randomize and have unrestricted computation.
An oblivious adversary draws \((\mu,\sigma)\) from a finitely supported distribution \(D_m\) over societies and arrival permutations, independently of the strategy's random bits. Define \(\mathrm{ALG}_A(\mu,\sigma)\) as the final backward-edge count of strategy \(A\).
Does there exist a constant \(c>0\) and a family \((D_m)\), for all sufficiently large \(m\), with \(\mathbb E_{D_m}[\mathrm{OPT}]>0\), such that every randomized online strategy \(A\) satisfies \(\mathbb E_{D_m,A}[\mathrm{ALG}_A]\geq cm\,\mathbb E_{D_m}[\mathrm{OPT}]\), or is such a family impossible?
For arbitrary finite tournaments with adversarial vertex arrivals and the same insertion constraint, a distributional \(\Omega(m)\) randomized competitive lower bound and an \(O(m)\) competitive algorithm are known ([source](https://ojs.aaai.org/index.php/AAAI/article/download/30051/31851)).
No result for precisely this rational-society formulation was located in the search.
Yes. There is an explicit distribution \(D_m\), supported on at most three rational societies, such that every randomized online strategy \(A\) satisfies
\(\mathbb E_{D_m,A}[\mathrm{ALG}_A]\geq \dfrac m3\,\mathbb E_{D_m}[\mathrm{OPT}]\)
for every \(m\geq3\). Each society has optimum exactly \(1\), support size at most \(m(m-1)\), and polynomial encoding length.
Use the alternative labels \(a,b,c,x_1,\ldots,x_{m-3}\). Every instance has the fixed arrival order
\(\sigma=(a,b,c,x_1,\ldots,x_{m-3})\),
and the first three alternatives induce the directed cycle \(a\to b\to c\to a\).
Choose \(w\) uniformly from \(\{a,b,c\}\). Write the other two triangle vertices as \(u,v\), uniquely determined by
\(w\to u,\qquad u\to v,\qquad v\to w.\)
Construct the tournament \(T_w\) as follows:
These rules specify every pair of alternatives.
Claim. The minimum backward-edge count of \(T_w\) is exactly \(1\).
Proof. The triangle on \(w,u,v\) is directed cyclically, so every linear ordering has at least one backward edge: an ordering with all three edges forward would require \(w\) before \(u\), \(u\) before \(v\), and \(v\) before \(w\).
Conversely, order the vertices as \(v\), followed by \(W\) in its transitive order, followed by \(u\). All edges are forward except \(u\to v\). Thus the optimum is \(1\). \(\square\)
Fix any randomized strategy \(A\). Its information during the first three arrivals is identical for all three choices of \(w\). Because \(w\) is independent of its random bits, the maintained ordering \(\pi_3\) after those arrivals is independent of \(w\).
For any realization of \(\pi_3\), let \(F(\pi_3)\) be the number of forward edges of the initial directed triangle. We have both
\(F(\pi_3)\geq1\)
and at least one backward edge. Indeed, making all three edges forward would contradict their cyclic orientation; making all three backward would contradict the cyclic orientation obtained by reversing every edge.
For the chosen \(w\), consider its opposite triangle edge \(u\to v\). Suppose this edge is forward in \(\pi_3\), so \(u\) precedes \(v\). The insertion constraint preserves that relative order permanently.
Every later vertex \(x_i\) has edges \(x_i\to u\) and \(v\to x_i\). Those two edges cannot both be forward: that would require \(v\) before \(x_i\) before \(u\), contradicting the permanently fixed order of \(u,v\). Consequently, each later vertex contributes at least one backward edge whenever \(u\to v\) is forward in \(\pi_3\).
The edges counted for different \(x_i\) are distinct, and none belongs to the initial triangle. Therefore, pointwise,
\(\mathrm{ALG}_A(T_w,\sigma)\geq1+(m-3)\mathbf 1\{u\to v\text{ is forward in }\pi_3\}.\)
As \(w\) ranges uniformly over the three triangle vertices, its opposite edge ranges uniformly over the three triangle edges. Conditional on \(\pi_3\), therefore,
\(\Pr\{u\to v\text{ is forward in }\pi_3\mid\pi_3\}=\dfrac{F(\pi_3)}3\geq\dfrac13.\)
Taking expectations gives
\(\mathbb E[\mathrm{ALG}_A(T_w,\sigma)]\geq1+\dfrac{m-3}{3}=\dfrac m3.\)
This argument permits unrestricted computation and even knowledge of the distribution: only the unrevealed choice of \(w\) matters.
We now prove that each tournament above is the majority tournament of a society satisfying the required representation conditions.
Lemma. Every tournament \(T\) on \(m\) alternatives is realizable by a rational society with no pairwise majority ties and support size at most \(m(m-1)\).
Proof. Put \(q=\binom m2\). For each directed edge \(s\to t\) of \(T\), list the remaining alternatives in any fixed order \(r_1,\ldots,r_{m-2}\), and introduce the two strict complete rankings
\(s,t,r_1,\ldots,r_{m-2}\)
and
\(r_{m-2},\ldots,r_1,s,t.\)
Give each of these \(2q\) ranking occurrences mass \(1/(2q)\).
Within the pair associated with \(s\to t\), both rankings put \(s\) before \(t\). For every other unordered pair, the two rankings disagree:
Fix any edge \(a\to b\) of \(T\). Its own associated pair contributes two occurrences putting \(a\) before \(b\). Each of the other \(q-1\) associated pairs contributes exactly one such occurrence. Thus the total mass putting \(a\) before \(b\) is
\(\dfrac{2+(q-1)}{2q}=\dfrac12+\dfrac1{2q}>\dfrac12.\)
The resulting majority tournament is exactly \(T\), with no ties.
If a ranking occurs more than once, merge its occurrences into one positive-mass type. Every resulting mass is \(k/(2q)\) for a positive integer \(k\), and the masses sum to \(1\). The number of distinct types is at most \(2q=m(m-1)\). \(\square\)
Under the usual explicit encoding of rankings by binary alternative labels, each ranking requires \(O(m\log m)\) bits and each mass requires \(O(\log m)\) bits. Hence the constructed society has total encoding length \(L=O(m^3\log m)\). Generating the rankings and merging duplicates takes polynomial time in \(m\); no computational restriction is imposed on the online strategy.
For each \(w\in\{a,b,c\}\), apply the lemma to \(T_w\), obtaining a society \(\mu_w\). Define \(D_m\) by choosing \(w\) uniformly and returning \((\mu_w,\sigma)\).
This distribution has finite support of size at most three and is independent of the strategy’s random bits. Each society has majority tournament \(T_w\), so
\(\mathbb E_{D_m}[\mathrm{OPT}]=1>0.\)
The online observations and all backward-edge costs depend only on that majority tournament. The bound proved in Section 2 therefore yields, for every randomized strategy \(A\),
\(\mathbb E_{D_m,A}[\mathrm{ALG}_A]\geq\dfrac m3=\dfrac m3\,\mathbb E_{D_m}[\mathrm{OPT}].\)
Thus the requested family exists with \(c=\tfrac13\), already for every \(m\geq3\).
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the task. It establishes the requested family with \(c=\tfrac13\) for every \(m\geq3\), including the required condition \(\mathbb E_{D_m}[\mathrm{OPT}]>0\). No major or minor mathematical issues were found.
The argument is self-contained and does not rely on the externally cited tournament result.
For each choice of \(w\), the vertices \(u,v\) are uniquely determined by the fixed directed triangle.
The construction specifies exactly one direction for every unordered pair:
These rules are consistent with the initial triangle: they give \(w\to u\), \(u\to v\), and \(v\to w\). Consequently, every choice of \(w\) reveals the same majority directions during the first three arrivals.
The construction also applies when \(m=3\), where \(W=\{w\}\) and there are no later vertices.
Finding: Correct and complete.
The directed triangle forces at least one backward edge in every ordering. The three requirements for all its edges to be forward are incompatible.
In the proposed ordering—\(v\), then \(W\) in its transitive order, then \(u\)—every edge category listed above is forward except \(u\to v\). Thus this ordering has exactly one backward edge.
Both bounds hold for every \(m\geq3\).
Finding: The claim \(\mathrm{OPT}(T_w)=1\) is proved.
The strategy receives the same labels, arrival order, and revealed directions through the third arrival for all choices of \(w\). It receives neither the society nor a sample.
Therefore its maintained ordering \(\pi_3\) depends only on this common observation history and its random bits. Since the adversary’s choice of \(w\) is independent of those bits, \(\pi_3\) is independent of \(w\).
This remains valid if the strategy knows the distribution: such knowledge does not reveal its realized choice.
Finding: The independence assertion satisfies the stated information model and quantifiers.
Suppose the opposite edge \(u\to v\) is forward in \(\pi_3\). Then \(u\) precedes \(v\), and the insertion constraint preserves this relation.
For any later vertex \(x_i\), making both \(x_i\to u\) and \(v\to x_i\) forward would require \(v\) to precede \(x_i\) and \(x_i\) to precede \(u\). This contradicts the preserved order of \(u,v\).
Hence at least one of those two edges is backward for each \(x_i\). The pairs counted for different \(x_i\) are distinct and exclude the initial triangle. The triangle itself still contributes at least one backward edge. Therefore the displayed pointwise inequality is justified:
\[ \mathrm{ALG}_A(T_w,\sigma)\geq 1+(m-3)\mathbf 1\{u\to v\text{ is forward in }\pi_3\}. \]
Finding: Correct, with no double counting or assumptions about later insertion choices.
A linear ordering of a directed triangle has at least one forward edge and at least one backward edge. Thus \(F(\pi_3)\geq1\).
The mapping from \(w\) to its opposite directed edge is a bijection onto the three triangle edges. Independence ensures that, conditional on any realized \(\pi_3\) of positive probability, \(w\) remains uniform. Consequently,
\[ \Pr\{u\to v\text{ is forward in }\pi_3\mid\pi_3\} =\frac{F(\pi_3)}3\geq\frac13. \]
Taking expectations in the pointwise inequality gives
\[ \mathbb E[\mathrm{ALG}_A(T_w,\sigma)] \geq1+\frac{m-3}{3} =\frac m3. \]
For \(m=3\), the later-vertex term vanishes and the bound is exactly the triangle’s unavoidable cost.
Finding: The bound applies to every randomized insertion strategy, including strategies with unrestricted computation.
Each gadget contains two strict complete rankings. Both put its designated tail before its designated head.
For every other unordered pair, the two rankings disagree:
Thus, for any prescribed edge, its own gadget contributes two supporting occurrences, while each other gadget contributes one. With \(q=\binom m2\), its supporting mass is correctly computed as
\[ \frac{q+1}{2q}=\frac12+\frac1{2q}. \]
Every prescribed majority is therefore strict, and the realized tournament is exactly the intended tournament.
Merging repeated rankings preserves all pairwise masses. Each merged mass is a positive rational \(k/(2q)\), the masses sum to one, and the number of distinct types is at most \(2q=m(m-1)\).
Under the explicitly stated binary-label encoding, the claimed bound \(L=O(m^3\log m)\) follows from at most \(O(m^2)\) rankings, each using \(O(m\log m)\) bits, and rational masses using \(O(\log m)\) bits. Duplicate merging is a routine polynomial-time operation.
Finding: All required representation conditions are satisfied.
Choosing \(w\) uniformly and returning \((\mu_w,\sigma)\) defines a finitely supported distribution independent of the strategy’s random bits. Its support has size at most three. For \(m=3\), coincident outcomes merely reduce that support size.
Because both observations and costs depend only on majority directions, the tournament lower bound transfers directly to these societies. Each has optimum one, so the required inequality follows with \(c=\tfrac13\).
No repair or additional clarification is needed. The proof establishes an online competitive lower bound; it does not classify computational complexity of a continuous problem.
⟨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.