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 aEuclideanSpace
; 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 thevoters_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 aEuclideanSpace
; 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 thecandidates_positions_args
argument.voters_positions_args (dict, default:
dict()
) – Additional keyword arguments passed to thevoters_positions
sampler when the latter is a Callable.candidates_positions_args (dict, default:
dict()
) – Additional keyword arguments passed to thecandidates_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 aEuclideanSpace
; 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 thevoters_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 aEuclideanSpace
; 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 thecandidates_positions_args
argument.voters_positions_args (dict, default:
dict()
) – Additional keyword arguments passed to thevoters_positions
sampler when the latter is a Callable.candidates_positions_args (dict, default:
dict()
) – Additional keyword arguments passed to thecandidates_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 aEuclideanSpace
; 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 thevoters_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 aEuclideanSpace
; 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 thecandidates_positions_args
argument.voters_positions_args (dict, default:
dict()
) – Additional keyword arguments passed to thevoters_positions
sampler when the latter is a Callable.candidates_positions_args (dict, default:
dict()
) – Additional keyword arguments passed to thecandidates_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)[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.