The uniqueness property for networks with several origin-destination\n pairs

We consider congestion games on networks with nonatomic users and\nuser-specific costs. We are interested in the uniqueness property defined by\nMilchtaich [Milchtaich, I. 2005. Topological conditions for uniqueness of\nequilibrium in networks. Math. Oper. Res. 30 225-244] as the uniqueness of\nequilibrium flows for all assignments of strictly increasing cost functions. He\nsettled the case with two-terminal networks. As a corollary of his result, it\nis possible to prove that some other networks have the uniqueness property as\nwell by adding common fictitious origin and destination.\n In the present work, we find a necessary condition for networks with several\norigin-destination pairs to have the uniqueness property in terms of excluded\nminors or subgraphs. As a key result, we characterize completely bidirectional\nrings for which the uniqueness property holds: it holds precisely for nine\nnetworks and those obtained from them by elementary operations. For other\nbidirectional rings, we exhibit affine cost functions yielding to two distinct\nequilibrium flows. Related results are also proven. For instance, we\ncharacterize networks having the uniqueness property for any choice of\norigin-destination pairs.\n