ProfileNoisyDiscrete

Welcome to this series of tutorials! The objective here is to get you up and running with the package Poisson Approval, but not to present all its features in detail. For more exhaustive information, refer to the Reference section of the documentation.

from fractions import Fraction
import poisson_approval as pa

A Profile and its Basic Properties

To get familiar with profiles, we will consider the example of the class ProfileNoisyDiscrete. Let’s create a profile:

profile = pa.ProfileNoisyDiscrete({
    ('abc', 0.5, 0.01): Fraction(1, 10),
    ('bac', 0.25, 0.01): Fraction(3, 10),
    ('bac', 0.75, 0.01): Fraction(3, 10),
    ('cab', 0.4, 0.01): Fraction(3, 10)
})
profile

<abc 0.5 ± 0.01: 1/10, bac 0.25 ± 0.01: 3/10, bac 0.75 ± 0.01: 3/10, cab 0.4 ± 0.01: 3/10> (Condorcet winner: b)

In the example above, let us examine the first group of voters. They have the preference ranking \(abc\). By convention, their utility for their top candidate \(a\) is 1 and their utility for their bottom candidate \(c\) is 0. In our example, their utility for their middle candidate \(b\) is 0.5 with a noise of 0.01, which means that it is uniformly distributed in the interval [0.49, 0.51]. This group represents a share 1/10 of the voters.

Similarly, there is a second group of voters \(bac\), with a utility for \(a\) that is \(0.25 \pm 0.01\), representing 3/10 of the voters; etc.

You can define the same profile with an alternate syntax, specifying the noise parameter once and for all:

profile = pa.ProfileNoisyDiscrete({
    ('abc', 0.5): Fraction(1, 10),
    ('bac', 0.25): Fraction(3, 10),
    ('bac', 0.75): Fraction(3, 10),
    ('cab', 0.4): Fraction(3, 10)
}, noise=0.01)
profile

<abc 0.5 ± 0.01: 1/10, bac 0.25 ± 0.01: 3/10, bac 0.75 ± 0.01: 3/10, cab 0.4 ± 0.01: 3/10> (Condorcet winner: b)

Share of voters \(abc\) (i.e. who prefer candidate \(a\), then \(b\), then \(c\)):

profile.abc

Fraction(1, 10)

Which rankings are in the profile?

profile.support_in_rankings

{abc, bac, cab}

Are all possible rankings in the profile?

profile.is_generic_in_rankings

False

Is one ranking shared by a majority of voters?

profile.has_majority_ranking

True

Is one candidate prefered by a majority of voters?

profile.has_majority_favorite

True

Is the profile single-peaked?

profile.is_single_peaked

True

Weighted majority graph:

profile.weighted_maj_graph

array([[0, Fraction(-1, 5), Fraction(2, 5)],
       [Fraction(1, 5), 0, Fraction(2, 5)],
       [Fraction(-2, 5), Fraction(-2, 5), 0]], dtype=object)

Condorcet winner(s):

profile.condorcet_winners

{'b'}

Does the profile have a Condorcet winner?

profile.is_profile_condorcet

1.0

For is_profile_condorcet, the output 1.0 conventionally means that there is a strict Condorcet winner; 0.5 that there are one or several weak Condorcet winners, and 0.0 means that there is no Condorcet winner at all.

Ordinal Strategy

Define an ordinal strategy:

strategy = pa.StrategyOrdinal({'abc': 'a', 'bac': 'ab', 'cab': 'c'})
strategy

<abc: a, bac: ab, cab: c>

Ballot of the voters with ranking \(abc\):

strategy.abc

'a'

Tau-vector (ballot shares) associated to the strategy in the given profile:

profile.tau(strategy)

<a: 1/10, ab: 3/5, c: 3/10> ==> a

Is the strategy an equilibrium for the given profile?

profile.is_equilibrium(strategy)

EquilibriumStatus.EQUILIBRIUM

Alternatively, as soon as you define a strategy, you can attach a profile to it. In that case, the strategy is considered from the point of view of its usage in the given profile. Thus you can write:

strategy = pa.StrategyOrdinal({'abc': 'a', 'bac': 'ab', 'cab': 'c'}, profile=profile)
strategy

<abc: a, bac: ab, cab: c> ==> a

strategy.tau

<a: 1/10, ab: 3/5, c: 3/10> ==> a

strategy.is_equilibrium

EquilibriumStatus.EQUILIBRIUM

Threshold Strategy

Not all strategies are ordinal. In the following strategy, voters \(bac\) vote for their preferred candidate \(b\) if their utility for \(a\) is lower than 0.5 but vote for their two first candidates, \(b\) and \(a\), if their utility for \(a\) is greater than 0.5:

strategy = pa.StrategyThreshold({'abc': 1, 'bac': 0.5, 'cab': 1}, profile=profile)
strategy

<abc: a, bac: utility-dependent (0.5), cab: c> ==> b

strategy.tau

<a: 1/10, ab: 3/10, b: 3/10, c: 3/10> ==> b

strategy.is_equilibrium

EquilibriumStatus.NOT_EQUILIBRIUM

Analyze Several Strategies

Analyze all ordinal strategies:

profile.analyzed_strategies_ordinal

Equilibria:
<abc: a, bac: b, cab: ac> ==> b (FF)
<abc: a, bac: ab, cab: c> ==> a (D)

Non-equilibria:
<abc: a, bac: b, cab: c> ==> b (FF)
<abc: a, bac: ab, cab: ac> ==> a (D)
<abc: ab, bac: b, cab: c> ==> b (FF)
<abc: ab, bac: b, cab: ac> ==> b (FF)
<abc: ab, bac: ab, cab: c> ==> a, b (FF)
<abc: ab, bac: ab, cab: ac> ==> a (D)

To access one of these strategies in particular:

profile.analyzed_strategies_ordinal.equilibria[0]

<abc: a, bac: b, cab: ac> ==> b

profile.analyzed_strategies_ordinal.non_equilibria[0]

<abc: a, bac: b, cab: c> ==> b

Group strategies do not correspond to a well-defined theoretical notion, but they are convenient in practice for ProfileNoisyDiscrete. In these strategies, roughly speaking, each group has the same ballot. In our profile, it means for example that all the voters of the group \((bac, 0.25, 0.01)\) have the same ballot; and all the voters of the group \((bac, 0.75, 0.01)\) have the same ballot (but not necessarily the same as the previous group). In this example, it is a threshold strategy where the threshold utility for voters \(bac\) can be:

• 1: they all vote for \(b\),

• 0.5: voters \((bac, 0.25, 0.01)\) vote for \(b\), voters \((bac, 0.75, 0.01)\) vote for \(b\) and \(a\),

• 0: they all vote for \(b\) and \(a\).

profile.analyzed_strategies_group

Equilibria:
<abc: a, bac: ab, cab: c> ==> a (D)
<abc: a, bac: b, cab: ac> ==> b (FF)

Non-equilibria:
<abc: ab, bac: ab, cab: ac> ==> a (D)
<abc: ab, bac: ab, cab: c> ==> a, b (FF)
<abc: ab, bac: utility-dependent (0.5), cab: ac> ==> a, b (FF)
<abc: ab, bac: utility-dependent (0.5), cab: c> ==> b (D)
<abc: ab, bac: b, cab: ac> ==> b (FF)
<abc: ab, bac: b, cab: c> ==> b (FF)
<abc: a, bac: ab, cab: ac> ==> a (D)
<abc: a, bac: utility-dependent (0.5), cab: ac> ==> a (FF)
<abc: a, bac: utility-dependent (0.5), cab: c> ==> b (D)
<abc: a, bac: b, cab: c> ==> b (FF)

More generally, there is a method analyzed_strategies where you can specify an iterable of strategies that you want to study:

profile.analyzed_strategies(strategies=[
    pa.StrategyOrdinal({'abc': 'a', 'bac': 'ab', 'cab': 'c'}),
    pa.StrategyThreshold({'abc': 1, 'bac': 0.5, 'cab': 1})
])

Equilibrium:
<abc: a, bac: ab, cab: c> ==> a (D)

Non-equilibrium:
<abc: a, bac: utility-dependent (0.5), cab: c> ==> b (D)

Iterated Voting and Fictitious Play

Seek an equilibrium by iterated voting:

profile.iterated_voting(init='sincere', n_max_episodes=100)

{'converges': True,
 'cycle_taus_perceived': [<a: 0.1, ac: 0.3, b: 0.6> ==> b],
 'cycle_strategies': [<abc: a, bac: b, cab: ac> ==> b],
 'cycle_taus_actual': [<a: 0.1, ac: 0.3, b: 0.6> ==> b],
 'tau_init': <a: 0.05, ab: 0.35, b: 3/10, c: 3/10> ==> b,
 'n_episodes': 4,
 'd_candidate_winning_frequency': {b: 1}}

Seek an equilibrium by fictitious play:

profile.fictitious_play(init='sincere', n_max_episodes=100)

{'converges': False,
 'tau': None,
 'strategy': None,
 'tau_init': <a: 0.05, ab: 0.35, b: 3/10, c: 3/10> ==> b,
 'n_episodes': 100,
 'd_candidate_winning_frequency': {b: 1}}

For the precise differences between iterated voting and fictitious play, cf. the Reference section.

In practice, iterated voting and fictitious play converge more often and faster with update ratios of the form \(\frac{1}{\log(t) + 1}\), where \(t\) is the index of the episode:

profile.fictitious_play(
    init='sincere',
    n_max_episodes=100,
    perception_update_ratio=pa.one_over_log_t_plus_one,
    ballot_update_ratio=pa.one_over_log_t_plus_one,
    winning_frequency_update_ratio=pa.one_over_log_t_plus_one
)

{'converges': True,
 'tau': <a: 1/10, ac: 3/10, b: 3/5> ==> b,
 'strategy': <abc: a, bac: b, cab: ac> ==> b,
 'tau_init': <a: 0.05, ab: 0.35, b: 3/10, c: 3/10> ==> b,
 'n_episodes': 47,
 'd_candidate_winning_frequency': {b: 1}}

There are several ways to initialize these processes:

• 'sincere' (like above): voters vote for their preferred candidate if their utility for their second candidate is lower than 0.5, and vote for their two first candidates if it is greater than 0.5.

• 'fanatic': voters vote for their preferred candidate only.

• 'random_tau': a tau-vector (ballot shares) drawn uniformly at random.

• 'random_tau_undominated': a random tau-vector where each voter uses an undominated ballot.

• A given tau-vector,

• Or a given strategy.