论文标题
对网络创建游戏的平衡结构的新见解
New Insights into the Structure of Equilibria for the Network Creation Game
论文作者
论文摘要
我们研究Fabrikant等人推出的总和网络创建游戏。其中$ n $播放器以个人价格$α$符合网络购买链接。在研究此模型时，我们对\ emph {nash equilibria}（\ ne）和\ emph {无政府状态}（\ poa）都感兴趣。据推测，对于任何$α$，\ poa都是恒定的。到目前为止，已证明它的范围为$α= o（n^{1-Δ_1}）$的恒定\ poa，$δ_1> 0 $ a正常常数，并且已证明$α> n（1+δ_2）$的范围\ poa \ poa \ poa，n（1+Δ_2）$，$δ_2> 0 $ 0 $ a正常$ a a正常数。 我们的贡献包括证明\ ne图满足了文献中证明的某些特性的非常限制性的拓扑特性，并提供了新的见解，这些见解可能有助于解决\ poa在其余$α$的范围内是恒定的： （i）我们证明\ emph {every}节点在\ emph {same}狭窄距离范围内具有\ ne图的其他大部分节点。 （ii）如果没有考虑平均度，我们专注于为任何玩家购买的非桥梁链接的数量，我们可以证明存在常数$ d $，因此，对于任何大于$ r $的diameter of diameter the ne forth $ r $，$ r $的平均度是由$ \ max（r，\ frac {2n}α+6）$的上限。
We study the sum classic network creation game introduced by Fabrikant et al. in which $n$ players conform a network buying links at individual price $α$. When studying this model we are mostly interested in \emph{Nash equilibria} (\NE) and the \emph{Price of Anarchy} (\PoA). It is conjectured that the \PoA is constant for any $α$. Up until now, it has been proved constant \PoA for the range $α= O(n^{1-δ_1})$ with $δ_1>0$ a positive constant and it has been proved constant \PoA for the range $α>n(1+δ_2)$ with $δ_2>0$ a positive constant. Our contribution consists in proving that \NE graphs satisfy very restrictive topological properties generalising some properties proved in the literature and providing new insights that might help settling the conjecture that the \PoA is constant for the remaining range of $α$: (i) We show that \emph{every} node has the majority of the other nodes of the \NE graph at the \emph{same} narrow range of distances. (ii) If instead of considering the average degree, we focus on the number of non-bridge links bought for any player, we can prove that there exists a constant $D$ such that the average degree is upper bounded by $\max(R, \frac{2n}α+6)$ for any \NE graph of diameter larger than $D$, where $R$ is a positive constant.
