Convergence to Strong Equilibrium in Network Design Games
Authors: Feldman Michal , Friedler Ophir 
Published: November 2015

In a network design game [1] each agent seeks to connect two nodes in a directed network at a minimal cost. The strategies employed by each agent include all the paths that connect that agent's two nodes (termed origin and destination). The paths may represent roads, internet cables, or even water pipelines. The cost of an edge is a function of the number of agents that use it.
An agent pays the total cost of the edges in its path, where an edge cost is a function of the number of agents using the edge. In this work we focus on nonincreasing edge costs, where agents impose positive externalities on one another. Such settings emerge in cases where agents collectively construct a network and share the cost of the network links.
Each network design game possesses a pure Nash equilibrium (PNE): an outcome that is sustainable against unilateral deviations. However, a PNE is not necessarily stable against coalitional deviations; Therefore, this is an inadequate solution concept in settings where agents are capable of coordinating their actions. The most well studied solution concept that is stable against coalitional deviations is termed strong equilibrium (SE) [2]. An SE is an outcome where no beneficial coalitional deviation (BCD) exists (i.e., a deviation in which each member of the coalition strictly decreases its cost).
Epstein et al. [3] studied the existence and efficiency of SEs in non-increasing network design games. They showed that in a single-origin, any-destination (SOAD) setting (i.e., where all agents have the same origin but may have arbitrary destinations) with a seriesparallel (SP) network [3, 4], an SE is guaranteed to exist. Holzman and Monderer [4] showed that this result is tight, i.e., for any network that is not SP, there exists a non-increasing SOAD network design game that does not admit an SE.
A natural question arises: Given an arbitrary outcome of an SOAD network design game with an SP network, can strategic agents converge to an SE via BCDs? and if yes, how fast?
Our contribution. We start by showing that there exist BCD sequences that do not converge to an SE. We then define a class of BCDs, termed dominance based BCDs. This class is based on the notion of domination between agents. In an SOAD setting, we say that agent i is dominated by agent j if there is a path from the destination of i to the destination of j. Thus, domination is a partial order between the agents.
Dominance based BCDs proceed in the following manner: Take any (full) order of the agents consistent with the partial order. Every agent i, in its turn, computes the optimal profile for itself together with all the successive agents that can intersect its path (thus reducing its cost). We show that if such a coalitional deviation reduces it's cost, then every agent in the coalition benefits from the deviation as well. Therefore, this is a BCD. We show that any sequence of dominance based BCDs converges to an SE within n iterations at the most (where n is the number of agents). Moreover, we present an algorithm that efficiently computes dominance based BCDs.