IDEAS home Printed from https://ideas.repec.org/p/aeg/report/2014-05.html
   My bibliography  Save this paper

Relationships between centrality measures and VCG mechanism

Author

Listed:
  • Alessandro Avenali

    (Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza")

Abstract

In this work we show that some recent centrality measures in network analysis are exactly an application of the principles underlying the Vickrey-Clarke-Groves (VCG) mechanism. We then present specific examples of completely different frameworks which highlights how these centrality measures à la VCG can indeed provide valuable information to fairly assess the importance of the analyzed network elements. However, by taking inspiration from the relevant literature on the VCG auction design, we verify that in general cases centrality measures à la VCG can determine a poor estimate of the actual significance of some network elements; therefore, we provide a general approach to effectively improve such estimates, based on applying the VCG rule to suitable groups of elements of the network.

Suggested Citation

  • Alessandro Avenali, 2014. "Relationships between centrality measures and VCG mechanism," DIAG Technical Reports 2014-05, Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza".
    • Handle: RePEc:aeg:report:2014-05
    as

    Download full text from publisher

    File URL: http://www.dis.uniroma1.it/~bibdis/RePEc/aeg/report/2014-05.pdf
    File Function: First version, 2014
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Jean Tirole, 1988. "The Theory of Industrial Organization," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262200716, April.
    2. Gómez, Daniel & Figueira, José Rui & Eusébio, Augusto, 2013. "Modeling centrality measures in social network analysis using bi-criteria network flow optimization problems," European Journal of Operational Research, Elsevier, vol. 226(2), pages 354-365.
    3. Milgrom,Paul, 2004. "Putting Auction Theory to Work," Cambridge Books, Cambridge University Press, number 9780521551847.
    4. Milgrom,Paul, 2004. "Putting Auction Theory to Work," Cambridge Books, Cambridge University Press, number 9780521536721.
    5. William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, March.
    6. Avenali, Alessandro, 2009. "Exploring the VCG mechanism in combinatorial auctions: The threshold revenue and the threshold-price rule," European Journal of Operational Research, Elsevier, vol. 199(1), pages 262-275, November.
    7. Ausubel Lawrence M & Milgrom Paul R, 2002. "Ascending Auctions with Package Bidding," The B.E. Journal of Theoretical Economics, De Gruyter, vol. 1(1), pages 1-44, August.
    8. Edward Clarke, 1971. "Multipart pricing of public goods," Public Choice, Springer, vol. 11(1), pages 17-33, September.
    9. Groves, Theodore, 1973. "Incentives in Teams," Econometrica, Econometric Society, vol. 41(4), pages 617-631, July.
    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. Lawrence M. Ausubel, 2006. "An Efficient Dynamic Auction for Heterogeneous Commodities," American Economic Review, American Economic Association, vol. 96(3), pages 602-629, June.
    2. Lawrence M. Ausubel & Paul Milgrom, 2004. "Ascending Proxy Auctions," Discussion Papers 03-035, Stanford Institute for Economic Policy Research.
    3. Committee, Nobel Prize, 2020. "Improvements to auction theory and inventions of new auction formats," Nobel Prize in Economics documents 2020-2, Nobel Prize Committee.
    4. Núñez, Marina & Rafels, Carlos & Robles, Francisco, 2020. "A mechanism for package allocation problems with gross substitutes," Journal of Mathematical Economics, Elsevier, vol. 87(C), pages 6-14.
    5. Lawrence M. Ausubel & Paul Milgrom, 2004. "The Lovely but Lonely Vickrey Auction," Discussion Papers 03-036, Stanford Institute for Economic Policy Research.
    6. Francisco Robles, 2016. "An implementation of the Vickrey outcome with gross-substitutes," UB School of Economics Working Papers 2016/353, University of Barcelona School of Economics.
    7. Paul Milgrom, 2006. "Package Auctions and Package Exchanges: the 2004 Fisher-Schultz Lecture," Levine's Bibliography 321307000000000131, UCLA Department of Economics.
    8. Eric Maskin, 2004. "The Unity of Auction Theory: Paul Milgrom's Masterclass," Economics Working Papers 0044, Institute for Advanced Study, School of Social Science.
    9. Chen, Yan & Takeuchi, Kan, 2010. "Multi-object auctions with package bidding: An experimental comparison of Vickrey and iBEA," Games and Economic Behavior, Elsevier, vol. 68(2), pages 557-579, March.
    10. Loertscher, Simon & Mezzetti, Claudio, 2021. "A dominant strategy, double clock auction with estimation-based tatonnement," Theoretical Economics, Econometric Society, vol. 16(3), July.
    11. Hiroki Saitoh & Shigehiro Serizawa, 2008. "Vickrey allocation rule with income effect," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 35(2), pages 391-401, May.
    12. Song, Yangwei, 2018. "Efficient Implementation with Interdependent Valuations and Maxmin Agents," Rationality and Competition Discussion Paper Series 92, CRC TRR 190 Rationality and Competition.
    13. Schnizler, Bjorn & Neumann, Dirk & Veit, Daniel & Weinhardt, Christof, 2008. "Trading grid services - a multi-attribute combinatorial approach," European Journal of Operational Research, Elsevier, vol. 187(3), pages 943-961, June.
    14. Mochon, A. & Saez, Y. & Gomez-Barroso, J.L. & Isasi, P., 2012. "Exploring pricing rules in combinatorial sealed-bid auctions," Journal of Economic Behavior & Organization, Elsevier, vol. 82(2), pages 462-478.
    15. Matt Van Essen, 2013. "Making efficient public good decisions using an augmented Ausubel auction," Economic Theory Bulletin, Springer;Society for the Advancement of Economic Theory (SAET), vol. 1(1), pages 57-68, May.
    16. Zhou, Yu & Serizawa, Shigehiro, 2023. "Multi-object auction design beyond quasi-linearity: Leading examples," Games and Economic Behavior, Elsevier, vol. 140(C), pages 210-228.
    17. Patrick Hummel, 2018. "Hybrid mechanisms for Vickrey–Clarke–Groves and generalized second-price bids," International Journal of Game Theory, Springer;Game Theory Society, vol. 47(1), pages 331-350, March.
    18. Wada, Kentaro & Akamatsu, Takashi, 2013. "A hybrid implementation mechanism of tradable network permits system which obviates path enumeration: An auction mechanism with day-to-day capacity control," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 60(C), pages 94-112.
    19. Kazumori, Eiichiro & Belch, Yaakov, 2019. "t-Tree: The Tokyo toolbox for large-scale combinatorial auction experiments," Journal of Behavioral and Experimental Finance, Elsevier, vol. 24(C).
    20. Ehrhart, Karl-Martin & Ott, Marion & Seifert, Stefan & Wang, Runxi, 2024. "Combinatorial auctions for renewable energy — potentials and challenges," Energy Policy, Elsevier, vol. 186(C).

    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:aeg:report:2014-05. 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: Antonietta Angelica Zucconi (email available below). General contact details of provider: https://edirc.repec.org/data/dirosit.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.