The Ethernet and Wi-Fi standards (802.3 and 802.11) both define exponential backoff algorithms to avoid collisions. Exponential backoff works well when all stations use it. However, a selfish station can force those who follow the standards to back off, thus increasing his own bandwidth share. If we assume that all stations act in their own self-interest, we can analyze backoff game-theoretically by defining a packet-transmission game and finding properties of its equilibria. We define such a game, find and analyze its pure and mixed strategy Nash equilibria, use variants of a regret-matching algorithm to analyze its correlated equilibria and briefly explore other solution concepts. We measure stability, fairness, throughput and delay at equilibrium, and use these measures to compare game-theoretic backoff with exponential backoff. In some cases, game-theoretic backoff seems to lead to better performance than exponential backoff.
Advised by Anna Karlin and Ioannis Giotis
CSE 403
Wednesday
May 16, 2007
3:30 - 4:20 pm