Preference elicitation for single crossing domain

Show simple item record Dey, Palash Misra, Neeldhara 2016-06-09T09:26:24Z 2016-06-09T09:26:24Z 2016-04
dc.identifier.citation Dey, Palash and Misra, Neeldhara, "Preference elicitation for single crossing domain”, arXiv, Cornell University Library, DOI: arXiv:1604.05194, Apr. 2016. en_US
dc.identifier.other arXiv:1604.05194
dc.description.abstract Eliciting the preferences of a set of agents over a set of alternatives is a problem of fundamental importance in social choice theory. Prior work on this problem has studied the query complexity of preference elicitation for the unrestricted domain and for the domain of single peaked preferences. In this paper, we consider the domain of single crossing preference profiles and study the query complexity of preference elicitation under various settings. We consider two distinct situations: when an ordering of the voters with respect to which the profile is single crossing is known versus when it is unknown. We also consider different access models: when the votes can be accessed at random, as opposed to when they are coming in a pre-defined sequence. In the sequential access model, we distinguish two cases when the ordering is known: the first is that sequence in which the votes appear is also a single-crossing order, versus when it is not. The main contribution of our work is to provide polynomial time algorithms with low query complexity for preference elicitation in all the above six cases. Further, we show that the query complexities of our algorithms are optimal up to constant factors for all but one of the above six cases. We then present preference elicitation algorithms for profiles which are close to being single crossing under various notions of closeness, for example, single crossing width, minimum number of candidates | voters whose deletion makes a profile single crossing. en_US
dc.description.statementofresponsibility by Palash Dey and Neeldhara Misra
dc.language.iso en_US en_US
dc.publisher Cornell University Library en_US
dc.title Preference elicitation for single crossing domain en_US
dc.type Preprint en_US

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


My Account