Preference elicitation and robust winner determination for single- and multi-winner social choice (Q2287202)

In this work the authors address the problem of group decision making or preference aggregation given only partial -- instead of complete -- preference rankings of the voters. They consider both single winner problems and multi-winner problems. Two kinds of problems are treated: 1) Given \textit{partial} information about voter preferences, how does one choose a suitable outcome or winning alternative? They propose the use of \textit{maximum regret} to quantify the worst-case error of any selected alternative over possible realizations of voters' complete preferences and next they use \textit{minimax regret} as their selection criterion, choosing as a winner the alternative that minimizes this error or maximum regret. They give polynomial time algorithms for computing minimax regret and robust outcome selection for several common voting rules, including Borda, Bucklin, maximin and egalitarian, in single-winner settings. They also describe exact and approximate algorithms for multi-winner settings, focusing on robust optimization for the Chamberlin-Courant scheme. Let \(n\) be the number of voters and \(m\) the number of alternatives. Among others the authors show that minimax regret can be computed in: \(O(nm^3)\) time for any positional scoring rule; \(O(nm^4)\) time for the maximin voting rule; \(O(nm^5)\) time for the Bucklin voting rule; \(O(nm^3)\) time for egalitarian voting. 2) The second issue they address is incremental \textit{vote elicitation}. They show how to use their regret-based decision criterion to drive the process of \textit{preference elicitation}. They develop a meta-strategy called the \textit{current solution strategy} (CSS) that allows one to determine queries that quickly reduce minimax regret in practice and demonstrate its effectiveness with computational experiments on several datasets. They present a CSS for positional scoring rules and one for egalitarian voting. The authors consider two types of queries: a \textit{comparison query} identifies a voter \(k\) and asks \(k\) to compare two alternatives; a \textit{top-t query} identifies and asks voter \(k\) to state which alternative is \(t\)th in their ranking. CSS generates queries by considering the current solution to the minimax optimization and uses this to choose a voter-query pair with greatest potential to reduce minimax regret. They test their strategies on three different data sets, Sushi, Irish and Mallows, and compare their results with other strategies known from the literature: random strategy (Rand) and volumetric strategy (Vol). Finally, the authors turn their attention to the multi-winner problem, focusing primarily on the Chamberlin-Courant rule, and consider the robust optimization of a slate of alternatives given a partial preference profile, using minimax regret as their robustness criterion. They describe a greedy algorithm for robust slate selection and again give an empirical evaluation.