“Nash Implementation with Partially Honest Individuals,” B. Dutta & A. Sen (2009)

Sometimes a lovely, unintuitive result seems a too simple once you see the proof. Here’s one, from Dutta and Sen, that I bet you didn’t expect.

Consider Nash implementability of social choice functions; that is, we want to know if, for some social choice correspondence (a mapping from preferences R to outcomes), there exists a game form whose only Nash equilibrium outcomes given preferences is in the social choice correspondence (scc). Maskin famously showed that, with three or more players, any social choice correspondence satisfying No Veto Power (if (n-1) of the players top-rank an outcome A, then the scc must select it) and Maskin Monotonicity (roughly, if the scc selects outcome A under preferences R, but not under R’, then at least one agent must reverse their ranking of a and some other outcome b). It turns out that Maskin Monotonicity is a super-strong assumption, actually: the scc must be dictatorial (Muller-Satterthwaite), and if it is a function, then the scc must be constant regardless of preferences (Saijo 1987, JET).

Dutta and Sen say, fine, but what if a single agent, whose identity is not known to the mechanism designer, has lexicographic preferences for honesty. That is, the agent maximizes her preferences while playing the designer’s chosen game form, but when two actions (here, the relevant action space is just revelation of the preference ordering) give the same outcome, and one of those actions is truthful, then the agent takes the truthful action. It turns out that this simple assumption allows any scc with three or more agents to be implemented!

The proof is simple if you know Maskin’s result. The game is the same as in Maskin: each agent’s strategy is to reveal the preference ordering of all agents, a recommended action, and an integer. As in Maskin, this is a game of complete information, so every agent but the designer knows other agent’s preference ordering; Matt Jackson has a paper on Bayesian implementability if you don’t like this assumption. If at least (n-1) reveals the same thing, and if the action A recommended is such that f(R)=A in the specified social choice correspondence, then that action is chosen. Otherwise, the action announced by the agent who chose the highest integer is implemented.

No veto power alone gets us everything except ensuring that there is no equilibrium where every agent deviates to some false preference orderings R’ and action a’. To show there is no such equilibrium, we can use Maskin Monotonicity. Alternatively, just note that with lexicographic honesty, such a deviation cannot be an equilibrium. By the (n-1) part of the game outcome above, the honest agent can deviate to (R,a) and not change the outcome. In that case, he prefers the honest revelation (R,a). So everyone revealing (R’,a’) is not an equilibrium. This is literally the whole proof. Basically, Maskin’s proof involved a snitch who is incentivized by monotonicity to deviate and entire the integer subgame when everyone reveals (R’,a’). Here, lexicographic honesty does the same job.

A few final notes: Dutta and Sen, of course, prove many more results, particularly for the more difficult problem of two-agent implementability; the general difficulty there is that one person deviates, since there are only two agents, you don’t know who deviated as the designer. They also show, with some reasonable restrictions on mechanism types, that if even there is an epsilon chance that a single agent may have lexicographic honesty, that is enough to allow existence of a mechanism implementing any scc. This paper does not get around a well-known objection to the Maskin mechanism, however: the strategy space is not compact. In particular, the integers are unbounded. Lombardi and Yoshihara (2011) show that some reductions in the strategy space far weaker than requiring compactness and requiring that agents know only their own preferences nonetheless drastically change what is Nash implementable with lexicographically honest players.

http://www2.warwick.ac.uk/fac/soc/economics/research/papers_2009/twerp_920.pdf (2009 Working Paper; hat tip to Dimitrios Diamantaras for the reference)


4 thoughts on ““Nash Implementation with Partially Honest Individuals,” B. Dutta & A. Sen (2009)

  1. Jonathan Weinstein says:

    I thought integer games went out of fashion a long time ago; one famous critique (due to Jackson, I’m pretty sure) was that in many such mechanisms the equilibrium strategies are weakly dominated. Then there was a literature on implementation in undominated strategies. Are the eq strategies weakly dominated here?

    • afinetheorem says:

      I believe they are for exactly the same reason as non-partially truthful papers.

  2. First, thanks for the hat-tip. I do have two nits to pick. To start with the really trivial one, my last name ends in “ras”, not “ris”. By far more important, however, is that you have presented Maskin monotonicity as much more restrictive than it is for social choice correspondences. In a domain of classical exchange economies, for example, such a non-dictatorial SCC as the constrained Walrasian SCC is Maskin Monotonic, and similarly for a classical domain of economies with private and public goods, in which the constrained Lindahl SCC is Maskin monotonic. There are other examples of non-dictatorial SCCs that are Maskin monotonic, too. Of course, that is not to say that Maskin monotonicity is easy to satisfy, but it is not as restrictive as you made it appear. You are quite right in celebrating these implementation theory results that employ partial honesty to move a little away from the necessity of Maskin monotonicity in Nash implementation.

    • afinetheorem says:

      Apologies for the mistake with the name! I’ve fixed it.

      I agree completely with you on Maskin Monotonicity in a lot of economic concepts, but there are also a lot of interesting sccs that are ruled out; the only point I wanted to make is that the domain of preferences really needs to be limited to implement anything.

Comments are closed.

%d bloggers like this: