Source code for pref_voting.stochastic_methods
'''
File: stochastic_methods.py
Author: Wes Holliday (wesholliday@berkeley.edu) and Eric Pacuit (epacuit@umd.edu)
Date: November 22, 2024
Implementations of voting methods that output winners stochastically (unlike probabilistic methods, which output a probability distribution in the form of a dictionary).
'''
from pref_voting.voting_method import *
from pref_voting.iterative_methods import consensus_builder
from pref_voting.probabilistic_methods import maximal_lottery, RaDiUS
import math
[docs]
@vm(name="Random Consensus Builder (Stochastic)")
def random_consensus_builder_st(profile, curr_cands=None, beta=0.5):
"""Version of the Random Consensus Builder (RCB) voting method due to Charikar et al. (https://arxiv.org/abs/2306.17838) that actually chooses a winner stochastically rather than outputting a probability distribution.
Args:
profile (Profile): An anonymous profile of linear orders
curr_cands (List[int], optional): Candidates to consider. Defaults to all candidates if not provided.
beta (float): Threshold for elimination (default 0.5). When processing candidate i, eliminates a candidate j
above i in the consensus building ranking if the proportion of voters preferring i to j is >= beta
Returns:
A sorted list of candidates.
.. seealso::
:meth:`pref_voting.iterative_methods.consensus_builder`
:meth:`pref_voting.probabilistic_methods.random_consensus_builder`
"""
consensus_building_ranking = random.choice(profile.rankings)
return consensus_builder(profile, curr_cands=curr_cands, consensus_building_ranking=consensus_building_ranking, beta=beta)
[docs]
@vm(name="Maximal Lotteries mixed with Random Consensus Builder")
def MLRCB(profile, curr_cands=None, p = 1 / math.sqrt(2), B = math.sqrt(2) - 1/2):
"""With probability p, choose the winner from the Maximal Lotteries distribution. With probability 1-p, run the stochastic version of Random Consensus Builder with beta chosen uniformly from (1/2, B). Ths method comes from Theorem 4 of Charikar et al. (https://arxiv.org/abs/2306.17838).
Args:
profile (Profile): An anonymous profile of linear orders
curr_cands (List[int], optional): Candidates to consider. Defaults to all candidates if not provided.
p (float): Probability of choosing the winner from the Maximal Lotteries distribution
B (float): Upper bound for elimination threshold in the Random Consensus Builder method
Returns:
A sorted list of candidates.
"""
if random.random() < p:
return [maximal_lottery.choose(profile, curr_cands=curr_cands)]
else:
beta = random.uniform(0.5, B)
return random_consensus_builder_st(profile, curr_cands=curr_cands, beta=beta)
[docs]
@vm(name="Maximal Lotteries mixed with RaDiUS")
def MLRaDiUS(profile, curr_cands=None):
"""For p, B, and the probability distribution over beta given in the proof of Theorem 5 of Charikar et al. (https://arxiv.org/abs/2306.17838), choose the winner from the Maximal Lotteries distribution with probability p; with probability 1-p, run the RaDiUS method with beta chosen according to the distribution over beta.
Args:
profile (Profile): An anonymous profile of linear orders
curr_cands (List[int], optional): Candidates to consider. Defaults to all candidates if not provided.
Returns:
A sorted list of candidates.
"""
# Parameters
B = 0.876353 # given in the proof of Theorem 5 of Charikar et al. (https://arxiv.org/abs/2306.17838)
# Calculate p as per proof
ln3 = np.log(3)
LB = np.log((1 + B) / (1 - B))
I = 0.5 * (LB - ln3) # Integral value
p = 1 / (1 + I)
def sample_beta(B):
# Generate a single uniform random number
u = np.random.uniform(0, 1)
# Compute E(u)
Eu = np.exp(u * (LB - ln3) + ln3)
# Compute beta sample
beta_sample = (Eu - 1) / (Eu + 1)
return beta_sample
if random.random() < p:
return [maximal_lottery.choose(profile, curr_cands=curr_cands)]
else:
beta = sample_beta(B)
return [RaDiUS.choose(profile, curr_cands=curr_cands, beta=beta)]