Dodgson Yöntemi - Minimum ikili takas ile Condorcet tamamlama

Formül adımları

Analiz motorunun yöntem bildirimindeki (manifest F.steps) adımlar; raporlardaki formüllerle aynı kaynaktır.

1. Adım 1 — Sıralamaları topla; ikili tercih sayım matrisi p_ij hesapla.

   $$R=[r_{ik}{]}_{m\times n},p_{ij}=\#\{k:r_{ik}<r_{jk}\}$$
   LaTeX

   R=[r_{ik}]_{m\times n},\ p_{ij}=\#\{k: r_{ik} < r_{jk}\}

2. Adım 2 — Her alternatif i için, i'nin Condorcet kazananı olması için (tüm sıralamalarda) gereken minimum bitişik takas sayısını bul; toplam takaslar = s_i.

   $$s_i={min}_{\pi \in S_m^n}\#\{\text{adjacent swaps in }{\pi }^{(1)},\dots ,{\pi }^{(n)}\}\text{s.t.}{p}_{ij}^{\pi }>p_{ji}^{\pi }\forall j\ne i$$
   LaTeX

   s_{i} = \min_{\pi\in S_{m}^{n}} \#\{\text{adjacent swaps in } \pi^{(1)},\ldots,\pi^{(n)}\}\ \text{s.t.}\ p_{ij}^{\pi} > p_{ji}^{\pi}\ \forall j\neq i

3. Adım 3 — Dodgson kazananı = arg min_i s_i (en az takasa gerek duyan alternatif). Diğerleri artan takas sayısına göre sıralanır.

   $$i^{*}=\mathrm{\backslash arg}{min}_{i\in \{1,\dots ,m\}}{s}_i;\text{Rank}(i)\propto s_i$$
   LaTeX

   i^{*} = \arg\min_{i\in\{1,\ldots,m\}} s_{i};\quad \text{Rank}(i) \propto s_{i}

Sezgi

Pairwise-swap distance - alternative needing fewest swaps to become Condorcet winner. Output typically rank_position (lower value = preferred).

Sonucu okuma: Dodgson selects the alternative that is 'closest' to being a Condorcet winner - measured in pairwise swap distance. Always returns a winner (no paradox), but winner determination is NP-hard for unrestricted preference profiles. For m ≤ 10, exhaustive search is practical; beyond that, use approximation algorithms. Orakçı 2024 (Bölüm 3) shows Dodgson fails to produce full rankings in 82-99% of random samples for m ≥ 3 - use Kemeny or RAT for guaranteed full rankings.

Varsayımlar

• Input is a rank matrix (1=best, m=worst per voter)
• Each voter ranks all alternatives

Ne zaman kullanılmaz

• Cardinal preferences important → use a MAUT method

Sınırlılıklar

• Assumes: Input is a rank matrix (1=best, m=worst per voter)
• Assumes: Each voter ranks all alternatives

Sık yapılan hatalar

• Kazanan belirleme NP-zordur - pratikte m>12 için tükenmesiz hesaplama imkansız. Yaklaşım algoritmaları kullanın.
• Sık tam-olmayan sıralama: Orakçı 2024'e göre Dodgson %82-99 oranında tam sıralama üretemez - tamlık önemliyse RAT/Kemeny kullanın.