Let’s continue on the theme of secrecy from the last post with a recent GEB by a group of computer scientists. In standard mechanism design, there is either a lot of information revealed or there is a lot of trust placed in some mediator (which we call “the mechanism”). Consider a second-price auction. Either the auctioneer reveals everyone’s bids after bidding or the bidders must trust the auctioneer is not “making up” a second bid arbitrarily close to the highest bid, which the auctioneer certainly has an incentive to do. Revelation ex-post is worrying, though. If bidders are revealing their types, they may wish to shade or randomize their bids so that their competitors in the same industry do not learn what value they place on an object.
Micali, one of the coauthors of this paper, has a series of papers in the 1980s about “zero-knowledge” proofs, which essentially show a method for proving a statement to a verifier with high probability, but not giving the verifier details of how to do the proof. This new paper is a similar idea, applied to mechanism design. We want to find a mechanism that is strategically equivalent to the original mechanism, that preserves the privacy of the players (to the level of the original game – in the second-price auction, there is no way around revealing the “private” information that the ex-post winner had the highest private value), and that is not too computationally complex.
Let’s ignore complexity and focus on the first two criteria. A “private” deterministic mechanism is surprisingly simple. Let the action consist of reports of length k-bits; that is, if the action space is the integers 0 to 100, these numbers can be represented in binary using 7 bits. Let g(m1,m2) be the deterministic outcome function mapping messages (from 2 players, in this case) to outcomes. The mechanism creates a matrix of sealed envelopes containing g(m(i),m(j)), where the matrix is of size IxJ where I is the number of action available to player 1, and J for player 2. Player 1 is then given this matrix of envelopes and is allowed to permute the row however she wishes, but ensuring that the row containing m(i) is on top. Player 2 is then given this permuted matrix and is allowed to secretly permute the columns, but ensuring that m(j) is on the left. The mechanism then opens only the envelope on the top left. This gives away only information that would be known in the non-“private” mechanism (i.e., in a second-price auction, it would give away the value submitted by the loser and the fact that the winner submitted a higher value) and does not require anyone to trust a secret mediator.
Izmalkov et al do not particularly like this mechanism because it involves 2^(2k) envelopes, so as the action space grows, the “number of envelopes” gets very large very quickly. The authors use some well-known results in complexity theory to show that since the outcome function can be represented using only a fixed number of elementary operations on secret enveloped which encode each player’s action, there is a “not-too-complex” way to privately and verifiably implement any mechanism.
A nice result, then. My remaining comments have solely to do with style. I’m all for cross-disciplinary work, but I consider customs and traditions within a field to be a critical part of paradigmatic science. That is, economics and law and computer science and literary criticism all have certain styles in how research is presented, and those styles exist so that novel results can be efficiently transmitted to members of a given field. The results in this paper are simply presented in the style of a computer science conference paper. Sections of essay-like paragraphs, common in economics, are instead replaced with oddly mechanistic notes and side-comments. The action space is represented in terms of bit complexity instead of in the standard economic manner, and I don’t see anything that couldn’t have easily been “translated” into usual econ-talk. The majority of the paper discusses results in computational complexity that, frankly, are going to be much less interesting to the average GEB reader than the initial result on private-mechanism existence; these results on complexity are presented at the expense of the type of results an economic theorist would be most interested in. For instance, if the action space is a continuum, is there a “private” mechanism satisfying strategic equivalence? Who knows – it is never discussed. These types of issues really need to be hashed out before papers are published in the top journals in our field.
http://dspace-test.mit.edu/handle/1721.1/50634 (Final WP version published at MIT’s lovely repository of research. The published version is in GEB 2010.
A Fine Theorem 