Probabilistic Methods

Random Dictator

pref_voting.probabilistic_methods.random_dictator(profile, curr_cands=None)[source]

Returns lottery over the candidates that is proportional to the Plurality scores.

Parameters:

  • profile (Profile) – A Profile object.

  • curr_cands (list) – A list of candidates to restrict the ranking to. If None, then the ranking is over the entire domain of the profile.

Returns:

A dictionary mapping candidates to probabilities.

Return type:

dict

Random Dictator on the Beta-Uncovered Set

pref_voting.probabilistic_methods.RaDiUS(profile, curr_cands=None, beta=0.5)[source]

Runs the Random Dictator method on the profile restricted to the beta-uncovered set, as proposed by 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.

Returns:

Maps each candidate to their probability of winning under the RaDiUS method.

Return type:

dict

Proportional Borda

pref_voting.probabilistic_methods.pr_borda(profile, curr_cands=None)[source]

Returns lottery over the candidates that is proportional to the Borda scores.

Parameters:

  • profile (Profile) – A Profile object.

  • curr_cands (list) – A list of candidates to restrict the ranking to. If None, then the ranking is over the entire domain of the profile.

Returns:

A dictionary mapping candidates to probabilities.

Return type:

dict

Maximal Lottery

pref_voting.probabilistic_methods.maximal_lottery(edata, curr_cands=None, algorithm='lp')[source]

Returns the maximal lottery over the candidates. See http://dss.in.tum.de/files/brandt-research/fishburn_slides.pdf.

Parameters:

  • edata (Profile, MarginGraph) – A Profile object.

  • curr_cands (list) – A list of candidates to restrict the ranking to. If None, then the ranking is over the entire domain of the profile.

  • algorithm (str) – The algorithm to use. Either ‘enumeration’ or ‘lp’. Defaults to ‘enumeration’.

Returns:

A dictionary mapping candidates to probabilities.

Return type:

dict

Note

The ‘enumeration’ algorithm averages over the extremal maximal lotteries. The ‘lp’ is faster, but only returns a single maximal lottery (not necessarily the average)

C1 Maximal Lottery

pref_voting.probabilistic_methods.c1_maximal_lottery(edata, curr_cands=None, algorithm='enumeration')[source]

Returns the C1 maximal lottery over the candidates. See http://dss.in.tum.de/files/brandt-research/fishburn_slides.pdf.

Parameters:

  • edata (Profile, MarginGraph) – A Profile object.

  • curr_cands (list) – A list of candidates to restrict the ranking to. If None, then the ranking is over the entire domain of the profile.

  • algorithm (str) – The algorithm to use. Either ‘enumeration’ or ‘lp’. Defaults to ‘enumeration’.

Returns:

A dictionary mapping candidates to probabilities.

Return type:

dict

Note

The ‘enumeration’ algorithm averages over the extremal maximal lotteries. The ‘lp’ is faster, but only returns a single maximal lottery (not necessarily the average)

Random Consensus Builder

pref_voting.probabilistic_methods.random_consensus_builder(profile, curr_cands=None, beta=0.5)[source]

Random Consensus Builder (RCB) voting method due to Charikar et al. (https://arxiv.org/abs/2306.17838).

For each ranking type in the profile, runs the deterministic Consensus Builder voting method using that ranking as the consensus building ranking. The probability of a candidate winning is proportional to the number of voters with rankings that would make that candidate win when used as the consensus building ranking.

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:

Maps each candidate to their probability of winning under the RCB method

Return type:

dict

See also

pref_voting.iterative_methods.consensus_builder() pref_voting.stochastic_methods.random_consensus_builder_st()