We study a novel game theoretic incentive mechanism design problem for network congestion control in the context of selfish users sending data through a single store-and-forward router (a.k.a. “server” in this work). The scenario is modeled as an M/M/1 queueing game with each user (a.k.a. “player”) aiming to optimize a tradeoff between throughput and delay in a selfish distributed manner. We first show that the original game has an inefficient unique Nash Equilibrium (NE). In order to improve the outcome efficiency, we propose an incentivizing packet dropping scheme that can be easily implemented at the server. We then show that if the packet dropping scheme is a function of the sum of arrival rates, we have a modified M/M/1 queueing game that is an ordinal potential game with a unique NE. In particular, for a linear packet dropping scheme, which is similar to the Random Early Detection (RED) algorithm used with TCP, we show that there exists a unique Nash Equilibrium. For this scheme, the social welfare (expressed either as the summation of utilities of all players or log summation of utilities of all players) at the equilibrium point can be arbitrarily close to the social welfare at the global optimal point. Finally, we show that the simple best response dynamic converges to this unique efficient Nash Equilibrium.

We consider a problem where two selfish cognitive radio users try to share two channels on which they each have potentially different valuations. We first formulate the problem as a non-cooperative simultaneous game, and identify its equilibria. For cases where the resulting Nash equilibria are not efficient, we then propose a novel coordinated channel access mechanism that can be implemented with low overhead in a decentralized fashion. This mechanism, based on the Nash bargaining solution, guarantees full utilization of the spectrum resources while improving the utility of each user compared to the non-cooperative setting. We quantify the resulting gains. Finally, we prove that risk-averse users that are willing to accept offered information at face value have no incentive to lie to each other about their valuations for the non-cooperative game. However, we find that truthfulness is not guaranteed in the bargaining process, suggesting as an open problem the design of an incentive compatible mechanism for bargaining.

A new generation of community-based social networking mobile applications is emerging. In these applications, there is often a fundamental tension between users' desire for preserving the privacy of their own data and their need for fine-grained information about others. Our work is motivated by a community-based mobile application called Aegis, a personal safety enhancement service based on sharing location information with trusted nearby friends. We model the privacy-participation tradeoffs in this application using a game theoretic formulation. Users in this game are assumed to be self-interested. They prefer to obtain more fine-grained knowledge from others while limiting their own privacy leak (i.e. their own contributions to the game) as much as possible. We design a tit-for-tat mechanism to give user incentives to contribute to the application. We investigate the convergence of two best response dynamics to achieve a non-trivial Nash equilibrium for this game. Further, we propose an algorithm that yields a Pareto optimal Nash equilibrium. We show that this algorithm guarantees polynomial time convergence and can be executed in a distributed manner.