咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >Computing and testing Pareto o... 收藏

Computing and testing Pareto optimal committees

作     者:Aziz, Haris Monnot, Jerome 

作者机构:UNSW Sydney Sydney NSW 2052 Australia Data61 CSIRO Sydney NSW 2052 Australia Univ Paris 09 LAMSADE Paris France 

出 版 物:《AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS》 (独立代理和多头代理系统)

年 卷 期:2020年第34卷第1期

页      面:1-20页

核心收录:

学科分类:08[工学] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术(可授工学、理学学位)] 

基  金:UNSW Scientia Fellowship 

主  题:Committee selection Multiwinner voting Pareto optimality Algorithms and complexity Set extensions 

摘      要:Selecting a set of alternatives based on the preferences of agents is an important problem in committee selection and beyond. Among the various criteria put forth for desirability of a committee, Pareto optimality is a minimal and important requirement. As asking agents to specify their preferences over exponentially many subsets of alternatives is practically infeasible, we assume that each agent specifies a weak order on single alternatives, from which a preference relation over subsets is derived using some preference extension. We consider five prominent extensions (responsive, downward lexicographic, upward lexicographic, best, and worst). For each of them, we consider the corresponding Pareto optimality notion, and we study the complexity of computing and verifying Pareto optimal outcomes. For each of the preference extensions, we give a complete characterization of the complexity of testing Pareto optimality when preferences are dichotomous or linear. We also consider strategic issues: for four of the set extensions, we present a linear-time, Pareto optimal and strategyproof algorithm that even works for weak preferences.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分