Coverage for /home/simon/Git/preflibtools/preflibtools/instances/sampling.py: 84%
74 statements
« prev ^ index » next coverage.py v6.4.4, created at 2022-09-22 11:34 +0200
« prev ^ index » next coverage.py v6.4.4, created at 2022-09-22 11:34 +0200
1""" This module describes procedures to sample preferences for different probability distributions.
2"""
4import numpy as np
7def generate_mallows(num_voters, num_alternatives, mixture, dispersions, references):
8 """ Generates a profile following a mixture of Mallow's models.
10 :param num_voters: Number of orders to sample.
11 :type num_voters: int
12 :param num_alternatives: Number of alternatives for the sampled orders.
13 :type num_alternatives: int
14 :param mixture: A list of the weights of each element of the mixture.
15 :type mixture: list of positive numbers
16 :param dispersions: A list of the dispersion coefficient of each element of the mixture.
17 :type dispersions: list of float
18 :param references: A list of the reference orders for each element of the mixture.
19 :type references: list of tuples of tuples of int
21 :return: A vote map, i.e., a dictionary whose keys are orders, mapping to the number of voters with
22 the given order as their preferences.
23 :rtype: dict
24 """
26 def mallows_insert_distributions(num_alternatives, phi):
27 distributions = {}
28 for i in range(1, num_alternatives + 1):
29 # Start with an empty distro of length i
30 distribution = [0] * i
31 # compute the denom = phi^0 + phi^1 + ... phi^(i-1)
32 denominator = sum([pow(phi, k) for k in range(i)])
33 # Fill each element of the distro with phi^(i-j) / denominator
34 for j in range(1, i + 1):
35 distribution[j - 1] = pow(phi, i - j) / denominator
36 distributions[i] = distribution
37 return distributions
39 if len(mixture) != len(dispersions) or len(mixture) != len(references):
40 raise ValueError("Parameters of Mallows' mixture do not have the same length.")
41 # We normalize the mixture so that it sums up to 1
42 if sum(mixture) != 1:
43 mixture = [m / sum(mixture) for m in mixture]
45 # Precompute the distros for each Phi.
46 insert_distributions = []
47 for i in range(len(mixture)):
48 insert_distributions.append(mallows_insert_distributions(num_alternatives, dispersions[i]))
50 # Now, generate votes...
51 vote_map = {}
52 for voter in range(num_voters):
53 model = np.random.choice(range(len(mixture)), 1, p=mixture)[0]
55 # Generate a vote for the selected model
56 insert_vector = [0] * num_alternatives
57 for i in range(1, len(insert_vector) + 1):
58 # options are 1...max
59 insert_vector[i - 1] = np.random.choice(range(1, i + 1), 1, p=insert_distributions[model][i])[0]
61 vote = []
62 for i in range(len(references[model])):
63 vote.insert(insert_vector[i] - 1, references[model][i])
65 vote = tuple((alt,) for alt in vote)
66 vote_map[vote] = vote_map.get(vote, 0) + 1
68 return vote_map
71def generate_mallows_mix(num_voters, alternatives, num_references):
72 """ Generates a profile following a mixture of Mallow's models for which reference points and dispersion
73 coefficients are independently and identically distributed.
75 :param num_voters: Number of orders to sample.
76 :type num_voters: int
77 :param alternatives: List of alternatives for the sampled orders.
78 :type alternatives: list of int
79 :param num_references: Number of element
80 :type num_references: int
82 :return: A vote map, i.e., a dictionary whose keys are orders, mapping to the number of voters with
83 the given order as their preferences.
84 :rtype: dict
85 """
86 mixture = []
87 dispersions = []
88 references = []
89 for i in range(num_references):
90 references.append(tuple(generate_IC(1, alternatives))[0])
91 dispersions.append(round(np.random.rand(), 5))
92 mixture.append(np.random.randint(1, 101))
93 mixture = [float(i) / float(sum(mixture)) for i in mixture]
94 return generate_mallows(num_voters, len(alternatives), mixture, dispersions, references)
97def generate_urn(num_voters, alternatives, replace):
98 """ Generates a profile following the urn model.
100 :param num_voters: Number of orders to sample.
101 :type num_voters: int
102 :param alternatives: List of alternatives.
103 :type alternatives: list of int
104 :param replace: The number of replacements for the urn model.
105 :type replace: int
107 :return: A vote map, i.e., a dictionary whose keys are orders, mapping to the number of voters with
108 the given order as their preferences.
109 :rtype: dict
110 """
111 vote_map = {}
112 replace_votes = {}
114 IC_size = np.math.factorial(len(alternatives))
115 replace_size = 0
117 for x in range(num_voters):
118 flip = np.random.randint(1, IC_size + replace_size + 1)
119 if flip <= IC_size:
120 # generate an IC vote and make a suitable number of replacements...
121 vote = generate_IC_ballot(alternatives)
122 vote_map[vote] = (vote_map.get(vote, 0) + 1)
123 replace_votes[vote] = (replace_votes.get(vote, 0) + replace)
124 replace_size += replace
126 else:
127 # iterate over replacement hash and select proper vote.
128 flip = flip - IC_size
129 for vote in replace_votes.keys():
130 flip = flip - replace_votes[vote]
131 if flip <= 0:
132 vote = tuple((alt,) for alt in vote)
133 vote_map[vote] = (vote_map.get(vote, 0) + 1)
134 replace_votes[vote] = (replace_votes.get(vote, 0) + replace)
135 replace_size += replace
136 break
137 else:
138 print("We Have a problem... replace fell through....")
139 exit()
141 return vote_map
144def generate_IC(num_voters, alternatives):
145 """ Generates a profile of strict preferences following the impartial culture.
147 :param num_voters: Number of orders to sample.
148 :type num_voters: int
149 :param alternatives: List of alternatives.
150 :type alternatives: list of int
152 :return: A vote map, i.e., a dictionary whose keys are orders, mapping to the number of voters with
153 the given order as their preferences.
154 :rtype: dict
155 """
156 return generate_urn(num_voters, alternatives, 0)
159def generate_IC_anon(num_voters, alternatives):
160 """ Generates a profile of strict preferences following the anonymous impartial culture.
162 :param num_voters: Number of orders to sample.
163 :type num_voters: int
164 :param alternatives: List of alternatives.
165 :type alternatives: list of int
167 :return: A vote map, i.e., a dictionary whose keys are orders, mapping to the number of voters with
168 the given order as their preferences.
169 :rtype: dict
170 """
171 return generate_urn(num_voters, alternatives, 1)
174def generate_IC_ballot(alternatives):
175 """ Generates a strict order over the set of alternatives following the impartial culture.
177 :param alternatives: List of alternatives.
178 :type alternatives: list of int
180 :return: A strict order over the alternatives, i.e., a tuple of tuples of size 1.
181 :rtype: tuple
182 """
183 options = list(alternatives)
184 vote = []
185 while len(options) > 0:
186 # randomly select an option
187 vote.append(options.pop(np.random.randint(0, len(options))))
188 return tuple((alt,) for alt in vote)