IDEAS home Printed from https://ideas.repec.org/a/kap/compec/v62y2023i4d10.1007_s10614-022-10324-9.html
   My bibliography  Save this article

An Incentive-Compatible and Computationally Efficient Fog Bargaining Mechanism

Author

Listed:
  • Kwang Mong Sim

Abstract

This work contributes an (approximately) incentive-compatible and computationally efficient bargaining mechanism for pricing fog computing resources. In network settings (e.g., fog computing), it is plausible to think that self-interested and incompletely informed players (represented by software agents) will attempt to maximize their own benefits at the expense of others. Hence, it is crucial that fog bargaining mechanisms give incentives to agents for behaving in a manner consistent with the desired outcome where every agent’s benefit is maximized. Equilibrium analyses validate that the fog bargaining mechanism in this work is approximately Bayesian incentive compatible because every agent can approximately maximize its expected utility by adhering to the strategy recommended by the bargaining mechanism given that all other agents also adhere to their equilibrium strategies. That is, if every agent in the market adheres to the strategy recommended by the bargaining mechanism, then the strategy profile of the agents forms an approximate Bayesian Nash equilibrium. Given that a fog resource market has a large number of buyers and a large number of sellers, computational efficiency is also imperative since every agent needs to process a huge number of trading alternatives. Computational complexity analyses validate that 1) the procedure for carrying out the bargaining strategy has a linear time complexity, and with every passing round, the search space dwindles but the solutions become progressively better, 2) the number of rounds for each agent to complete bargaining is logarithmic in the number of its opponents, and 3) each agent has a linear message complexity.

Suggested Citation

  • Kwang Mong Sim, 2023. "An Incentive-Compatible and Computationally Efficient Fog Bargaining Mechanism," Computational Economics, Springer;Society for Computational Economics, vol. 62(4), pages 1883-1918, December.
    • Handle: RePEc:kap:compec:v:62:y:2023:i:4:d:10.1007_s10614-022-10324-9
    DOI: 10.1007/s10614-022-10324-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10614-022-10324-9
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10614-022-10324-9?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Bulow, Jeremy & Klemperer, Paul, 1996. "Auctions versus Negotiations," American Economic Review, American Economic Association, vol. 86(1), pages 180-194, March.
    2. Eduardo M Azevedo & Eric Budish, 2019. "Strategy-proofness in the Large," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 86(1), pages 81-116.
    3. Muthoo,Abhinay, 1999. "Bargaining Theory with Applications," Cambridge Books, Cambridge University Press, number 9780521576475, January.
    4. Tucci, Marco P. & Kendrick, David A. & Amman, Hans M., 2010. "The parameter set in an adaptive control Monte Carlo experiment: Some considerations," Journal of Economic Dynamics and Control, Elsevier, vol. 34(9), pages 1531-1549, September.
    5. Nisan, Noam & Ronen, Amir, 2001. "Algorithmic Mechanism Design," Games and Economic Behavior, Elsevier, vol. 35(1-2), pages 166-196, April.
    6. Swinkels, Jeroen M, 2001. "Efficiency of Large Private Value Auctions," Econometrica, Econometric Society, vol. 69(1), pages 37-68, January.
    7. Myerson, Roger B. & Satterthwaite, Mark A., 1983. "Efficient mechanisms for bilateral trading," Journal of Economic Theory, Elsevier, vol. 29(2), pages 265-281, April.
    8. Steven R. Williams, 1999. "A characterization of efficient, bayesian incentive compatible mechanisms," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 14(1), pages 155-180.
    9. Kalyan Chatterjee & William Samuelson, 1983. "Bargaining under Incomplete Information," Operations Research, INFORMS, vol. 31(5), pages 835-851, October.
    10. Carpenter, Jeffrey P, 2002. "Evolutionary Models of Bargaining: Comparing Agent-Based Computational and Analytical Approaches to Understanding Convention Evolution," Computational Economics, Springer;Society for Computational Economics, vol. 19(1), pages 25-49, February.
    11. Roberts, Donald John & Postlewaite, Andrew, 1976. "The Incentives for Price-Taking Behavior in Large Exchange Economies," Econometrica, Econometric Society, vol. 44(1), pages 115-127, January.
    12. Fang, Xichen & Guo, Hongye & Zhang, Xian & Wang, Xuanyuan & Chen, Qixin, 2022. "An efficient and incentive-compatible market design for energy storage participation," Applied Energy, Elsevier, vol. 311(C).
    13. Claus-Jochen Haake & Sonja Recker, 2018. "The Generalized Nash Bargaining Solution for Transfer Price Negotiations Under Incomplete Information," Group Decision and Negotiation, Springer, vol. 27(6), pages 905-932, December.
    14. H. M. Amman & D. A. Kendrick, 2000. "Stochastic Policy Design in a Learning Environment with Rational Expectations," Journal of Optimization Theory and Applications, Springer, vol. 105(3), pages 509-520, 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. Kwang Mong Sim, 2024. "A Strongly Group Strategyproof and Shill Resistant Bargaining Mechanism for Fog Resource Pricing," Dynamic Games and Applications, Springer, vol. 14(5), pages 1238-1267, November.

    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. Tim Roughgarden & Inbal Talgam-Cohen, 2018. "Approximately Optimal Mechanism Design," Papers 1812.11896, arXiv.org, revised Aug 2020.
    2. Andrés Abeliuk & Gerardo Berbeglia & Pascal Van Hentenryck, 2015. "Bargaining Mechanisms for One-Way Games," Games, MDPI, vol. 6(3), pages 1-21, September.
    3. Alan Kirman & Sonia Moulet, 2008. "Impact de l'organisation du marché: Comparaison de la négociation de gré à gré et des enchères descendantes," Working Papers halshs-00349034, HAL.
    4. Robert E. Hall, 2005. "Employment Fluctuations with Equilibrium Wage Stickiness," American Economic Review, American Economic Association, vol. 95(1), pages 50-65, March.
    5. Thomas A. Gresik & Mark A. Satterthwaite, 1985. "The Rate at Which a Simple Market Becomes Efficient as the Number of Traders Increases: An Asymptotic Result for Optimal Trading Mechanisms," Discussion Papers 641, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    6. Song, Yangwei, 2022. "Approximate Bayesian Implementation and Exact Maxmin Implementation: An Equivalence," Rationality and Competition Discussion Paper Series 362, CRC TRR 190 Rationality and Competition.
    7. 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.
    8. Soumendu Sarkar, 2017. "Mechanism design for land acquisition," International Journal of Game Theory, Springer;Game Theory Society, vol. 46(3), pages 783-812, August.
    9. Yoon, Kiho, 2015. "On budget balance of the dynamic pivot mechanism," Games and Economic Behavior, Elsevier, vol. 94(C), pages 206-213.
    10. Rohit Lamba, 2022. "Efficiency with(out) intermediation in repeated bilateral trade," Papers 2202.04201, arXiv.org.
    11. Yannick Gabuthy, 2004. "Online Dispute Resolution and Bargaining," European Journal of Law and Economics, Springer, vol. 17(3), pages 353-371, May.
    12. Troyan, Peter & Morrill, Thayer, 2020. "Obvious manipulations," Journal of Economic Theory, Elsevier, vol. 185(C).
    13. Petra Nieken & Patrick W. Schmitz, 2023. "Contracting under asymmetric information and externalities: an experimental study," Experimental Economics, Springer;Economic Science Association, vol. 26(5), pages 989-1021, November.
    14. Galavotti, Stefano, 2009. "Bilateral trade with apositional traders," Research in Economics, Elsevier, vol. 63(3), pages 172-188, September.
    15. Bradley J Larsen, 2021. "The Efficiency of Real-World Bargaining: Evidence from Wholesale Used-Auto Auctions," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 88(2), pages 851-882.
    16. Yi, Jianxin & Li, Yong, 2016. "A general impossibility theorem and its application to individual rights," Mathematical Social Sciences, Elsevier, vol. 81(C), pages 79-86.
    17. Yoon, Kiho, 2001. "The Modified Vickrey Double Auction," Journal of Economic Theory, Elsevier, vol. 101(2), pages 572-584, December.
    18. Zacharias, Eleftherios & Williams, Steven R., 2001. "Ex Post Efficiency in the Buyer's Bid Double Auction When Demand Can Be Arbitrarily Larger Than Supply," Journal of Economic Theory, Elsevier, vol. 97(1), pages 175-190, March.
    19. Song, Yangwei, 2023. "Approximate Bayesian implementation and exact maxmin implementation: An equivalence," Games and Economic Behavior, Elsevier, vol. 139(C), pages 56-87.
    20. Bichler, Martin & Kohring, Nils & Oberlechner, Matthias & Pieroth, Fabian R., 2023. "Learning equilibrium in bilateral bargaining games," European Journal of Operational Research, Elsevier, vol. 311(2), pages 660-678.

    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:kap:compec:v:62:y:2023:i:4:d:10.1007_s10614-022-10324-9. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.