Price of Anarchy in Undirected Networks with Variable Sources and Sinks

Many systems obey principles of least action, such as electricity taking paths of least resistance through a network and even drivers taking paths of shortest travel time. The dependence of such flows on the underlying network topology often results in a substantial waste of network resources and even sub-optimality caused by the topology itself. The Price of Anarchy (PoA) provides a measure of sub-optimality, being defined as the ratio of the cost of the worst case Nash equilibrium to that of the system’s global optimum. This work investigates least action flows in undirected complex networks whose variable numbers of nodes represent sources and sinks of the flow, augmented by passive sites. This is motivated by the problem of optimising efficiency in smart and renewable power grid applications, which typically have many small generators and consumers coming on and off grid throughout the day. By recognising the correspondence between least action flows and Nash equilibria, the PoA can be used to quantify sub-optimality and network redundancy even in cases where the system’s optimum may be physically unattainable, as is the case for electrical networks. While previous studies of the PoA in network flows have used either single source-sink node pairs or multiple source-sink pairs, with each pair routing a distinct commodity [1][2], we introduce a more flexible model in which flow from any source can be routed to any number of sinks allowing investigation of networks spanning a greater range of functionality. The value and location of the maximum of the PoA depends on the relative proportions of the types of node comprising the network and exhibits symmetries in the network’s configuration space as shown in Figure 1. These symmetries persist across a wide variety of topologies and scale linearly with increasing network size. The implications for renewable energy grids will be discussed.

Oliver Smith, Keith Hopcraft, Reuben O'Dea and John Crowe
Tuesday, September 25, 2018 - 17:15 to 17:30


The official Hotel of the Conference is
Makedonia Palace.

Conference Organiser: NBEvents

The official travel agency of the Conference is: Air Maritime

Photo of Thessaloniki seafront courtesy of Juli Bellou
fb flickr flickr