Complexity of the Stable Invitations Problem

We study the Stable Invitations Problem (SIP) in which an event organizer is to invite a subset of agents (from a group of agents) to an event, subject to certain rationality criteria. In SIP, the agents have friends, enemies, and preferences on the number of attendees at the event; an agent is willing to attend the event if all friends of the agent attend, no enemy of the agent attends, and the number of attendees is acceptable to the agent. We consider two solution concepts: (1) individual rationality (everyone who is invited is willing to attend) and (2) (Nash) stability (no agent wants to deviate from the given invitation). It is known that finding an invitation of given size for either concept is NP-complete. In this work, we study the complexity of SIP on a finer scale, through the lense of parameterized complexity. For the two solution concepts and the special cases where the number of friends and/or enemies is bounded above by a constant, we show that the problems belong to different complexity classes when parameterized by the size of solutions. For instance finding an individually rational invitation of size k is W[1]-complete, yet finding a stable invitation is W[2]-complete. Moreover, when all friend and enemy relations are symmetric, finding a solution of either of the concepts becomes fixed-parameter tractable unless agents have unbounded number(s) of enemies.

Authors

• Hooyeon Lee
• Vassilevska Williams

Keywords

No keywords are indexed for this paper.