IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v48y2023i1p332-362.html

New Constructions of Obviously Strategyproof Mechanisms

Author

Listed:
  • Diodato Ferraioli

    (DIEM, Università degli Studi di Salerno, 84084 Fisciano, Italy)

  • Adrian Meier

    (Department of Computer Science, ETH Zurich, 8092 Zurich, Switzerland)

  • Paolo Penna

    (Department of Computer Science, ETH Zurich, 8092 Zurich, Switzerland)

  • Carmine Ventre

    (Department of Informatics, King’s College London, London WC2B 4BG, United Kingdom)

Abstract

Catering to the incentives of people with limited rationality is a challenging research direction that requires novel paradigms to design mechanisms. Obviously strategy-proof (OSP) mechanisms have recently emerged as the concept of interest to this research agenda. However, the majority of the literature in the area has either highlighted the shortcomings of OSP or focused on the “right” definition rather than on the construction of these mechanisms. Here, we give the first set of tight results on the approximation guarantee of OSP mechanisms for scheduling related machines and a characterization of set system instances for which OSP mechanisms that return optimal solutions exist. By extending the well-known cycle monotonicity technique, we are able to concentrate on the algorithmic component of OSP mechanisms and provide some novel paradigms for their design, when private types belong to a set with few values. In essence, we prove that OSP encompasses careful interleaving of ascending and descending auctions.

Suggested Citation

  • Diodato Ferraioli & Adrian Meier & Paolo Penna & Carmine Ventre, 2023. "New Constructions of Obviously Strategyproof Mechanisms," Mathematics of Operations Research, INFORMS, vol. 48(1), pages 332-362, February.
    • Handle: RePEc:inm:ormoor:v:48:y:2023:i:1:p:332-362
    DOI: 10.1287/moor.2022.1264
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.2022.1264
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2022.1264?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. 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.
    2. Lavi, Ron & Swamy, Chaitanya, 2009. "Truthful mechanism design for multidimensional scheduling via cycle monotonicity," Games and Economic Behavior, Elsevier, vol. 67(1), pages 99-124, September.
    3. 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.
    4. Luyao Zhang & Dan Levin, 2017. "Bounded Rationality and Robust Mechanism Design: An Axiomatic Approach," American Economic Review, American Economic Association, vol. 107(5), pages 235-239, May.
    5. Shengwu Li, 2017. "Obviously Strategy-Proof Mechanisms," American Economic Review, American Economic Association, vol. 107(11), pages 3257-3287, November.
    6. Rochet, J. C., 1985. "The taxation principle and multi-time Hamilton-Jacobi equations," Journal of Mathematical Economics, Elsevier, vol. 14(2), pages 113-128, April.
    7. Peter Troyan, 2019. "Obviously Strategy‐Proof Implementation Of Top Trading Cycles," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 60(3), pages 1249-1261, August.
    8. Kagel, John H & Harstad, Ronald M & Levin, Dan, 1987. "Information Impact and Allocation Rules in Auctions with Affiliated Private Values: A Laboratory Study," Econometrica, Econometric Society, vol. 55(6), pages 1275-1304, November.
    9. Müller, R.J. & Gui, H. & Vohra, R., 2004. "Dominant strategy mechanisms with multidimensional types," Research Memorandum 046, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    10. Paul Dütting & Vasilis Gkatzelis & Tim Roughgarden, 2017. "The Performance of Deferred-Acceptance Auctions," Mathematics of Operations Research, INFORMS, vol. 42(4), pages 897-914, November.
    11. Penna, Paolo & Ventre, Carmine, 2014. "Optimal collusion-resistant mechanisms with verification," Games and Economic Behavior, Elsevier, vol. 86(C), pages 491-509.
    Full references (including those not matched with items on IDEAS)

    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. Inácio Bó & Rustamdjan Hakimov, 2024. "Pick-an-Object Mechanisms," Management Science, INFORMS, vol. 70(7), pages 4693-4721, July.
    2. Breitmoser, Yves & Schweighofer-Kodritsch, Sebastian, 2019. "Obviousness around the clock," Discussion Papers, Research Unit: Market Behavior SP II 2019-203, WZB Berlin Social Science Center.
    3. Peter Katuščák & Thomas Kittsteiner, 2025. "Strategy-Proofness Made Simpler," Management Science, INFORMS, vol. 71(9), pages 7560-7578, September.
    4. Arribillaga, R. Pablo & Massó, Jordi & Neme, Alejandro, 2020. "On obvious strategy-proofness and single-peakedness," Journal of Economic Theory, Elsevier, vol. 186(C).
    5. Yves Breitmoser & Sebastian Schweighofer-Kodritsch, 2022. "Obviousness around the clock," Experimental Economics, Springer;Economic Science Association, vol. 25(2), pages 483-513, April.
    6. Mariya Halushka, 2021. "Obviously Strategy-proof Mechanism Design With Rich Private Information," Working Papers 2104E, University of Ottawa, Department of Economics.
    7. Bó, Inácio & Hakimov, Rustamdjan, 2022. "The iterative deferred acceptance mechanism," Games and Economic Behavior, Elsevier, vol. 135(C), pages 411-433.
    8. Marek Pycia & Peter Troyan, 2023. "A Theory of Simplicity in Games and Mechanism Design," Econometrica, Econometric Society, vol. 91(4), pages 1495-1526, July.
    9. Echenique, Federico & Miyashita, Masaki & Nakamura, Yuta & Pomatto, Luciano & Vinson, Jamie, 2022. "Twofold multiprior preferences and failures of contingent reasoning," Journal of Economic Theory, Elsevier, vol. 202(C).
    10. Maurizio Canavari & Andreas C. Drichoutis & Jayson L. Lusk & Rodolfo M. Nayga, Jr., 2018. "How to run an experimental auction: A review of recent advances," Working Papers 2018-5, Agricultural University of Athens, Department Of Agricultural Economics.
    11. McGee, Peter & Levin, Dan, 2019. "How obvious is the dominant strategy in an English Auction? Experimental evidence," Journal of Economic Behavior & Organization, Elsevier, vol. 159(C), pages 355-365.
    12. Arribillaga, R. Pablo & Massó, Jordi & Neme, Alejandro, 2023. "All sequential allotment rules are obviously strategy-proof," Theoretical Economics, Econometric Society, vol. 18(3), July.
    13. Yannai A. Gonczarowski & Ori Heffetz & Clayton Thomas, 2022. "Strategyproofness-Exposing Descriptions of Matching Mechanisms," Papers 2209.13148, arXiv.org, revised Oct 2025.
    14. Ji Yong Lee & Rodolfo M. Nayga & Cary Deck & Andreas C. Drichoutis, 2020. "Cognitive Ability and Bidding Behavior in Second Price Auctions: An Experimental Study," American Journal of Agricultural Economics, John Wiley & Sons, vol. 102(5), pages 1494-1510, October.
    15. Takehito Masuda & Ryo Mikami & Toyotaka Sakai & Shigehiro Serizawa & Takuma Wakayama, 2023. "Correction to: The net effect of advice on strategy-proof mechanisms: an experiment for the Vickrey auction," Experimental Economics, Springer;Economic Science Association, vol. 26(1), pages 249-250, March.
    16. Bo Chen & Dmitriy Knyazev, 2026. "Optimal Discrimination-Free Auctions," Management Science, INFORMS, vol. 72(3), pages 2267-2283, March.
    17. Shengwu Li, 2024. "Designing Simple Mechanisms," Journal of Economic Perspectives, American Economic Association, vol. 38(4), pages 175-192, Fall.
    18. Nobel Prize Committee, 2020. "Improvements to auction theory and inventions of new auction formats," Nobel Prize in Economics documents 2020-2, Nobel Prize Committee.
    19. Mandal, Pinaki & Roy, Souvik, 2022. "On obviously strategy-proof implementation of fixed priority top trading cycles with outside options," Economics Letters, Elsevier, vol. 211(C).
    20. Hagenbach, Jeanne & Perez-Richet, Eduardo, 2018. "Communication with evidence in the lab," Games and Economic Behavior, Elsevier, vol. 112(C), pages 139-165.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;
    ;

    JEL classification:

    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:inm:ormoor:v:48:y:2023:i:1:p:332-362. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.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.