Computing an Approximately Optimal Agreeable Set of Items

Computing an Approximately Optimal Agreeable Set of Items

Pasin Manurangsi, Warut Suksompong

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 338-344. https://doi.org/10.24963/ijcai.2017/48

We study the problem of finding a small subset of items that is agreeable to all agents, meaning that all agents value the subset at least as much as its complement. Previous work has shown worst-case bounds, over all instances with a given number of agents and items, on the number of items that may need to be included in such a subset. Our goal in this paper is to efficiently compute an agreeable subset whose size approximates the size of the smallest agreeable subset for a given instance. We consider three well-known models for representing the preferences of the agents: ordinal preferences on single items, the value oracle model, and additive utilities. In each of these models, we establish virtually tight bounds on the approximation ratio that can be obtained by algorithms running in polynomial time.
Keywords:
Agent-based and Multi-agent Systems: Economic paradigms, auctions and market-based systems
Agent-based and Multi-agent Systems: Social Choice Theory