Computing and Testing Pareto Optimal Committees
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 the 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. 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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A fixed point approach for computing actuarially fair Pareto optimal risk-sharing rules
Risk-sharing is one way to pool risks without the need for a third party. To ensure the attractiveness of such a system, the rule should be accepted and understood by all participants. A desirable risk-sharing rule shoul…
FairnessOptimal Decision Mechanisms for Committees: Acquitting the Guilty
A group of privately informed agents chooses between two alternatives. How should the decision rule be designed if agents are known to be biased in favor of one of the options? We address this question by considering the…
Multi-Agent LLM Committees for Autonomous Software Beta Testing
Manual software beta testing is costly and time-consuming, while single-agent large language model (LLM) approaches suffer from hallucinations and inconsistent behavior. We propose a multi-agent committee framework in wh…
Towards Efficient Pareto-optimal Utility-Fairness between Groups in Repeated Rankings
In this paper, we tackle the problem of computing a sequence of rankings with the guarantee of the Pareto-optimal balance between (1) maximizing the utility of the consumers and (2) minimizing unfairness between producer…
FairnessEfficiently Controlling Multiple Risks with Pareto Testing
Machine learning applications frequently come with multiple diverse objectives and constraints that can change over time. Accordingly, trained models can be tuned with sets of hyper-parameters that affect their predictiv…