Stochastic Methods

Random Consensus Builder (Stochastic)

pref_voting.stochastic_methods.random_consensus_builder_st(profile, curr_cands=None, beta=0.5)[source]

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.

Parameters:

  • 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.

See also

pref_voting.iterative_methods.consensus_builder() pref_voting.probabilistic_methods.random_consensus_builder()

Maximal Lotteries mixed with Random Consensus Builder

pref_voting.stochastic_methods.MLRCB(profile, curr_cands=None, p=0.7071067811865475, B=0.9142135623730951)[source]

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).

Parameters:

  • 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.

Maximal Lotteries mixed with RaDiUS

pref_voting.stochastic_methods.MLRaDiUS(profile, curr_cands=None)[source]

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.

Parameters:

  • 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.