Discipline: Physics
Subcategory: Physics (not Nanoscience)
Ricky Dixon - University of Alabama
Co-Author(s): Neal Solmeyer, Army Research Laboratory, Adelphi, MD; Radhakrishnan Balu, Army Research Laboratory, Adelphi, MD
It is becoming increasingly important to consider congestion of information in communication networks. In ad-hoc mobile networks, that may change dynamically with nodes that act independently of one another, it can be particularly difficult to efficiently route information. Routing games are formulated as a collection of source-sink pairs in a directed graph. Flow on the graph represents traffic or information flow over a communication network. We model a non-atomic game where the information is divided in continuous units, with a total flow from the source to the sink normalized to 1. The players can be interpreted as each infinitesimal unit of information at each node being routed through the network. Since each player acts independently it is natural to analyze this game in a game theoretical context. Each edge in the graph has a latency which is a function of the flow on that edge. This serves as the cost function of the game. The selfish routing case is where the players try to minimize their own latency. This leads to the Wardrop equilibrium, which is analogous to the Nash equilibrium in standard game theory. Our study focused on the Braess’ paradox which arises from the intuition that a new, zero cost, link in a network will only improve the efficiency of the network. It is formulated on a four-node network with source s and sink t. the paths s u and vt have a latency equal to the amount of flow on the edge, while the paths s v and u t have a constant latency equal to 1. Without the path through u and v, the equilibrium flow of the network is with the flow equally shared on the two possible paths, s u t and s v t with a total cost of 3/2. This is also the optimal flow giving the network a price of anarchy equal to 1. By adding the zero-cost edge between u and v the equilibrium flow has a higher total cost of 2 as each player attempts to take advantage of the lowest cost path s u v t. The optimal flow is the same as without the central node and therefore the price of anarchy here is 4/3. To quantize the game in the EWL quantization scheme, one qubit is assigned to each node where a player must choose which direction to route information. The initial state of the players’ qubits is |000>. An N qubit entangling operation is performed between the three nodes. The amount of entanglement is parametrized by = π/4 and zero at = 0. Next the players at each node apply an arbitrary unitary rotation to their qubits which serves as their strategy choice. Lastly, an un-entangling operation is performed on the qubits and the resulting state is measured. For each qubit, the two possible measurement outcomes are associated with the two outgoing paths from the node, and the expectation value of the measured qubit determines the amount of information it routes along each path as a fraction of the information that is incoming to the node. This determines the flow along the path, which is used to calculate the latencies and cost of the flow. To model the selfish behavior, we simulated a repeated game where players update their strategy choice based on their local latencies which should converge on the Wardrop equilibrium. If no player can improve their payoff by unilaterally altering their strategy choice an equilibrium is reached. Each player locally samples the cost function as they adjust each of the three parameters in their strategy choice to approximate the local slope of the cost function to update their strategy choice to minimize the difference in latencies of their two outgoing paths. We simulate the full network including the central 0 cost edge, as the graph with no central edge is already optimal with a cost of anarchy equal to 1 and cannot be improved with quantum players. The present scheme serves as a proof of principle that quantum game ideas may be useful in improving the efficiency of classical networks when the players can act in their self-interest. Another important consideration this work demonstrates is that a quantum network can exhibit the Braess’ Paradox even for maximally entangles states. Thus, quantum networking schemes may necessarily have to incorporate these types of counter intuitive behaviors into their analysis of network performance.
Not SubmittedFunder Acknowledgement(s): Department of Defense-Army Research Lab Thurgood Marshall College Fund
Faculty Advisor: Timothy Holston, thost@mvsu.edu
Role: In this research I was in charge of building the code needed to run the simulations in Mathematica. I also wrote the code to build the charts used to analyze our results.