Euclidean Models#

In Euclidean models, the voters and the candidates are assigned random positions in a given space. The preferences of a voter are then defined based on the distance between the voter and the candidates.

euclidean_threshold(num_voters: int, num_candidates: int, threshold: float, num_dimensions: int, voters_positions: EuclideanSpace | Callable | Iterable[Iterable[float]], candidates_positions: EuclideanSpace | Callable | Iterable[Iterable[float]], voters_positions_args: dict = None, candidates_positions_args: dict = None, seed: int = None) → list[set[int]][source]#

Generates approval votes according to the threshold Euclidean model.

In this model voters and candidates are assigned random positions in a Euclidean space (positions can also be provided as argument to the function). A voter then approves of the candidates that are at a distance no greater tha min_d * threshold where min_d is the minimum distance between the voter and any candidates.

A collection of num_voters vote is generated independently and identically following the process described above (as long as the point distribution is independent and identical).

Parameters:

num_voters (int) – Number of Voters.
num_candidates (int) – Number of Candidates.
threshold (float) – Threshold of approval. Voters approve all candidates that are at distance threshold times minimum distance between the voter and any candidates. This value should be 1 or more.
num_dimensions (int) – The number of dimensions to use. Using this argument is mandatory when passing a space as argument. If you pass samplers as arguments and use the num_dimensions, then, the value of num_dimensions is passed as a kwarg to the samplers.
voters_positions (EuclideanSpace | Callable | Iterable[Iterable[float]]) – The positions of the voters, or a way to determine them. If an Iterable is passed, then it is assumed to be the positions themselves. Otherwise, it is assumed that a sampler for the positions is passed. It can be either the nickname of a sampler—when passing a EuclideanSpace; or a sampler. A sampler is a function that takes as keywords arguments: ‘num_points’, ‘num_dimensions’, and ‘seed’. Additional arguments can be provided with by using the voters_positions_args argument.
candidates_positions (EuclideanSpace | Callable | Iterable[Iterable[float]]) – The positions of the candidates, or a way to determine them. If an Iterable is passed, then it is assumed to be the positions themselves. Otherwise, it is assumed that a sampler for the positions is passed. It can be either the nickname of a sampler—when passing a EuclideanSpace; or a sampler. A sampler is a function that takes as keywords arguments: ‘num_points’, ‘num_dimensions’, and ‘seed’. Additional arguments can be provided with by using the candidates_positions_args argument.
voters_positions_args (dict, default: dict()) – Additional keyword arguments passed to the voters_positions sampler when the latter is a Callable.
candidates_positions_args (dict, default: dict()) – Additional keyword arguments passed to the candidates_positions sampler when the latter is a Callable.
seed (int, default: None) – Seed for numpy random number generator. Also passed to the point samplers if a value is provided.

Returns:

Approval votes.

Return type:

list[set[int]]

Examples

Using EuclideanSpace

The easiest is to use one of the Euclidean spaces defined in EuclideanSpace.

from prefsampling.approval import euclidean_threshold
from prefsampling.core.euclidean import EuclideanSpace

# Here for 2 voters and 3 candidates with 5D uniform ball for both voters and candidates
# with threshold 2.5
euclidean_threshold(
    2,  # Number of voters
    3,  # Number of candidates
    2.5,  # Threshold value
    5,  # Number of dimensions
    EuclideanSpace.UNIFORM_BALL,  # For the voters
    EuclideanSpace.UNIFORM_BALL  # For the candidates
)

# You can use different spaces for the voters and the candidates
euclidean_threshold(
    2,
    3,
    2.5,
    5,
    EuclideanSpace.UNIFORM_SPHERE,
    EuclideanSpace.GAUSSIAN_CUBE,
    )

Using prefsampling.point

If you need more flexibility, you can also pass the point samplers directly.

from prefsampling.approval import euclidean_threshold
from prefsampling.point import ball_uniform

# Here for 2 voters and 3 candidates with 5D uniform ball for both voters and candidates
# with threshold value 2.5
euclidean_threshold(2, 3, 2.5, 5, ball_uniform, ball_uniform)

# You can specify additional arguments to the point sampler
euclidean_threshold(
    2,
    3,
    2.5,
    5,
    ball_uniform,
    ball_uniform,
    voters_positions_args = {'widths': (1, 3, 2, 4, 2)}
)

# You can also specify different point samplers for voters and candidates
from prefsampling.point import cube

euclidean_threshold(
    2,
    3,
    2.5,
    5,
    ball_uniform,
    ball_uniform,
    voters_positions_args = {'widths': (4, 7, 3, 3, 1), 'only_envelope': True},
    candidates_positions_args = {'center_point': (0.5, 1, 0, 0, 0)}
)

Using already known-positions

If you already have positions for the voters or the candidates, you can also pass them to the sampler.

from prefsampling.approval import euclidean_threshold
from prefsampling.point import gaussian
from prefsampling.core.euclidean import EuclideanSpace

# First sampler positions of the 3 candidates in 2 dimensions
candidates_positions = gaussian(3, 2, sigmas=(0.4, 0.8), widths=(5, 1))

# Then sample preferences for 2 voters based on the candidates positions
euclidean_threshold(
    2,
    3,
    2.5,
    2,
    EuclideanSpace.GAUSSIAN_BALL,
    candidates_positions
)

References

An Analysis of Approval-Based Committee Rules for 2D-Euclidean Elections, Michał T. Godziszewski, Paweł Batko, Piotr Skowron and Piotr Faliszewski, Proceedings of the AAAI Conference on Artificial Intelligence, 2021.

Price of Fairness in Budget Division and Probabilistic Social Choice, Marcin Michorzewski, Dominik Peters and Piotr Skowron, Proceedings of the AAAI Conference on Artificial Intelligence, 2020.

euclidean_vcr(num_voters: int, num_candidates: int, voters_radius: float | Iterable[float], candidates_radius: float | Iterable[float], num_dimensions: int, voters_positions: EuclideanSpace | Callable | Iterable[Iterable[float]], candidates_positions: EuclideanSpace | Callable | Iterable[Iterable[float]], voters_positions_args: dict = None, candidates_positions_args: dict = None, seed: int = None) → list[set[int]][source]#

Generates approval votes according to the voters and candidates range Euclidean model.

In this model voters and candidates are assigned random positions in a Euclidean space (positions can also be provided as argument to the function). The voters and the candidates have a radius (can be the set agent per agent, or globally). A voter approves of all the candidates that are at distance no more than voter_radius + candidate_radius, where these two values can be agent-specific. It models the idea that a voter approves of a candidate if and only if their respective influence spheres overlap.

A collection of num_voters vote is generated independently and identically following the process described above (as long as the point distribution is independent and identical).

Parameters:

num_voters (int) – Number of Voters.
num_candidates (int) – Number of Candidates.
voters_radius (float | Iterable[float]) – Radius of approval. Voters approve all candidates for which the two balls centered in the position of the voter and the candidate of radius voter_radius and candidate_radius overlap. If a single value is given, it applies to all voters. Otherwise, it is assumed that one value per voter is provided.
candidates_radius (float | Iterable[float]) – Radius of approval. Voters approve all candidates for which the two balls centered in the position of the voter and the candidate of radius voter_radius and candidate_radius overlap. If a single value is given, it applies to all voters. Otherwise, it is assumed that one value per voter is provided.
num_dimensions (int) – The number of dimensions to use. Using this argument is mandatory when passing a space as argument. If you pass samplers as arguments and use the num_dimensions, then, the value of num_dimensions is passed as a kwarg to the samplers.
voters_positions (EuclideanSpace | Callable | Iterable[Iterable[float]]) – The positions of the voters, or a way to determine them. If an Iterable is passed, then it is assumed to be the positions themselves. Otherwise, it is assumed that a sampler for the positions is passed. It can be either the nickname of a sampler—when passing a EuclideanSpace; or a sampler. A sampler is a function that takes as keywords arguments: ‘num_points’, ‘num_dimensions’, and ‘seed’. Additional arguments can be provided with by using the voters_positions_args argument.
candidates_positions (EuclideanSpace | Callable | Iterable[Iterable[float]]) – The positions of the candidates, or a way to determine them. If an Iterable is passed, then it is assumed to be the positions themselves. Otherwise, it is assumed that a sampler for the positions is passed. It can be either the nickname of a sampler—when passing a EuclideanSpace; or a sampler. A sampler is a function that takes as keywords arguments: ‘num_points’, ‘num_dimensions’, and ‘seed’. Additional arguments can be provided with by using the candidates_positions_args argument.
voters_positions_args (dict, default: dict()) – Additional keyword arguments passed to the voters_positions sampler when the latter is a Callable.
candidates_positions_args (dict, default: dict()) – Additional keyword arguments passed to the candidates_positions sampler when the latter is a Callable.
seed (int, default: None) – Seed for numpy random number generator. Also passed to the point samplers if a value is provided.

Returns:

Approval votes.

Return type:

list[set[int]]

Examples

Using EuclideanSpace

The easiest is to use one of the Euclidean spaces defined in EuclideanSpace.

from prefsampling.approval import euclidean_vcr
from prefsampling.core.euclidean import EuclideanSpace

# Here for 2 voters and 3 candidates with 5D uniform ball for both voters and candidates
# with radius 2.5 for the voters and 5.3 for the candidates
euclidean_vcr(
    2,  # Number of voters
    3,  # Number of candidates
    2.5,  # Voters radius
    5.3,  # Candidates radius
    5,  # Number of dimensions
    EuclideanSpace.UNIFORM_BALL,  # For the voters
    EuclideanSpace.UNIFORM_BALL  # For the candidates
)

# You can use different spaces for the voters and the candidates
euclidean_vcr(
    2,
    3,
    2.5,
    5.3,
    5,
    EuclideanSpace.UNIFORM_SPHERE,
    EuclideanSpace.GAUSSIAN_CUBE,
    )

# You can provide individual radius
euclidean_vcr(
    2,
    3,
    (2.5, 2.8),
    (5.3, 5.1, 5.9),
    5,
    EuclideanSpace.UNIFORM_SPHERE,
    EuclideanSpace.UNIFORM_CUBE,
    )

Using prefsampling.point

If you need more flexibility, you can also pass the point samplers directly.

from prefsampling.approval import euclidean_vcr
from prefsampling.point import ball_uniform

# Here for 2 voters and 3 candidates with 5D uniform ball for both voters and candidates
# with radius 2.5 for the voters and 5.3 for the candidates
euclidean_vcr(2, 3, 2.5, 5.3, 5, ball_uniform, ball_uniform)

# You can specify additional arguments to the point sampler
euclidean_vcr(
    2,
    3,
    2.5,
    5.3,
    5,
    ball_uniform,
    ball_uniform,
    voters_positions_args = {'widths': (1, 3, 2, 4, 2)}
)

# You can also specify different point samplers for voters and candidates
from prefsampling.point import cube

euclidean_vcr(
    2,
    3,
    2.5,
    5.3,
    5,
    ball_uniform,
    ball_uniform,
    voters_positions_args = {'widths': (4, 7, 3, 3, 1), 'only_envelope': True},
    candidates_positions_args = {'center_point': (0.5, 1, 0, 0, 0)}
)

Using already known-positions

If you already have positions for the voters or the candidates, you can also pass them to the sampler.

from prefsampling.approval import euclidean_vcr
from prefsampling.point import gaussian
from prefsampling.core.euclidean import EuclideanSpace

# First sampler positions of the 3 candidates in 2 dimensions
candidates_positions = gaussian(3, 2, sigmas=(0.4, 0.8), widths=(5, 1))

# Then sample preferences for 2 voters based on the candidates positions
euclidean_vcr(
    2,
    3,
    2.5,
    5.3,
    2,
    EuclideanSpace.GAUSSIAN_BALL,
    candidates_positions
)

References

An Experimental View on Committees Providing Justified Representation, Robert Bredereck, Piotr Faliszewski, Andrzej Kaczmarczyk and Rolf Niedermeier, Proceedings of the International Joint Conference on Artificial Intelligence, 2019.

How to Sample Approval Elections?, Stanisław Szufa, Piotr Faliszewski, Łukasz Janeczko, Martin Lackner, Arkadii Slinko, Krzysztof Sornat and Nimrod Talmon, Proceedings of the International Joint Conference on Artificial Intelligence, 2022.

euclidean_constant_size(num_voters: int, num_candidates: int, rel_num_approvals: float, num_dimensions: int, voters_positions: EuclideanSpace | Callable | Iterable[Iterable[float]], candidates_positions: EuclideanSpace | Callable | Iterable[Iterable[float]], voters_positions_args: dict = None, candidates_positions_args: dict = None, seed: int = None) → list[set[int]][source]#

Generates approval votes according to the constant size Euclidean model.

In this model voters and candidates are assigned random positions in a Euclidean space (positions can also be provided as argument to the function). A voter then approves of the rel_num_approvals * num_candidates the closest candidates to their position. This ensures that all approval ballots have length ⌊rel_num_approvals * num_candidates⌋.

A collection of num_voters vote is generated independently and identically following the process described above (as long as the point distribution is independent and identical).

Parameters:

num_voters (int) – Number of Voters.
num_candidates (int) – Number of Candidates.
rel_num_approvals (float) – Proportion of approved candidates in a ballot.
num_dimensions (int) – The number of dimensions to use. Using this argument is mandatory when passing a space as argument. If you pass samplers as arguments and use the num_dimensions, then, the value of num_dimensions is passed as a kwarg to the samplers.
voters_positions (EuclideanSpace | Callable | Iterable[Iterable[float]]) – The positions of the voters, or a way to determine them. If an Iterable is passed, then it is assumed to be the positions themselves. Otherwise, it is assumed that a sampler for the positions is passed. It can be either the nickname of a sampler—when passing a EuclideanSpace; or a sampler. A sampler is a function that takes as keywords arguments: ‘num_points’, ‘num_dimensions’, and ‘seed’. Additional arguments can be provided with by using the voters_positions_args argument.
candidates_positions (EuclideanSpace | Callable | Iterable[Iterable[float]]) – The positions of the candidates, or a way to determine them. If an Iterable is passed, then it is assumed to be the positions themselves. Otherwise, it is assumed that a sampler for the positions is passed. It can be either the nickname of a sampler—when passing a EuclideanSpace; or a sampler. A sampler is a function that takes as keywords arguments: ‘num_points’, ‘num_dimensions’, and ‘seed’. Additional arguments can be provided with by using the candidates_positions_args argument.
voters_positions_args (dict, default: dict()) – Additional keyword arguments passed to the voters_positions sampler when the latter is a Callable.
candidates_positions_args (dict, default: dict()) – Additional keyword arguments passed to the candidates_positions sampler when the latter is a Callable.
seed (int, default: None) – Seed for numpy random number generator. Also passed to the point samplers if a value is provided.

Returns:

Approval votes.

Return type:

list[set[int]]

Examples

Using EuclideanSpace

The easiest is to use one of the Euclidean spaces defined in EuclideanSpace.

from prefsampling.approval import euclidean_constant_size
from prefsampling.core.euclidean import EuclideanSpace

# Here for 2 voters and 3 candidates with 5D uniform ball for both voters and candidates
# with relative size of the approval ballots 0.5
euclidean_constant_size(
    2,  # Number of voters
    3,  # Number of candidates
    0.5,  # Relative size of the approval ballots
    5,  # Number of dimensions
    EuclideanSpace.UNIFORM_BALL,  # For the voters
    EuclideanSpace.UNIFORM_BALL  # For the candidates
)

# You can use different spaces for the voters and the candidates
euclidean_constant_size(
    2,
    3,
    0.5,
    5,
    EuclideanSpace.UNIFORM_SPHERE,
    EuclideanSpace.GAUSSIAN_CUBE,
)

# The relative size of the approval ballots need to be in [0, 1]
try:
    euclidean_constant_size(
        2,
        3,
        1.5,
        5,
        EuclideanSpace.UNIFORM_SPHERE,
        EuclideanSpace.GAUSSIAN_CUBE,
    )
except ValueError:
    pass
try:
    euclidean_constant_size(
        2,
        3,
        -0.5,
        5,
        EuclideanSpace.UNIFORM_SPHERE,
        EuclideanSpace.GAUSSIAN_CUBE,
    )
except ValueError:
    pass

Using prefsampling.point

If you need more flexibility, you can also pass the point samplers directly.

from prefsampling.approval import euclidean_constant_size
from prefsampling.point import ball_uniform

# Here for 2 voters and 3 candidates with 5D uniform ball for both voters and candidates
# with relative size of the approval ballots 2.5
euclidean_constant_size(2, 3, 0.5, 5, ball_uniform, ball_uniform)

# You can specify additional arguments to the point sampler
euclidean_constant_size(
    2,
    3,
    0.5,
    5,
    ball_uniform,
    ball_uniform,
    voters_positions_args = {'widths': (1, 3, 2, 4, 2)}
)

# You can also specify different point samplers for voters and candidates
from prefsampling.point import cube

euclidean_constant_size(
    2,
    3,
    0.5,
    5,
    ball_uniform,
    ball_uniform,
    voters_positions_args = {'widths': (4, 7, 3, 3, 1), 'only_envelope': True},
    candidates_positions_args = {'center_point': (0.5, 1, 0, 0, 0)}
)

Using already known-positions

If you already have positions for the voters or the candidates, you can also pass them to the sampler.

from prefsampling.approval import euclidean_threshold
from prefsampling.point import gaussian
from prefsampling.core.euclidean import EuclideanSpace

# First sampler positions of the 3 candidates in 2 dimensions
candidates_positions = gaussian(3, 2, sigmas=(0.4, 0.8), widths=(5, 1))

# Then sample preferences for 2 voters based on the candidates positions
euclidean_constant_size(
    2,
    3,
    0.5,
    2,
    EuclideanSpace.GAUSSIAN_BALL,
    candidates_positions
)

References

Perpetual Voting: Fairness in Long-Term Decision Making, Martin Lackner, Proceedings of the AAAI Conference on Artificial Intelligence, 2020.

class EuclideanSpace(value, names=None, *, module=None, qualname=None, type=None, start=1, boundary=None)[source]#

Constants for some pre-defined Euclidean distributions.

GAUSSIAN_BALL = 'gaussian_ball'#: Constants representing a Gaussian ball with center point at the origin and width of 1 for all dimensions. The inner Gaussian sampler has mean 0 and standard deviation 0.33.

GAUSSIAN_CUBE = 'gaussian_cube'#: Constants representing a Gaussian ball with center point at the origin and width of 1 for all dimensions.

UNBOUNDED_GAUSSIAN = 'unbounded_gaussian'#: Constants representing an unbounded Gaussian space.The inner Gaussian sampler has mean 0 and standard deviation 1.

UNIFORM_BALL = 'uniform_ball'#: Constants representing a uniform ball with center point at the origin and width of 1 for all dimensions.

UNIFORM_CUBE = 'uniform_cube'#: Constants representing a uniform cube with center point at the origin and width of 1 for all dimensions.

UNIFORM_SPHERE = 'uniform_sphere'#: Constants representing a uniform sphere with center point at the origin and width of 1 for all dimensions. This is the envelope of the uniform ball.

Euclidean Models

Contents

Euclidean Models#