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

The Pareto Frontier of Inefficiency in Mechanism Design

Author

Listed:
  • Aris Filos-Ratsikas

    (Department of Computer Science, University of Liverpool, Liverpool L69 3BX, United Kingdom)

  • Yiannis Giannakopoulos

    (Department of Data Science, Friedrich-Alexander-Universität Erlangen-Nürnberg, 91058 Erlangen, Germany)

  • Philip Lazos

    (Department of Computer, Control and Management Engineering, Antonio Ruberti, Sapienza University of Rome, 00185 Roma, Italy)

Abstract

We study the trade-off between the price of anarchy (PoA) and the price of stability (PoS) in mechanism design in the prototypical problem of unrelated machine scheduling. We give bounds on the space of feasible mechanisms with respect to these metrics and observe that two fundamental mechanisms, namely the first price (FP) and the second price (SP), lie on the two opposite extrema of this boundary. Furthermore, for the natural class of anonymous task-independent mechanisms, we completely characterize the PoA/PoS Pareto frontier; we design a class of optimal mechanisms S P α that lie exactly on this frontier. In particular, these mechanisms range smoothly with respect to parameter α ≥ 1 across the frontier, between the first price ( S P 1 ) and second price ( S P ∞ ) mechanisms. En route to these results, we also provide a definitive answer to an important question related to the scheduling problem, namely whether nontruthful mechanisms can provide better makespan guarantees in the equilibrium compared with truthful ones. We answer this question in the negative by proving that the price of anarchy of all scheduling mechanisms is at least n , where n is the number of machines.

Suggested Citation

  • Aris Filos-Ratsikas & Yiannis Giannakopoulos & Philip Lazos, 2022. "The Pareto Frontier of Inefficiency in Mechanism Design," Mathematics of Operations Research, INFORMS, vol. 47(2), pages 923-944, May.
    • Handle: RePEc:inm:ormoor:v:47:y:2022:i:2:p:923-944
    DOI: 10.1287/moor.2021.1154
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.2021.1154
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2021.1154?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:47:y:2022:i:2:p:923-944. 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.