Thread by @ShengwuLi

New working paper! Consider the decision problem, "For this choice rule, does there exist a strategy-proof mechanism?" This is an easy problem; by the revelation principle, we just need to check that the direct mechanism is IC, which takes linear time. (thread) #EconTwitter

Now consider the problem, "For this choice rule, does there exist an obviously strategy-proof (OSP) mechanism?" OSP depends on the extensive form, so the class of candidate mechanisms is combinatorially complex.

A prior result establishes that, if such a mechanism exists, it can be verified in polynomial time. (So the decision problem is in the complexity class NP.) But can we decide the problem quickly? A brute force search through all the mechanisms would take exponential time.

We provide a polynomial-time algorithm that, given a choice rule, determines whether there exists an OSP mechanism. It also constructs that mechanism, if it exists! This implies that the decision problem is in P.

This is joint work with Louis Golowich, a Harvard undergraduate math/CS major, who deserves the lion's share of the credit.

\thread

drive.google.com/file/d/1toESMZ…