Group-Separable Models

group_separable(num_voters: int, num_candidates: int, tree_sampler: TreeSampler = TreeSampler.SCHROEDER, seed: int = None) → list[list[int]]

Samplers for group separable votes. For the definition of group-seprable preferences, see Elkind, Lackner, Peters (2022).

This sampler implements the algorithm presented by Faliszewski, Karpov, Obraztsova (2022). The implementation follows these general steps. First, a decomposition tree is sampled at random. Then, for each internal node of the tree the order of its children is reversed with probability 0.5. The vote then corresponds to the label of the leaves of the tree read from left to right.

This sampler only generates neutral collections of votes. This means that the first vote is always 0 > 1 > 2 > ….

When used with a uniform sampler over all decomposition trees it is meant to yield a uniform distribution over neutral group separable collections of votes. However, our analysis indicates that it is not the case: collections of vote containing only 0 < 1 < 2 < … ` or `m-1 < m-2 < m-3 < … are over-represented.

Note that for a given number of voters, votes are sampled independently but the number of voters can impact the sampling of the decomposition tree.

Parameters:

• num_voters (int) – Number of Voters.

• num_candidates (int) – Number of Candidates.

• tree_sampler (TreeSampler, default: SCHROEDER) – Sampler used to sample the tree. Should be one of the constants defined in the

• seed (int, default: None) – Seed for numpy random number generator.

Returns:

Ordinal votes.

Return type:

list[list[int]]

Examples

from prefsampling.ordinal import group_separable, TreeSampler

# Sample a group-separable profile model with 2 voters and 3 candidates using the
# sampler for Schröder trees proposed by Alonso, Rémy, Schott (1997)
group_separable(2, 3, tree_sampler=TreeSampler.SCHROEDER)

# For reproducibility, you can set the seed.
group_separable(2, 3, tree_sampler=TreeSampler.SCHROEDER_UNIFORM, seed=1002)

Validation

When using a sampler for trees that is uniform, the probability distribution over group-separable profiles generated by this sampler should be uniform too.

References

The complexity of election problems with group-separable preferences, Faliszewski, Piotr, Alexander Karpov, and Svetlana Obraztsova, Autonomous Agents and Multi-Agent Systems 36:18, 2022.

class TreeSampler(value, names=<not given>, *values, module=None, qualname=None, type=None, start=1, boundary=None)

Constants use to represent different samplers for trees that can be used for group separable preferences.

BALANCED = 'Balanced Tree'

Balanced trees

CATERPILLAR = 'Caterpillar Tree'

Caterpillar trees

SCHROEDER = 'Scröder Tree by Alsonso, Rémy, Schott'

Random Schröder trees sampled following Alonso, Rémy, Schott (1997)

SCHROEDER_LESCANNE = 'Scröder Tree by Lescanne'

Random Schröder trees sampled following Lescanne (2022)

SCHROEDER_UNIFORM = 'Scröder Tree by brute-force'

Random Schröder sampled uniformly via complete enumeration algorithm