Group Decision Making with Partial Preferences
Collective decision making is of fundamental importance in all aspects of a modern society. Many commonly studied decision procedures require that agents provide full preference information, such as rankings and ratings, over all available alternatives. This requirement imposes significant cognitive and time burdens on agents, while increasing communication overhead and infringing on agents' private information. As a result, specifying full preferences is one of the contributing factors for the limited adoption of some commonly studied voting rules.
This thesis introduces a framework consisting of new concepts, algorithms, and theoretical results to provide a sound foundation on which one can address informational and algorithmic problems by being able to make good group decisions with only partial preference information.
We focus on single and multi-winner voting (where multiple alternatives are selected). We introduce a group decision making criterion called minimax regret (MMR), for partial preferences, which quantifies the loss in social welfare of chosen alternative(s) compared to the underlying true, but unknown, winning alternative(s). We develop polynomial-time algorithms for computing MMR for a set of common of voting rules, and prove intractability results for a set of other rules. We address preference elicitation, the second part of this framework, which concerns the extraction of only the relevant agent preferences that reduce MMR. We develop a few elicitation strategies, based on common ideas, for different voting rules and query types.
While MMR can be applied without a prior distribution, in many practical scenarios one has access to historical datasets or probabilistic knowledge of agent preferences. To leverage such information, we first address the problem of learning probabilistic models of preferences from pairwise comparisons for which previous techniques cannot handle. Then we extend our framework to a multi-round elicitation process that uses probabilistic models to guide and analyze elicitation strategies.
We empirically validate our algorithms on real datasets. Experiments show our elicitation strategies query only a fraction of full preferences to obtain alternative(s) with small MMR. Experiments also show our learning algorithms learns accurate heterogeneous models of preferences, which we then use for designing single-round elicitation protocols.
