IDEAS home Printed from https://ideas.repec.org/p/kue/epaper/e-19-012.html
   My bibliography  Save this paper

Menu Mechanisms

Author

Listed:
  • Andrew MACKENZIE
  • Yu ZHOU

Abstract

We investigate menu mechanisms: dynamic mechanisms where at each history, an agent selects from a menu of his possible assignments. In comparison to direct mechanisms, menu mechanisms offer better privacy to participants; we formalize this with a novel notion of mechanism informativeness. We consider both ex-post implementation and full implementation, for both subgame perfection and a strengthening of dominance that covers off-path histories, and provide conditions under which menu mechanisms provide these implementations of rules. Our results cover a variety of environments, including elections, marriage, college admissions, auctions, labor markets, matching with contracts, and object allocation.

Suggested Citation

  • Andrew MACKENZIE & Yu ZHOU, 2020. "Menu Mechanisms," Discussion papers e-19-012, Graduate School of Economics , Kyoto University.
    • Handle: RePEc:kue:epaper:e-19-012
    as

    Download full text from publisher

    File URL: http://www.econ.kyoto-u.ac.jp/dp/papers/e-19-012.pdf
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Klijn, Flip & Pais, Joana & Vorsatz, Marc, 2019. "Static versus dynamic deferred acceptance in school choice: Theory and experiment," Games and Economic Behavior, Elsevier, vol. 113(C), pages 147-163.
    2. Moore, John & Repullo, Rafael, 1988. "Subgame Perfect Implementation," Econometrica, Econometric Society, vol. 56(5), pages 1191-1220, September.
    3. Ehlers, Lars & Hafalir, Isa E. & Yenmez, M. Bumin & Yildirim, Muhammed A., 2014. "School choice with controlled choice constraints: Hard bounds versus soft bounds," Journal of Economic Theory, Elsevier, vol. 153(C), pages 648-683.
    4. Chambers,Christopher P. & Echenique,Federico, 2016. "Revealed Preference Theory," Cambridge Books, Cambridge University Press, number 9781107087804, October.
    5. Battigalli, Pierpaolo & Siniscalchi, Marciano, 2007. "Interactive epistemology in games with payoff uncertainty," Research in Economics, Elsevier, vol. 61(4), pages 165-184, December.
    6. Barbera, Salvador & Jackson, Matthew O. & Neme, Alejandro, 1997. "Strategy-Proof Allotment Rules," Games and Economic Behavior, Elsevier, vol. 18(1), pages 1-21, January.
    7. Inácio Bó & Rustamdjan Hakimov, 2020. "Iterative Versus Standard Deferred Acceptance: Experimental Evidence," The Economic Journal, Royal Economic Society, vol. 130(626), pages 356-392.
    8. Ashlagi, Itai & Gonczarowski, Yannai A., 2018. "Stable matching mechanisms are not obviously strategy-proof," Journal of Economic Theory, Elsevier, vol. 177(C), pages 405-425.
    9. Crawford, Vincent P & Knoer, Elsie Marie, 1981. "Job Matching with Heterogeneous Firms and Workers," Econometrica, Econometric Society, vol. 49(2), pages 437-450, March.
    10. Sprumont, Yves, 1991. "The Division Problem with Single-Peaked Preferences: A Characterization of the Uniform Allocation Rule," Econometrica, Econometric Society, vol. 59(2), pages 509-519, March.
    11. Marx, Leslie M. & Swinkels, Jeroen M., 2000. "Order Independence for Iterated Weak Dominance," Games and Economic Behavior, Elsevier, vol. 31(2), pages 324-329, May.
    12. , R., 2010. "Nash implementation with little communication," Theoretical Economics, Econometric Society, vol. 5(1), January.
    13. moldovanu, benny & ,, 2019. "Abortions, Brexit and Trees," CEPR Discussion Papers 14183, C.E.P.R. Discussion Papers.
    14. Arribillaga, R. Pablo & Massó, Jordi & Neme, Alejandro, 2023. "All sequential allotment rules are obviously strategy-proof," Theoretical Economics, Econometric Society, vol. 18(3), July.
    15. Lars-Gunnar Svensson, 1999. "Strategy-proof allocation of indivisible goods," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 16(4), pages 557-567.
    16. Dirk Bergemann & Stephen Morris, 2012. "Robust Mechanism Design," World Scientific Book Chapters, in: Robust Mechanism Design The Role of Private Information and Higher Order Beliefs, chapter 2, pages 49-96, World Scientific Publishing Co. Pte. Ltd..
    17. Yuichiro Kamada & Fuhito Kojima, 2015. "Efficient Matching under Distributional Constraints: Theory and Applications," American Economic Review, American Economic Association, vol. 105(1), pages 67-99, January.
    18. Glazer, Jacob & Rubinstein, Ariel, 1996. "An Extensive Game as a Guide for Solving a Normal Game," Journal of Economic Theory, Elsevier, vol. 70(1), pages 32-42, July.
    19. Battigalli Pierpaolo & Siniscalchi Marciano, 2003. "Rationalization and Incomplete Information," The B.E. Journal of Theoretical Economics, De Gruyter, vol. 3(1), pages 1-46, June.
    20. Roth, Alvin E & Xing, Xiaolin, 1997. "Turnaround Time and Bottlenecks in Market Clearing: Decentralized Matching in the Market for Clinical Psychologists," Journal of Political Economy, University of Chicago Press, vol. 105(2), pages 284-329, April.
    21. Eric Maskin, 1999. "Nash Equilibrium and Welfare Optimality," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 66(1), pages 23-38.
    22. Shengwu Li, 2017. "Obviously Strategy-Proof Mechanisms," American Economic Review, American Economic Association, vol. 107(11), pages 3257-3287, November.
    23. Shapley, Lloyd & Scarf, Herbert, 1974. "On cores and indivisibility," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 23-37, March.
    24. Pycia, Marek & Unver, Utku, 2017. "Incentive compatible allocation and exchange of discrete resources," Theoretical Economics, Econometric Society, vol. 12(1), January.
    25. Carlos Alós-Ferrer & Klaus Ritzberger, 2016. "The Theory of Extensive Form Games," Springer Series in Game Theory, Springer, number 978-3-662-49944-3, June.
    26. Marek Pycia & Peter Troyan, 2023. "A Theory of Simplicity in Games and Mechanism Design," Econometrica, Econometric Society, vol. 91(4), pages 1495-1526, July.
    27. Satterthwaite, Mark Allen, 1975. "Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions," Journal of Economic Theory, Elsevier, vol. 10(2), pages 187-217, April.
    28. Yamato Takehiko, 1993. "Double Implementation in Nash and Undominated Nash Equilibria," Journal of Economic Theory, Elsevier, vol. 59(2), pages 311-323, April.
    29. James Schummer & Rodrigo A. Velez, 2021. "Sequential Preference Revelation in Incomplete Information Settings," American Economic Journal: Microeconomics, American Economic Association, vol. 13(1), pages 116-147, February.
    30. Mackenzie, Andrew, 2018. "A revelation principle for obviously strategy-proof implementation," Research Memorandum 014, Maastricht University, Graduate School of Business and Economics (GSBE).
    31. , & , & ,, 2007. "Secure implementation," Theoretical Economics, Econometric Society, vol. 2(3), September.
    32. Alex Gershkov & Benny Moldovanu & Xianwen Shi, 2017. "Optimal Voting Rules," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 84(2), pages 688-717.
    33. , Emin & , Bumin & , Ali, 2013. "Effective affirmative action in school choice," Theoretical Economics, Econometric Society, vol. 8(2), May.
    34. John William Hatfield & Paul R. Milgrom, 2005. "Matching with Contracts," American Economic Review, American Economic Association, vol. 95(4), pages 913-935, September.
    35. Segal, Ilya, 2007. "The communication requirements of social choice rules and supporting budget sets," Journal of Economic Theory, Elsevier, vol. 136(1), pages 341-378, September.
    36. Barbera, Salvador & Sonnenschein, Hugo & Zhou, Lin, 1991. "Voting by Committees," Econometrica, Econometric Society, vol. 59(3), pages 595-609, May.
    37. Takamiya, Koji, 2001. "Coalition strategy-proofness and monotonicity in Shapley-Scarf housing markets," Mathematical Social Sciences, Elsevier, vol. 41(2), pages 201-213, March.
    38. Eilat, Ran & Eliaz, Kfir & Mu, Xiaosheng, 2021. "Bayesian privacy," Theoretical Economics, Econometric Society, vol. 16(4), November.
    39. Sophie Bade, 2020. "Random Serial Dictatorship: The One and Only," Mathematics of Operations Research, INFORMS, vol. 45(1), pages 353-368, February.
    40. Gradwohl, Ronen & Smorodinsky, Rann, 2017. "Perception games and privacy," Games and Economic Behavior, Elsevier, vol. 104(C), pages 293-308.
    41. Escudé, Matteo & Sinander, Ludvig, 2020. "Strictly strategy-proof auctions," Mathematical Social Sciences, Elsevier, vol. 107(C), pages 13-16.
    42. Saijo, Tatsuyoshi & Yamato, Takehiko, 2007. "Secure Implementation―Theory and Experiments―," Economic Review, Hitotsubashi University, vol. 58(2), pages 122-135, April.
    43. Pearce, David G, 1984. "Rationalizable Strategic Behavior and the Problem of Perfection," Econometrica, Econometric Society, vol. 52(4), pages 1029-1050, July.
    44. Ning Sun & Zaifu Yang, 2014. "An Efficient and Incentive Compatible Dynamic Auction for Multiple Complements," Journal of Political Economy, University of Chicago Press, vol. 122(2), pages 422-466.
    45. Demange, Gabrielle & Gale, David & Sotomayor, Marilda, 1986. "Multi-Item Auctions," Journal of Political Economy, University of Chicago Press, vol. 94(4), pages 863-872, August.
    46. Haluk I. Ergin, 2002. "Efficient Resource Allocation on the Basis of Priorities," Econometrica, Econometric Society, vol. 70(6), pages 2489-2497, November.
    47. Fadel, Ronald & Segal, Ilya, 2009. "The communication cost of selfishness," Journal of Economic Theory, Elsevier, vol. 144(5), pages 1895-1920, September.
    48. William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, March.
    49. Mark A. Satterthwaite & Hugo Sonnenschein, 1981. "Strategy-Proof Allocation Mechanisms at Differentiable Points," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 48(4), pages 587-597.
    50. Mackenzie, Andrew, 2020. "A revelation principle for obviously strategy-proof implementation," Games and Economic Behavior, Elsevier, vol. 124(C), pages 512-533.
    51. Lawrence M. Ausubel, 2006. "An Efficient Dynamic Auction for Heterogeneous Commodities," American Economic Review, American Economic Association, vol. 96(3), pages 602-629, June.
    52. John William Hatfield & Scott Duke Kominers & Alexander Westkamp, 2021. "Stability, Strategy-Proofness, and Cumulative Offer Mechanisms [Stability and Incentives for College Admissions with Budget Constraints]," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 88(3), pages 1457-1502.
    53. Lawrence M. Ausubel, 2004. "An Efficient Ascending-Bid Auction for Multiple Objects," American Economic Review, American Economic Association, vol. 94(5), pages 1452-1475, December.
    54. Shimoji, Makoto & Watson, Joel, 1998. "Conditional Dominance, Rationalizability, and Game Forms," Journal of Economic Theory, Elsevier, vol. 83(2), pages 161-195, December.
    55. Battigalli, Pierpaolo, 2003. "Rationalizability in infinite, dynamic games with incomplete information," Research in Economics, Elsevier, vol. 57(1), pages 1-38, March.
    56. Rothkopf, Michael H & Teisberg, Thomas J & Kahn, Edward P, 1990. "Why Are Vickrey Auctions Rare?," Journal of Political Economy, University of Chicago Press, vol. 98(1), pages 94-109, February.
    57. Ronen Gradwohl, 2018. "Privacy in implementation," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 50(3), pages 547-580, March.
    58. Saijo, Tatsuyoshi & Tatamitani, Yoshikatsu & Yamato, Takehiko, 1996. "Toward Natural Implementation," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 37(4), pages 949-980, November.
    59. Hatfield, John William & Kojima, Fuhito, 2009. "Group incentive compatibility for matching with contracts," Games and Economic Behavior, Elsevier, vol. 67(2), pages 745-749, November.
    60. Kamada, Yuichiro & Kojima, Fuhito, 2018. "Stability and strategy-proofness for matching with constraints: a necessary and sufficient condition," Theoretical Economics, Econometric Society, vol. 13(2), May.
    61. Kelso, Alexander S, Jr & Crawford, Vincent P, 1982. "Job Matching, Coalition Formation, and Gross Substitutes," Econometrica, Econometric Society, vol. 50(6), pages 1483-1504, November.
    62. Yasushi Kawase & Keisuke Bando, 2021. "Subgame perfect equilibria under the deferred acceptance algorithm," International Journal of Game Theory, Springer;Game Theory Society, vol. 50(2), pages 503-546, June.
    63. Roger B. Myerson, 1981. "Optimal Auction Design," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 58-73, February.
    64. Penta, Antonio, 2015. "Robust dynamic implementation," Journal of Economic Theory, Elsevier, vol. 160(C), pages 280-316.
    65. Kojima, Fuhito, 2010. "Impossibility of stable and nonbossy matching mechanisms," Economics Letters, Elsevier, vol. 107(1), pages 69-70, April.
    66. Umut Dur & Scott Duke Kominers & Parag A. Pathak & Tayfun Sönmez, 2018. "Reserve Design: Unintended Consequences and the Demise of Boston’s Walk Zones," Journal of Political Economy, University of Chicago Press, vol. 126(6), pages 2457-2479.
    67. Gibbard, Allan, 1973. "Manipulation of Voting Schemes: A General Result," Econometrica, Econometric Society, vol. 41(4), pages 587-601, July.
    68. Elliott Peranson & Alvin E. Roth, 1999. "The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design," American Economic Review, American Economic Association, vol. 89(4), pages 748-780, September.
    69. Alvin E. Roth, 1982. "The Economics of Matching: Stability and Incentives," Mathematics of Operations Research, INFORMS, vol. 7(4), pages 617-628, November.
    70. Paul Milgrom & Ilya Segal, 2020. "Clock Auctions and Radio Spectrum Reallocation," Journal of Political Economy, University of Chicago Press, vol. 128(1), pages 1-31.
    71. Andreas Kleiner & Benny Moldovanu, 2017. "Content-Based Agendas and Qualified Majorities in Sequential Voting," American Economic Review, American Economic Association, vol. 107(6), pages 1477-1506, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Catonini, Emiliano & Xue, Jingyi, 2020. "Local Dominance," Economics and Statistics Working Papers 1-2021, Singapore Management University, School of Economics.
      • Emiliano Catonini & Jingyi Xue, 2020. "Local Dominance," Papers 2012.14432, arXiv.org, revised Apr 2023.
    2. Gian Caspari & Manshu Khanna, 2021. "Non-Standard Choice in Matching Markets," Papers 2111.06815, arXiv.org, revised Aug 2024.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Marek Pycia & Peter Troyan, 2023. "A Theory of Simplicity in Games and Mechanism Design," Econometrica, Econometric Society, vol. 91(4), pages 1495-1526, July.
    2. Scott Duke Kominers & Alexander Teytelboym & Vincent P Crawford, 2017. "An invitation to market design," Oxford Review of Economic Policy, Oxford University Press and Oxford Review of Economic Policy Limited, vol. 33(4), pages 541-571.
    3. Raghavan, Madhav, 2020. "Influence in private-goods allocation," Journal of Mathematical Economics, Elsevier, vol. 89(C), pages 14-28.
    4. Mackenzie, Andrew, 2020. "A revelation principle for obviously strategy-proof implementation," Games and Economic Behavior, Elsevier, vol. 124(C), pages 512-533.
    5. Jagadeesan, Ravi & Kominers, Scott Duke & Rheingans-Yoo, Ross, 2018. "Strategy-proofness of worker-optimal matching with continuously transferable utility," Games and Economic Behavior, Elsevier, vol. 108(C), pages 287-294.
    6. Ryuji Sano, 2021. "Dynamic communication mechanism design," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 57(1), pages 163-180, July.
    7. Hafalir, Isa E. & Kojima, Fuhito & Yenmez, M. Bumin, 2022. "Interdistrict school choice: A theory of student assignment," Journal of Economic Theory, Elsevier, vol. 201(C).
    8. Bó, Inácio & Hakimov, Rustamdjan, 2022. "The iterative deferred acceptance mechanism," Games and Economic Behavior, Elsevier, vol. 135(C), pages 411-433.
    9. Atila Abdulkadiroglu & Parag A. Pathak & Alvin E. Roth & Tayfun Sönmez, 2006. "Changing the Boston School Choice Mechanism," Levine's Bibliography 122247000000001022, UCLA Department of Economics.
    10. Salvador Barberà & Dolors Berga & Bernardo Moreno, 2016. "Group Strategy-Proofness in Private Good Economies," American Economic Review, American Economic Association, vol. 106(4), pages 1073-1099, April.
    11. repec:cte:werepe:we081207 is not listed on IDEAS
    12. Shengwu Li, 2024. "Designing Simple Mechanisms," Papers 2403.18694, arXiv.org, revised Jul 2024.
    13. Avinatan Hassidim & Assaf Romm & Ran I. Shorrer, 2021. "The Limits of Incentives in Economic Matching Procedures," Management Science, INFORMS, vol. 67(2), pages 951-963, February.
    14. Madhav Raghavan, 2018. "Influence in Private-Good Economies," Cahiers de Recherches Economiques du Département d'économie 18.05, Université de Lausanne, Faculté des HEC, Département d’économie.
    15. Joseph Root & David S. Ahn, 2020. "Incentives and Efficiency in Constrained Allocation Mechanisms," Papers 2006.06776, arXiv.org, revised Nov 2023.
    16. Roberto Serrano, 2003. "The Theory of Implementation of Social Choice Rules," Working Papers 2003-19, Brown University, Department of Economics.
    17. Yuichiro Kamada & Fuhito Kojima, 2020. "Accommodating various policy goals in matching with constraints," The Japanese Economic Review, Springer, vol. 71(1), pages 101-133, January.
    18. Mizukami, Hideki & Saijo, Tatsuyoshi & Wakayama, Takuma, 2003. "Strategy-Proof Sharing," Working Papers 1170, California Institute of Technology, Division of the Humanities and Social Sciences.
    19. Markus Möller, 2024. "Transparent Matching Mechanisms," ECONtribute Discussion Papers Series 306, University of Bonn and University of Cologne, Germany.
    20. Arribillaga, R. Pablo & Massó, Jordi & Neme, Alejandro, 2023. "All sequential allotment rules are obviously strategy-proof," Theoretical Economics, Econometric Society, vol. 18(3), July.
    21. Alvin Roth, 2008. "Deferred acceptance algorithms: history, theory, practice, and open questions," International Journal of Game Theory, Springer;Game Theory Society, vol. 36(3), pages 537-569, March.

    More about this item

    Keywords

    menu mechanism; privacy; strategy-proofness; robust implementation;
    All these keywords.

    JEL classification:

    • D82 - Microeconomics - - Information, Knowledge, and Uncertainty - - - Asymmetric and Private Information; Mechanism Design
    • D47 - Microeconomics - - Market Structure, Pricing, and Design - - - Market Design
    • C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:kue:epaper:e-19-012. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Graduate School of Economics Project Center (email available below). General contact details of provider: https://edirc.repec.org/data/fekyojp.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.