IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2107.03754.html
   My bibliography  Save this paper

Network manipulation algorithm based on inexact alternating minimization

Author

Listed:
  • David Muller
  • Vladimir Shikhman

Abstract

In this paper, we present a network manipulation algorithm based on an alternating minimization scheme from (Nesterov 2020). In our context, the latter mimics the natural behavior of agents and organizations operating on a network. By selecting starting distributions, the organizations determine the short-term dynamics of the network. While choosing an organization in accordance with their manipulation goals, agents are prone to errors. This rational inattentive behavior leads to discrete choice probabilities. We extend the analysis of our algorithm to the inexact case, where the corresponding subproblems can only be solved with numerical inaccuracies. The parameters reflecting the imperfect behavior of agents and the credibility of organizations, as well as the condition number of the network transition matrix have a significant impact on the convergence of our algorithm. Namely, they turn out not only to improve the rate of convergence, but also to reduce the accumulated errors. From the mathematical perspective, this is due to the induced strong convexity of an appropriate potential function.

Suggested Citation

  • David Muller & Vladimir Shikhman, 2021. "Network manipulation algorithm based on inexact alternating minimization," Papers 2107.03754, arXiv.org, revised Jul 2021.
    • Handle: RePEc:arx:papers:2107.03754
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2107.03754
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Mogens Fosgerau & Emerson Melo & André de Palma & Matthew Shum, 2020. "Discrete Choice And Rational Inattention: A General Equivalence Result," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 61(4), pages 1569-1589, November.
    2. Daron Acemoglu & Asuman Ozdaglar, 2011. "Opinion Dynamics and Learning in Social Networks," Dynamic Games and Applications, Springer, vol. 1(1), pages 3-49, March.
    3. Fã–Rster, Manuel & Mauleon, Ana & Vannetelbosch, Vincent J., 2016. "Trust and manipulation in social networks," Network Science, Cambridge University Press, vol. 4(2), pages 216-243, June.
    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. David Müller & Vladimir Shikhman, 2022. "Network manipulation algorithm based on inexact alternating minimization," Computational Management Science, Springer, vol. 19(4), pages 627-664, October.
    2. Buechel, Berno & Hellmann, Tim & Klößner, Stefan, 2015. "Opinion dynamics and wisdom under conformity," Journal of Economic Dynamics and Control, Elsevier, vol. 52(C), pages 240-257.
    3. Fã–Rster, Manuel & Mauleon, Ana & Vannetelbosch, Vincent J., 2016. "Trust and manipulation in social networks," Network Science, Cambridge University Press, vol. 4(2), pages 216-243, June.
    4. Rusinowska, Agnieszka & Taalaibekova, Akylai, 2019. "Opinion formation and targeting when persuaders have extreme and centrist opinions," Journal of Mathematical Economics, Elsevier, vol. 84(C), pages 9-27.
    5. Lindbeck, Assar & Weibull, Jörgen, 2020. "Delegation of investment decisions, and optimal remuneration of agents," European Economic Review, Elsevier, vol. 129(C).
    6. Kanu, Edmond Augustine & Henning, Christian H. C. A., 2019. "An assessment of land reform policy processes in Sierra Leone: A network based approach," Working Papers of Agricultural Policy WP2019-04, University of Kiel, Department of Agricultural Economics, Chair of Agricultural Policy.
    7. Crès, Hervé & Tvede, Mich, 2022. "Aggregation of opinions in networks of individuals and collectives," Journal of Economic Theory, Elsevier, vol. 199(C).
    8. Nchare, Karim, 2021. "Dogit model and rational inattention," Economics Letters, Elsevier, vol. 205(C).
    9. Andreas Koulouris & Ioannis Katerelos & Theodore Tsekeris, 2013. "Multi-Equilibria Regulation Agent-Based Model of Opinion Dynamics in Social Networks," Interdisciplinary Description of Complex Systems - scientific journal, Croatian Interdisciplinary Society Provider Homepage: http://indecs.eu, vol. 11(1), pages 51-70.
    10. Davide Crapis & Bar Ifrach & Costis Maglaras & Marco Scarsini, 2017. "Monopoly Pricing in the Presence of Social Learning," Management Science, INFORMS, vol. 63(11), pages 3586-3608, November.
    11. Bartosz Maćkowiak & Filip Matějka & Mirko Wiederholt, 2023. "Rational Inattention: A Review," Journal of Economic Literature, American Economic Association, vol. 61(1), pages 226-273, March.
    12. Kashaev, Nail & Aguiar, Victor H., 2022. "A random attention and utility model," Journal of Economic Theory, Elsevier, vol. 204(C).
    13. Emerson Melo, 2022. "On the Distributional Robustness of Finite Rational Inattention Models," Papers 2208.03370, arXiv.org, revised May 2023.
    14. Germano, Fabrizio & Sobbrio, Francesco, 2020. "Opinion dynamics via search engines (and other algorithmic gatekeepers)," Journal of Public Economics, Elsevier, vol. 187(C).
    15. Michel Grabisch & Fen Li, 2020. "Anti-conformism in the Threshold Model of Collective Behavior," Dynamic Games and Applications, Springer, vol. 10(2), pages 444-477, June.
    16. Walid Ben-Ameur & Adam Ouorou & Guanglei Wang & Mateusz Żotkiewicz, 2018. "Multipolar robust optimization," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(4), pages 395-434, December.
    17. Emerson Melo, 2021. "Learning in Random Utility Models Via Online Decision Problems," Papers 2112.10993, arXiv.org, revised Aug 2022.
    18. Andrea Galeotti & Benjamin Golub & Sanjeev Goyal & Rithvik Rao, 2021. "Discord and Harmony in Networks," Papers 2102.13309, arXiv.org.
    19. M'ed'eric Motte & Huy^en Pham, 2021. "Optimal bidding strategies for digital advertising," Papers 2111.08311, arXiv.org.
    20. Tabasso, Nicole, 2019. "Diffusion of multiple information: On information resilience and the power of segregation," Games and Economic Behavior, Elsevier, vol. 118(C), pages 219-240.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    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:arx:papers:2107.03754. 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: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    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.