Elicitation for Preferences Single Peaked on Trees
In multiagent systems, we often have a set of agents each of which have a preference ordering over a set of items and one would like to know these preference orderings for various tasks, for example, data analysis, preference aggregation, voting etc. However, we often have a large number of items which makes it impractical to ask the agents for their complete preference ordering. In such scenarios, we usually elicit these agents' preferences by asking (a hopefully small number of) comparison queries --- asking an agent to compare two items. Prior works on preference elicitation focus on unrestricted domain and the domain of single peaked preferences and show that the preferences in single peaked domain can be elicited by much less number of queries compared to unrestricted domain. We extend this line of research and study preference elicitation for single peaked preferences on trees which is a strict superset of the domain of single peaked preferences. We show that the query complexity crucially depends on 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 then investigate the query complexity for finding a weak Condorcet winner for preferences single peaked on a tree and show that this task has much less query complexity than preference elicitation. Here again we observe that the number of leaves in the underlying single peaked tree and the path cover number of the tree influence the query complexity of the problem.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Preference Elicitation For Single Crossing Domain
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 elicitatio…
Strategy-proofness with single-peaked and single-dipped preferences
We analyze the problem of locating a public facility in a domain of single-peaked and single-dipped preferences when the social planner knows the type of preference (single-peaked or single-dipped) of each agent. Our mai…
Agenda manipulation-proofness, stalemates, and redundant elicitation in preference aggregation. Exposing the bright side of Arrow's theorem
This paper provides a general framework to explore the possibility of agenda manipulation-proof and proper consensus-based preference aggregation rules, so powerfully called in doubt by a disputable if widely shared unde…
Recognizing and Eliciting Weakly Single Crossing Profiles on Trees
We introduce and study the weakly single-crossing domain on trees which is a generalization of the well-studied single-crossing domain in social choice theory. We design a polynomial-time algorithm for recognizing prefer…
Open-Ended Question AnsweringCompatibility between Stability and Strategy-Proofness: A Single-Peaked Preferences Investigation
In two-sided matching markets, ensuring both stability and strategy-proofness poses a significant challenge; it is impossible when agents' preferences are unrestricted. But what if agents' preferences have specific restr…