Computer Science – Computer Science and Game Theory
Scientific paper
2011-06-20
Computer Science
Computer Science and Game Theory
This work is an extended version of the conference paper: Y. Gai, H. Liu and B. Krishnamachari, "A packet dropping-based incen
Scientific paper
We consider a fundamental game theoretic problem concerning selfish users contributing packets to an M/M/1 queue. In this game, each user controls its own input rate so as to optimize a desired tradeoff between throughput and delay. We first show that the original game has an inefficient Nash Equilibrium (NE), with a Price of Anarchy (PoA) that scales linearly or worse in the number of users. In order to improve the outcome efficiency, we propose an easily implementable mechanism design whereby the server randomly drops packets with a probability that is a function of the total arrival rate. We show that this results in a modified M/M/1 queueing game that is an ordinal potential game with at least one NE. In particular, for a linear packet dropping function, which is similar to the Random Early Detection (RED) algorithm used in Internet Congestion Control, we prove that there is a unique NE. We also show that the simple best response dynamic converges to this unique equilibrium. Finally, for this scheme, we prove that the social welfare (expressed either as the summation of utilities of all players, or as the summation of the logarithm of utilities of all players) at the equilibrium point can be arbitrarily close to the social welfare at the global optimal point, i.e. the PoA can be made arbitrarily close to 1. We also study the impact of arrival rate estimation error on the PoA through simulations.
Gai Yi
Krishnamachari Bhaskar
Liu Hua
No associations
LandOfFree
A Packet Dropping Mechanism for Efficient Operation of M/M/1 Queues with Selfish Users does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Packet Dropping Mechanism for Efficient Operation of M/M/1 Queues with Selfish Users, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Packet Dropping Mechanism for Efficient Operation of M/M/1 Queues with Selfish Users will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-254964