IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v48y2023i1p332-362.html
   My bibliography  Save this article

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
    ---><---

    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.

    We have no bibliographic references for this item. You can help adding them by using 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.