Robust Winners and Winner Determination Policies under Candidate Uncertainty
Authors: Craig Boutilier, Jérôme Lang, Joel Oren, Héctor Palacios
AAAI 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Empirical Evaluation We now discuss experiments that test the effectiveness of our algorithms for computing query policies, and examine the expected costs of these policies for various voting rules, preference distributions and availability distributions. We generate vote profiles using Mallows distributions over rankings (Mallows 1957), given by a modal ranking σ over X and dispersion φ 2 (0, 1]: the probability of vote v is Pr(v|σ, φ) / φd(r,σ), where d is Kendall s -distance. Smaller φ concentrates mass around σ while φ = 1 gives the uniform distribution (i.e., impartial culture). We use m = 10 candidates and n = 100 voters, generating profiles for φ 2 {0.3, 0.8, 1.0}, and consider three voting rules: plurality, Borda and Copeland. We vary the availability probabilities p with each candidate having the same p. Results for each problem instance (combination of voting rule, φ, p) are averaged over 25 random vote profiles. Before exploring query policies, we measure the probability of selecting an incorrect winner using a policy that selects the na ıve winner, r(v), ignoring candidate unavailability. An obvious lower bound on this error is 1 p (i.e., when the winner is unavailable). Fig. 2 shows this error probability conditional on the winner being available for the three voting rules considered and different φ, as we vary p. For p near 1, the na ıve winner is, of course, almost always correct. At the other extreme, the na ıve winner is also usually correct, since it is highly likely to be the only available option. When preferences are very peaked (φ = 0.3), candidate availability has little impact (most voters have similar rankings; but as they become more uniform the impact is dramatic. This suggests that testing availability is important even for reasonably high values of p. These results give only a crude sense of the degree of robustness of a winner who is assumed to be available, even for low p, and provide minimal insight into the value of intelligent availability testing. We now consider the expected number of queries needed to determine the winner in the settings described above (using the same values of φ) under different availability probabilities: p = 0.3, 0.5, 0.9. Results for all three voting rules and six of nine parameter settings, with average expected cost (min, max) over 25 trials, are shown in the left half of Table 1.5 In most settings, optimal query policies offer significant savings relative to the approach that first tests the availability of all ten candidates. The myopic heuristic tends to produce trees with costs very close to the optimum: even in problems with the largest gap (i.e., plurality with φ = 1), myopic trees have an average expected cost of only 0.3 more queries than optimal; in most cases, myopic trees are almost identical to the optimum; so the more efficient myopic approach effectively minimizes query costs in practice. Not surprisingly, we see strong (negative) correlations between cost and availability probability in all three rules. Query cost is also correlated with dispersion φ: when φ is greater (more uniform), costs are higher since preferences are more diverse. When dispersion φ is low, given a fixed p, expected cost is the essentially the same for each rule, and the myopic approach is virtually optimal. The right half of Table 1 shows the sizes of the decision trees that result when running both of our algorithms: tree size is only indirectly related to expected query cost, since the relative balance of the trees also impacts costs. Nonetheless we see an expected correlation, though plurality tends to result in larger trees, especially for φ = 1. The myopic trees are not significantly larger than the optimal trees, though the differences in size are somewhat more pronounced than the differences in query cost. We also ran experiments to test the effectiveness of querying for approximate robustness, that is, terminating the querying process when the information set ensures that a specific candidate is the true winner with probability at least 1 δ. Space precludes a full discussion, but using a modified version of the DP algorithm, we computed optimal query policies for values of δ 2 {0.001, 0.01, 0.1} (i.e., exactly optimal policies given the goal of finding a 1 δ-robust winner). With plurality, dispersion φ = 1.0 and p = 0.9, fully robust policies had an expected cost of 5.42 queries on average. Allowing 1 δ-robust winners greatly reduced the expected cost: with δ = 0.001 average expected cost was 4.97 queries; for δ = 0.01, 4.36 queries; and for δ = 0.1, 3.04 queries. For p = 0.3, setting δ = 0.1 saw a reduction to 5.28 queries (compared to 6.73 for exact robustness). Other voting rules exhibited similar patterns. |
| Researcher Affiliation | Academia | Craig Boutilier Department of Computer Science University of Toronto cebly@cs.toronto.edu J erˆome Lang LAMSADE Universit e Paris-Dauphine lang@lamsade.dauphine.fr Joel Oren Department of Computer Science University of Toronto oren@cs.toronto.edu H ector Palacios Departament de Tecnologies Universitat Pompeu Fabra hector.palacios@upf.edu |
| Pseudocode | No | The paper describes algorithms but does not include structured pseudocode or clearly labeled algorithm blocks. |
| Open Source Code | No | The paper does not provide any concrete access information for open-source code (e.g., a repository link, an explicit code release statement, or mention of code in supplementary materials) for the methodology described. |
| Open Datasets | No | The paper states 'We generate vote profiles using Mallows distributions over rankings (Mallows 1957)', indicating data was generated rather than using a specific publicly available dataset with concrete access information. |
| Dataset Splits | No | The paper describes generating vote profiles and averaging results over 25 random vote profiles, but it does not specify any training, validation, or test dataset splits. |
| Hardware Specification | No | The paper does not provide specific hardware details (e.g., GPU/CPU models, processor types, or memory amounts) used for running its experiments. |
| Software Dependencies | No | The paper does not provide specific ancillary software details, such as library or solver names with version numbers, needed to replicate the experiment. |
| Experiment Setup | Yes | We use m = 10 candidates and n = 100 voters, generating profiles for φ 2 {0.3, 0.8, 1.0}, and consider three voting rules: plurality, Borda and Copeland. We vary the availability probabilities p with each candidate having the same p. Results for each problem instance (combination of voting rule, φ, p) are averaged over 25 random vote profiles. |