Local Dominance in Mixed-Strength Populations -- Fast Maximal Independent Set
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909941654093824 |
|---|---|
| author | Luby, Michael Irani, Sandy |
| author_facet | Luby, Michael Irani, Sandy |
| contents | In many natural and engineered systems, agents interact through local contests that determine which individuals become dominant within their neighborhoods. These interactions are shaped by inherent differences in strength, and they often lead to stable dominance patterns that emerge surprisingly quickly relative to the size of the population. This motivates the search for simple mathematical models that capture both heterogeneous agent strength and rapid convergence to stable local dominance.
A widely studied abstraction of local dominance is the Maximal Independent Set (MIS) problem. In the Luby MIS protocol that provably converges quickly to an MIS, each agent repeatedly generates a strength value chosen uniformly and becomes locally dominant if its value is smaller than those of its neighbors. This provides a theoretical explanation for fast dominance convergence in populations of equal-strength agents and naturally raises the question of whether fast convergence also holds in the more realistic setting where agents are inherently mixed-strength.
To investigate this question, we introduce the mixed-strength agents model, in which each agent draws its strength from its own distribution. We prove that the extension of the Luby MIS protocol where each agent repeatedly generates a strength value from its own distribution still exhibits fast dominance convergence, providing formal confirmation of the rapid convergence observed in many mixed-strength natural processes.
We also show that heterogeneity can significantly change the dynamics of the process. In contrast to the equal-strength setting, a constant fraction of edges need not be eliminated per round. We construct a population and strength profile in which progress per round is asymptotically smaller, illustrating how inherent strength asymmetry produces qualitatively different global behavior. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_03303 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Local Dominance in Mixed-Strength Populations -- Fast Maximal Independent Set Luby, Michael Irani, Sandy Multiagent Systems In many natural and engineered systems, agents interact through local contests that determine which individuals become dominant within their neighborhoods. These interactions are shaped by inherent differences in strength, and they often lead to stable dominance patterns that emerge surprisingly quickly relative to the size of the population. This motivates the search for simple mathematical models that capture both heterogeneous agent strength and rapid convergence to stable local dominance. A widely studied abstraction of local dominance is the Maximal Independent Set (MIS) problem. In the Luby MIS protocol that provably converges quickly to an MIS, each agent repeatedly generates a strength value chosen uniformly and becomes locally dominant if its value is smaller than those of its neighbors. This provides a theoretical explanation for fast dominance convergence in populations of equal-strength agents and naturally raises the question of whether fast convergence also holds in the more realistic setting where agents are inherently mixed-strength. To investigate this question, we introduce the mixed-strength agents model, in which each agent draws its strength from its own distribution. We prove that the extension of the Luby MIS protocol where each agent repeatedly generates a strength value from its own distribution still exhibits fast dominance convergence, providing formal confirmation of the rapid convergence observed in many mixed-strength natural processes. We also show that heterogeneity can significantly change the dynamics of the process. In contrast to the equal-strength setting, a constant fraction of edges need not be eliminated per round. We construct a population and strength profile in which progress per round is asymptotically smaller, illustrating how inherent strength asymmetry produces qualitatively different global behavior. |
| title | Local Dominance in Mixed-Strength Populations -- Fast Maximal Independent Set |
| topic | Multiagent Systems |
| url | https://arxiv.org/abs/2512.03303 |