CultureMallows#

class actinvoting.CultureMallows(m, phi, seed=None)[source]#

Mallows Culture.

The pole (a.k.a. reference ranking) is ranking = [0, 1, 2, 3, …], i.e. borda = [m-1, m-2, …].

Parameters:

m (int) – Number of candidates.
phi (sympy.Rational) – Concentration parameter. It must be in [0, 1]. In our paper, it is equal to exp(-rho). E.g., for phi = 1/2, i.e., for rho = log(2), the probability of a ranking at distance 1 from the pole is halved.
seed (int) – Random seed.

Examples

Usual case:

>>> culture = CultureMallows(m=3, phi=sympy.Rational(1, 2), seed=42)
>>> profile = culture.random_profile(n=10000)
>>> print(profile)
Profile((0, 1, 2): 3766,
        (0, 2, 1): 1930,
        (1, 0, 2): 1958,
        (1, 2, 0): 944,
        (2, 0, 1): 946,
        (2, 1, 0): 456)

Note that (0, 1, 2) is the most frequent, (0, 2, 1) and (1, 0, 2) (each at distance 1) are half as frequent because phi = .5, (1, 2, 0) and (2, 0, 1) (each at distance 2) are 1/4 as frequent, and (2, 1, 0) (at distance 3) is 1/8 as frequent.

Particular case of a Dirac:

>>> culture = CultureMallows(m=6, phi=sympy.Integer(0))
>>> list(culture.powers_of_phi)
[1, 0, 0, 0, 0, 0]
>>> list(culture.powers_of_phi_cumsum)
[1, 1, 1, 1, 1, 1]
>>> for candidate, insertion_probas in culture.d_candidate_insertion_probas.items():
...     print(candidate, list(insertion_probas))
0 [1]
1 [1, 0]
2 [1, 0, 0]
3 [1, 0, 0, 0]
4 [1, 0, 0, 0, 0]
5 [1, 0, 0, 0, 0, 0]
>>> culture.normalization_constant
1
>>> culture.proba_ranking([0, 1, 2, 3, 4, 5])
1
>>> culture.proba_ranking([2, 5, 0, 1, 3, 4])
0
>>> culture.proba_borda([5, 4, 3, 2, 1, 0])
1
>>> culture.proba_borda([3, 2, 5, 1, 0, 4])
0
>>> culture.random_ranking()
array([0, 1, 2, 3, 4, 5])
>>> culture.random_borda()
array([5, 4, 3, 2, 1, 0])

Particular case of the Impartial Culture:

>>> culture = CultureMallows(m=6, phi=sympy.Integer(1), seed=42)
>>> list(culture.powers_of_phi)
[1, 1, 1, 1, 1, 1]
>>> list(culture.powers_of_phi_cumsum)
[1, 2, 3, 4, 5, 6]
>>> for candidate, insertion_probas in culture.d_candidate_insertion_probas.items():
...     print(candidate, list(insertion_probas))
0 [1]
1 [1/2, 1/2]
2 [1/3, 1/3, 1/3]
3 [1/4, 1/4, 1/4, 1/4]
4 [1/5, 1/5, 1/5, 1/5, 1/5]
5 [1/6, 1/6, 1/6, 1/6, 1/6, 1/6]
>>> culture.normalization_constant
720
>>> culture.proba_ranking([0, 1, 2, 3, 4, 5])
1/720
>>> culture.proba_ranking([2, 5, 0, 1, 3, 4])
1/720
>>> culture.proba_borda([5, 4, 3, 2, 1, 0])
1/720
>>> culture.proba_borda([3, 2, 5, 1, 0, 4])
1/720
>>> culture.random_ranking()
array([5, 2, 3, 0, 1, 4])
>>> culture.random_borda()
array([3, 4, 0, 2, 1, 5])

References

Doignon, J. P., Pekeč, A., & Regenwetter, M. (2004). The repeated insertion model for rankings: Missing link between two subset choice models. Psychometrika, 69(1), 33-54.

Lu, T., & Boutilier, C. (2014). Effective sampling and learning for Mallows models with pairwise-preference data. J. Mach. Learn. Res., 15(1), 3783-3829.

property average_profile#

Average profile.

Returns:: A profile where the weight for each ranking is the corresponding probability in the culture.
Return type:: Profile

property d_candidate_insertion_probas#

Dictionary of candidate -> insertion probabilities.

Returns:: Dictionary of candidate -> insertion probabilities.
Return type:: dict

property d_candidate_insertion_probas_as_floats#

Dictionary of candidate -> insertion probabilities as floats.

Returns:: Dictionary of candidate -> insertion probabilities as floats.
Return type:: dict

property normalization_constant#

Normalization constant of the Mallows distribution.

Returns:: Normalization constant of the Mallows distribution, equal the product of powers_of_phi_cumsum, i.e., (1) * (1+phi) * (1+phi+phi^2) * … * (1+phi+phi^2+…+phi^(m-1)).
Return type:: sympy.Rational

property powers_of_phi#

Powers of phi.

Returns:: [1, phi, phi^2, phi^3, …, phi^(m-1)].
Return type:: ndarray

property powers_of_phi_cumsum#

Cumulative sum of the powers of phi.

Returns:: [1, 1+phi, 1+phi+phi^2, …, 1+phi+phi^2+…+phi^(m-1)].
Return type:: ndarray

proba_borda(borda)[source]#

Probability of a ranking, given in Borda format.

Parameters:: borda (List) – A ranking in Borda format. E.g. [3, 1, 2, 0] corresponds to the preference ranking 0 > 2 > 1 > 3.
Returns:: The probability to draw this ranking.
Return type:: float or sympy expr

proba_ranking(ranking)[source]#

Probability of a ranking.

Parameters:: ranking (List) – A ranking. E.g. [0, 2, 1, 3] corresponds to the preference ranking 0 > 2 > 1 > 3.
Returns:: The probability to draw this ranking.
Return type:: float or sympy expr

random_borda()[source]#

Random ranking in Borda format.

Returns:: A random ranking in Borda format. E.g. [3, 1, 2, 0] corresponds to the preference ranking 0 > 2 > 1 > 3.
Return type:: ndarray

random_profile(n)[source]#

Random profile.

Parameters:: n (int) – Number of voters.
Returns:: A random profile.
Return type:: Profile

random_ranking()[source]#

Random ranking.

Returns:: A random ranking. E.g. [0, 2, 1, 3] corresponds to the preference ranking 0 > 2 > 1 > 3.
Return type:: ndarray