Process Algebra Diary: Whence Algorithmic Game Theory?

Friday, November 27, 2015

Whence Algorithmic Game Theory?

I recently saw the slides for the invited talk delivered by Moshe Vardi at SR 2015, the third International Workshop on Strategic Reasoning, which was held in Oxford in the period 21-22 September 2015. The talk was entitled A Revisionist History of Algorithmic Game Theory and must have stimulated some discussion at the workshop.

Moshe's message was that algorithmic game theory is older than the "official history" would make one believe and that

it was initiated by logicians in 1957,
it was revitalized by Vol. B TCS in 1989 , and
has been active in Volume B TCS since then.

The most important message, however, is that one should tear down the wall between Vol. A and Vol. B. As readers of this blog may have realized, this is a message to which I wholeheartedly subscribe, perhaps because in the small research community I live in, we have to go to each other's talks to even have an audience at all.

2 comments:

Unknown said...: Can you elaborate on the difference in interpretation of the words "Algorithmic Game Theory" in the two communities (A and B)? Or was this a talk about nomenclature collision?; 9:49 pm
Luca Aceto said...: James, I think that this was definitely not a talk about nomenclature collision. If you read Moshe's slides, you will see that he holds the Goedel-prize-winning AGT work in very high esteem. What he is pointing out is that there is a whole line of work in volume B TCS (dating back at least to 1989) that has its roots in work in logic dating back to 1957 and that has led to a rich body of theoretical results. The focus of those results is the algorithmic study of games, with emphasis on the study of algorithmic synthesis of winning strategies. This work rests on IMHO deep results in algorithms and complexity and has very interesting connections with volume A TCS. (I like to think that it ought to be of interest to volume A folks.)

For a recent example, see for instance, the game-related papers in CONCUR 2015:

http://drops.dagstuhl.de/portals/extern/index.php?semnr=15013

(Look for game or synthesis.)

I sympathize with Moshe's plea to take a holistic view of TCS. AGT seems to be a prime example of an area where everyone would benefit by breaking down existing or purely perceived walls.; 6:13 pm