Computing a small agreeable set of indivisible items

Journal article

We study the problem of assigning a small subset of indivisible items to a group of agents so that the subset is agreeable to all agents, meaning that all agents value the subset as least as much as its complement. For an arbitrary number of agents and items, we derive a tight worst-case bound on the number of items that may need to be included in such a set. We then present polynomial-time algorithms that find an agreeable set whose size matches the worst-case bound when there are two or three agents. We also show that finding small agreeable sets is possible even when we only have access to the agents' preferences on single items. Furthermore, we investigate the problem of efficiently computing an agreeable set whose size approximates the size of the smallest agreeable set for any given instance. We consider two well-known models for representing the preferences of the agents—the value oracle model and additive utilities—and establish tight bounds on the approximation ratio that can be obtained by algorithms running in polynomial time in each of these models.

Authors: Manurangsi, P; Suksompong, W

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Artificial Intelligence
• Volume: 268
• Pages: 96-114
• Publication date: 2018-12-18
• Acceptance date: 2018-10-13
• DOI: 10.1016/j.artint.2018.10.001
• EISSN: 1872-7921
• ISSN: 0004-3702
• Keywords: social choice; resource allocation; indivisible items; agreeability