Coverage for /home/simon/Git/preflibtools/preflibtools/properties/basic.py: 83%

75 statements  

« prev     ^ index     » next       coverage.py v6.4.4, created at 2022-09-22 11:34 +0200

1""" This module describes several procedures to check for basic procedures of PrefLib instances. 

2""" 

3 

4 

5def pairwise_scores(instance): 

6 """ Returns a dictionary of dictionaries mapping every alternative a to the number of times it beats 

7 every other alternative b (the number of voters preferring a over b). 

8 

9 :param instance: The instance. 

10 :type instance: preflibtools.instance.preflibinstance.PreflibInstance 

11 

12 :return: A dictionary of dictionaries storing the scores. 

13 :rtype: dict 

14 """ 

15 if instance.data_type in ["soc", "toc", "soi", "toi"]: 

16 scores = {alt: {a: 0 for a in instance.alternatives_name if a != alt} for alt in instance.alternatives_name} 

17 for order in instance.orders: 

18 alternatives_before = [] 

19 for indif_class in order: 

20 # Every alternative appearing before are beating the ones in the current indifference class 

21 for alt_beaten in indif_class: 

22 for alt_winning in alternatives_before: 

23 scores[alt_winning][alt_beaten] += instance.multiplicity[order] 

24 alternatives_before += [alt for alt in indif_class] 

25 return scores 

26 

27 

28def copeland_scores(instance): 

29 """ Returns a dictionary of dictionaries mapping every alternative a to their Copeland score against every other 

30 alternative b (the number of voters preferring a over b minus the number of voters preferring b over a). 

31 

32 :param instance: The instance. 

33 :type instance: preflibtools.instance.preflibinstance.PreflibInstance 

34 

35 :return: A dictionary of dictionaries storing the scores. 

36 :rtype: dict 

37 """ 

38 if instance.data_type in ["soc", "toc", "soi", "toi"]: 

39 scores = {alt: {a: 0 for a in instance.alternatives_name if a != alt} for alt in instance.alternatives_name} 

40 for order in instance.orders: 

41 alternatives_before = [] 

42 for indif_class in order: 

43 # Every alternative appearing before are beating the ones in the current indifference class 

44 for alt_beaten in indif_class: 

45 for alt_winning in alternatives_before: 

46 scores[alt_winning][alt_beaten] += instance.multiplicity[order] 

47 scores[alt_beaten][alt_winning] -= instance.multiplicity[order] 

48 alternatives_before += [alt for alt in indif_class] 

49 return scores 

50 

51 

52def has_condorcet(instance): 

53 """ Checks whether the instance has a Condorcet winner, using different procedures depending on the data type of 

54 the instance. An alternative is a Condorcet winner if it strictly beats every other alternative in a pairwise 

55 majority contest.  

56 

57 :param instance: The instance. 

58 :type instance: preflibtools.instance.preflibinstance.PreflibInstance 

59 

60 :return: A boolean indicating whether the instance has a Condorcet winner or not. 

61 :rtype: bool 

62 """ 

63 if instance.data_type in ["soc", "toc", "soi", "toi"]: 

64 scores = copeland_scores(instance) 

65 for alt, scoreDict in scores.items(): 

66 if all(score > 0 for score in scoreDict.values()): 

67 return True 

68 return False 

69 

70 

71def borda_scores(instance): 

72 """ Computes the total Borda scores of all the alternatives of the instance. Within an indifference class, all 

73 alternatives are assigned the smallest score one alternative from the class would have gotten, had the order 

74 been strict. For instance, for the order ({a1}, {a2, a3}, {a4}), a1 gets score 3, a2 and a3 score 1 and a4  

75 score 0. 

76 

77 :param instance: The instance. 

78 :type instance: preflibtools.instance.preflibinstance.PreflibInstance 

79 

80 :return: A dictionary mapping every instance to their Borda score. 

81 :rtype: dict 

82 """ 

83 if instance.data_type not in ("toc", "soc", "toi", "soi"): 

84 raise TypeError("You are trying to compute the Borda scores of an instance of type " + 

85 str(instance.data_type) + ", this is not possible.") 

86 res = dict([]) 

87 for order in instance.orders: 

88 i = instance.num_alternatives 

89 for indif_class in order: 

90 i -= len(indif_class) 

91 for alt in indif_class: 

92 if alt not in res: 

93 res[alt] = i 

94 else: 

95 res[alt] += i 

96 return res 

97 

98 

99def num_alternatives(instance): 

100 """ Returns the number of alternatives of the instance. 

101 

102 :param instance: The instance. 

103 :type instance: preflibtools.instance.preflibinstance.PreflibInstance 

104 

105 :return: The number of alternatives of the instance. 

106 :rtype: int 

107 """ 

108 return instance.num_alternatives 

109 

110 

111def num_voters(instance): 

112 """ Returns the number of voters . 

113 

114 :param instance: The instance. 

115 :type instance: preflibtools.instance.preflibinstance.PreflibInstance 

116 

117 :return: The number of voters of the instance. 

118 :rtype: int 

119 """ 

120 return instance.num_voters 

121 

122 

123def num_different_preferences(instance): 

124 """ Returns the number of different orders of the instance. 

125 

126 :param instance: The instance. 

127 :type instance: preflibtools.instance.preflibinstance.PreflibInstance 

128 

129 :return: The number of different orders of the instance. 

130 :rtype: int 

131 """ 

132 if instance.data_type in ("toc", "soc", "toi", "soi"): 

133 return instance.num_unique_orders 

134 elif instance.data_type == "cat": 

135 return instance.num_unique_preferences 

136 

137 

138def largest_ballot(instance): 

139 """ Returns the size of the largest ballot of the instance, i.e., the maximum number of alternatives  

140 appearing in an order. 

141 

142 :param instance: The instance. 

143 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance 

144 

145 :return: The size of the largest ballot of the instance. 

146 :rtype: int 

147 """ 

148 return max([sum([len(indif_class) for indif_class in order]) for order in instance.orders]) 

149 

150 

151def smallest_ballot(instance): 

152 """ Returns the size of the smallest ballot of the instance, i.e., the smallest number of alternatives  

153 appearing in an order. 

154 

155 :param instance: The instance. 

156 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance 

157 

158 :return: The size of the smallest ballot of the instance. 

159 :rtype: int 

160 """ 

161 return min([sum([len(indif_class) for indif_class in order]) for order in instance.orders]) 

162 

163 

164def max_num_indif(instance): 

165 """ Returns the maximum number of indifference classes over the orders of the instance. 

166 

167 :param instance: The instance. 

168 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance 

169 

170 :return: The maximum number of indifference classes of the instance. 

171 :rtype: int 

172 """ 

173 return max([len([p for p in o if len(p) > 1]) for o in instance.orders] + [0]) 

174 

175 

176def min_num_indif(instance): 

177 """ Returns the minimum number of indifference classes over the orders of the instance. 

178 

179 :param instance: The instance. 

180 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance 

181 

182 :return: The minimum number of indifference classes of the instance. 

183 :rtype: int 

184 """ 

185 return min([len([p for p in o if len(p) > 1]) for o in instance.orders] + [instance.num_alternatives]) 

186 

187 

188def largest_indif(instance): 

189 """ Returns the size of the largest indifference class of any voter of the instance. 

190 

191 :param instance: The instance. 

192 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance 

193 

194 :return: The size of the largest indifference class of the instance. 

195 :rtype: int 

196 """ 

197 return max([len(p) for o in instance.orders for p in o if len(p) > 0] + [0]) 

198 

199 

200def smallest_indif(instance): 

201 """ Returns the size of the smallest indifference class of any voter of the instance. 

202 

203 :param instance: The instance. 

204 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance 

205 

206 :return: The size of the smallest indifference class of the instance. 

207 :rtype: int 

208 """ 

209 return min([len(p) for o in instance.orders for p in o if len(p) > 0] + [instance.num_alternatives]) 

210 

211 

212def is_approval(instance): 

213 """ Checks whether the instance describes an approval profile. A profile is considered to represent approval  

214 ballots in two cases: All the orders are complete and consist of only two indifference classes; The orders 

215 are incomplete and consists of a single indifference class. 

216 

217 :param instance: The instance. 

218 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance 

219 

220 :return: A boolean indicating whether the instance describes an approval profile. 

221 :rtype: bool 

222 """ 

223 m = max([len(order) for order in instance.orders]) 

224 if m == 1: 

225 return True 

226 elif m == 2: 

227 return is_complete(instance) 

228 else: 

229 return False 

230 

231 

232def is_strict(instance): 

233 """ Checks whether the instance describes a profile of strict preferences. 

234 

235 :param instance: The instance. 

236 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance 

237 

238 :return: A boolean indicating whether the instance describes a profile of strict preferences. 

239 :rtype: bool 

240 """ 

241 return largest_indif(instance) == 1 

242 

243 

244def is_complete(instance): 

245 """ Checks whether the instance describes a profile of complete preferences. 

246 

247 :param instance: The instance. 

248 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance 

249 

250 :return: A boolean indicating whether the instance describes a profile of complete preferences. 

251 :rtype: bool 

252 """ 

253 return smallest_ballot(instance) == instance.num_alternatives