Thunder in the Khyber, pirates in the gulf of Aden, unrest in the Sudan and in bazaars from Cairo to Calcutta, rumors of the Mahdi. And, Richard Hannay nowhere to be found.

Meanwhile, in a little town in Germany, a workshop multidimensional mechanism design took place. This was the second of two workshops on mechanism design that are part of the Hausdorff’s institute special program on Mechanism Design. Full disclosure; I’m one of the organizers along with Arunava Sen and Rudolf Muller. Even more disclosure, Rudolf did most of the work.

First speaker was Dan Vincent, Rhodes scholar and perhaps the best prime minister Canada never had. Well, that remark needs some explanation. Rhodes scholars, typically aspire to high public office, so, you see, Dan, had he continued with rowing rather than economics, might have entered public life. Which makes one wonder about Barry Nalebuff as president.

Why the qualifier, Canadian? Well, Dan, like many famous American’s is, in fact, Canadian. Lones Smith, Jeroen Swinkels and Phil Reny are other examples. Insufficiently famous? John K. Galbraith, Michael J. Fox, Wayne Gretzky and Captain James Tiberius Kirk. Indeed, it is impossible for Canadians to be famous as Canadians unless they are named Pierre and have wives who sleep with Mick Jagger. They must become American.

Oddly enough, something of the same is true of English writers. Most famous English writers, dramatists and poets are not English. Wilde and Shaw were Irish. Burns and Doyle were Scotch. Conrad a Pole, Stoppard a Czech, Naipaul a West Indian Indian. Notice, no Canadians. But, I digress.

Dan’s presentation (joint work with Alejandro Mannelli) satisfyingly fills a gap in the literature. In a private values, one good environment every bayesian incentive compatible mechanism can be implemented in dominant strategies. Note the `every’ as opposed to the more limited `optimal’. Parenthetically, the organizers took an expansive view of the term multi-dimenisonal.

Sushil Bikhchandani’s (disclosure again: co-author) paper argued that Cremer-Mclean full extraction (a certain dental resonance) does not survive when agents have the opportunity acquire information.

Sergio Parreiras, gave a presentation on smooth ex-post implementation with a lot of mathematical machismo. In addition to showing that the JMMZ impossibility result extends to randomized social choice functions, he and Claudio Mezzeti show that the impossibility result depends on an imbalance between the dimension of the signal space and the range of possible outcomes. In particular, when signals are 2-dimensional but the set of outcomes lives in dimension that exceed 2N (where N is the number of agents), the impossibility result evaporates. Terms lie Lie bracket, Cauchy-Kovaleska conditions and Cartan-Kaehler theory were used. A shiver went down my spine.

Jason Hartline (a colleague) considered the problem of a monopolist with many distinct goods facing a single agent interested in buying at most one of the goods (unit demand). Valuations for each good are private and independent but not necessarily identically distributed. Let J(v,i) be the virtual value for the distribution of valuations for the i-th good. Here is a ridiculously simple pricing rule. Choose a price p(i) for good i so that the J(p(i),i)’s are equalized across goods. Surprisingly, for all possible distributions, the expected revenue from such a scheme is at least a third of the expected revenue of the optimal deterministic Bayesian incentive compatible mechanism. This is much better than some other simple minded schemes one might imagine. For example sell all the goods as a bundle. There are distributions where the expected revenue can be an arbitrarily small fraction of the maximum possible expected revenue.

Michal Schapira described an impossibility result about implementation in a computationally feasible way. There is a neat idea in the paper which irrespective of the main result is worth a read. Here is a high level and informal description. Take a problem class, C, in which instances are of size M (number of variables perhaps), say, that is known to be computationally hard. Pick out a subset, S, of the class. Might this subset of the class be computationally hard as well? Take an instance in the subset and fix the values of some of the variables. Choosing the remaining variables becomes an instance of the original class C, of size N < M. What if by this variable fixing for each instance in S, one can generate each instance in C of size N? Then S must be computationally hard as well. To top it off, there is an interesting connection to VC dimension. VC stands for Vapnik-Chervonenkis, and if you don’t know what it is, head for Wikipedia right now.

Cake time at the Institute calls, so I take your leave. As Roger Myerson says, calories into Theorems! The tale of the curious incident on the Drachenfells, Paul Milgrom’s entrepreneurial dreams, Arunava Sen’s brush with Brooke Shields and the debate about the correct number of references to prior work must wait.

Thunder in the Khyber, pirates in the gulf of Aden, unrest in the Sudan and in bazaars from Cairo to Calcutta, rumors of the Mahdi. And, Richard Hannay nowhere to be found.

Meanwhile, in a little town in Germany, a workshop on multidimensional mechanism design took place. This was the second of two workshops on mechanism design that are part of the Hausdorff institute’s special program on Mechanism Design. Full disclosure; I’m one of the organizers along with Arunava Sen and Rudolf Muller. Even more disclosure, Rudolf did most of the work.

Read the rest of this entry »

## Recent Comments