Artificial Life, and beyond

Artificial Life is here.  Computer Scientists who have been around for a while should be able to extrapolate.

Read Full Post »

Reshef Meir reports on AAMAS

Guest post by Reshef Meir

As can be inferred from the second part of its title, the 9^th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS) is all about multi-agent interaction, making it a natural forum for AGT papers. Nevertheless, the title, as well as the call for papers, leaves room for a wide variety of papers from different areas and disciplines.

The Game Theory / Econ community definitely had the most significant presence, with 5 sessions devoted to the topic and at least 6 more sessions featuring related talks (out of 22). In addition, there was a tutorial on Computational Voting Theory (by Ariel Procaccia and Vincent Conitzer), and a brand new collocated workshop on Cooperative Games (COOPMAS).

The two other largest communities sharing the AAMAS roof were arguably those of Robotics and Learning. Whereas all have a significant overlap with AI (see Ariel’s post on IJCAI for a definition), these three are considered to be almost mutually exclusive in terms of their motivation and applications. This divergence led some people to ask whether the scope of AAMAS is not too broad. In my view, MAS (much like AI) cannot be properly defined as a “field” or even a “union of fields”; rather, it is inherently interdisciplinary. As such, its primary conference, AAMAS, should give researchers from all related communities the opportunity to familiarize themselves with the developments in the sibling communities. This also allows authors to receive feedback on their work from a different angle, which may lead to surprising consequences and collaborations.

The schedule of the conference was better organized (in my opinion) than in previous years, and I will give two examples. First, the poster session was split into two two-hour sessions held on different days, making participation easier and more effective. Secondly, the best paper candidates were clustered into two parallel “best-paper sessions”, instead of putting other papers into an unfair competition. These two schedule decisions also promote the interdisciplinary interaction as these sessions are attended by all.

AAMAS is also renowned for its social program, which included this time a banquet dinner on the top of the CN tower, trying to beat the boat on the Danube of 2009, and the ancient Portuguese castle of 2008 (before that I did not attend…).  This was a brave attempt, but Portugal still wins. Another AAMAS tradition is the Europe-vs.-the-world soccer match. The Europeans took advantage of the absence of Peter Stone to crush the Americans 6-1. The game was later used by Markus Brill in his (best paper runner up) talk as an example for a “tournament” – an extremely simple one.

Interestingly, the Victor Lesser distinguished dissertation award was given for the forth time to a PhD in the area of AGT (the previous winners were Vince Conitzer, Radu Jurca, and Ariel Procaccia). This year the award went to Andrew Gilpin, for his contributions in two-player versions of Poker. The most interesting part of his talk was about how symmetries in the game tree can be exploited to solve the Rhode Island Hold’em Poker. An intriguing dilemma (at least to AGT people) was highlighted by the contradicting interpretations of the outcome of Poker tournaments, as some teams disagreed with Andrew’s claims regarding his group’s achievements.

As for the main track, 685 papers had been submitted, out of which 163 full papers were presented. More short papers were presented only as posters. While this acceptance ratio suggests a generally high level, there was a lot of variance in the quality of papers (perhaps due to difficulty in assigning the appropriate reviewers from the right field for each paper).

These are four and a half papers that I found particularly interesting:

–         On the Role of Distances in Defining Voting Rules, by Elkind, Faliszewski and Slinko, in which the authors suggested an interesting, intuitive way to characterize voting rules w.r.t. how they behave in “easy” cases (e.g., when there is a Condorcet winner).

–         Finding Approximate Competitive Equilibria: Efficient and Fair Course  Allocation, by Othman, Budish and Sandholm. The authors highlight the differences between actual auctions, and using coupon auctions as a means to achieve good allocations. Then they demonstrate how the latter problem can be solved efficiently.

–         Preference elicitation for risky prospects, by Hines and Larson, is a fascinating attempt to merge irrational factors of human decision making into a standard utilitarian decision theory. This is by relying on Prospect Theory [Kahnemann and Tversky ’79, ’92]. I believe that we will see such factors more and more in game-theoretic analyses as well.

–         Internal implementation, by Anderson, Shoham and Altman, is the natural extension of k-implementation [Monderer and Tennenholtz ‘04], in the spirit of Stackelberg games. Instead of assuming some external benevolent authority with the power to promise positive payments to players, the authors take a more worldly approach where the external authority is no longer external, but is simply one of the players. Thus, one player (the designer) commits to make some positive transfer (conditioned on the outcome), thereby changing the game. As with k-implementation, the designer aims to turn a particular desired outcome into a dominant strategy (for the other player). However, there is now a clear notion of a desired outcome – one that increases the utility of the designer (after the payments).

–         The last (half) paper is a workshop paper by Chakraborty and Stone, which aims to achieve an optimal result when playing with a cooperative or bounded opponent, while maintaining the min-max safety level against all other opponents. A more recent version of this paper is to appear in the upcoming ICML.

Next year, AAMAS 2011 will be held in Taipei, Taiwan, which might finally beat Portugal for the best banquet dinner. We’ll be keeping our eyes (and mouths) open.

Read Full Post »

Workshop on Advances in Algorithmic Game Theory

A Workshop on Advances in Algorithmic Game Theory will take place in Amsterdam on September 2-3, 2010.

Read Full Post »

Papers from AAMAS posted

The full papers from the AAMAS conference that was held last week have been posted on line.  Several sessions are on AGT/E.  I hope that more conferences will be posting all papers online.

Read Full Post »

Eva Tardos To Give Erdos Lectures

Next week, May 23-26, Eva Tardos will give the prestigious Erdos lectures in discrete mathematics and theoretical computer science at the Hebrew University of Jerusalem on her AGT work.

Read Full Post »

Internet Advertising: Theory and Practice

For those AGT/E researchers working on questions related to Ad-auctions (like most of those employed by Google/Yahoo/Microsoft), and writing nice theoretical papers for workshops like the coming “Ad auctions workshop“, it is interesting to see an overview of the messy real word, as can be found in keynote talk given by Terrence Kawaja in a recent event organized by the Interactive Advertising Bureau.

Read Full Post »

The Future of Journalism

The Atlantic monthly published a long interesting piece on “How to save the news“.  Rather than the usual dark prophesies about how the Internet is killing journalism — “Plummeting newspaper circulation, disappearing classified ads, “unbundling” of content…” — reporter James Fallows presents “the Google point of view” which is quite optimistic.  Google’s involvement in the question may be captured by a quote from Google executive Nikesh Arora:

As long as there is great content, people will come looking for it. When there’s no great content, it’s very hard for people to be interested in finding it.

The general point of view of the article may be summerized by a quote from CEO Eric Schmidt:

Newspapers don’t have a demand problem; they have a business-model problem.

So new business models should emerge that will let newspapers do what they should do in more efficient ways, and then make money.  The current inefficiencies of the industry are of course obvious, and Google’s Chief Economist Hal Varian is quoted as saying:

Burdened as they are with these “legacy” print costs, newspapers typically spend about 15 percent of their revenue on what, to the Internet world, are their only valuable assets: the people who report, analyze, and edit the news.

What these new  business models will be is not yet clear, and the general spirit is captured by a quote from Clay Shirky of New York University:

Nothing will work, but everything might.

So are there any insights from theory?

Read Full Post »

Ad Auction Workshop Accepted Papers

The Sixth Ad Auctions Workshop, co-located with EC 2010, has just released the list of accepted papers.

Read Full Post »

COMSOC and SAGT submission deadlines

The submission deadlines of COMSOC and of SAGT are near: COMSOC on May 15th and SAGT on May 10th (after extension).  The interest areas of these two conferences have a significant intersection: (algorithmic mechanism design) (algorithmic game theory) (computational social choice).  Interestingly, one may submit the same paper to both conferences as COMSOC is defined to be non-archival: “we stress that authors will retain the copyright of their papers and that submitting to COMSOC-2010 does not preclude publication of the same material in a journal or in archival conference proceedings.”  Does this make sense? (I think: yes.)

Read Full Post »

Notes on Computational Social Choice

Last month a Doctoral School on Computational Social Choice was held in Estoril, near Lisbon, Portugal.  The web site includes slides of many of the talks and tutorials.  I liked the crisp slides of Ulle Endriss’s tutorial on Fair Division.

Read Full Post »