Paper Info
Title
Network Formation for Asymmetric Players and Bilateral Contracting
Abstract
We study a network formation game where players wish to send traffic to other players. Players can be seen as nodes of an undirected graph whose edges are defined by contracts between the corresponding players. Each player can contract bilaterally with others to form bidirectional links or break unilaterally contracts to eliminate the corresponding links. Our model is an extension of the traffic routing model considered in Arcaute, E., Johari, R., Mannor, S., (IEEE Trans. Automat. Contr. 54(8), 1765---1778 2009) in which we do not require the traffic to be uniform and all-to-all. Player i specifies the amount of traffic tij ź 0 that wants to send to player j. Our notion of stability is the network pairwise Nash stability, when no node wishes to deviate unilaterally and no pair of nodes can obtain benefit from deviating bilaterally. We show a characterization of the topologies that are pairwise Nash stable for a given traffic matrix. We prove that the best response problem is NP-hard and devise a myopic dynamics so that the deviation of the active node can be computed in polynomial time. We show the convergence of the dynamics to pairwise Nash configurations, when the contracting functions are anti-symmetric and affine, and that the expected convergence time is polynomial in the number of nodes when the node activation process is uniform.
Year
DOI
Venue
2016
10.1007/s00224-015-9640-6
Theory Comput. Syst.
Keywords
Field
DocType
Network formation games,Bilateral contracting,Pairwise Nash equilibrium,Myopic dynamics
Affine transformation,Network formation,Convergence (routing),Discrete mathematics,Topology,Pairwise comparison,Mathematical economics,Polynomial,Best response,Network topology,Time complexity,Mathematics
Journal
Volume
Issue
ISSN
59
3
1432-4350
Citations 
PageRank 
References 
0
0.34
13
Authors
3
Name
Order
Citations
PageRank
Carme Àlvarez131628.75
Maria J. Serna247370.53
Aleix Fernàndez320.73