FOCS Accepted Papers and ITCS Call For Papers

The list of accepted papers for FOCS 2012 is out.  As always, there are lots of interesting titles on the list.  By my count, three of the accepted papers are explicitly in the area of Game Theory or Economics:

• The Exponential Mechanism for Social Welfare: Private, Truthful, and Nearly Optimal
  Zhiyi Huang and Sampath Kannan
• Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to Welfare Maximization
  Yang Cai and Constantinos Daskalakis and S. Matthew Weinberg
• Concave Generalized Flows with Applications to Market Equilibria
  Laszlo A. Vegh

The following five papers are on closely related topics.

• A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint
  Yuval Filmus and Justin Ward
• A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
  Niv Buchbinder and Moran Feldman and Joseph (Seffi) Naor and Roy Schwartz
• The Dynamics of Influence Systems
  Bernard Chazelle
• Online Matching with Stochastic Rewards
  Aranyak Mehta and Debmalya Panigrahi
• Matching with Our Eyes Closed
  Gagan Goal and Pushkar Tripathi

This year represents a pretty noticeable dip in the number of accepted Algorithmic Game Theory/Economics papers compared to the last two years of STOC and FOCS.  I’m curious if this stems from a dip in the number of submissions related to Game Theory or Economics (possibly linked to the vastly greater number of papers in EC this year, though it seems doubtful that a large number of FOCS papers in prior years had been rejected from the previous EC), or if the percentage of accepted AGT/E papers is significantly lower in this FOCS than in recent history.  (In the latter case, I’m inclined to attribute it to random fluctuation rather than conscious bias, especially considering who the program committee chair was!)

In other news, the Call for Papers for ITCS 2013 was announced yesterday.  Now in its fourth year, ITCS (formerly known as ICS) is a conference that seeks to promote research in theoretical computer science that carries a strong conceptual message.  In its first three years, the conference has been very friendly to Algorithmic Game Theory and Economics research, and some excellent papers have appeared there.  (See my blog post reporting on this year’s ITCS, for example.)  This year I’m chairing the PC, and we’ve decided to adopt EC’s policy allowing authors to designate their submission as a working paper, meaning that the conference proceedings will contain only a one-page abstract (together with a link to the full paper) rather than the paper itself.  This helps with the dilemma faced by authors who want to present their research in a CS conference and then submit it to an Economics journal.  Unlike EC in past years, authors selecting the working-paper option do not forfeit their eligibility for the Best Student Paper award.  (There is no Best Paper award at ITCS.)  I hope many of the readers of this blog will submit some of their work!

More controversially, the ITCS call for papers includes the option of submitting work that is previously published or has been accepted for publication, e.g. in a journal, provided this work has never been presented at a CS conference before.  (Nor has it been accepted, or simultaneously submitted, to such a conference.)  This policy is primarily aimed at helping out with some of the dilemmas faced by authors who work on the interface of TCS and the physical and biological sciences, but it may affect some authors working at the TCS interface with social sciences as well.  At the very least, it will be interesting to see how many submissions we receive under this new policy, and what research areas they come from.

Advertisement

Read Full Post »

Game theory and the bomb

Today’s online edition of the Israeli newspaper Haaretz features an op-ed by the journalist Ari Shavit (I actually know him personally, but of course all Israelis know each other). Its title is “Game theory and the bomb”. Which bomb? The hypothetical Iranian nuclear bomb. Shavit summarizes a discussion with the retired general Yitzhak Ben Israel. The latter observed that an Israeli military strike against Iran may speed up rather than slow down the development of the Iranian nuclear arsenal. His argument is that after the strike, the fear of bringing about a military strike will no longer hold the Iranians back. Of course a strike may also be successful in delaying the bomb, but its outcome is uncertain.

The crucial paragraph, which gives the article its name, is puzzling. It loosely translates as follows:

“No one … can predict the outcome of action or inaction. But when there is uncertainty, the guiding principle should be the one defined by the father of game theory, John von Neumann. The Jewish mathematician, who was one of the leaders of the Manhattan project, argued that in critical situations where you do not know the outcome, you should not maximize benefit but rather minimize loss in case of failure. If a strike hastens the bomb then Israel would pay the maximum price. Therefore, via mathematical analysis, Israel must choose to avoid a strike.”

QED. I found it amusing that Shavit points out that von Neumann was Jewish, as if that makes him uniquely qualified to save the Jewish state via his mathematical insights. More importantly, this has got to be the most informal “mathematical analysis” I have ever seen. It also seems fundamentally flawed. von Neumann’s Maxmin strategies deal, in a sense, with uncertainty about the other player’s intentions, and therefore work under the assumption that the other player plays adversarially (the game may not be zero-sum). It seems that Shavit, and presumably Ben Israel, are confusing this type of uncertainty with the uncertainty that comes from a move by nature (throwing dice to determine the outcome of a strike).

Any ideas on how to formalize Shavit’s argument, or whether it makes any sense at all, for that matter? To give you a bit of incentive, the first successful solution will receive the Nobel peace prize.

Read Full Post »

Is game theory useful?

Al Roth recently recounted an amusing story about a seminar where he gave a talk on market design. His talk was followed by a talk by Ariel Rubinstein, who argued (as he often does) that game theory is not useful. When asked about Roth’s work, Rubinstein reportedly answered: “Oh, Al’s stuff is useful alright. But it’s not game theory.”

I guess the answer to the question “is game theory useful” depends on how you define “game theory”, and how you define “useful” (fortunately the word “is” is clear). Rubinstein has a point though. Take kidney exchange for example. Arguably the most useful results, which inform deployed applications that are saving lives, deal with efficient exchanges and algorithms for computing them. In contrast, game theoretic results are more speculative at the moment.

Nevertheless, I do think that game theory is useful. A recent line of work on security games, which is most associated with Milind Tambe’s group at USC, is a case in point (which seems to provide a counterexample to the specifics of Rubinstein’s argument). Strangely enough, it seems that this line of work is not yet well-known outside the AI community. (I realized this last week when, during AAMAS, I bumped into a group of prominent theory guys who accidentally wandered into the conference while trying to escape an EC workshop. Reeling from culture shock, they wanted to know what this AAMAS thing was anyway, and what all those AI people were doing. Security games is one of the hottest topics in AAMAS in recent years, so it came up.) Anyway, IMHO work on security games is one of the few examples of research coming out of algorithmic economics that is directly making the world a better place (kidney exchange is another example), so it deserves some discussion.

To understand security games one must know a bit about Stackelberg games. A Stackelberg game typically has two players, a leader and a follower. The leader commits to a strategy, and the follower selects a best response. For example, consider the following game.

1,1	3,0
0,0	2,1

The only (mixed) Nash equilibrium is (up,left). However, by committing to down, the row player can get the column player to play right, thereby increasing his own payoff from 1 to 2. An even higher payoff of 2.5 can be guaranteed by committing to a mixed strategy that plays down with probability slightly greater than 0.5. The computation of optimal strategies to commit to was first explored in an EC’06 paper by Conitzer and Sandholm.

Now, suppose you are in charge of airport security. You must decide how to deploy patrols, where to point security cameras, etc. Potential attackers can observe your (possibly randomized) policy and respond accordingly (by choosing which targets to attack). Therefore, you are playing a (Bayesian) Stackelberg game where you are the leader, and the attacker is the follower. The main technical challenge is the computation of good strategies for the leader despite the huge strategy space, and the solutions, published in scores of AAAI/IJCAI/AAMAS papers, tend to rely on heuristic mixed integer programming techniques. Amazingly, these algorithms now run security for LA International Airport (LAX), the federal air marshals, and the coast guard!

Should we be worried? I was, initially. After all, game theory doesn’t really work, does it? I was able to dig up a 2007 Newsweek story, which I read at the time. Here is a scary quote:

Now all airport security officials have to do is press a button labeled RANDOMIZE, and they can throw a sort of digital cloak of invisibility over where they place the cops’ antiterror checkpoints on any given day.

Wow, RANDOMIZE; truly futuristic technology! One can only hope that the relevant security experts and decision makers have a better grasp of the details of the game-theoretic approach and the assumptions that are being made. In any case, I gathered from Tambe that the above security forces have their ways of reliably comparing methods, and the game theoretic methods outperformed their previously used methods.

But wait, to compute an optimal strategy to commit to we need to see the game; where do the payoffs come from? Apparently there is a vast literature on risk analysis, and there are people whose job it is to come up with these numbers. Hold on, can the attacker actually observe the defender’s strategy? Air Marshals for example typically work undercover; should the air marshals identify themselves to potential terrorists to justify the Stackelberg model?!

These seem like reasonable concerns, but the experience of the last few years shows that the approach works and the issues are solvable. If that doesn’t count as both “game theory” and “useful”, I don’t know what does.

Read Full Post »