TL;DR
This paper introduces a new model for strategic resource selection where agents are "homophilic," meaning they prefer to share resources with others of their own type. They analyze equilibria under different assumptions about agent knowledge and propose an efficient algorithm for finding "impact-blind" equilibria, which are robust approximations of more informed equilibria.
What Problem Does This Paper Address?
The classic problem of resource selection games, like choosing a server or a facility, often assumes agents are anonymous and only care about the total number of users on a resource. However, in many real-world scenarios, like residential segregation or choosing schools, people have preferences for interacting with similar individuals. This paper addresses this gap by introducing "homophilic agents" who aim to share resources with a certain fraction of their own type. They explore the implications of this homophily on equilibrium behavior and social welfare, particularly when agents have limited information about the exact number of users on a resource.
Methods
The authors extend classic Resource Selection Games by incorporating agent types (red and blue) and a "tolerance threshold" ($\tau$) that defines the minimum fraction of same-type agents an agent desires on a resource. They introduce two types of equilibria:
- Impact-aware equilibrium (IAE): Agents make moves that improve their utility, fully considering the consequences of their actions on others.
- Impact-blind equilibrium (IBE): Agents make moves that improve their utility based on limited information, only knowing the fraction of same-type agents on a resource before their move, not the exact numbers after. This models a form of bounded rationality.
They analyze the existence and properties of these equilibria, including the finite improvement property (FIP) and the price of anarchy (PoA) and stability (PoS). A key technical contribution is an efficient greedy algorithm for computing IBEs.
Datasets
Not discussed in the paper. The paper focuses on theoretical modeling and algorithmic analysis rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Homophily matters: Introducing preferences for same-type agents fundamentally changes resource selection dynamics, leading to potentially different equilibrium outcomes and social welfare compared to anonymous models.
- Bounded rationality as a feature, not a bug: The concept of "impact-blind" agents, who don't know the exact impact of their moves, is a realistic model for many scenarios. Surprisingly, IBEs exhibit favorable properties and can closely approximate IAEs, suggesting that limited information doesn't necessarily lead to drastically worse outcomes.
- Efficient equilibria computation: The paper provides an efficient greedy algorithm for finding impact-blind equilibria, which is a significant practical contribution for scenarios where agents might not have perfect information.
- Trade-offs between segregation and welfare: The social optimum in this model often leads to highly segregated resource usage, which might be undesirable in applications like schools, highlighting the need to consider diversity as a welfare measure.
Key Results
- Existence of Equilibria: Both IAEs (for $\tau < \frac{1}{2}$) and IBEs (for all $\tau$) are shown to exist.
- Algorithmic Efficiency: An efficient greedy algorithm is presented to compute IBEs in $O((m+k) \log k)$ time, where $m$ is the number of edges and $k$ is the number of resources.
- Approximation Guarantees: A 2-approximate IAE can be computed using an IBE as a proxy, demonstrating that IBEs are good approximations of IAEs.
- Price of Anarchy (PoA): The PoA for both IAE and IBE is bounded by $\frac{4}{3}$ for $\tau < 2 - \sqrt{2}$ and $2\tau$ for $\tau \ge 2 - \sqrt{2}$.
- Price of Stability (PoS): The IBE-PoS is 1 for $\tau=1$ and can be greater than 1 for $\tau < \frac{1}{2}$, with specific instances showing it can be larger than 1.
- Complexity: Maximizing social welfare is NP-hard in general, but efficient computation is possible for restricted instances (e.g., low-degree resource nodes).
Limitations and Future Work
- Limited Agent Types: The current model considers only two types of agents (red and blue). Extending this to multiple agent types would be a natural next step.
- Specific Threshold Function: The homophily is modeled using a fixed threshold $\tau$. Exploring other functional forms of homophilic preferences could offer richer insights.
- Real-World Data: The authors suggest investigating real-world examples, particularly school choice, to test the model's applicability and to potentially inform desegregation strategies. They also note that while social welfare is maximized in the social optimum, diversity might be a more appropriate welfare measure in certain contexts like schools.
- Impact-Aware Equilibria: While IBEs are well-studied, the analysis of IAEs is more limited, especially for $\tau \ge \frac{1}{2}$. Further exploration of IAEs and their properties would be valuable.
Summary updated