CS and Game Theory

I read Papadimitriou’s article on Algorithms, Games, and the Internet, and found it to be a rather nice overview strongly hinting at future emphasis within the Theoretical Computer Science community. I’ve long thought that a good game theoretic background would help in the development of network protocols, esp. wireless protocols. I particularly liked FON‘s original approach (Bills, Linus’s, and Aliens) to popularizing the spread of wifi.

I also really liked section 6, Mechanism Design, where he says that:

If an artifact (a new congestion control protocol, a new caching scheme, a new routing algorithm, etc.) is demonstrated to have superior performance, this does not necessarily mean that it will be successful. For the artifact to be “fit,” there must exist a path leading from the present situation to its prevalence.

A formalization of this observation could really help out those in Software Software Engineering.

All in all I’d like to see the development of a Universal Protocol that lets all devices communicate in a wireless fashion. So that I can buy a TV, Computer, Equalizer, and Speakers all separately, and by simply having them in the same room, I can pipe video from Computer to TV, audio from Computer to Speakers, or from TV to Equalizer and then Equalizer to Speakers. A single protocol should be able to carry everything from audio to video to any device that publicly announces a stream or slot. Internet traffic should be similarly transparent. With the correct allocation algorithms, we can build a nation-wide wireless aethernet one $40 router at a time. (Even better if we could work in roaming.) And it’ll all come from a coupling of Game Theory and Computer Science.