Social Choice for Partial Preferences Using Imputation

Social Choice Theory;Artificial Intelligence;Machine Learning;Computational Social Choice

Doucette, John Anthony Erskine

University of Waterloo

关键词: Social Choice Theory;    Artificial Intelligence;    Machine Learning;    Computational Social Choice;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/10564/3/Doucette_John.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

Within the field of multiagent systems, the area of computational social choice considersthe problems arising when decisions must be made collectively by a group of agents.Usually such systems collect a ranking of the alternatives from each member of the groupin turn, and aggregate these individual rankings to arrive at a collective decision. However,when there are many alternatives to consider, individual agents may be unwilling, orunable, to rank all of them, leading to decisions that must be made on the basis of incompleteinformation. While earlier approaches attempt to work with the provided rankingsby making assumptions about the nature of the missing information, this can lead to undesirableoutcomes when the assumptions do not hold, and is ill-suited to certain problemdomains. In this thesis, we propose a new approach that uses machine learning algorithms(both conventional and purpose-built) to generate plausible completions of each agent’srankings on the basis of the partial rankings the agent provided (imputations), in a waythat reflects the agents’ true preferences. We show that the combination of existing socialchoice functions with certain classes of imputation algorithms, which forms the core of ourproposed solution, is equivalent to a form of social choice. Our system then undergoesan extensive empirical validation under 40 different test conditions, involving more than50,000 group decision problems generated from real-world electoral data, and is foundto outperform existing competitors significantly, leading to better group decisions overall.Detailed empirical findings are also used to characterize the behaviour of the system,and illustrate the circumstances in which it is most advantageous. A general testbed forcomparing solutions using real-world and artificial data (Prefmine) is then described, inconjunction with results that justify its design decisions. We move on to propose a newmachine learning algorithm intended specifically to learn and impute the preferences ofagents, and validate its effectiveness. This Markov-Tree approach is demonstrated to besuperior to imputation using conventional machine learning, and has a simple interpretationthat characterizes the problems on which it will perform well. Later chapters containan axiomatic validation of both of our new approaches, as well as techniques for mitigatingtheir manipulability. The thesis concludes with a discussion of the applicability of itscontributions, both for multiagent systems and for settings involving human elections. Inall, we reveal an interesting connection between machine learning and computational socialchoice, and introduce a testbed which facilitates future research efforts on computationalsocial choice for partial preferences, by allowing empirical comparisons between competingapproaches to be conducted easily, accurately, and quickly. Perhaps most importantly, weoffer an important and effective new direction for enabling group decision making whenpreferences are not completely specified, using imputation methods.