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

1""" This module describes procedures to sample preferences for different probability distributions. 

2""" 

3 

4import numpy as np 

5 

6 

7def generate_mallows(num_voters, num_alternatives, mixture, dispersions, references): 

8 """ Generates a profile following a mixture of Mallow's models. 

9 

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 

20 

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 """ 

25 

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 

38 

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] 

44 

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])) 

49 

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] 

54 

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] 

60 

61 vote = [] 

62 for i in range(len(references[model])): 

63 vote.insert(insert_vector[i] - 1, references[model][i]) 

64 

65 vote = tuple((alt,) for alt in vote) 

66 vote_map[vote] = vote_map.get(vote, 0) + 1 

67 

68 return vote_map 

69 

70 

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. 

74 

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 

81 

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) 

95 

96 

97def generate_urn(num_voters, alternatives, replace): 

98 """ Generates a profile following the urn model. 

99 

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 

106 

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 = {} 

113 

114 IC_size = np.math.factorial(len(alternatives)) 

115 replace_size = 0 

116 

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 

125 

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() 

140 

141 return vote_map 

142 

143 

144def generate_IC(num_voters, alternatives): 

145 """ Generates a profile of strict preferences following the impartial culture. 

146 

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 

151 

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) 

157 

158 

159def generate_IC_anon(num_voters, alternatives): 

160 """ Generates a profile of strict preferences following the anonymous impartial culture. 

161 

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 

166 

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) 

172 

173 

174def generate_IC_ballot(alternatives): 

175 """ Generates a strict order over the set of alternatives following the impartial culture. 

176 

177 :param alternatives: List of alternatives. 

178 :type alternatives: list of int 

179 

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)