Monday, September 23, 2024

A 40 year old proof about top trading cycles is corrected (by two Berkeley grad students)

 Science (and math) can be self-correcting, sometimes slowly.  Here's an article that corrects the first proof that the top trading cycles algorithm is group strategy proof.  That's a true result, with multiple subsequent proofs.  But apparently the first proof presented wasn't the best one.  That's good to know.

One reason this may have taken a long time to spot is that the result is correct, and that there are subsequent proofs that connect the result to properties of other mechanisms.  

Will Sandholtz and Andrew Tai, the authors, did this work as Ph.D. students at UC Berkeley. (good for them!)

Group incentive compatibility in a market with indivisible goods: A comment  by Will Sandholtz and Andrew Tai

"Highlights

• Bird (1984), first to show top trading cycles is group strategy-proof, has errors.

•We present corrected results and proofs.

•We present a novel proof of strong group strategy-proofness without non-bossiness.

"Abstract: We note that the proofs of Bird (1984), the first to show group strategy-proofness of top trading cycles (TTC), require correction. We provide a counterexample to a critical claim and present corrected proofs in the spirit of the originals. We also present a novel proof of strong group strategy-proofness using the corrected results."

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.