Abstract
The "Stable Invitation Problem" (SIP) addresses the challenge of an organizer inviting a subset of individuals to an event such that the resulting guest list is stable. Stability is defined by two criteria: Individual Rationality (invited guests want to attend) and No Exclusion-Regret (uninvited individuals do not wish to be included). This paper maps the computational landscape of SIP, distinguishing between anonymous preferences (based on crowd size) and general preferences (based on specific attendees). We demonstrate that while simple cases are tractable, the introduction of rejection sets and strategic behavior quickly leads to NP-hardness and the impossibility of strategy-proof mechanisms.
Introduction
Organizing a successful event often involves more than just sending out mass invites. Organizers frequently aim to maximize attendance while ensuring that the guest list remains "stable." In this context, stability implies that no invited guest regrets attending and no excluded person feels slighted. However, guest preferences are rarely simple. They may depend on the total number of attendees (size preferences) or the presence of specific individuals (composition preferences).
This paper formalizes these dynamics through the Stable Invitation Problem (SIP). An invitation is considered stable if it satisfies:
- Individual Rationality (IR): Every invitee prefers attending given the current list over staying home.
- No Exclusion-Regret (ER): No non-invitee would prefer to be added to the current list.
Problem Variants: ASIP vs. GSIP
The authors distinguish between two primary models:
- Anonymous Stable Invitation Problem (ASIP): Guests' preferences depend solely on the number of attendees.
- General Stable Invitation Problem (GSIP): Guests have specific "acceptance" sets (people they want to see) and "rejection" sets (people they want to avoid).
The complexity of these problems is analyzed through $(\alpha, \beta)$-instances, where $\alpha$ is the maximum size of an individual's acceptance set and $\beta$ is the maximum size of their rejection set.
Computational Complexity
The core contribution of the paper is a comprehensive mapping of the computational boundaries for finding the maximum stable invitation. The researchers categorized different versions of the problem based on the constraints of the acceptance and rejection sets.
As shown in the table above, the problem remains in P (polynomial time) for very restricted cases. For instance, ASIP is generally tractable when guests are truthful. However, in GSIP, even small increases in the size of rejection sets ($\beta$) or acceptance sets ($\alpha$) trigger a transition to NP-hardness. Specifically, if guests can reject just two specific people ($\beta \geq 2$), finding a stable invitation becomes NP-hard. Similarly, the combination of simple preferences with even minimal acceptance/rejection constraints often leads to computational intractability.
Strategic Manipulation and Mechanism Design
Beyond computational limits, the paper explores the game-theoretic aspects of invitations. Can an organizer design a mechanism where guests have no incentive to lie about their preferences?
The findings are largely discouraging. The authors prove a "No-Go" theorem: for general preferences, no strategy-proof mechanism can guarantee a stable invitation. If an organizer tries to maximize the crowd, guests can often manipulate the outcome by misreporting their thresholds or "vetoing" others to ensure their own preferred social outcome.
A notable exception exists for "Increasing" (INC) preferences, where guests always prefer more attendees to fewer. In this "more the merrier" scenario, a strategy-proof mechanism exists that can find the maximum stable invitation in linear time.
Conclusion
The Stable Invitation Problem reveals a fundamental tension between an organizer's desire for a large crowd and the guests' specific social preferences. While anonymity simplifies the problem, real-world social dynamics—characterized by specific likes and dislikes—render the search for an optimal, stable, and honest guest list computationally and strategically difficult. Future research may look into randomized mechanisms or relaxing stability requirements to find practical solutions for these complex social coordination problems.
Summary updated