Archive for March, 2011

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 »

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 »

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 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 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:

Read Full Post »

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:

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 »

Older Posts »