Wireless Access Network Selection Game with Negative Network Externality

Network service acquisition in a wireless environment requires the selection of a wireless access network. A key problem in wireless access network selection is to study the rational strategy considering the negative network externality, i.e, the influence of subsequent users´ decisions on an individual´s throughput due to the limited available resources. In this work, we formulate the wireless network selection problem as a stochastic game with negative network externality and show that finding the optimal decision rule can be modelled as a multi-dimensional Markov Decision Process (MDP). A modified value iteration algorithm is proposed to efficiently obtain the optimal decision rule with a simple threshold structure, which enables us to reduce the storage space of the strategy profile. We further investigate the mechanism design problem with incentive compatibility constraints, which enforce the networks to reveal the truthful state information. The formulated problem is a mixed integer programming problem which in general lacks an efficient solution. Exploiting the optimality of substructures, we propose a dynamic programming algorithm that can optimally solve the problem in the two-network scenario. For the multi-network scenario, the proposed algorithm can outperform the heuristic greedy approach in a polynomial-time complexity. Finally, simulation results are shown to validate the analysis and demonstrate the effectiveness of the proposed algorithms..