GCHs (Grand Challenge Homeworks) are open problems that my colleagues and I have faced in our research and have not been able to solve them. Typically, these are math problems that we have spent quite some time to prove or disprove without any success. If you have a suggestion to solve any of our GCHs, I would be very eager to talk to you. I am in the process of posting all of our GCHs, so stay tuned!

GCH Problmes

Problem 1 : Network Selection Game and Nash Equilibrium

Basic Concept

We treat the Base Station (BS) selection issue as a game where users independently choose their BS to boost their data speeds. Imagine the users as players in this game (let's assume they are N players), and each player (user) has a strategy, which is the BS they pick. We use σi to represent the strategy chosen by player i. The strategy profile,
σ =(σ1,σ2,...,σ_N), is the combination of all users' chosen BSs.

Now, an improvement path is a series of steps where, at each stage, only one user changes their chosen BS, ensuring a definite increase in their data speed. Specifically, a best response improvement path is one where, at each step, the user switching BS selects the one that offers the maximum throughput among all available BSs.

The competition among self-interested users trying to maximize their data speeds might result in a situation where no user can enhance their throughput by unilaterally changing their chosen BS. This scenario, where each user's choice is optimal given others' choices, is termed a Nash equilibrium.

The Game Explained

Players, represented by the set N, strategically choose from a set of base stations, denoted by K, to optimize network performance. The throughput for any client i at a given base station K is signified by ω_i,k, weighted by φ_i,k to reflect the client's priority. The PHY rate of client j on base station K is given by R_j,k. The subsequent equation illustrates the weighted throughput ω_i,k as a function of these parameters.

The goal

Provide proof or find a counterexample for the conjecture below.

Conjecture

Let G be a network selection game with ϕ_i,k = (R_i,k)^β for all players i in set N and each network k in set K. The conjecture states that the game G always converges to a Nash Equilibrium for any value of β.

Equation

For every player i in set N and every network k in set K, the conjecture states,
ϕ_i,k= (R_i,k)^β
The game G always converges to a Nash Equilibrium for any value of β.

where,
G: Represents the network selection game.
N: The set of all players (clients) in the game.
K: The set of all possible strategies (base stations) that players can choose from.
φ_i,k: This is the weight of client i on base station K.
R_i,k: This is the PHY rate of client i on BS K
β: scaling factor (The paper mentioned below provides a range of β values, including 0, -∞, 1/2, 1, and +∞, for which the corresponding games are proven to converge to a Nash equilibrium.)

You can refer to our INFOCOM 2015 paper for a deeper understanding of this conjecture.