Nemmers conference in honor of Paul Milgrom

A few days ago, Nortrhwestern hosted a conference in honor of  Paul Milgrom winning the Nemmers Prize.  (As reported here and here.) The speakers seem to be the A-list of Economists in Mechanism Design, and their talks slides, as well as a video of Milgrom’s talk, are on the web page.  Computer Scientists were not invited, but it seems that Lance Fortnow was still able to tweet from there gems like:

Preston McAfee: Left to their own devices computer scientists would recreate the Soviet Union

Susan Athey: CS still needs to catch up in auction theory (on why Microsoft hires economists)

Circulating Announcements

The following announcements have been circulating lately, with requests to circulate further, so I comply:

• Liverpool (the university) is looking for a chaired Professor  in “Economics and Computation”.
• The website for the 2010 workshop on computational social choice is up.

Israeli Computational Game Theory Seminar

The fifth Israeli Seminar on Computational Game Theory will be held on December 10th at Microsoft Israel R&D Center in Herzliya.  The speakers are: Dov Samet, Seffi Naor, Noga Alon, Svetlana Olenetsky, and Joe Halpern.

Facebook Hiring in AGT

A large number of AGT researchers work in just three large companies: Google, Microsoft, and Yahoo, mostly working on ad auctions.  From two or three data points, it seems that Facebook is now attempting to hire such researchers too (although maybe not in “research” roles).   Looking in Facebook’s “careers” page, they are indeed looking for an “advertising auction expert” whose requirements include “Expert knowledge of algorithmic game theory, auction theory, mechanism design and their applications to online advertising” as well as a Ph.D. in CS or OR.

I can well see the potential for Algorithmic Mechanism Design research in Facebook.  Facebook’s information about its users is enormous,  detailed, and lives within the context of their complex social network.  Making good use of this complex information seems to require another level of sophistication relative to today’s ad auctions.  Privacy issues are always there, and while Facebook has already had problems in that department, it seems that its users do not consider their “identity” to be too private.  I wonder if within a year or two we’ll start seeing research papers coming from Facebook too.

DARPA Netwrok Challenge

Despite my better judgement , I am fascinated by DARPA’s Network Challenge.  The basic idea is simple: on this Saturday, December 5th, at 10AM (EST),  ten large red weather balloons with be placed in various locations in the USA.  The first person to report the locations of all balloons wins $40K.  This seems to be an exercise in crowdsourcing, and it is not difficult to see various reasons why the US military may be interested in such an exercise.

If you want to win, the question seems to be how to get many potential balloon-sighters to report their findings to you rather than to someone else.  Offers of $1K for the first sighting of a balloon (conditioned on winning) came fast, soon to be trumped by $3K offers, which is within a factor of 4/3 from optimizing this approach.   Indeed the prize amount seems to be intentionally low, as to provide barriers to this natural monetary technique.  At this point, the edge of rationality, non-monetary rewards were started to be offered, like world peace or, my favorite, “use the winnings to create a giant flying cupcake built entirely out of balloons!“.  My own contribution (probably discovered independently by countless others) is the observation that the monetary technique is not really limited by the prize money: winning may have significant advertising value for the right kind of company, who may invest much larger amounts of money in attracting collaborators to its effort.

An analysis of possible approaches can be found here, including some thoughts on satellite or aerial surveys and on negative tactics (mis-report balloons to your competitors) and a link to a wiki.

ICS accepted papers

The accepted papers for ICS 2010 have just been announced.  Judging by the list of titles and abstracts, this is the most interesting list of accepted papers that I’ve seen in years.  So Hooray for the conceptualists as well as to the organizers.  Now we have to see if the actual papers match the promise of their abstract and title.

Many accepted papers are AGT-related:

• Leveraging Collusion in Combinatorial Auctions by Jing Chen, Silvio Micali, and Paul Valiant
• Guaranteeing Perfect Revenue From Perfectly Informed Players by Jing Chen, Avinatan Hassidim, and Silvio Micali
• A New Look at Selfish Routing by Christos Papadimitriou and Gregory Valiant
• Game Theory with Costly Computation by Joseph Halpern and Rafael Pass
• Adversarial Leakage in Games by Noga Alon, Yuval Emek, Michal Feldman, and Moshe Tennenholtz
• Beyond Equilibria: Mechanisms for Repeated Combinatorial Auctions by Brendan Lucier (see also this blog post).
• Playing games without observing payoffs by Michal Feldman, Adam Kalai and Moshe Tennenholtz
• Market Equilibrium under Separable, Piecewise-Linear, Concave Utilities by Vijay V. Vazirani and Mihalis Yannakakis
• Bounding Rationality by Discounting Time by Lance Fortnow and Rahul Santhanam
• Local Algorithms for Finding Interesting Individuals in Large Networks by Mickey Brautbar and Michael Kearns
• Circumventing the Price of Anarchy: Leading Dynamics to Good Behavior by Maria-Florina Balcan and Avrim Blum and Yishay Mansour
• Computational Complexity and Information Asymmetry in Financial Products by Sanjeev Arora, Boaz Barak, Markus Brunnermeier, Rong Ge.  (This paper has been much blogged about from Boingboing to the TCS blogosphere,  and elsewhere.)
• Reaching Consensus on Social Networks by Elchanan Mossel and Grant Schoenebeck

LPUs: game theory or psychology?

In a recent (guest) blog post, Yehuda Lindell makes fun of (or maybe just complains about) “applying game-theoretic principles to our work as academics”.  He lists several such strategic acts, starting with the well known principle of “least publishable unit” (LPU):

The first observation is that the “best strategy” is to write papers that are just good enough to get into the conference that you want, but no better. This way you minimize your work while maximizing your publications.

Even taking the totally cynical “rational” point of view, I doubt that this LPU strategy is “best” or even good.  The LPU strategy may indeed be optimal if you want to maximize the number of your publications, but not at all if you want to get hired, get promoted, get grants, or other selfish utility measures.  In most reasonable places, “paper counting”  – especially of conference papers — is rarely significant. Reputation (of author and of the venue), letters, even citation counts (and impact factors) are used instead — and these all do not fare well under the LPU strategy.

So why do so many researchers seem to follow this strategy to some extent?  Why do so many of us produce many mediocre papers rather than fewer good papers?  I think that the reason is not game-theoretic: most researchers who trade-off quality for quantity are not trying to cynically optimize their career.  They know that their many mediocre papers will fool no-one.  Well, almost no-one: they do manage to fool themselves.  Indeed producing a paper gives us a very concrete sense of achievement.  We can add it to our CV, count it, tell our spouse that we wrote it, and in general have something specific to show for our work.  It gives us the required psychological boost of success.   A fake one, unfortunately, like some drugs do.  The antidote: don’t fool yourself. Easier said than done, of course.

Guest Guest post from FOCS

[Noam: Since I didn't go to FOCS, I asked Shahar to write a guest blog post from there.]

[Shahar: Noam asked me to write a guest post on FOCS. However, Shaddin wanted to write a post so badly that I had to let him guest post in my own guest post.]

Guest Post by Shahar Dobzinski
Guest Guest Post by Shaddin Dughmi

When Shahar asked me on monday night to write this guest guest post, my first reaction was that I wish I knew ahead of time so that I would take notes. Since much of this is from memory, I apologize for any unintentional omissions or inaccuracies. Since this is an AGT blog, I will focus mostly on AGT-related papers.

This year FOCS is being held in downtown Atlanta, and the conference hotel is only a few blocks from Georgia Tech. The conference talks are all in the hotel conference center as usual, though the celebration on day 0 was located at the Lecraw Auditorium at Georgia Tech.

Saturday featured the celebration of the 50th anniversary of FOCS and the 20th anniversary of the ACO program at GATech. There were talks by four distinguished speakers: Richard Karp, Mihalis Yannakakis, Noga Alon, and Manuel Blum. All four talks were inpsiring. Manuel Blum’s talk on “Can TCS get a grip on Consciousness” was particularly entertaining and thought provoking. In the talk, Manuel chronicles his own personal journey towards understanding consciousness. The talk culminates with a description of “Global Workspace Theory” as a model of consciousness. Manuel draws concrete connections between this model and mathematical proofs, suggesting that TCS can benefit from models of consciousness as guides for high-level planning.

The conference talks were held in two adjacent conference rooms on the second floor of the conference hotel. Luckily, there was an adjacent conference being held on the same floor called “The Secrets of the Millionaire Mind”. The colorful characters from this conference occasionally ventured into the same lobbies as the FOCS audience, and doubtless managed to recruit many TCS graduate students who are fed up with meager stipends and left-over pizza.

There were two AGT sessions. Due to incurable jetlag, I unfortunately missed the first one on Monday morning. Luckily, however, all talks will be available online soon. Nevertheless, word around the conference lobby was that Amin Saberi’s talk on Convergence in local interaction games was fantastic. The second AGT session was monday afternoon, featuring three talks. The first talk was on Rationalizing Network Formation, where Kalyanaraman and Umans prove hardness results on inferring valuations of players in network formation games. I interpreted this as a hardness result for effective market research. The second talk in that session was on pricing strategies for Revenue Maximization. In this talk, the authors obtain improved lower and upper bounds on pricing strategies for revenue maximization when a limited number of items are sold to bidders with unknown subadditive valuations. The lower bounds apply to the previously studied static single-price, and they relax the model to one that allows prices to vary with time. An interesting question that was brought up after the talk was whether their results could be improved
by using a benchmark other than welfare. The third talk was on my paper with Shahar Dobzinski (the guest blogger one level up in the blogging tree), where we introduce a new class of truthful-in-expectation mechanisms and use it to get a truthful-in-expectation FPTAS for multi-unit auctions. We also show the first separation between truthfulness-in-expectation and universal truthfulness.

All in all, this FOCS was the usual mix of talks, good conversation, and blossoming collaborations. The southern hospitality was warm, and the sourthern food was an experience. As revealed in the business meeting, the next FOCS will be held in Las Vegas! In light of this choice of location, lets hope they tape the talks next year as well for those of us one roll of dice away from the big one!

Not a Journal

A recent blog post by Jeff Elly brought to my attention “NAJ Economics“, an overlay journal devoted to Economics that has been in operation for about eight years, although at pretty low volume.  ”NAJ” stands for “Not a Journal” (or the geek-wannabe GNU-like “NAJ aint a journal”), and the idea is that the set of (rather distinguished) editors choose papers that they like on the web, peer-review them, and publish links to the “reviewed” papers.  The way it works is that the editors pick what they want to review:  you can not submit your paper to NAJ, nor can you ask them not to review your paper once you’ve put it openly on the web.  The idea is that this gives a peer-reviewed publication: the author takes care of publication on the web, and NAJ provides the peer-review.    (I started thinking about “NAJ AGT” which could handle publication more elegantly by relying on the arXiv.  But then, it doesn’t seem that “NAJ economics” is a success story, so maybe not.)

At the same time, Daniel Lemire posts a 1987 “EWD” by Dijkstra going against the whole notion of trusting peer review too much.  Indeed, Dijkstra rarely published his work in the usual sense but rather mailed out photocopies of his hand-written writings, termed EWDs, to colleagues. While my sympathies (like those of Lemire)  are with this mode of publication, I’m afraid that few non-Turing-Award-winners will get their work noticed this way, so some mechanism for allocation of attention is still needed.

Theoretical Economics as Math

Eran Shmaya, in a beautiful recent blog post, adds some sociological angles to the economists’ never-ending introspection of whether their field is a science, where the starting point of such discussion is Popper’s falsifiability.  The discussion about whether economic theory has any significant prediction power has certainly picked up lately due to the financial crisis that convinced many people that the answer is “No”.  (With a variant taken by many micro-economists claiming that micro is fine and only macro-economics is a superstition.)

Whenever I hear these types of discussions about the prediction power economic theory, I always think about the irony that, as an algorithmic game-theorist, I am mostly interested in using economic theory as a branch of mathematics…  Arrow’s theorem is simply true, not falsifiable.  So is Meyrson’s expression for optimal auctions, as well as many other mathematical tidbits that we, computer scientists, pick up from economic theory.  We don’t really care how well these theorems relate to human situations, since we use them in different circumstances, those related to computer systems.  I often wish that theoretical economists would allow themselves to stray even farther away from the realities of their human subjects.

This is not to say that we, in algorithmic game theory, need not worry about how well our theories correspond with reality.  We should.  We have not really started doing so.   And, it’s getting high time we do.  But our concerns may be more like those of engineers rather than those of scientists.  From economics, I’m happy to just take the theory…