We consider a multilevel network game, where nodes can improve their communication costs by connecting to a high-speed network. The n nodes are connected by a static network and each node can decide individually to become a gateway to the high-speed network. The goal of a node v is to minimize its private costs, i.e., the sum (SUM-game) or maximum (MAX-game) of communication distances from v to all other nodes plus a fixed price α > 0 if it decides to be a gateway. Between gateways the communication distance is 0, and gateways also improve other nodes’ distances by behaving as shortcuts. For the SUM-game, we show that for α ≤ n − 1, the price of anarchy is Θ (n/√α) and in this range equilibria always exist. In range α ∈ (n−1, n(n−1)) the price of anarchy is Θ( √α), and for α ≥ n(n − 1) it is constant. For the MAX-game, we show that the price of anarchy is either Θ (1 + n/√α), for α ≥ 1, or else 1. Given a graph with girth of at least 4α, equilibria always exist. Concerning the dynamics, both games are not potential games. For the SUM-game, we even show that it is not weakly acyclic.
We study a scenario in which n nodes of a mobile ad-hoc network continuously collect data. Their task is to repeatedly update aggregated information about the data, e.g., the maximum, the sum, or the full information about all data received by all nodes at a given time step. This aggregated information has to be disseminated to all nodes. We propose two performance measures for distributed algorithms for these tasks: The delay is the maximum time needed until the aggregated information about the data measured at some time is output at all nodes. We assume that a node can broadcast information proportional to a constant number of data items per round. A too large communication volume needed for producing an output can lead to the effect that the delay grows unboundedly over time. Thus, we have to cope with the restriction that outputs are computed not for all but only for a fraction of rounds. We refer to this fraction as the output rate of the algorithm. Our main technical contributions are trade-offs between delay and output rate for aggregation problems under the assumption of T-stable dynamics in the mobile ad-hoc network: The network is always connected and is stable for time intervals of length T c · MIS(n) where MIS(n) is the >time needed to compute a maximal independent set. For the maximum function, we are able to show that we can achieve an output rate of (T/(n · MIS(n))) with delay O(n · MIS(n)). For the sum, we show that it is possible to achieve an output rate of (T5/2/(n2 · MIS(n)3)with delay O(n2 ·MIS(n)2/T3/2) if T = O(n2/3 ·MIS(n)2/3), and if T = n2/3 ·MIS(n)2/3), we can achieve an output rate of (T/(n·MIS(n)2)) with delay O(n ·MIS(n)).