import streamlit as st import pandas as pd import matplotlib.pyplot as plt import seaborn as sns import math from copy import deepcopy from itertools import permutations, product from collections import defaultdict # Initialize session state if "voters" not in st.session_state: st.session_state.voters = [] if "scoring_history" not in st.session_state: st.session_state.scoring_history = [] # List of tuples: (label, vector, manipulability %) st.title("🎯 Strategy-Proof Ranked Voting System") # 1. Alternatives and scoring vector num_alts = st.number_input("Number of alternatives:", min_value=2, value=3) alternatives = [f"M{i+1}" for i in range(num_alts)] scoring_input = st.text_input("Enter scoring vector (comma-separated):", value="2,1,0") try: scoring_vector = list(map(int, scoring_input.strip().split(','))) assert len(scoring_vector) == num_alts except: st.error("Scoring vector must contain exactly one value per alternative.") st.stop() # 2. Add voter st.subheader("🗳️ Add Voter") with st.form("add_voter_form"): voter_name = st.text_input("Voter Name:", f"Voter{len(st.session_state.voters)+1}") ranking = st.multiselect("Rank alternatives (top to bottom):", alternatives, default=alternatives) submit = st.form_submit_button("Add Voter") if submit: if len(ranking) != num_alts: st.warning("Rank all alternatives uniquely.") else: preferences = {ranking[i]: scoring_vector[i] for i in range(num_alts)} st.session_state.voters.append({ "name": voter_name, "ranking": ranking, "preferences": preferences }) st.success(f"{voter_name} added.") # 3. Show all voter preferences st.subheader("👥 Voter Preferences") if st.session_state.voters: df_votes = pd.DataFrame([{**{"Voter": v["name"]}, **v["preferences"]} for v in st.session_state.voters]) st.dataframe(df_votes) # --- Function to detect manipulation --- import math def detect_manipulation(voters, alternatives, scoring_vector): total_profiles = math.factorial(len(alternatives)) ** len(voters) manipulable_cases = 0 manipulable_info = [] def get_rank(score_dict): sorted_alts = sorted(score_dict.items(), key=lambda x: -x[1]) return {alt: rank + 1 for rank, (alt, _) in enumerate(sorted_alts)} # Original overall ranking original_scores = {alt: 0 for alt in alternatives} for v in voters: for i, alt in enumerate(v["ranking"]): original_scores[alt] += scoring_vector[i] original_ranks = get_rank(original_scores) original_winner = max(original_scores, key=original_scores.get) for voter in voters: original_ranking = voter["ranking"] # Skip if voter's top choice is already the winner if original_ranking[0] == original_winner: continue for alt in alternatives: if alt == original_ranking[0]: continue # skip if same as current top new_ranking = original_ranking.copy() if alt in new_ranking: new_ranking.remove(alt) new_ranking.insert(0, alt) simulated_scores = {a: 0 for a in alternatives} for v in voters: rank_list = new_ranking if v == voter else v["ranking"] for i, a in enumerate(rank_list): simulated_scores[a] += scoring_vector[i] simulated_ranks = get_rank(simulated_scores) new_winner = max(simulated_scores, key=simulated_scores.get) # Manipulation is beneficial ONLY IF new winner is ranked *higher* than original winner if original_ranking.index(new_winner) < original_ranking.index(original_winner): rank_improvements = [] for a in alternatives: old_rank = original_ranks[a] new_rank = simulated_ranks[a] if new_rank < old_rank: rank_improvements.append(f"{a}: {old_rank} → {new_rank}") manipulable_cases += 1 manipulable_info.append({ "voter": voter["name"], "original_ranking": original_ranking, "manipulated_ranking": new_ranking, "original_winner": original_winner, "new_winner": new_winner, "rank_improvements": rank_improvements, "simulated_ranks": simulated_ranks # ✅ Add this for your DataFrame logic }) break return manipulable_cases, len(voters), manipulable_info def get_winners(scores): max_score = max(scores.values()) return [alt for alt, score in scores.items() if score == max_score] # --- Function to count manipulable profile --- from itertools import permutations, product from collections import defaultdict def count_manipulable_profiles(m, n, scoring_vector): alternatives = [f"M{i+1}" for i in range(m)] all_rankings = list(permutations(alternatives)) total_profiles = len(all_rankings) ** n manipulable_count = 0 def get_rank(scores): # Returns a ranking dictionary based on scores (highest score first) sorted_items = sorted(scores.items(), key=lambda x: -x[1]) return {alt: i + 1 for i, (alt, _) in enumerate(sorted_items)} # Iterate over all possible profiles for profile in product(all_rankings, repeat=n): # Calculate the original scores for this profile original_scores = defaultdict(int) for ranking in profile: for i, alt in enumerate(ranking): original_scores[alt] += scoring_vector[i] # Identify the original winner (the alternative with the highest score) original_winner = max(original_scores, key=original_scores.get) # Calculate the original rank order original_ranks = get_rank(original_scores) # Check if the profile can be manipulated by at least one voter profile_manipulated = False for voter_idx, ranking in enumerate(profile): # If the original winner is already the first choice for this voter, no manipulation is possible if ranking[0] == original_winner: continue # Find the alternatives this voter prefers over the original winner preferred_alts = [] for alt in ranking: if alt == original_winner: break preferred_alts.append(alt) # Try manipulating the vote by promoting each preferred alternative for alt in preferred_alts: # Create a manipulated vote where 'alt' is ranked first manipulated = list(ranking) manipulated.remove(alt) manipulated.insert(0, alt) # Recalculate the scores with the manipulated vote new_scores = original_scores.copy() # Subtract the original vote's scores for pos, a in enumerate(ranking): new_scores[a] -= scoring_vector[pos] # Add the manipulated vote's scores for pos, a in enumerate(manipulated): new_scores[a] += scoring_vector[pos] # Determine the new winner after manipulation new_winner = max(new_scores, key=new_scores.get) # Check if the new winner is one of the preferred alternatives and is better than the original winner if new_winner in preferred_alts and new_scores[new_winner] > new_scores[original_winner]: manipulable_count += 1 profile_manipulated = True break if profile_manipulated: break # Count the profile if at least one voter can manipulate it if profile_manipulated: manipulable_count += 1 # Return manipulable count, total profiles, and manipulability percentage manipulability = (manipulable_count / total_profiles) * 100 return manipulable_count, total_profiles, manipulability # 4. Compute results if st.button("📊 Compute Result") and st.session_state.voters: scores = {alt: 0 for alt in alternatives} for v in st.session_state.voters: for alt, pts in v["preferences"].items(): scores[alt] += pts st.subheader("📈 Result Table") score_df = pd.DataFrame(scores.items(), columns=["Alternative", "Score"]).sort_values("Score", ascending=False) st.dataframe(score_df) # Bar chart st.subheader("📊 Score Distribution") fig, ax = plt.subplots() sns.barplot(data=score_df, x="Alternative", y="Score", palette="Blues_d", ax=ax) ax.set_title("Total Points per Alternative") st.pyplot(fig) # Heatmap of votes st.subheader("🔥 Voter Preferences Heatmap") heatmap_df = pd.DataFrame( [{alt: v["preferences"][alt] for alt in alternatives} for v in st.session_state.voters], index=[v["name"] for v in st.session_state.voters] ) fig2, ax2 = plt.subplots(figsize=(8, 4)) sns.heatmap(heatmap_df, annot=True, cmap="YlGnBu", ax=ax2) st.pyplot(fig2) # Tie-breaking logic top_score = score_df["Score"].max() top_alts = score_df[score_df["Score"] == top_score]["Alternative"].tolist() if len(top_alts) > 1: st.warning(f"Tie detected between: {', '.join(top_alts)}") # Top-rank frequency first_rank = {alt: 0 for alt in top_alts} for v in st.session_state.voters: top = v["ranking"][0] if top in first_rank: first_rank[top] += 1 max_first = max(first_rank.values()) tied_top = [a for a in top_alts if first_rank[a] == max_first] if len(tied_top) == 1: st.success(f"🏅 Winner by top-rank frequency: {tied_top[0]}") else: final = sorted(tied_top)[0] st.success(f"🏅 Still tied after top-rank votes. Tie-breaker by alphabetical order: {final}") else: st.success(f"🏅 Winner: {top_alts[0]}") # 5. Manipulation Detection st.subheader("🕵️ Manipulation Detection") m_cases, t_cases, m_profiles = detect_manipulation( st.session_state.voters, alternatives, scoring_vector ) st.markdown(f"📊 **Voters who can potentially improve their outcome:** `{m_cases} / {t_cases}`") if m_profiles: for item in m_profiles: # Corrected rank improvements with accurate old and new positions rank_changes = [] original_ranking = item['original_ranking'] manipulated_ranking = item['manipulated_ranking'] for imp in item['rank_improvements']: alt_name, _ = imp.split(':') # Only keep the alternative name, ignore the rank change part alt_name = alt_name.strip() # Get original and new rank positions (1-based) old = original_ranking.index(alt_name) + 1 new = manipulated_ranking.index(alt_name) + 1 benefit = old - new if benefit > 0: rank_changes.append(f"✅ {alt_name}: Rank {old} → {new} (↑ {benefit})") elif benefit < 0: rank_changes.append(f"⚠️ {alt_name}: Rank {old} → {new} (↓ {abs(benefit)})") else: rank_changes.append(f"➖ {alt_name}: Rank {old} → {new} (no change)") # Simulated overall rank table sim_ranks_df = pd.DataFrame.from_dict(item["simulated_ranks"], orient="index", columns=["Rank"]) sim_ranks_df.index.name = "Alternative" sim_ranks_df = sim_ranks_df.sort_values("Rank") # Display voter manipulation info st.markdown(f"""
🔍 {item['voter']} can manipulate:
""", unsafe_allow_html=True) st.markdown("**📌 Simulated Ranks after Manipulation:**") st.dataframe(sim_ranks_df) else: st.success("✅ No manipulable profiles detected.") # 6. Global Manipulability (All Possible Profiles) st.subheader("📚 Global Profile Manipulability") m = len(alternatives) n = len(st.session_state.voters) with st.spinner("Computing over all possible profiles..."): manipulable, total,manipulability_perc = count_manipulable_profiles(m, n, scoring_vector) st.success(f"Out of {total} total profiles, at least one voter can manipulate in {manipulable} profiles.") st.metric("Manipulable Profiles", f"{manipulable} / {total}", delta=f"{round((manipulable/total)*100, 2)}%") current_label = f"Custom {scoring_vector}" # After detect_manipulation() #m_cases, t_cases, m_profiles = detect_manipulation(st.session_state.voters, alternatives, scoring_vector) # Accurate manipulability % for the current scoring vector global_m, global_t, manipulability = count_manipulable_profiles(len(alternatives), len(st.session_state.voters), scoring_vector) #manipulability = (global_m / global_t) * 100 # Avoid duplicates if not any(vector == scoring_vector for _, vector, _, _, _ in st.session_state.scoring_history): st.session_state.scoring_history.append((f"Custom {scoring_vector}", scoring_vector.copy(), manipulability, len(alternatives), len(st.session_state.voters))) # 6. Accumulated Scoring Vector Comparison if st.session_state.scoring_history: df_hist = pd.DataFrame( [(label, m, n, percent) for label, _, percent, m, n in st.session_state.scoring_history], columns=["Scoring Vector", "Alternatives", "Voters", "Manipulable %"] ) st.subheader("📊 Manipulability of All Used Scoring Vectors") fig_hist, ax_hist = plt.subplots(figsize=(10, 6)) sns.barplot(data=df_hist, x="Manipulable %", y="Scoring Vector", palette="Spectral", ax=ax_hist) ax_hist.set_xlim(0, 100) ax_hist.set_xlabel("Percentage of Manipulable Profiles") ax_hist.set_title("Manipulability by Scoring Vector") # Annotate each bar with m, n and manipulability % for i, row in df_hist.iterrows(): label = f"m={row['Alternatives']}, n={row['Voters']} | {row['Manipulable %']:.2f}%" ax_hist.text(row['Manipulable %'] + 1, i, label, va='center', fontsize=9, color='black') st.pyplot(fig_hist) # Reset if st.button("🔄 Reset Voters"): st.session_state.voters = [] st.session_state.scoring_history = [] st.rerun()