Analysis of a Forwarding Game without Payments

We consider a forwarding game on directed graphs where nodes need to send certain amount of flow (packets) to specific destinations, possibly through several relay nodes. All nodes in the network act selfishly and will forward packets only if it is to their benefit. The model assumes that each node receives some utility from sending it flow to the predetermined destinations and from receiving flow. However each node has to decide whether to relay flow as an intermediate node from other sources, as relaying has an associated cost. This model assumes that there is no payment scheme. Somewhat surprisingly, this game has possibly several strategies that allow a significant amount of the flow to be routed while all nodes have a positive outcome, which suggest that in this model the nodes have indeed incentives to relay flow even if payments are not explicitly allocated. Although previous theoretical work establishes the existence of these strategies (Nash equilibrium solutions), it is not known how often networks have such solutions, and what percentage of flow is actually relayed through the network. In this work we simplify the original network model, and provide the first experimental evaluation of these equilibria for various classes of graphs. We provide clear evidence that these equilibrium solutions are indeed significant and establish how these equilibria depend on various properties of the network such as average degrees and flow demand density.