## 2 Model and Background  
**Definition 2.1** (LMCF Game). : _Given a connected, undirected, edge-weighted graph \(G=(V,E)\) (with \(V=(1,2,\ldots,n)\), weight function \(w:E\to R^{3}\) and designated destination node \(t\), \(LMCF(G,w,t)\) consists of the following: Players are nodes \(v\in V\setminus\{t\}\), each player \(v\) with strategy set \(N(v)=\{\) one-hop neighbors of \(v\}\). Given a pure strategy-tuple \(S=(s_{1},s_{2},\ldots,s_{n-1})\) refer to \(G_{S}\), the graph induced by \(S\), as the directed graph formed by the set of directed edges of the form \((u,s_{u})\). Finally, the cost \(c_{S}(v)\) of strategy-tuple \(S\) to player \(v\) is \(c_{S}(v)=w(v,s_{v})\) if \(G_{S}\) contains a path from \(v\) to \(t\) and \(\infty\) otherwise._  
For any node \(v\) and any strategy-tuple \(S\), at most one path may exist from \(v\) to \(t\) in \(G_{S}\). Denote by \(dist_{S}(v)\) the total weight of that path if such exists and \(\infty\) otherwise. Clearly, this distance is minimum in a shortest path tree (SPT) rooted at \(t\). Denote the shortest path distance by \(dist(v)\). Now, we present two alternative formulations for the _Social Cost_ of a strategy-tuple \(S\) for the LMCF Game. The first is based on the stretch factor of node-destination paths in \(G_{S}\), the second based directly on the maximum distance of any node to the destination in \(G_{S}\). \[SC_{\textit{stretch}}(S)=max_{v\in V\setminus\{t\}}\frac{dist_{S}(v)}{dist(v)} \tag{1}\]  
\[SC_{\textit{md}}(S)=max_{v\in V\setminus\{t\}}dist_{S}(v) \tag{2}\]  
As we are concerned with the relative social optimality of a strategy-tuple, in a manner consistent with the literature we denote the _price_ of a strategy tuple \(S\) to be the ratio of the social cost of \(S\) over the social cost of the globally optimal strategy, which for the LMCF game is the SPT. In an incentive compatible topology control problem, the goal is to find a \"recommendation algorithm\" for selfish nodes to forward such that the nodes are in a Nash equilibrium or approximate Nash equilibrium configuration that also performs well socially. A **Nash equilibrium** is a fixed-point best-response strategy profile: a strategy-tuple from which no agent has a unilateral incentive to deviate, _i.e._, any such deviation would not improve the cost to the agent. The **price of anarchy**, \(PoA\), with respect to a social cost function on a given instance is the maximum (worst) ratio of the social cost of a Nash equilibrium to the best possible social cost (that for the SPT). The **price of stability**, \(PoS\), is the minimum (best) such ratio. We investigate the _price of anarchy_ and _price of stability_, as well as their computability, for _Nash equilibria_ of the Locally Minimum Cost Forwarding (LMCF) Game. We study these quantities in both the worst-case and average-case. Since by definition \(SC_{stretch}(S)=1\) for the SPT, \(PoA\) and \(PoS\) over \(SC_{stretch}\) are precisely the maximum and minimum social cost over all Nash equilibria. We will focus on the prices of anarchy and stability on _Euclidean power graphs_ and _random link_ graphs. A Euclidean \(p\)-power graph in dimension \(d\) is a complete graph consisting of nodes embedded into \(d\)-dimensional Euclidean space with edge weights defined by \(w(i,j)=d^{p}(i,j)\), the \(p^{th}\) power of the distance.4_Random_ Euclidean power graphs are induced by placing each node uniformly at random into the \(d\)-dimensional unit-cube. These are especially relevant models of wireless ad-hoc sensor networks due to the randomness of placement and the modeling of energy, when \(p=d=2\). Footnote 4: When the dimension is not specified, we may assume it is \(2\). When the power is not specified then assume that it is \(1\). Note that for powers higher than \(1\) these graphs do not necessarily obey a metric though they are induced by such.