Setup: the 48 election states¶
In [1]:
import itertools
from itertools import permutations, product
from collections import deque
import pandas as pd
import networkx as nx
from IPython.display import HTML, display
pd.set_option('display.max_colwidth', None)
display(HTML('''<style>
.dataframe td, .dataframe th { white-space: nowrap; padding: 4px 12px; text-align: left; }
table.dataframe { display: block; overflow-x: auto; }
</style>'''))
CANDS = ['A', 'B', 'C']
PAIRS = [frozenset(p) for p in itertools.combinations(CANDS, 2)]
def all_states():
# a state assigns each of the 3 pairs to a margin-rank slot 0 (smallest)
# .. 2 (largest) and picks a winner for each pair: 3! * 2^3 = 48 states
out = []
for pair_order in permutations(PAIRS):
for bits in product([0, 1], repeat=3):
matchups = []
for pair, bit in zip(pair_order, bits):
a, b = tuple(pair)
matchups.append((a, b) if bit == 0 else (b, a))
out.append(tuple(matchups))
return out
def condorcet_winner(P):
wins = {}
for w, _ in P:
wins[w] = wins.get(w, 0) + 1
return next((c for c in CANDS if wins.get(c) == 2), None)
def winner(P):
# f(P): the Condorcet winner if one exists, else the minimax tiebreak --
# the candidate who loses the smallest-margin matchup (= win(P0))
cw = condorcet_winner(P)
return cw if cw is not None else P[0][1]
def is_cycle(P):
return condorcet_winner(P) is None
def swap01(P): # reverse the smallest matchup -- "swap of the second kind"
w1, l1 = P[0]
return ((l1, w1), P[1], P[2])
def swap12(P): # "swap of the first kind" on the two closest matchups
return (P[1], P[0], P[2])
def swap23(P): # "swap of the first kind" on the two widest matchups
return (P[0], P[2], P[1])
SIGMAS = {'(0,1)': swap01, '(1,2)': swap12, '(2,3)': swap23}
def fmt_state(P):
# plain text, not LaTeX: MathJax's automatic line-breaking splits this
# mid-expression at narrow widths instead of using the column's full space
return ' | '.join(f'{w}→{l}' for w, l in P)
STATES = all_states()
CYCLIC = [s for s in STATES if is_cycle(s)]
pd.Series({
'total states': len(STATES),
'unique states': len(set(STATES)),
'cyclic (no Condorcet winner)': len(CYCLIC),
**{f'Condorcet winner = {c}': sum(1 for s in STATES if condorcet_winner(s) == c) for c in CANDS},
}, name='count').to_frame()
Out[1]:
| count | |
|---|---|
| total states | 48 |
| unique states | 48 |
| cyclic (no Condorcet winner) | 12 |
| Condorcet winner = A | 12 |
| Condorcet winner = B | 12 |
| Condorcet winner = C | 12 |
One-way push: what a coalition can achieve¶
In [2]:
def prefers(order, x, y):
# order = coalition's sincere ranking, most preferred first
return order.index(x) < order.index(y)
def achievable(P, sigma_name, order):
# Lemma (One-Way Push): a coalition can only move a margin toward its
# LESS preferred candidate, never toward its favorite
if sigma_name == '(0,1)':
w1, l1 = P[0]
return prefers(order, w1, l1)
(w_i, l_i), (w_j, l_j) = (P[0], P[1]) if sigma_name == '(1,2)' else (P[1], P[2])
return prefers(order, l_i, w_i) or prefers(order, w_j, l_j)
def profitable_simple(P, order):
fp = winner(P)
out = []
for name, fn in SIGMAS.items():
if not achievable(P, name, order):
continue
Q = fn(P)
if prefers(order, winner(Q), fp):
out.append((name, Q))
return out
Four theorems about simple manipulations¶
In [ ]:
results = []
def check(label, ok):
results.append((label, 'PASS' if ok else 'FAIL'))
assert ok, label
# Theorem (Condorcet Stability): a state with a Condorcet winner has no
# profitable simple manipulation, for any coalition
v = [(s, o) for s in STATES if not is_cycle(s) for o in permutations(CANDS) if profitable_simple(s, o)]
check('Condorcet Stability: CW states have no profitable simple manipulation', len(v) == 0)
# Lemma: a swap of the second kind (reversing the smallest matchup) is
# never profitable
v = [(s, o) for s in STATES for o in permutations(CANDS)
if achievable(s, '(0,1)', o) and prefers(o, winner(swap01(s)), winner(s))]
check('A swap of the second kind is never profitable', len(v) == 0)
# Lemma: a (2,3) swap (the two widest matchups) is never profitable for n=3
v = [(s, o) for s in STATES for o in permutations(CANDS)
if achievable(s, '(2,3)', o) and prefers(o, winner(swap23(s)), winner(s))]
check('A (2,3) swap is never profitable', len(v) == 0)
# Corollary: an intransitive, non-adjacent deviation (e.g. voting C>A while
# sincerely A>B>C) is never profitable
def flip_pair(P, pair):
return tuple(((l, w) if frozenset((w, l)) == pair else (w, l)) for w, l in P)
AC = frozenset(('A', 'C'))
v = [s for s in STATES
if next(w for w, l in s if frozenset((w, l)) == AC) == 'A'
and prefers(('A', 'B', 'C'), winner(flip_pair(s, AC)), winner(s))]
check('Voting your least favorite over your favorite is never profitable', len(v) == 0)
# Corollary (Voting intransitively): a coalition sincerely preferring
# A>B>C can cast a genuinely cyclic ballot (not a valid ranking) in exactly
# two ways: flip only A>C (the check above -- ballot A>B, B>C, C>A), or flip
# both A>B and B>C at once (ballot B>A, C>B, A>C, the mirror cycle). Neither
# is ever profitable, so an intransitive ballot never helps a transitive
# voter -- despite the system allowing it, unlike a typical ranked ballot.
def flip_pairs(P, pairs):
return tuple(((l, w) if frozenset((w, l)) in pairs else (w, l)) for w, l in P)
AB, BC = frozenset(('A', 'B')), frozenset(('B', 'C'))
v = [s for s in STATES
if next(w for w, l in s if frozenset((w, l)) == AB) == 'A'
and next(w for w, l in s if frozenset((w, l)) == BC) == 'B'
and prefers(('A', 'B', 'C'), winner(flip_pairs(s, {AB, BC})), winner(s))]
check('The other intransitive ballot pattern (bury both A>B and B>C at once) is never profitable', len(v) == 0)
pd.DataFrame(results, columns=['claim', 'result'])
The two gates¶
In [4]:
order_ABC = ('A', 'B', 'C')
gates = [s for s in STATES if profitable_simple(s, order_ABC)]
# the post's Theorem (Profitable Cycles) names these two states explicitly
G1 = (('C', 'B'), ('B', 'A'), ('A', 'C'))
G2 = (('B', 'C'), ('A', 'B'), ('C', 'A'))
check("Brute-forced gates for A>B>C match the post's G1, G2 exactly", set(gates) == {G1, G2})
# generalize across all 6 coalition orderings
by_order = {o: [s for s in STATES if profitable_simple(s, o)] for o in permutations(CANDS)}
all_pairs = [(s, o) for o, ss in by_order.items() for s in ss]
distinct_states = {s for s, _ in all_pairs}
check('12 total (state, coalition) profitable-simple-manipulation pairs', len(all_pairs) == 12)
check('every one of them starts from a cyclic state', all(is_cycle(s) for s, _ in all_pairs))
check('each cyclic state has a UNIQUE exploiting coalition',
all(sum(1 for s2, _ in all_pairs if s2 == s) == 1 for s in distinct_states))
check('...covering all 12 cyclic states', len(distinct_states) == len(CYCLIC))
pd.DataFrame(results[-5:], columns=['claim', 'result'])
Out[4]:
| claim | result | |
|---|---|---|
| 0 | Brute-forced gates for A>B>C match the post's G1, G2 exactly | PASS |
| 1 | 12 total (state, coalition) profitable-simple-manipulation pairs | PASS |
| 2 | every one of them starts from a cyclic state | PASS |
| 3 | each cyclic state has a UNIQUE exploiting coalition | PASS |
| 4 | ...covering all 12 cyclic states | PASS |
Complex manipulations: the reachability theorem¶
In [ ]:
def slot_of(P, pair):
return next(i for i, (w, l) in enumerate(P) if frozenset((w, l)) == pair)
def concordant(P, pair, order):
w = next(w for w, l in P if frozenset((w, l)) == pair)
a, b = tuple(pair)
return w == (a if prefers(order, a, b) else b)
def reachable(P0, Q, order):
# Theorem (Reachability): Q is reachable from P0 by chaining one-way-push
# moves iff (a) every matchup concordant in Q was already concordant in
# P0, and (b) a discordant matchup that out-ranked a concordant one in
# P0 still out-ranks it in Q
for pair in PAIRS:
if concordant(Q, pair, order) and not concordant(P0, pair, order):
return False
for d in PAIRS:
if concordant(P0, d, order):
continue
for c in PAIRS:
if c == d or not concordant(Q, c, order):
continue
if slot_of(P0, d) > slot_of(P0, c) and not slot_of(Q, d) > slot_of(Q, c):
return False
return True
def R(P0, order):
return [Q for Q in STATES if reachable(P0, Q, order)]
check('every state trivially reaches itself', all(reachable(s, s, order_ABC) for s in STATES))
pd.DataFrame(results[-1:], columns=['claim', 'result'])
Six states, two chains¶
In [ ]:
admits_complex = [s for s in STATES if any(prefers(order_ABC, winner(q), winner(s)) for q in R(s, order_ABC))]
check('exactly 6 of 48 states admit a profitable complex manipulation', len(admits_complex) == 6)
# footnote: across all 6 coalitions, 36 (state, coalition) pairs over 30
# distinct states -- all 12 cyclic states plus half (18/36) of the CW states
by_order_c = {o: [s for s in STATES if any(prefers(o, winner(q), winner(s)) for q in R(s, o))]
for o in permutations(CANDS)}
all_pairs_c = [(s, o) for o, ss in by_order_c.items() for s in ss]
distinct_c = {s for s, _ in all_pairs_c}
check('36 (state, coalition) pairs across 30 distinct states', len(all_pairs_c) == 36 and len(distinct_c) == 30)
check('...covering all 12 cyclic states', sum(1 for s in distinct_c if is_cycle(s)) == 12)
check('...and exactly half (18/36) of the Condorcet-winner states', sum(1 for s in distinct_c if not is_cycle(s)) == 18)
# Corollary (One-notch bound): can never jump from C's outcome straight to A's
v = [(s, q) for s in STATES if winner(s) == 'C' for q in R(s, order_ABC) if winner(q) == 'A']
check('one-notch bound: no C -> A complex manipulation', len(v) == 0)
# Theorem (No favorite betrayal under a CW): among CW states that admit a
# profitable complex manipulation, that CW is always the coalition's MIDDLE
# choice (B), never their least favorite (C)
cw_ancestors = [s for s in admits_complex if not is_cycle(s)]
check("every CW that can be complexly overturned is the coalition's 2nd choice",
all(winner(s) == 'B' for s in cw_ancestors))
pd.DataFrame(results[-5:], columns=['claim', 'result'])
Reconstructing the burial and betrayal chains¶
In [7]:
# rebuild the chains from scratch via graph search (not hand-copied from the
# post) to keep this an independent check, not a restatement
def induced_edges(node_set):
return {s: [(name, fn(s)) for name, fn in SIGMAS.items() if fn(s) in node_set] for s in node_set}
def bfs_path(root, targets, node_set):
edges = induced_edges(node_set)
prev = {root: None}
q = deque([root])
while q:
u = q.popleft()
if u in targets:
path = []
while u is not None:
path.append(u)
u = prev[u]
return list(reversed(path))
for _, v in edges[u]:
if v not in prev:
prev[v] = u
q.append(v)
return None
def find_chain(root, order):
Rroot = set(R(root, order))
best = max((winner(q) for q in Rroot), key=lambda c: -order.index(c))
targets = {q for q in Rroot if winner(q) == best}
return bfs_path(root, targets, Rroot)
chains = {root: find_chain(root, order_ABC) for root in admits_complex}
burial_chain = max((c for c in chains.values() if winner(c[-1]) == 'A'), key=len)
betrayal_chain = max((c for c in chains.values() if winner(c[-1]) == 'B'), key=len)
check('every discovered chain lands on a strictly-preferred winner',
all(prefers(order_ABC, winner(c[-1]), winner(c[0])) for c in chains.values()))
check('burial chain has length 5 (post: 3 ancestors + G1 + Q1)', len(burial_chain) == 5)
check('betrayal chain has length 3 (post: 1 ancestor + G2 + Q2)', len(betrayal_chain) == 3)
def chain_table(chain):
return pd.DataFrame([{
'step': i, 'state': fmt_state(s), 'winner': winner(s),
'type': 'cycle' if is_cycle(s) else 'Condorcet winner',
} for i, s in enumerate(chain)])
display(HTML('<b>Burial chain</b>'))
display(HTML(chain_table(burial_chain).to_html(index=False)))
display(HTML('<b>Betrayal chain</b>'))
display(HTML(chain_table(betrayal_chain).to_html(index=False)))
pd.DataFrame(results[-3:], columns=['claim', 'result'])
Burial chain
| step | state | winner | type |
|---|---|---|---|
| 0 | B→A | A→C | B→C | B | Condorcet winner |
| 1 | B→A | B→C | A→C | B | Condorcet winner |
| 2 | B→C | B→A | A→C | B | Condorcet winner |
| 3 | C→B | B→A | A→C | B | cycle |
| 4 | B→A | C→B | A→C | A | cycle |
Betrayal chain
| step | state | winner | type |
|---|---|---|---|
| 0 | B→C | C→A | A→B | C | cycle |
| 1 | B→C | A→B | C→A | C | cycle |
| 2 | A→B | B→C | C→A | B | cycle |
Out[7]:
| claim | result | |
|---|---|---|
| 0 | every discovered chain lands on a strictly-preferred winner | PASS |
| 1 | burial chain has length 5 (post: 3 ancestors + G1 + Q1) | PASS |
| 2 | betrayal chain has length 3 (post: 1 ancestor + G2 + Q2) | PASS |
The actual manipulation graph around both gates¶
In [8]:
# real single-step edges only (not the R(P0) closure used for the chains
# above) -- this is what the weakest-link tool calls "single step preimages"
def achievable_moves(P, order):
return [(name, fn(P)) for name, fn in SIGMAS.items() if achievable(P, name, order)]
# the full local achievable-move digraph for the A>B>C coalition
LOCAL = nx.DiGraph()
for s in STATES:
for name, q in achievable_moves(s, order_ABC):
LOCAL.add_edge(s, q, sigma=name)
Q1, Q2 = burial_chain[-1], betrayal_chain[-1]
check('G1 is not reachable from G2 in the local achievable-move graph', G1 not in nx.descendants(LOCAL, G2))
check('G1 is not reachable from Q2 in the local achievable-move graph', G1 not in nx.descendants(LOCAL, Q2))
# the 1-hop external boundary: real predecessors of the chain states that
# are not themselves part of either chain
chain_nodes = burial_chain + betrayal_chain
boundary_edges = [(p, LOCAL.edges[p, s]['sigma'], s)
for s in chain_nodes for p in LOCAL.predecessors(s) if p not in chain_nodes]
boundary = list(dict.fromkeys(p for p, _, _ in boundary_edges)) # de-duped, order preserved
check('every boundary node already gives the coalition at least as good an outcome as the chain node it feeds',
all(not prefers(order_ABC, winner(s), winner(p)) for p, _, s in boundary_edges))
pd.DataFrame(results[-3:], columns=['claim', 'result'])
Out[8]:
| claim | result | |
|---|---|---|
| 0 | G1 is not reachable from G2 in the local achievable-move graph | PASS |
| 1 | G1 is not reachable from Q2 in the local achievable-move graph | PASS |
| 2 | every boundary node already gives the coalition at least as good an outcome as the chain node it feeds | PASS |
In [9]:
import matplotlib.pyplot as plt
from matplotlib.patches import FancyBboxPatch, FancyArrowPatch
WIN_COLOR = {'A': '#4C72B0', 'B': '#DD8452', 'C': '#55A868'}
def describe_lie(P, name, order):
# every insincere vote that alone achieves this step (see achievable())
if name == '(0,1)':
w1, l1 = P[0]
return f'{l1}>{w1}'
(w_i, l_i), (w_j, l_j) = (P[0], P[1]) if name == '(1,2)' else (P[1], P[2])
lies = []
if prefers(order, l_i, w_i):
lies.append(f'{w_i}>{l_i}')
if prefers(order, w_j, l_j):
lies.append(f'{l_j}>{w_j}')
return ' or '.join(lies)
node_set = list(dict.fromkeys(chain_nodes + boundary))
GRAPH = LOCAL.subgraph(node_set)
CHAIN_EDGES = set()
for chain in (burial_chain, betrayal_chain):
for a, b in zip(chain, chain[1:]):
CHAIN_EDGES.add((a, b))
# Corollary (Single-lie sufficiency): every edge of the burial chain can be
# achieved by the SAME lie (C>B, burying B) applied with more mass; every
# edge of the betrayal chain by the same B>A (betraying A) -- the chains
# differ only in how far the lie must be pushed, not in what the lie is
def lie_options(a, b):
return set(describe_lie(a, LOCAL.edges[a, b]['sigma'], order_ABC).split(' or '))
check('single-lie sufficiency: C>B alone suffices at every burial-chain edge',
all('C>B' in lie_options(a, b) for a, b in zip(burial_chain, burial_chain[1:])))
check('single-lie sufficiency: B>A alone suffices at every betrayal-chain edge',
all('B>A' in lie_options(a, b) for a, b in zip(betrayal_chain, betrayal_chain[1:])))
pd.DataFrame(results[-2:], columns=['claim', 'result'])
Out[9]:
| claim | result | |
|---|---|---|
| 0 | single-lie sufficiency: C>B alone suffices at every burial-chain edge | PASS |
| 1 | single-lie sufficiency: B>A alone suffices at every betrayal-chain edge | PASS |
In [10]:
# lay out the graph with networkx
# GRAPH is two disconnected components (burial side, betrayal side) --
# kamada_kawai has no path length to place them
# apart by, so it packs them near each other; lay each out on its own and
# offset them side by side instead
pos_nx = {}
x_cursor = 0.0
for component in nx.weakly_connected_components(GRAPH):
sub_pos = nx.kamada_kawai_layout(GRAPH.subgraph(component))
xs = [x for x, y in sub_pos.values()]
width = max(xs) - min(xs) if len(xs) > 1 else 0.0
for node, (x, y) in sub_pos.items():
pos_nx[node] = (x - min(xs) + x_cursor, y)
x_cursor += width + 1.2
fig, ax = plt.subplots(figsize=(12, 8))
cw_nodes = [s for s in GRAPH.nodes if not is_cycle(s)]
cyclic_nodes = [s for s in GRAPH.nodes if is_cycle(s)]
nx.draw_networkx_nodes(GRAPH, pos_nx, nodelist=cw_nodes, node_size=2600,
node_color=[WIN_COLOR[winner(s)] for s in cw_nodes],
edgecolors='black', linewidths=1.4, ax=ax)
cyclic_coll = nx.draw_networkx_nodes(GRAPH, pos_nx, nodelist=cyclic_nodes, node_size=2600,
node_color=[WIN_COLOR[winner(s)] for s in cyclic_nodes],
edgecolors='black', linewidths=1.8, ax=ax)
cyclic_coll.set_linestyle('dashed')
edge_colors = ['#333333' if (u, v) in CHAIN_EDGES else '#aaaaaa' for u, v in GRAPH.edges]
edge_widths = [1.8 if (u, v) in CHAIN_EDGES else 1.0 for u, v in GRAPH.edges]
nx.draw_networkx_edges(GRAPH, pos_nx, edge_color=edge_colors, width=edge_widths,
arrowstyle='-|>', arrowsize=15, connectionstyle='arc3,rad=0.12',
node_size=2600, ax=ax)
labels = {s: f"{fmt_state(s)}\nwinner {winner(s)}" for s in GRAPH.nodes}
nx.draw_networkx_labels(GRAPH, pos_nx, labels=labels, font_size=6.3, ax=ax)
edge_labels = {(u, v): describe_lie(u, data['sigma'], order_ABC) for u, v, data in GRAPH.edges(data=True)}
nx.draw_networkx_edge_labels(GRAPH, pos_nx, edge_labels=edge_labels, font_size=6,
font_color='#333333', connectionstyle='arc3,rad=0.12', rotate=False, ax=ax)
# tag every chain node -- G1/Q1/G2/Q2 by name, the ancestors by position --
# so that whatever's left unlabeled is visibly the boundary
named = {}
for i, node in enumerate(burial_chain):
named[node] = {3: 'G1', 4: 'Q1'}.get(i, f'B{i + 1}')
for i, node in enumerate(betrayal_chain):
named[node] = {1: 'G2', 2: 'Q2'}.get(i, f'T{i + 1}')
for node, tag in named.items():
x, y = pos_nx[node]
ax.annotate(tag, (x, y), xytext=(0, 34), textcoords='offset points',
ha='center', fontsize=12, fontweight='bold', color='#111111')
ax.set_title("Same graph, laid out automatically by networkx (kamada-kawai) instead of by hand",
fontsize=10)
ax.axis('off')
plt.tight_layout()
plt.show()
Here we display the 6 manipulable states (gates $G_1,G_2$, and their four manipulable ancestors) along with $Q_1$ and $Q_2$, laid out automatically by networkx using the kamada-kawai layout. We also include the "boundary nodes" which have an edge to any of these 8 pertinent nodes. The only nodes that have an edge to the start of the chains elect $A$, meaning there is no reason to manipulate the outcome.
That is to say, to reach $G_1$, which can move the outcome from $B$ to $A$, you either need to start in the burial chain where $B$ is winning, or in a state where $A$ is already winning. This showcases the one-notch bound: no state with $C$ winning can reach a state where $A$ wins.
Why are only some Condorcet winner states vulnerable?¶
In [ ]:
def condorcet_loser(P):
# the candidate who loses BOTH of their matchups
losses = {}
for _, l in P:
losses[l] = losses.get(l, 0) + 1
return next((c for c in CANDS if losses.get(c) == 2), None)
def burial_coalition(s):
# for a CW=W state: L is the Condorcet loser, F is the third candidate
# (F beats L, loses to W) -- F>W>L is the only coalition that could ever
# threaten s, since the mirror L>W>F would require L to beat F
W, L = condorcet_winner(s), condorcet_loser(s)
F = next(c for c in CANDS if c not in (W, L))
return F, W, L
def vulnerable_to_burial(s):
# Theorem (Burial vulnerability): s is vulnerable to the F>W>L coalition
# iff margin(F->L) is wider than margin(W->F) -- at G1 the only
# concordant pair is F-vs-L and the only discordant pair in a CW state is
# W-vs-F, so the reachability theorem collapses to this single comparison
F, W, L = burial_coalition(s)
FL, WF = frozenset((F, L)), frozenset((W, F))
return slot_of(s, FL) > slot_of(s, WF)
def actually_vulnerable(s):
F, W, L = burial_coalition(s)
order = (F, W, L)
return any(prefers(order, winner(q), winner(s)) for q in R(s, order))
cw_states = [s for s in STATES if condorcet_winner(s) is not None]
check('closed-form rule (Burial vulnerability) matches brute-forced vulnerability for every CW state',
all(vulnerable_to_burial(s) == actually_vulnerable(s) for s in cw_states))
check('exactly half (18/36) of Condorcet-winner states are vulnerable', sum(map(vulnerable_to_burial, cw_states)) == 18)
pd.DataFrame({
'state': [fmt_state(s) for s in cw_states],
'W': [condorcet_winner(s) for s in cw_states],
'F (beats L, loses to W)': [burial_coalition(s)[0] for s in cw_states],
'L (Condorcet loser)': [burial_coalition(s)[2] for s in cw_states],
'rank(F→L) > rank(W→F)': ['yes' if vulnerable_to_burial(s) else 'no' for s in cw_states],
'vulnerable to F>W>L burial?': ['yes' if actually_vulnerable(s) else 'no' for s in cw_states],
'metrics match?': ['yes' if vulnerable_to_burial(s) == actually_vulnerable(s) else 'no' for s in cw_states],
}).sort_values(['vulnerable to F>W>L burial?', 'W'], ascending=[False, True]).reset_index(drop=True)
No favorite betrayal under a Condorcet winner¶
In [ ]:
# Theorem (No Favorite Betrayal Under a Condorcet Winner): starting from
# ANY state with a Condorcet winner, a coalition can never do strictly
# better -- via a simple OR complex manipulation -- by voting against their
# own favorite (A>B or A>C) than by staying sincere on both of A's own
# matchups and exploiting whatever else is achievable.
#
# By the one-way-push lemma, the ONLY way an A-matchup's winner can ever
# flip is a (0,1) move applied while A currently holds the tightest matchup
# (flipping A away is achievable; flipping toward A never is, since that
# would push toward the coalition's own favorite). So "never betray A" means
# never taking a (0,1) step out of a state where A is the tightest winner --
# build a second graph, LOCAL but without exactly those edges, and check
# that disallowing them never improves the best reachable outcome.
def is_betrayal_step(s, sigma_name, order):
return sigma_name == '(0,1)' and s[0][0] == order[0]
LOCAL_LOYAL = nx.DiGraph()
for s in STATES:
for name, q in achievable_moves(s, order_ABC):
if not is_betrayal_step(s, name, order_ABC):
LOCAL_LOYAL.add_edge(s, q, sigma=name)
def best_reachable(graph, s, order):
reach = {s} | (nx.descendants(graph, s) if s in graph else set())
return max(reach, key=lambda q: -order.index(winner(q)))
v = [s for s in STATES if condorcet_winner(s) is not None
and prefers(order_ABC, winner(best_reachable(LOCAL, s, order_ABC)),
winner(best_reachable(LOCAL_LOYAL, s, order_ABC)))]
check('no favorite betrayal: betraying A never reaches a strictly better outcome than staying loyal, from any CW state',
len(v) == 0)
pd.DataFrame(results[-1:], columns=['claim', 'result'])
Full results¶
In [13]:
# every check in this notebook, in one place
assert all(r == 'PASS' for _, r in results)
pd.DataFrame(results, columns=['claim', 'result'])
Out[13]:
| claim | result | |
|---|---|---|
| 0 | Condorcet Stability: CW states have no profitable simple manipulation | PASS |
| 1 | A swap of the second kind is never profitable | PASS |
| 2 | A (2,3) swap is never profitable | PASS |
| 3 | Voting your least favorite over your favorite is never profitable | PASS |
| 4 | The other intransitive ballot pattern (bury both A>B and B>C at once) is never profitable | PASS |
| 5 | Brute-forced gates for A>B>C match the post's G1, G2 exactly | PASS |
| 6 | 12 total (state, coalition) profitable-simple-manipulation pairs | PASS |
| 7 | every one of them starts from a cyclic state | PASS |
| 8 | each cyclic state has a UNIQUE exploiting coalition | PASS |
| 9 | ...covering all 12 cyclic states | PASS |
| 10 | every state trivially reaches itself | PASS |
| 11 | exactly 6 of 48 states admit a profitable complex manipulation | PASS |
| 12 | 36 (state, coalition) pairs across 30 distinct states | PASS |
| 13 | ...covering all 12 cyclic states | PASS |
| 14 | ...and exactly half (18/36) of the Condorcet-winner states | PASS |
| 15 | one-notch bound: no C -> A complex manipulation | PASS |
| 16 | every CW that can be complexly overturned is the coalition's 2nd choice | PASS |
| 17 | every discovered chain lands on a strictly-preferred winner | PASS |
| 18 | burial chain has length 5 (post: 3 ancestors + G1 + Q1) | PASS |
| 19 | betrayal chain has length 3 (post: 1 ancestor + G2 + Q2) | PASS |
| 20 | G1 is not reachable from G2 in the local achievable-move graph | PASS |
| 21 | G1 is not reachable from Q2 in the local achievable-move graph | PASS |
| 22 | every boundary node already gives the coalition at least as good an outcome as the chain node it feeds | PASS |
| 23 | single-lie sufficiency: C>B alone suffices at every burial-chain edge | PASS |
| 24 | single-lie sufficiency: B>A alone suffices at every betrayal-chain edge | PASS |
| 25 | closed-form rule (Burial vulnerability) matches brute-forced vulnerability for every CW state | PASS |
| 26 | exactly half (18/36) of Condorcet-winner states are vulnerable | PASS |
| 27 | no favorite betrayal: betraying A never reaches a strictly better outcome than staying loyal, from any CW state | PASS |