Reshef Meir reports from AAMAS 2011:
Held this year in Taipei, Taiwan, the 10th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS) was somewhat smaller than the last one, with 127 full papers and 131 posters out of 575 submissions. This is presumably due the location and the double competition from AAAI and IJCAI. The poster format in AAMAS has 2 pages in the proceedings and does not prevent future publication in other venues. All AAMAS full and short papers are freely available online.
The dominance of game theory in MAS was demonstrated by the selection of both the best student paper award, Designing Incentives for Boolean Games by Yair Zick and Edith Elkind (who also won best SPC member); and the best paper award, Designing Incentives for Boolean Games by Endriss, Kraus, Lang and Wooldridge. In the latter, an opposite approach to subsidy (in the sense of k-implementation) is suggested. Here the designer implements a desired outcome (a Boolean formula) by casting fines on players. However, there are hard constraints as agents also try to achieve their goals (other Boolean formulas), regardless of their cost.
While many AGT papers (including both mentioned best papers) were theoretical, AAMAS this year witnessed three major applications in which AGT and mechanism design are taking an increasingly important role.
The first is a game-theoretic approach to security issues (building on work by Sarit Kraus, Peter Stone and others).
The second is the assimilation and management of green technologies, as exemplified in the best paper runner-up (Agent-Based Control for Decentralised Demand Side Management in the Smart Grid, by Ramchurn et al.), and other papers throughout the conference, some of which were presented in a designated session.
The third application, which I found least expected, is the designing of incentives that allow for better human computation (Capability-Aligned Matching: Improving Quality of Games with a Purpose, by Chiou and Hsu). The potential of efficiently exploiting human computation resources such as Amazon Turk for image and video annotation was highlighted in the excellent invited talk by Kristen Grauman.
However, the application of game-theoretic solutions such as Nash equilibrium to real world situations is often inappropriate due to the strong implicit rationality assumptions in game theory. This painful drawback partially accounts for the criticism about the actual contribution of AGT to AI (a glimpse into this debate is in a previous post by Ariel Procaccia). In his ACM research award talk, Joe Halpern considered several solution concepts that are aimed at relaxing the strict notion of rationality, by allowing a limited number of agents to follow various behaviors from “crazy” (Byzantine) actions, to bounded rationality (in either the information or computation sense), to collusion. The new types of equilibria are thus more robust to small changes and better predict real behavior (by a human or a machine). Closing the loop, Halpern demonstrated how mechanism design (mediators) and “classic” CS (cryptography) can be recruited to implement such solutions.
Much related to this issue, Cigler and Falting suggested an interesting way to tackle drawbacks of Correlated equilibria (Reaching Correlated Equilibria through Multi-agent Learning). While convergence to CE is possible without a mediator (e.g., with regret methods), it does not guarantee that a good CE is reached. Thus, the outcome might be unfair or inefficient. On the other hand, good mediators might be unavailable or hard to implement. The paper offers an algorithm that converges to a fair and efficient CE, albeit in a very specific game, using a simple coordination device. I find the idea that partial coordination can be used instead of full coordination to be a promising one.
AAMAS also supplies a good platform for papers that combine ideas from multiple disciplines. The two following papers demonstrate the fine line between cooperation and self-interest.
- Who Goes There? Selecting a Robot to Reach a Goal Using Social Regret, by Traub, Kaminka, and Agmon, show how economic paradigms and decision theory can be used to improve coordination among fully cooperative robots in the face of uncertainty.
- In the other direction, we find Incentive Design for Adaptive Agents, by Chen et al. Here the authors study ad-hoc teaching, which is usually considered as a cooperative action, as means to increase the utility of a selfish teacher.
Having high expectations from previous years, I much anticipated this year’s banquet. The traditional 9-course meal that was served was undoubtedly the most, well, interesting dinner I have had for a long time. It was very good in fact, if you were brave enough to try J. There were also other surprises throughout dinner, such as the Telemann’s Canonic Sonata #2, performed live by conference chair Peter Stone and Joun-Huei Soo (daughter of the local arrangements chair Von-Wun Soo).
Three years ago in an invited lecture at AAMAS-08, Yoav Shoham (who this year received the Influential Paper award for his 1993 paper, “Agent-Oriented Programming”) challenged the multi-agent systems community, by reiterating the importance of game theory in the analysis and design of agent interactions. Indeed, it seems that the message has been well-accepted.
Even more so than in previous years, game theory is no longer a field within MAS (or in the intersection of MAS with other areas). Rather, game theory (and AGT in particular) serves as a powerful tool whose presence is inevitable in nearly all levels of MAS research, from multi-agent learning, to emergent behavior, logic based systems, and even robotics. Deepening the involvement of AGT researchers as authors and reviewers in AI venues will benefit all the involved parties (even if self-interested). See you in next year in Valencia!
Turing's Invisible Hand 
