| Group 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. This requirement imposes significant cognitive and time burdens on agents, increases communication overhead, and infringes agent privacy. As a result, specifying full preferences is one of the contributing factors for the limited real-world adoption of some commonly studied voting rules.;In this dissertation, we introduce a framework consisting of new concepts, algorithms, and theoretical results to provide a sound foundation on which we can address these problems by being able to make group decisions with only partial preference information.;In particular, we focus on single and multi-winner voting. We introduce minimax regret (MMR), a group decision-criterion for partial preferences, which quantifies the loss in social welfare of chosen alternative(s) compared to the unknown, but true winning alternative(s). We develop polynomial-time algorithms for the computation of MMR for a number of common of voting rules, and prove intractability results for other rules. We address preference elicitation, the second part of our 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 in a distribution-free context, in many practical environments decision makers have access to historical datasets of, and probabilistic knowledge of agent preferences. To leverage such information, we first address the problem of learning probabilistic models of preferences from pairwise comparisons---the building block of many preference structures---for which previous techniques cannot handle. Then we extend our framework to a multi-round elicitation process that leverages probabilistic models to guide and analyze elicitation strategies.;We empirically validate our framework and algorithms on real datasets. Experiments show our elicitation algorithms query only a fraction of full preferences to obtain alternative(s) with small MMR. Experiments also show our learning algorithms can learn accurate mixture models of preference types, which we then use to guide the design of one-round top-k elicitation protocols. |
