How do rational agents self-organize when trying to connect to a common target? We study this question with a simple tree formation game which is related to the well-known fair single-source connection game by Anshelevich et al. (FOCS'04) and selfish spanning tree games by Gourv\`es and Monnot (WINE'08). In our game agents correspond to nodes in a network that activate a single outgoing edge to connect to the common target node (possibly via other nodes). Agents pay for their path to the common target, and edge costs are shared fairly among all agents using an edge. The main novelty of our model is dynamic edge costs that depend on the in-degree of the respective endpoint. This reflects that connecting to popular nodes that have increased internal coordination costs is more expensive since they can charge higher prices for their routing service. In contrast to related models, we show that equilibria are not guaranteed to exist, but we prove the existence for infinitely many numbers of agents. Moreover, we analyze the structure of equilibrium trees and employ these insights to prove a constant upper bound on the Price of Anarchy as well as non-trivial lower bounds on both the Price of Anarchy and the Price of Stability. We also show that in comparison with the social optimum tree the overall cost of an equilibrium tree is more fairly shared among the agents. Thus, we prove that self-organization of rational agents yields on average only slightly higher cost per agent compared to the centralized optimum, and at the same time, it induces a more fair cost distribution. Moreover, equilibrium trees achieve a beneficial trade-off between a low height and low maximum degree, and hence these trees might be of independent interest from a combinatorics point-of-view. We conclude with a discussion of promising extensions of our model.

翻译：理性代理商在试图连接到一个共同的目标时如何自我组织? 我们研究这个问题时, 使用一个简单的树组游戏, 与Anshelevich等人( FOCS'04) 和Gourv ⁇ es和Monnot( WINE'08) 的众所周知的公平单一来源连接游戏( FOCS'04) 和自私的跨树游戏( Gourv ⁇ es and Monnot)( WINE'08) 相关。 在我们的游戏代理商与一个网络的节点相对应, 该网络激活一个单一的向外边缘连接, 以连接到共同的目标节点( 可能通过其他节点) 。 代理商为其通往共同目标的路径支付费用, 边际成本由所有代理人公平分享。 此外, 我们分析平衡树的结构, 并运用这些洞察力 来证明一个固定的上层的比值取决于相关终点点的水平。 这反映了通俗性价格的上比值, 也表明, 稳定度的比值的比值的比价值的比值的比值, 的比值的比值的比值也比值的比值的比值的比值越高。