[Model] MaximumLikelihoodRanking

[isPANN]

Motivation

MAXIMUM LIKELIHOOD RANKING (MS11) from Garey & Johnson, A12. Given an n × n comparison matrix A where a_ij represents the number of times item i was preferred over item j (with a_ij + a_ji = c for a fixed constant c representing total comparisons per pair), find a permutation (ranking) of items that minimizes the total disagreement cost. NP-hard in the strong sense. Related to the minimum-weight feedback arc set problem on tournaments, but with a different input structure (matrix vs. graph) and variable space (permutations vs. arc subsets). Applications include sports ranking, social choice theory, search engine result aggregation, and the Kemeny ranking problem.

Definition

Name: MaximumLikelihoodRanking
Reference: Garey & Johnson, Computers and Intractability, A12 MS11

Mathematical definition:

INSTANCE: An n × n matrix A of non-negative integers with a_ij + a_ji = c for a fixed constant c ≥ 0 (each pair has the same total comparison count), and a_ii = 0 for all i.
OBJECTIVE: Find a permutation π of {1, 2, ..., n} that minimizes the total disagreement cost: Σ_{i>j} a_{π(i),π(j)} (the sum of entries below the main diagonal after permuting rows and columns by π).

Variables

• Count: n (one per item)
• Per-variable domain: {0, 1, ..., n-1} (the permutation rank assigned to each item)
• Meaning: The position of each item in the ranking. The configuration must be a valid permutation (all values distinct). The objective is to minimize the disagreement cost.

Schema

Type name: MaximumLikelihoodRanking
Variants: none

Field	Type	Description
matrix	Vec<Vec<i32>>	The n × n comparison matrix A where a_ij is the preference count of i over j

Invariant: The matrix is square (n × n). Diagonal entries are 0. Entries are non-negative. a_ij + a_ji = c for a fixed constant c.

Complexity

• NP-completeness: NP-hard in the strong sense, via reduction from FEEDBACK ARC SET. The original G&J citation is to Rafsky (1977, private communication). The NP-hardness of the closely related minimum feedback arc set on tournaments was independently established by Alon (2006, "Ranking Tournaments," SIAM J. Discrete Math. 20(1)) and Charbit, Thomassé & Yeo (2007).
• Best known exact algorithm: O*(n² · 2^n) via Held-Karp-style dynamic programming over subsets.
• Complexity string: "num_items^2 * 2^num_items"
• Polynomial special cases: When the matrix is consistent (there exists a permutation with 0 disagreement), the problem is trivially solvable by topological sort.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all n! permutations of items and compute the disagreement cost for each; return the minimum.)
• It can be solved by reducing to integer programming. (ILP: binary variables x_ij = 1 iff item i is ranked before item j, with antisymmetry and transitivity constraints; minimize Σ a_ij · x_ji.) See companion issue [Rule] MaximumLikelihoodRanking to ILP #969.
• Other:

Reduction Rule Crossref

• [Rule] MaximumLikelihoodRanking to ILP #969 — [Rule] MaximumLikelihoodRanking to ILP (direct ILP formulation)

Example Instance

Input:
4 items with comparison matrix A (c = 5 comparisons per pair):

A = [[0, 4, 3, 5],
     [1, 0, 4, 3],
     [2, 1, 0, 4],
     [0, 2, 1, 0]]

Antisymmetry: a_ij + a_ji = 5 for all pairs. Item 0 dominates (beats all others strongly), item 3 is weakest (loses all pairwise comparisons to 0, and mostly loses to 1 and 2).

Optimal ranking π = (0, 1, 2, 3):
Disagreement = Σ_{i>j} a_{π(i),π(j)} = a_{1,0} + a_{2,0} + a_{2,1} + a_{3,0} + a_{3,1} + a_{3,2}
= 1 + 2 + 1 + 0 + 2 + 1 = 7

Suboptimal ranking π = (0, 1, 3, 2):
Disagreement = a_{1,0} + a_{3,0} + a_{3,1} + a_{2,0} + a_{2,1} + a_{2,3}
= 1 + 0 + 2 + 2 + 1 + 4 = 10

Why this ranking is optimal: Item 0 beats all others decisively (a_{0,j} ≥ 3 for all j), so placing 0 first incurs minimal backward cost. The remaining items form a chain 1 > 2 > 3 with decreasing strength, and the ordering (1, 2, 3) minimizes disagreements among them.

Expected Outcome

Optimal value: Min(7) — the minimum disagreement cost is 7, achieved uniquely by π = (0, 1, 2, 3). Out of 24 permutations, there are 12 distinct cost values ranging from 7 to 23.

Extra Remark

Full book text:

INSTANCE: n × n antisymmetric matrix A of non-negative integers (a_ij + a_ji = constant for each pair), positive integer B.
QUESTION: Is there a permutation π of {1, ..., n} such that Σ_{i>j} a_{π(i),π(j)} ≤ B?

Reference: [Rafsky, 1977]. Transformation from FEEDBACK ARC SET.
Comment: NP-complete in the strong sense.

Note: The original G&J formulation is a decision problem with bound B. We use the equivalent optimization formulation: minimize the total disagreement cost. The reference [Rafsky, 1977] is a private communication cited by Garey & Johnson; the NP-hardness result is corroborated by later published work on minimum feedback arc set in tournaments (Alon 2006, Charbit, Thomassé & Yeo 2007).

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	❌ Fail	No planned reduction rules; problem appears isomorphic to existing MinimumFeedbackArcSet on tournaments
Non-trivial	❌ Fail	Issue itself states equivalence to minimum-weight feedback arc set in tournaments; MinimumFeedbackArcSet already exists
Correctness	❌ Fail	Antisymmetry condition is a tautology; Rafsky 1977 unverifiable; Betzler et al. 2009 complexity claim misrepresented
Well-written	❌ Fail	Missing Expected Outcome; garbled definition; self-correcting example; no reduction crossrefs

Overall: 0 passed, 0 warnings, 4 failed

---

Usefulness

1. Problem does not yet exist in the codebase — pred show MaximumLikelihoodRanking returns not found.

2. No planned reductions. The issue does not mention any concrete reduction rule connecting this problem to the existing reduction graph. The "How to solve" section only checks brute-force and mentions ILP as a possibility but does not link a companion [Rule] MaximumLikelihoodRanking to ILP issue. An orphan problem with no planned reductions has no value in the reduction graph.

3. Isomorphic to existing problem. The issue itself states: "The problem is equivalent to the minimum-weight feedback arc set in tournaments." MinimumFeedbackArcSet already exists in the codebase (src/models/graph/minimum_feedback_arc_set.rs). If the problem is truly equivalent, it should be handled as a variant or the equivalence should be exploited as a reduction rule — not as a brand-new problem.

Non-trivial

The issue explicitly claims mathematical equivalence to the minimum-weight feedback arc set in tournaments. The existing MinimumFeedbackArcSet<W> model operates on directed graphs, which subsumes tournaments. The only structural difference is the input representation (comparison matrix vs. directed graph), but this is a data-format difference, not a different feasibility constraint or objective function. The objective in both cases is to find a permutation (equivalently, a topological ordering after removing minimum-weight backward arcs) that minimizes disagreement cost.

This makes the proposed problem either:

• Isomorphic to MinimumFeedbackArcSet restricted to tournament graphs, or
• A trivial variant that could be handled by adding a tournament graph type to the existing model.

Either way, it does not introduce a genuinely distinct feasibility constraint or objective.

Correctness

1. Antisymmetry condition is a tautology. The definition states: "a_ij + a_ji = a_ji + a_ij" — this is trivially true for all matrices and imposes no constraint. The intended condition is likely "a_ij + a_ji = c" for some constant c (the total number of comparisons between items i and j), or the stricter "a_ij + a_ji = 0" (as in Garey & Johnson's original formulation per npcomplete.owu.edu).

2. Rafsky 1977 cannot be verified. According to the NP-Complete Problems discussion site, this is a "private communication" result — no published paper by Rafsky on this topic could be found via web search. The NP-completeness claim itself is plausible (it follows from NP-hardness of minimum feedback arc set on tournaments, proven by Alon 2006 and Charbit, Thomasse & Yeo 2007), but the specific citation to "Rafsky 1977" is unverifiable.

3. Betzler et al. (2009) complexity claim is misrepresented. The issue claims "Betzler et al. (2009) give an O*(1.403^n) algorithm for the Kemeny ranking variant." However, Betzler et al. (2009) provide fixed-parameter tractable algorithms parameterized by the average Kendall-Tau distance, not an O*(1.403^n) algorithm in the number of candidates. The 1.403^k bound (if it appears) is parameterized by the Kemeny score k, not by n. This is a significant misrepresentation.

4. Complexity string is unnecessarily loose. The proposed "2^num_items" is a naive bound (enumerate all n! permutations, bounded by 2^n for the DP). Better exact algorithms exist — e.g., the Held-Karp-style DP runs in O(n^2 * 2^n), and there may be improvements. The complexity string should cite a specific algorithm.

Well-written

1. Missing Expected Outcome section. The template requires a concrete optimal solution with the optimal objective value. The issue does not provide one — it ends mid-computation with "Answer: YES with B = 4" after changing the bound partway through.

2. Garbled antisymmetry definition. As noted above, "a_ij + a_ji = a_ji + a_ij" is a tautology, not a constraint. The parenthetical clarification is also confusing — it says "antisymmetric" but then describes a non-negative matrix, which contradicts standard antisymmetry (a_ij = -a_ji).

3. Self-correcting example. The example tries permutation after permutation, finds none work for B=3, then changes the bound to B=4 mid-stream. A well-written example should present one clean instance with a definitive answer, not a trial-and-error narrative.

4. Variable domain issue. The variables section states the domain is {0, 1, ..., n-1} and configurations must be valid permutations, but the standard dims() framework (which would return [n, n, ..., n]) does not enforce the permutation constraint. The issue should address how this will be handled in the implementation (e.g., via a custom evaluate that returns a penalty for non-permutation configs, or via a different representation).

5. No reduction crossrefs. There are no links to companion [Rule] issues. At minimum, the natural reduction to/from MinimumFeedbackArcSet should be discussed.

Recommendations

• Consider whether this problem is better handled as a reduction rule (MaximumLikelihoodRanking <-> MinimumFeedbackArcSet) rather than a standalone model, given the stated equivalence.
• If proceeding as a new model, the issue must clearly articulate what distinguishes it from MinimumFeedbackArcSet — different input structure (matrix vs. graph), different variable semantics (permutation vs. arc selection), or a genuinely different objective.
• Fix the antisymmetry condition to match Garey & Johnson's original: a_ij + a_ji = 0 (or a_ij + a_ji = constant).
• Provide a clean, non-trivial example with an explicit optimal permutation and optimal objective value.
• Cite verifiable references — the NP-hardness of minimum FAS on tournaments was proven by Charbit, Thomasse & Yeo (2007) and Alon (2006), which are citable published papers.