This might be a central processing node in a sensor network, the access point (AP) that allows the nodes to connect to the Internet, or a base station in a hybrid cell phone network. Our cost and utility model is as follows. Individual nodes care only about minimizing their own power consumption given that they must forward what has been given to them in this reverse-multicast scenario, and adopt their strategies accordingly, whereas the global objective is to minimize the total energy used. In other words, the social goal is to minimize the expected amount of power consumed by transmitting a single message from source to destination. Assuming fixed routing tables (pure strategy) this will also be the cost-per-message in the long term. We assume that messages are generated at random sources. For simplicity we will assume uniformly at random, but all our results will hold for _any_ probability distribution, which guarantees that each node has a non-zero probability of being a message source. Specifically, define:  
* \(q_{v}=\) load generated at node \(v\)
* \(Q_{v}=\) total outgoing load at \(v\) from all data passing through \(v\)
* \(c_{v}=\) cost per-bit of forwarding from \(v\) to \(v\)'s chosen neighbor
* \(PATH_{v}=\) sum of \(c_{i}\) along the path from \(v\) to the destination  
Player \(v\) wants to minimize \(Q_{v}c_{v}\), but has no control over \(Q_{v}\) and can only minimize \(c_{v}\). The global objective is to minimize the total induced load times the forwarding cost, \(\sum_{v}Q_{v}c_{v}=\sum_{v}q_{v}PATH_{v}\)Given an aggregate load \(\sum_{v}q_{v}\), the worst-case distribution would be concentrated along the most costly path, with exactly one nonzero \(q_{v}\). The global objective is therefore to keep that longest directed path short. Since a node's interest is limited to having a path to the destination, and it does not care how long that path is, so long as its _individual_ or _local_ forwarding cost is minimized, we refer to this setting as a _Locally Minimum Cost Forwarding Game_ (LMCF). Of course, from a system-wide perspective, short paths are desirable, as explained above so that our _social_ optimum objectives are the following: (i) minimize the maximum stretch factor1 in the resulting topology with respect to true shortest path distances, or (ii) minimize the cost of the longest path in the resulting topology. Our aim is to find and to characterize Nash equilibria that optimize the social objective. The ratio of the objective value achieved by the best Nash equilibrium and the (non-selfish) value of the social optimum is called the _price of stability_, whereas that ratio for the worst Nash equilibrium is called the _price of anarchy_[12, 13, 14]. Footnote 1: Given a designated destination \(t\), the stretch factor of a weighted directed subgraph \(G_{s}\) of \(G\) is the maximum ratio of a node’s distance to \(t\) in \(G_{s}\) compared with its distance to \(t\) in \(G\). Intuitively, this measures the dilation of paths of \(t\) in \(G_{s}\) w.r.t \(G\). Note that when \(t\) is not designated, the stretch of \(G_{s}\) simply takes the maximum respective ratio over all-pairs distances. The prices of stability and anarchy have been extensively investigated in other network settings under other objectives, particularly for congestion-based games and fair-allocation games (for example [12, 13, 14, 15]). The problem of finding good Nash equilibria in the context of topology-control for ad-hoc networks has also been investigated [3, 4, 6, 7, 8, 9]. We note that the LMCF game differs from previously considered games in its objectives, both individually and socially. Our work is related to the non-game-theoretic results of [16] that construct spanning structures balancing edge costs, _i.e._, Minimum Spanning Trees(MSTs), and path costs, _i.e._, Shortest Path Trees (SPTs). However the game-theoretic aspect of this work, in particular the locality of individual preferences, makes a crucial difference as the algorithms of [16] do not directly relate to Nash equilibria for LMCF.