  We study the Nash equilibrium and the price of anarchy in the max-distance
network creation game. Network creation game, first introduced and studied by
Fabrikant et al., is a classic model for real-world networks from a
game-theoretic point of view. In a network creation game with n selfish vertex
agents, each vertex can build undirected edges incident to a subset of the
other vertices. The goal of every agent is to minimize its creation cost plus
its usage cost, where the creation cost is the unit edge cost $\alpha$ times
the number of edges it builds, and the usage cost is the sum of distances to
all other agents in the resulting network. The max-distance network creation
game, introduced and studied by Demaine et al., is a key variant of the
original game, where the usage cost takes into account the maximum distance
instead. The main result of this paper shows that for $\alpha > 19$ all
equilibrium graphs in the max-distance network creation game must be trees,
while the best bound in previous work is $\alpha > 129$. We also improve the
constant upper bound on the price of anarchy to 3 for tree equilibria. Our work
brings new insights into the structure of Nash equilibria and takes one step
forward in settling the so-called tree conjecture in the max-distance network
creation game.
