{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T12:18:25Z","timestamp":1740140305676,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,7,15]],"date-time":"2022-07-15T00:00:00Z","timestamp":1657843200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,7,15]],"date-time":"2022-07-15T00:00:00Z","timestamp":1657843200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100009117","name":"Technische Universit\u00e4t Chemnitz","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100009117","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Manag Sci"],"published-print":{"date-parts":[[2022,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we present a network manipulation algorithm based on an alternating minimization scheme from Nesterov (Soft Comput 1\u201312, 2020). In our context, the alternative process 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.<\/jats:p>","DOI":"10.1007\/s10287-022-00429-9","type":"journal-article","created":{"date-parts":[[2022,7,15]],"date-time":"2022-07-15T15:44:00Z","timestamp":1657899840000},"page":"627-664","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Network manipulation algorithm based on inexact alternating minimization"],"prefix":"10.1007","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8705-8245","authenticated-orcid":false,"given":"David","family":"M\u00fcller","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vladimir","family":"Shikhman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,7,15]]},"reference":[{"issue":"1","key":"429_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s13235-010-0004-1","volume":"1","author":"D Acemoglu","year":"2011","unstructured":"Acemoglu D, Ozdaglar A (2011) Opinion dynamics and learning in social networks. Dyn Games Appl 1(1):3\u201349","journal-title":"Dyn Games Appl"},{"key":"429_CR2","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/2450.001.0001","volume-title":"Discrete choice theory of product differentiation","author":"SP Anderson","year":"1992","unstructured":"Anderson SP, Palma AD, Thisse LF (1992) Discrete choice theory of product differentiation. MIT press, Cambridge"},{"issue":"1","key":"429_CR3","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1137\/13094829X","volume":"25","author":"A Beck","year":"2015","unstructured":"Beck A (2015) On the convergence of alternating minimization for convex programming with applications to iteratively reweighted least squares and decomposition schemes. SIAM J Optim 25(1):185\u2013209","journal-title":"SIAM J Optim"},{"key":"429_CR4","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974997","volume-title":"First-order methods in optimization","author":"A Beck","year":"2017","unstructured":"Beck A (2017) First-order methods in optimization. SIAM, Philadelphia, PA"},{"issue":"3","key":"429_CR5","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0167-6377(02)00231-6","volume":"31","author":"A Beck","year":"2003","unstructured":"Beck A, Teboulle M (2003) Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper Res Lett 31(3):167\u2013175","journal-title":"Oper Res Lett"},{"issue":"2","key":"429_CR6","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1137\/100818327","volume":"22","author":"A Beck","year":"2012","unstructured":"Beck A, Teboulle M (2012) Smoothing and first order methods: a unified framework. SIAM J Optim 22(2):557\u2013580","journal-title":"SIAM J Optim"},{"issue":"3","key":"429_CR7","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/0304-4076(93)90049-B","volume":"58","author":"A B\u00f6rsch-Supan","year":"1993","unstructured":"B\u00f6rsch-Supan A, Hajivassiliou VA (1993) Smooth unbiased multivariate probability simulators for maximum likelihood estimation of limited dependent variable models. J Econ 58(3):347\u2013368","journal-title":"J Econ"},{"key":"429_CR8","unstructured":"Chen Y, Ye X (2011) Projection onto a simplex. arXiv preprint arXiv:1101.6081"},{"issue":"2","key":"429_CR9","first-page":"119","volume":"10","author":"RD Connors","year":"2014","unstructured":"Connors RD, Hess S, Daly A (2014) Analytic approximations for computing probit choice probabilities. Transp A Trans Sci 10(2):119\u2013139","journal-title":"Transp A Trans Sci"},{"issue":"345","key":"429_CR10","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1080\/01621459.1974.10480137","volume":"69","author":"MH DeGroot","year":"1974","unstructured":"DeGroot MH (1974) Reaching a consensus. J Am Stat Assoc 69(345):118\u2013121","journal-title":"J Am Stat Assoc"},{"key":"429_CR11","unstructured":"Duchi J, Shalev-Shwartz S, Singer Y, Tewari A (2010) Composite objective mirror descent. In: Proceedings of the 23rd annual conference on learning theory. Omnipress. pp 14\u201326"},{"issue":"2","key":"429_CR12","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1017\/nws.2015.34","volume":"4","author":"M F\u00f6rster","year":"2016","unstructured":"F\u00f6rster M, Mauleon A, Vannetelbosch VJ (2016) Trust and manipulation in social networks. Netw Sci 4(2):216\u2013243","journal-title":"Netw Sci"},{"issue":"4","key":"429_CR13","doi-asserted-by":"publisher","first-page":"1569","DOI":"10.1111\/iere.12469","volume":"61","author":"M Fosgerau","year":"2020","unstructured":"Fosgerau M, Melo E, De Palma A, Shum M (2020) Discrete choice and rational inattention: a general equivalence result. Int Econ Rev 61(4):1569\u20131589","journal-title":"Int Econ Rev"},{"key":"429_CR14","doi-asserted-by":"publisher","DOI":"10.1002\/9781119387596","volume-title":"Markov chains: from theory to implementation and experimentation","author":"PA Gagniuc","year":"2017","unstructured":"Gagniuc PA (2017) Markov chains: from theory to implementation and experimentation. Wiley, Hoboken"},{"issue":"4","key":"429_CR15","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1080\/10556789908805730","volume":"10","author":"L Grippof","year":"1999","unstructured":"Grippof L, Sciandrone M (1999) Globally convergent block-coordinate techniques for unconstrained optimization. Optim Methods Softw 10(4):587\u2013637","journal-title":"Optim Methods Softw"},{"key":"429_CR16","unstructured":"Jaggi M (2013) Revisiting Frank-Wolfe: projection-free sparse convex optimization. In: International conference on machine learning. PMLR. pp 427\u2013435"},{"issue":"9","key":"429_CR17","first-page":"121","volume":"30","author":"A Juditsky","year":"2011","unstructured":"Juditsky A, Nemirovski A (2011) First order methods for nonsmooth convex large-scale optimization, I: general purpose methods. Optim Mach Learn 30(9):121\u2013148","journal-title":"Optim Mach Learn"},{"key":"429_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-39568-1","volume-title":"First-order and stochastic optimization methods for machine learning","author":"G Lan","year":"2020","unstructured":"Lan G (2020) First-order and stochastic optimization methods for machine learning. Springer Nature, Heidelberg"},{"issue":"2","key":"429_CR19","doi-asserted-by":"publisher","first-page":"1379","DOI":"10.1137\/140992382","volume":"26","author":"G Lan","year":"2016","unstructured":"Lan G, Zhou Y (2016) Conditional gradient sliding for convex optimization. SIAM J Optim 26(2):1379\u20131409","journal-title":"SIAM J Optim"},{"issue":"1","key":"429_CR20","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/s10107-017-1173-0","volume":"171","author":"G Lan","year":"2018","unstructured":"Lan G, Zhou Y (2018) An optimal randomized incremental gradient method. Math Program 171(1):167\u2013215","journal-title":"Math Program"},{"issue":"4","key":"429_CR21","first-page":"145","volume":"4","author":"B Lindqvist","year":"1977","unstructured":"Lindqvist\u00a0 B (1977) How fast does a Markov chain forget the initial state? Adecision theoretical approach. Scand J Stat 4(4):145\u2013152.","journal-title":"Scand J Stat"},{"issue":"1","key":"429_CR22","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF02096261","volume":"46","author":"ZQ Luo","year":"1993","unstructured":"Luo ZQ, Tseng P (1993) Error bounds and convergence analysis of feasible descent methods: a general approach. Ann Oper Res 46(1):157\u2013178","journal-title":"Ann Oper Res"},{"key":"429_CR23","first-page":"72","volume":"673","author":"D McFadden","year":"1978","unstructured":"McFadden D (1978) Modeling the choice of residential location. Transp Res Rec 673:72\u201377","journal-title":"Transp Res Rec"},{"issue":"5","key":"429_CR24","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1002\/1099-1255(200009\/10)15:5<447::AID-JAE570>3.0.CO;2-1","volume":"15","author":"D McFadden","year":"2000","unstructured":"McFadden D, Train K (2000) Mixed MNL models for discrete response. J Appl Economet 15(5):447\u2013470","journal-title":"J Appl Economet"},{"issue":"1","key":"429_CR25","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1287\/moor.2021.1136","volume":"47","author":"D M\u00fcller","year":"2021","unstructured":"M\u00fcller D, Nesterov Y, Shikhman V (2021) Discrete choice prox-functions on the simplex. Math Oper Res 47(1):485\u2013507. https:\/\/doi.org\/10.1287\/moor.2021.1136","journal-title":"Math Oper Res"},{"issue":"6","key":"429_CR26","first-page":"1435","volume":"6","author":"D M\u00fcller","year":"2021","unstructured":"M\u00fcller D, Nesterov Y, Shikhman V (2021) Dynamic pricing under nested logit demand. J Pure Appl Funct Anal 6(6):1435\u20131451","journal-title":"J Pure Appl Funct Anal"},{"issue":"1","key":"429_CR27","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s10107-004-0552-5","volume":"103","author":"Y Nesterov","year":"2005","unstructured":"Nesterov Y (2005) Smooth minimization of non-smooth functions. Math Program 103(1):127\u2013152","journal-title":"Math Program"},{"key":"429_CR28","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-91578-4","volume-title":"Lectures on convex optimization","author":"Y Nesterov","year":"2018","unstructured":"Nesterov Y (2018) Lectures on convex optimization, vol 137. Springer, New York"},{"issue":"23","key":"429_CR29","doi-asserted-by":"publisher","first-page":"17609","DOI":"10.1007\/s00500-020-05148-4","volume":"24","author":"Y Nesterov","year":"2020","unstructured":"Nesterov\u00a0 Y (2020) Soft clustering by convex electoral model. Soft Comput 24(23):17609\u201317620","journal-title":"Soft Comput"},{"key":"429_CR30","unstructured":"Page L, Brin S, Motwani R, Winograd T (1999) The pagerank citation ranking: bringing order to the web. Tech. rep, Stanford InfoLab"},{"key":"429_CR31","doi-asserted-by":"crossref","unstructured":"Pu Y, Zeilinger MN, Jones CN (2014) Inexact fast alternating minimization algorithm for distributed model predictive control. In: 53rd IEEE conference on decision and control. pp 5915\u20135921","DOI":"10.1109\/CDC.2014.7040315"},{"key":"429_CR32","doi-asserted-by":"crossref","unstructured":"Stonyakin FS, Dvinskikh D, Dvurechensky P, Kroshnin A, Kuznetsova O, Agafonov A, Gasnikov A, Tyurin A, Uribe CA, Pasechnyuk D, Artamonov S (2019) Gradient methods for problems with inexact model of the objective. In: International conference on mathematical optimization theory and operations research. Springer. pp 97\u2013114","DOI":"10.1007\/978-3-030-22629-9_8"},{"issue":"4","key":"429_CR33","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1037\/h0070288","volume":"34","author":"L Thurstone","year":"1927","unstructured":"Thurstone L (1927) A law of comparative judgment. Psychol Rev 34(4):273","journal-title":"Psychol Rev"},{"key":"429_CR34","volume-title":"Discrete choice methods with simulation","author":"KE Train","year":"2009","unstructured":"Train KE (2009) Discrete choice methods with simulation. Cambridge University Press, Cambridge"},{"issue":"7","key":"429_CR35","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1016\/S0191-2615(00)00045-X","volume":"35","author":"CH Wen","year":"2001","unstructured":"Wen CH, Koppelman FS (2001) The generalized nested logit model. Trans Res Part B Methodol 35(7):627\u2013641","journal-title":"Trans Res Part B Methodol"},{"issue":"1","key":"429_CR36","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1109\/3468.553220","volume":"27","author":"J Yang","year":"1997","unstructured":"Yang J, Xu Y, Chen CS (1997) Human action learning via hidden Markov model. IEEE Trans Syst Man Cybern-Part A Syst Humans 27(1):34\u201344","journal-title":"IEEE Trans Syst Man Cybern-Part A Syst Humans"}],"container-title":["Computational Management Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10287-022-00429-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10287-022-00429-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10287-022-00429-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,14]],"date-time":"2022-11-14T15:07:20Z","timestamp":1668438440000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10287-022-00429-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,15]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["429"],"URL":"https:\/\/doi.org\/10.1007\/s10287-022-00429-9","relation":{},"ISSN":["1619-697X","1619-6988"],"issn-type":[{"type":"print","value":"1619-697X"},{"type":"electronic","value":"1619-6988"}],"subject":[],"published":{"date-parts":[[2022,7,15]]},"assertion":[{"value":"1 August 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 June 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 July 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"Not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}]}}