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

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

    References listed on IDEAS

    as
    1. 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.
    2. William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, March.
    3. S. M. Johnson, 1954. "Optimal two‐ and three‐stage production schedules with setup times included," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 1(1), pages 61-68, March.
    4. M. R. Garey & D. S. Johnson & Ravi Sethi, 1976. "The Complexity of Flowshop and Jobshop Scheduling," Mathematics of Operations Research, INFORMS, vol. 1(2), pages 117-129, May.
    5. C N Potts & V A Strusevich, 2009. "Fifty years of scheduling: a survey of milestones," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 41-68, May.
    6. Itai Ashlagi & Shahar Dobzinski & Ron Lavi, 2012. "Optimal Lower Bounds for Anonymous Scheduling Mechanisms," Mathematics of Operations Research, INFORMS, vol. 37(2), pages 244-258, May.
    7. Mu'alem, Ahuva & Schapira, Michael, 2018. "Setting lower bounds on truthfulness," Games and Economic Behavior, Elsevier, vol. 110(C), pages 174-193.
    8. Roger B. Myerson, 1981. "Optimal Auction Design," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 58-73, February.
    9. Edward Clarke, 1971. "Multipart pricing of public goods," Public Choice, Springer, vol. 11(1), pages 17-33, September.
    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. Georgiou, Konstantinos & Swamy, Chaitanya, 2019. "Black-box reductions for cost-sharing mechanism design," Games and Economic Behavior, Elsevier, vol. 113(C), pages 17-37.
    2. Dominik Kress & Sebastian Meiswinkel & Erwin Pesch, 2018. "Mechanism design for machine scheduling problems: classification and literature overview," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(3), pages 583-611, July.
    3. Mu'alem, Ahuva & Schapira, Michael, 2018. "Setting lower bounds on truthfulness," Games and Economic Behavior, Elsevier, vol. 110(C), pages 174-193.
    4. Siddharth Prasad & Maria-Florina Balcan & Tuomas Sandholm, 2025. "Revenue-Optimal Efficient Mechanism Design with General Type Spaces," Papers 2505.13687, arXiv.org.
    5. Song, Yangwei, 2018. "Efficient Implementation with Interdependent Valuations and Maxmin Agents," Rationality and Competition Discussion Paper Series 92, CRC TRR 190 Rationality and Competition.
    6. Marek Pycia & Peter Troyan, 2023. "A Theory of Simplicity in Games and Mechanism Design," Econometrica, Econometric Society, vol. 91(4), pages 1495-1526, July.
    7. Philippe Jehiel & Laurent Lamy, 2018. "A Mechanism Design Approach to the Tiebout Hypothesis," Journal of Political Economy, University of Chicago Press, vol. 126(2), pages 735-760.
    8. Corchón, Luis C., 2008. "The theory of implementation : what did we learn?," UC3M Working papers. Economics we081207, Universidad Carlos III de Madrid. Departamento de Economía.
    9. Debasis Mishra & Abdul Quadir, 2012. "Deterministic single object auctions with private values," Discussion Papers 12-06, Indian Statistical Institute, Delhi.
    10. Tomoya Kazumura & Shigehiro Serizawa, 2016. "Efficiency and strategy-proofness in object assignment problems with multi-demand preferences," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 47(3), pages 633-663, October.
    11. Pathikrit Basu, 2023. "Optimal mechanism design with approximate incentive compatibility and many players," The Journal of Mechanism and Institution Design, Society for the Promotion of Mechanism and Institution Design, University of York, vol. 8(1), pages 97-106, December.
    12. Claude d'Aspremont & Jacques Crémer & Louis-André Gérard-Varet, 2003. "Correlation, independence, and Bayesian incentives," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 21(2), pages 281-310, October.
    13. Maria-Florina Balcan & Siddharth Prasad & Tuomas Sandholm, 2023. "Bicriteria Multidimensional Mechanism Design with Side Information," Papers 2302.14234, arXiv.org, revised May 2026.
    14. Matthias Lang, 2020. "Mechanism Design with Narratives," CESifo Working Paper Series 8502, CESifo.
    15. Paul Milgrom, 2011. "Critical Issues In The Practice Of Market Design," Economic Inquiry, Western Economic Association International, vol. 49(2), pages 311-320, April.
    16. Hyoung-Goo Kang & Richard M. Burton & Will Mitchell, 2021. "How firm boundaries and relatedness jointly affect diversification value: trade-offs between governance and flexibility," Computational and Mathematical Organization Theory, Springer, vol. 27(1), pages 1-34, March.
    17. Bierbrauer, Felix & Netzer, Nick, 2016. "Mechanism design and intentions," Journal of Economic Theory, Elsevier, vol. 163(C), pages 557-603.
    18. Xiaofei Bu & Yu-E Sun & Lina Zhang & He Huang & Baowei Wang, 2016. "A Variable bandwidth spectrum auction mechanism with performance guarantee," International Journal of Distributed Sensor Networks, , vol. 12(9), pages 15501477166, September.
    19. Yuhang Guo & Dong Hao & Bin Li, 2022. "Combinatorial Procurement Auction in Social Networks," Papers 2208.14591, arXiv.org.
    20. Nobel Prize Committee, 2020. "Improvements to auction theory and inventions of new auction formats," Nobel Prize in Economics documents 2020-2, Nobel Prize Committee.

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

    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.