iAGT workshop, May 22-26 in Jerusalem

The innovations in Algorithmic Game Theory workshop will be held in Jerusalem during May 22-26, 2011. Registration is free, and is requested to be done by April 10th.  Here is the poster.

Read Full Post »

March 2011 SigEcom Exchanges

The March 2011 issue of SigEcom exchanges has been published.  SigEcom Exchanges is the official newsletter of the ACM special interest group on E-commerce, and despite its “official” status contains interesting AGT-related articles.  Yiling Chen is now replacing Vincent Conitzer as the editor.  Thanks to Vince for his work and Wishes of success to Yiling.

Read Full Post »

Report on AGT semester I: Talks with Agendas

The AGT semester at the institute of advanced studies of the Hebrew University is gearing up with a sequence of AGT talks being given at various forums here.  What I liked about the last few talks that I heard is that each of them really advances an agenda by exhibiting a result, rather than just showing a result.

Christos Papadimitriou gave a special seminar with his usual title Games, Algorithms, and the Internet.  While the title remained fixed for quite some time (I have heard him talk with this title at least twice in the last few years), the technical content changes as the years pass, shifting to his most recent work (Christos remarks that this is better than keeping the content and changing the title, a not too unusual state of affairs).  This talk is the mother of all AGT-as-a-way-to-study-the-Internet agenda setting talks.  As usual the talk contained memorable one-liners, some that I’ve heard before (Scot Shenker: “The Internet is in Equilibrium, we just have to identify the game”), and some new to me (“If Game Theory is a beauty contest among modeling concepts, then Computational Complexity should be one of the judges”).  A particularly lively discussion with the audience ensued when he offered the interpretation that NP-completeness implies “mathematical-nastiness”, and thus in some vague sense, (which I’d be happy to see made more precise,) proving that a certain problem is NP-hard means that “you’re not going to get nice mathematical theorems about it”.   (The context was his recent paper with George Pierrakos on the difficulty of extending Myerson’s theorem to interdependent valuations.)

Tim Roughgarden talked in our group’s Computation and Economics seminar and his agenda was the possibility of designing “distribution-free” mechanisms.  The idea is that you want to design a mechanism that does not depend on the prior distribution of valuations (“detail free” as the “Wilson doctrine” would call it), and still is competitive with an optimal algorithm designed for a specific distribution; and for this to happen for all prior distributions.  Amazingly, this is possible, with the classic example being the Klemperer-Bulow result showing that, in a single item auction, having an additional single bidder and having no reserve price (and thus being detail-free) always gets at least as much revenue as using the optimal Myerson reserve price (which depends on the distribution).  Tim and his co-authors, Peerapong Dhangwatnotai and Qiqi Yan, were able to get competitive detail-free auctions for more complex settings and without adding an extra bidder.

Kevin Leyton-Brown actually gave two talks, the first in the rationality seminar, and the second in the CS colloquium.  While the “proof of concept” in both talks were actual software systems that he built, they served to demonstrate his agendas.   In the first talk he advocated modeling and analyzing games computationally, for which a good “language” to describe games is needed.  Such a language should be succinct and yet amenable to efficient computation, and he suggested — and provided software for — the language of “action graph games“.  In the second talk he advocated “meta-algorithmic” optimization techniques: taking existing algorithms and automatically combining them and/or optimizing their parameters using learning-like methods on a given data-set.  He built several systems along these lines, the most impressively demonstrated of which is SATzilla which won several medals in SAT solving competitions.

Read Full Post »

Google Grant on Electronic Markets and Auctions

Google has awarded a grant to a group of 20 PIs (including myself)  from three universities in Israel for the study of “electronic markets and auctions”.   It is defined rather widely from basic Algorithmic Game Theory type issues to more applied ad-auction questions and spans a spectrum of researchers from CS, AI, GT, EE, IE, math, economics, and business.  The crucial point is that this is academic non-Google-specific research and its results will be normally academically published.

Here is the official press release, and here is the post on Google’s research blog.

The list of PIs is:

• Hebrew University: Danny Dolev, Jeffrey S. Rosenschein, Noam Nisan (Computer Science and Engineering); Liad Blumrosen, Alex Gershkov, Eyal Winter (Economics); Michal Feldman and Ilan Kremer (Business). The last six are also members of the Center for the Study of Rationality.
• Tel Aviv University: Yossi Azar, Amos Fiat, Haim Kaplan, and Yishay Mansour (Computer Science); Zvika Neeman (Economics); Ehud Lehrer and Eilon Solan (Mathematics); and Gal Oestreicher (Business).
• Technion: Seffi Naor (Computer Science); Ron Lavi (Industrial Engineering); Shie Mannor and Ariel Orda (Electrical Engineering).

Many observers are curios about Google’s motives in such a grant.  It seems that Google is simply trying to support basic research in an area which is crucial for it, while strengthening its ties with researchers, students, and the academia in this area.

 

Read Full Post »

EC 2011 Accepted Papers

EC 2011 Accepted Papers have been posted.  49 accepted papers out of 189 submissions (26%).

Read Full Post »

EC 2011 Workshops

In conjunction with EC 2011 (itself part of FCRC 2011, to be held in San-Jose, California on June 4-11), there will be five workshops:

• NetEcon 2011 — 6th workshop on Economics of Networks, Systems, and Computation.  June 6th.  Submission deadline: March 25th.
• Workshop on Bayesian Mechanism Design.  June 5th.  Submission deadline: April 15th.
• Workshop on Implementation Theory.  June 6th.  Submission deadline: April 3rd.
• 7th Ad Auction Workshop.  June 5th.  Submission deadline April 15th.
• Workshop on Social Computing and User Generated Content.  June 5th.  Submission deadline: April 15th.

Read Full Post »

Center of Rationality postdoc positions

The Center of Rationality at the Hebrew University of Jerusalem is announcing five postdoc positions in game theory and rationality for the coming academic year.  This is certainly one of the best places in the world for interdisciplinary research involving game theory, with a large number of excellent researchers in Economics, Computer Science, Mathematics, Psychology, and other disciplines, all interested in Game Theory and Rationality.  The areas open this year are:

• Game Dynamics.  Host: Sergiu Hart
• Algorithmic Game Theory.  Hosts: Liad Blumrosen and Noam Nisan
• Game Theoretic Approaches to Financial Economics.  Host: Ilan Kremer

The positions carry unusually high Stipends.  The final deadline for application is May 31, 2011, but strong applications received by March 31, may get an early reply.  For details see the poster.

Read Full Post »

So what is AI?

As the New-York Times says, “It’s been a banner year or so for artificial intelligence”.  This particular article talks about Valiant’s Turing award, and refers also to IBM’s impressive recent display of Jeopardy playing by “Watson”.  This labeling of  Valiant as an AI researcher, as well as the connection to IBM’s Watson seems to be shared by most newspapers but does not really fit the award citation of  “For transformative contributions to the theory of computation, including the theory of probably approximately correct (PAC) learning, the complexity of enumeration and of algebraic computation, and the theory of parallel and distributed computing.” My own tendency is to view Valiant as a theoretical computer scientist, most admired, by me,  for his work on basic complexity theory (algebraic, counting,  graph-theoretic, and beautiful).  So I wonder again whether these newspapers are correct in their labeling, a question that raises again the old question of what is AI?

It seems that AI guys are often soul-searching about the definition of AI but non-AI CS-ers seem mostly oblivious to it.  Just recently, (in an aside to some CS department discussions,) several faculty members from my department sincerely asked me to explain what (the hell) are these AI researchers doing.  (I suppose that asking me rather than an AI researcher is more or less like asking an anthropologist who lived among the “natives” rather than the natives themselves.)

Part of the question is the discrepancy between the vision of AI, which talks about the ability of mimicking aspects of human behavior that we consider as intelligent, and the practice of AI by academic community.  It seems that once an aspect of AI is understood well enough, it ceases being part of the academic AI community and develops its own internal community.  Examples of this phenomena are the computer vision community, the machine learning community, and the information retrieval community, all central aspects of the concept of AI that are now mostly leading their separate academic lives in conferences like ICCV, NIPS, and SIGIR, respectively, rather than as part of AAAI or IJCAI.  Thus while Valiant’s foundational work on learning is clearly at the heart of the concept of AI, sociologically speaking it was part of theoretical computer science and machine learning communities rather than the academic AI community.

For a long time I was wondering why derivatives of Game-Theory are accepted as part of academic AI community under labels such as multi-agent systems (MAS).  I  now tend to adopt the answer I got from Aviv Zohar taking the view the strategic interaction with others is one of the central traits of intelligence and thus falls streight into the concept of AI.  It seems that while this MAS community clearly has its own venues like AAMAS and is also part of the AGT/EC one, it still considers itself part of the general AI community, and indeed publishes much in the general AAAI/IJCAI conferences.  Maybe this is an indication that the field still hasn’t reached the level of “being understood well enough” commonly needed for breaking away from the general AI community.

I was especially struck by Abe Othman using as a working definition of AI, “AI is whatever gets published at AAAI/IJCAI” similarly to Ariel Procaccia stating “in case you were wondering how one defines AI, my best definition is everything that might get published in AAAI/IJCAI”. These two  young bright stars in the field of AI made a point of using this definition, and even though they obviously used it in a somewhat tongue in cheek  manner, I think that they were trying to make a point.  (This is especially so since by the virtue of their own research both could have opted to call themselves Algorithmic-Game-Theorists and distanced themselves from the AI community.)  Discussing it with Jeff Rosenschein (who was also Ariel’s PhD advisor), he tended to think that they were acknowledging the community aspects of the scientific endeavor.  My own view is that they are expressing a confidence in the value and direction of the AI community — a confidence that the AI community did not always have.

My own point of view on the AI academic community comes mostly from looking at differences within the AGT/E community where AI and TCS researchers frolic together and seem to actually speak with each other.  In many cases they do the same type of work.  This is especially true for the stronger research which has both a compelling conceptual message and significant analysis.  (But weak papers from the two sides are often weak in their unique ways.)  Still, I can see different types of challenges driving the two communities.  The AI guys are drawn to ill-defined questions and try to define them it (or some aspects) better, while the TCS guys prefer clearer challenges and try to solve them better.  Even when working on similar issues, the AI guys will emphasize the question while the CS guys emphasize the answer.   The TCS guys often dislike the AI papers since they do not have any “meat”, and the AI guys often dislike the CS papers since they lack compelling questions but only give answers.

If I had to give my own definition for AI — the academic field rather than the basic concept — I would point to exactly the characteristic of having ill-defined questions:  The academic AI community is handling the sub-areas of conceptual AI (i.e. of mimicking aspects of human intelligence) that are not understood well enough as to have coherent and well-defined paradigms and questions.

Read Full Post »

Xtranormal advertisement for multi-unit auction paper

Heeding Rakesh’s call, and fascinated by xtranormal.com, I decided to try and explain why Shahar and me like our new paper (submitted to EC) so much, a point we do not seem to be able to explain by usual means.

Read Full Post »

Yahoo’s Key Scientific Challenges

Yahoo is offering graduate student support/prizes for those working on fields related to its set of “key scientific challenges”.   These include, among other areas, Computational Advertising, Algorithmic Economics, and Microeconomics and Market Design.  Applications are due March 11, 2011.

 

Read Full Post »