CS-ECON Seminar Series

Elicitation for Preferences Single Peaked on Trees

Speaker:Neeldhara Misra
Date: Friday, August 26, 2016
Time: 1:30pm - 2:30pm
Location: Gross 318, Duke


This talk will focus on the problem of preference elicitation, where the goal is to understand the preferences of agents (which we model by total orders) by querying them about their pairwise preferences. We will survey known results, which have studied the problem both on general domains and structured ones, such as the domain of single-peaked preferences. As one might expect, structured domains admit a lower query complexity. We will consider domains that are single peaked over trees, which generalize the notion of single-peakedness. We will see that the query complexity is influenced by the number of leaves, the path cover number, and the distance from path of the underlying single peaked tree, whereas the other natural parameters like maximum degree, diameter, pathwidth do not play any direct role in determining query complexity. We will also consider the query complexity for finding a weak Condorcet winner for this domain

Hosted by:
Vince Conitzer