TL;DR
This paper introduces "loyalty" as a new concept in hedonic games, where agents' utilities are influenced by the utilities of agents they are loyal to. This leads to a sequence of "loyal variants" of the game, culminating in a locally egalitarian outcome, and offers new insights into coalition formation with empathetic agents.
What Problem Does This Paper Address?
Traditional economic models often assume agents are purely self-interested, aiming solely to maximize their own utility (the "homo economicus"). This can lead to suboptimal outcomes in group settings, as seen in classic examples like the Prisoner's Dilemma. While some research explores agents considering others' well-being (altruism or social welfare), this paper tackles a more nuanced form of interdependence: loyalty. Specifically, it investigates how agents' preferences and coalition structures change when they consider the utilities of specific other agents they feel "loyal" towards, particularly within the context of coalition formation games. The authors aim to understand the stability and efficiency of coalitions formed under these "loyal" preferences.
Methods
The core contribution is the introduction of loyalty as a binary relation derived from an agent's utility for a two-person coalition. If agent i gains positive utility from a coalition with agent j (i.e., u_i({i, j}) > 0), then i is considered loyal to j. This loyalty is then incorporated into utility calculations. The authors define a loyal variant of a hedonic game where an agent's utility for a coalition is the minimum of their own utility and the utilities of the agents they are loyal to within that coalition. This process is iterated to create k-fold loyal variants, leading to a locally egalitarian variant where an agent's utility is the minimum among all agents in their coalition that are reachable through the loyalty graph. The paper then analyzes standard game theory concepts like the core (group stability) and Pareto optimality (efficiency) within these loyal variants, deriving theoretical results and computational complexity bounds.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Loyalty as a Mechanism for Empathy: Loyalty provides a formal way to model how agents' decisions are influenced by the well-being of specific others they value, moving beyond pure self-interest or universal altruism.
- Iterative Loyalty Leads to Egalitarianism: Repeatedly applying the loyalty concept naturally pushes the game towards outcomes where the worst-off agent in a coalition is better off, culminating in a locally egalitarian state. This suggests a mechanism for achieving fairer outcomes through social relationships.
- Complexity Trade-offs: While loyalty can lead to desirable egalitarian outcomes, it can also introduce computational hardness for problems like finding "best coalitions" or determining core stability, especially in certain types of games (like Friend-Oriented Hedonic Games).
- Mutual vs. Symmetric Loyalty: The paper distinguishes between mutual loyalty (if i is loyal to j, then j is loyal to i) and symmetric loyalty (if i is loyal to j, then j is loyal to i). Mutual loyalty is sufficient for many of their results, simplifying the analysis.
- The Limit Game is Special: The "locally egalitarian variant" (the limit of the iterative loyalty process) has strong egalitarian properties and often guarantees Pareto optimal coalition structures in the core, making it a desirable outcome.
Key Results
- The iterative loyalty process terminates in at most n steps (where n is the number of agents) in a locally egalitarian variant.
- The locally egalitarian variant of a loyalty-connected, mutual cardinal hedonic game always contains a Pareto optimal coalition structure in the core.
- Finding the "best coalition" for an agent is NP-complete for k-fold loyal variants of symmetric Friend-Oriented Hedonic Games (FOHGs).
- Computing a coalition structure in the core is NP-hard for k-fold loyal variants of symmetric FOHGs and symmetric ASHGs (Additively Separable Hedonic Games).
- However, for Modified Fractional Hedonic Games (MFHGs), computing best coalitions and core structures remains tractable (polynomial time) even with loyalty.
- For symmetric FOHGs with a tree-shaped loyalty graph, coalition structures in the core can be computed in polynomial time.
Limitations and Future Work
- Core Existence for FOHGs: The paper leaves open the question of whether the core is always non-empty for loyal variants of FOHGs, particularly for the 1-fold loyal variant.
- Computational Hardness: The NP-hardness results for FOHGs and ASHGs suggest that finding stable and efficient coalitions under loyalty can be computationally challenging.
- Ordinal Preferences: The current model focuses on cardinal utilities. Extending the loyalty concept to purely ordinal preferences would be a valuable next step.
- Alternative Aggregation: The paper uses a minimum-based aggregation for loyal utilities. Exploring other aggregation mechanisms (e.g., weighted sums, averages) for loyal utilities could lead to new insights.
- Dynamics of Blocking: The paper mentions that dynamics related to blocking coalitions can cycle, suggesting further research into the dynamic aspects of coalition formation with loyalty.
Summary updated