Optimal Multi-Attribute Decision Making in Social Choice Problems

1 Introduction

Several social choice problems involve making decisions over alternatives that are characterized by multiple attributes. For example, students may want to exchange research papers and time slots for presentation in a seminar class, in cloud computing, agents may want to allocate multiple types of computational resources, or agents may vote on multiple referenda addressing different issues. The problem of finding the best allocation, or the best decision on all issues can become challenging due to: (i) the number of alternatives grows exponentially with the number of attributes, and (ii) agents' preferences over the alternatives may have a complex combinatorial structure. My thesis addresses the following challenges that arise in multi-attribute decision making problems:

Preference Representation. I consider representations that balance the cognitive load of forming preferences over all alternatives, and practical considerations of elicitation.

Computation. Computing optimal decisions becomes challenging in combinatorial domains. I provide efficient algorithms for several problems, or complexity results otherwise. Strategic Behavior. Strategic manipulation is a serious concern in several settings. Wherever possible, I address this by providing strategyproof mechanisms.

Modeling and Learning Preferences. I develop models and methods to learn users' preferences from real world data of their implicit preferences and opinions, which often do not capture full preferences in a structured form.

2 My Contributions

I approach multi-attribute decision making from two directions, as summarized in Figure 1. Several positive results in decision making disappear when alternatives are characterized by multiple attributes. The main theme of my work is the identification of reasonable restrictions on the problem domain under which the positive results may be recovered. My thesis delivers the following positive message: We can design efficient mechanisms with desirable properties for multi-attribute decision making under natural assumptions on agents' preferences.

2.1 Direction 1: DecisionMaking under Preferences

Multi-type Resource Allocation. Here the attributes correspond to different types of items. In [Sikdar et al., 2017a], we provide the first positive results for multi-type housing markets [Moulin, 1995], when agents' preferences are lexicographic with possibly different importance orders over the types. Here, a collection of agents each endowed with a set of indivisible items of different types, have preferences over bundles consisting of subsets of all items. The goal is to find a redistribution of items that best satisfies agents' preferences without exchanging money. The notion of the core [Shapley and Scarf, 1974] of the market, the set of allocations where no group of agents has incentive to deviate by exchanging their initial endowments within the group, is the most widely accepted and studied notion of what the best such redistribution may be, as it is intuitively stable, and implies individual rationality and Pareto optimality.

When each agent owns a single item, and has strict preferences over items, a core allocation always exists, and can be computed in polynomial time by Gale's celebrated TopTrading-Cycles (TTC) algorithm [Shapley and Scarf, 1974], which is also strategyproof. Despite the vast literature on housing markets, multi-type housing markets have received very little attention because the core may be empty [Konishi et al., 2001]. Indeed, as S¨onmez and ¨Unver [2011] noted: "Positive results of this section [on housing markets] no longer hold in an economy in which one agent can consume multiple houses or multiple types of houses."

We address this problem and make the following contributions: (i) An extension of the TTC mechanism to multi-type housing markets which is strict core selecting, non-bossy, strong group strategyproof when agents cannot lie about importance orders, and runs in polynomial time. (ii) We show that no mechanism can satisfy both strict core selection and strategyproofness, when agents are allowed to lie about importance orders. (iii) Computational complexity results for checking if a given allocation is in the strict core.

Multi-issue voting. CP-nets [Boutilier et al., 2004] are a popular and natural preference representation language to compactly represent agents' preferences over multiple issues. Previous positive results assume acyclic CP-nets, or a common structure (see [Lang and Xia, 2016]) , leaving the following open questions: How to aggregate CP-nets without assuming a common structure? How to define the optimal outcome for cyclic CP-nets?

In [Sikdar et al., 2017b], I propose a new class of voting rules that allow the aggregation of CP-net preferences, allowing for the aggregation of possibly cyclic CP-nets with any dependency structure. I propose a quantitative, loss minimization framework, where the loss of an alternative is a function of the other alternatives that are preferred over it. The main contributions are: (i) Computational complexity results, and identifying cases when computing an optimal outcome is computationally tractable. (ii) A new class of voting rules for aggregating CP-nets that satisfy desirable properties.

2.2 Direction 2: Learning Preferences fromData

I model preferences using representation schema inspired by work on lexicographic heuristic decision making involving multiple factors from psychology literature as well as machine learning techniques. My contributions are: (i) Novel natural language and semantic features relevant to human decision making. (ii) Learning why users give some responses with higher frequency in a question answering setting using "fast and frugal heuristic (FFH)" based decision models borrowed from psychology literature that require very little training data. (iii) In [Horne et al., 2017], we model factors that drive discussions and voting behavior on reddit by learning to rank comments on noisy data, and analyze the learned models to understand factors affecting users' behavior.

3 FutureWork

I plan to converge on a unified approach by developing the theory on mechanism design for preference representations that accurately model agents' preferences in practice.

Direction 1. For housing markets, I plan to consider more general problem settings, more expressive preference representations, and develop mechanisms that satisfy desirable properties in these settings.

In multi-type resource allocation [Mackin and Xia, 2016], often, different organizations are responsible for the allocation of different types of items. I am interested in the following research questions: What properties can we expect from the resulting allocations? What properties must local mechanisms satisfy to obtain desirable allocations of all types?

Direction 2. I plan to build problem specific models for a better understanding of online communities discussing topics ranging from news and politics to question answering.