I’m attending this year’s SODA conference, in Austin. It has been blogged about widely (here, here, here, and here), as well as continuously tweeted. The buzz here is good: it’s a very large conference for TCS (over 300 attendees), and with three parallel sessions, there is almost always something interesting to listen too. I met many old friends as well as got to meet many of the up and coming younger generation which I haven’t met before.
There have many many talks related to algorithmic game theory this SODA. Session “5A” was more or less devoted to algorithmic mechanism design. The first talk was a merger of three separate papers that all basically proved that “VCG-based” combinatorial auctions cannot approximate welfare well even on very restricted valuations for which algorithmically approximation is easy. The techniques are combinatorial focusing on the VC-dimension and extensions for it. While this is bad news especial since “VCG-based” mechanisms are still the only known generic ones having incentive compatibility, these results can not rule out other types of incentive compatible mechanisms. The talk was split between representitives of two of the merged papers, Dave Buchfuhrer and Shaddin Dughmi, who emphasized different variants of the lower bound: Dave talked about the very simple valuations (additive-with-budget-limit) for which the lower bound holds, while Shaddin talked about more general classes (like sub-modular) for which a generic reduction is given and emphasized that the lower bound applies also to some family of randomized mechanisms. I’ve previously shortly posted about three of the other talks in this session: “price of anarchy for greedy auctions“, “incentive compatible budget elicitation in multi-unit auctions”, and “pricing randomized allocations” (with the talk explaining and motivating the model details that I didn’t fully get from skimming the first version of the paper). The talk on “utilitarian mechanism design for multi-objective optimization” considered a mechanism design setting in a graph where there are two different “weights” on each edge (“cost” and “length”) and the goal is to minimize the sum of the costs, under a constraint that upper bounds the sum of the lengths.
All the talks in this session were very good, I thought. The usual question of what can a speaker do in his allotted 20 minutes seems to be a bit more difficult in algorithmic game theory due to the double background needed. It seems that the choice of most of the speakers was the “explain and advertise your result”, rather than “discuss the basic ingredients of your technique” which was taken by the talk on multi-objective optimization. An approach that was not taken by anyone is “motivate and discuss your model” which is the natural one in economic theory. Such discussion of the model was called for in many of the papers since there are delicate modeling issues involved in them, but it is probably difficult-to-impossible to take this approach in a 20 minute talk while leaving time for the required background as well as even the statement of the results.
Of the other talks I’ve heard, I was especially intrigued by the talk “On the possibility of faster SAT algorithms” by Mihai Patrascu and Ryan Williams which under very strict assumptions about the running time needed to solve SAT on CNFs (regrading the constant in 
SODA 2011 is in SF. After a prolonged voting process in the business meeting, it was decided that the SODA 2012 will be in Kyoto rather than in Rome, Barcelona, Prague, or NYC. If only every conference had such an array of alternatives.
Turing's Invisible Hand 
what is SODA conference? is it like killing games?
is it true that was decided that the SODA 2012 will be in Kyoto ?
thanks
killing games
[…] basic open problem of AMD, that of reconciling computational complexity with incentives, there has been some progress, but the basic challenge still seems beyond our […]