#  Changing Answer Order Can Decrease MMLU Accuracy

Vipul Gupta$1,2,\dagger$ David Pantoja $1,3,\dagger$ Candace Ross$1$ Adina
Williams$1$ Megan Ung$1$
$1$ FAIR at Meta AI
$2$ Pennsylvania State University $3$ University of California, Berkeley

<EMAIL_ADDRESS><EMAIL_ADDRESS>
{ccross, adinawilliams<EMAIL_ADDRESS>

###### Abstract

As large language models (LLMs) have grown in prevalence, particular
benchmarks have become essential for the evaluation of these models and for
understanding model capabilities. Most commonly, we use test accuracy averaged
across multiple subtasks in order to rank models on leaderboards, to determine
which model is best for our purposes. In this paper, we investigate the
robustness of the accuracy measurement on a widely used multiple choice
question answering dataset, MMLU. When shuffling the answer label contents, we
find that all explored models decrease in accuracy on MMLU, but not every
model is equally sensitive. These findings suggest a possible adjustment to
the standard practice of leaderboard testing, where we additionally consider
the percentage of examples each model answers correctly by random chance.

##  1 Introduction

††$\dagger$ This work was done during their internships at FAIR, Meta.

One of the largest outstanding issues with interpreting the results of model
evaluation pertains to the robustness of accuracy measurements. For example,
NLP model accuracy has been shown to be fairly brittle. For example, accuracy
can drop when researchers apply input alterations based on paraphrasing (Gan
and Ng, 2019), word order changes (Gauthier and Levy, 2019; Ribeiro et al.,
2020; Sinha et al., 2021a, 2022; Allen-Zhu and Li, 2023a, b; Berglund et al.,
2023; Golovneva et al., 2024; Kitouni et al., 2024), or other minor, largely
meaning-preserving input variations or perturbations (Belinkov and Bisk, 2018;
Ebrahimi et al., 2018; Jiang et al., 2020; Gao et al., 2021; Li et al., 2021;
Sinha et al., 2021b; Moradi and Samwald, 2021; Papakipos and Bitton, 2022;
Qian et al., 2022; Goodarzi et al., 2023; Sinha et al., 2023). If many models
fail to be robust on a benchmark, regardless of their initially measured
accuracy, we may need to reconsider how we use it as the basis for a
leaderboard that actually ranks models.

While there are many approaches to investigating robustness, our approach
relies on the intuition that a test-taker, human or model, should always
select the right answer regardless of its label, i.e. whether it is listed as
answer ‘A’ or ‘C’. Surely, if the right answer is unknown to the test-taker
and they make an uneducated guess, they still could happen upon the right
answer by chance, but, in an ideal scenario, a true expert should achieve the
same score when tested multiple times on versions of a test where only the
order that answers are presented in changes.

In humans, this performance stability, often called test-retest reliability is
an important consideration to determine how to interpret the results of
running a test (Bland and Altman, 1986). Humans test scores can fluctuate over
time, because they are filtered through irrelevant mental or physical factors
that affect measurement (Spearman, 1910; Dunlap, 1933). Such uninformative
fluctuations can affect multiple choice tests, for example, when answers are
presented in a different order during retest (Krosnick and Fabrigar, 1991;
Tellinghuisen and Sulikowski, 2008; Lions et al., 2022). However, as models do
not have the biological limitations of humans, we may expect them to exhibit
less variation than humans, or possibly even none at all. Thus, we claim that
a model should be robust to answer order changes: if it gets the correct
answer to a question when the answer is labeled ‘A’, it should also always get
the correct answer when it is labeled ‘C’. Put another way, the model should
select the same answer for each question, regardless of its label, for every
possible version of a benchmark; its accuracy should be static between test
and retest.

In our work, we ask whether shuffling the order of the answer label contents,
leaving the order of the labels (A, B, C, D) the same, affects the measurement
of accuracy. We focus our investigation on the MMLU dataset, a popular dataset
included on the widely used Hugging Face Open LLM
Leaderboard111https://huggingface.co/spaces/open-llm-
leaderboard/open˙llm˙leaderboard, which runs with the Eleuther LM Evaluation
Harness (Gao et al., 2023) as its backend.

Testing top performers on the Open LLM Leaderboard, we find that all ten
models are affected by our answer shuffling. This indicates that serious non-
robustness in benchmarking with MMLU. To better rank models on a leaderboard
with the MMLU dataset, we may want to take more random shuffles of label
contents to better understand the extent to which a model genuinely can output
the correct answer.

##  2 Methods

###  2.1 MMLU

Massive Multitask Language Understanding (MMLU) is a commonly used benchmark
for evaluating LLMs (Hendrycks et al., 2021). It is intended to test a model’s
world knowledge and problem solving ability, and consists of 57 tasks. Each
example in MMLU consists of a question paired with four possible answers, only
one of which is correct. Answers are a concatenation of an answer label
denoted as a letter, with answer contents (a string of characters). To test
the robustness of models to answer choice ordering, we shuffle the answer
label contents, with prohibition that the correct answer contents don’t change
and that we preserve the ordering of MMLU answer labels (A, B, C, D) across
different evaluation runs, for example:

original | a possible shuffle
---|---
| A. 1 |  | A. 4 |  |
| B. 2 |  | B. 2 |  |
| C. 3 |  | C. 1 |  |
| D. 4 |  | D. 3 |  |

We can think of the original orders of answer content labels in each example
in MMLU as one of the $n$ (out of 24 possible) shuffles of the example. Given
the size of the MMLU dataset, it is not efficient to run all the possible
shuffles (as each example has 24 options and there are nearly 14 thousand
questions. To do a tractable exploration, we take two random seeds of MMLU,
each of which has been shuffled, where each example has been selected from one
of the 24 possible answer contents orders to create semantically equivalent
versions of MMLU. We utilize the original MMLU implementation (Hendrycks et
al., 2021), which uses 5-shot in context learning during evaluation.

Figure 1:  This figure illustrates the performance of a selection of state-of-
the-art models that we tested on the original MMLU (v0) and 2 shuffled
versions (v1 and v2). Models are ordered by accuracy drop in ‘our metric’.
Here ‘-it’ denotes an instruction tuned model. The width of the violin
corresponds to the number of subdatasets where the model received a particular
score. The white indicator marks the median score for subdataset accuracies.

###  2.2 Metrics

In essence, we adopt a simplification of the classic formulation of test-
retest repeatability from Bland and Altman to match the ML leaderboard
setting: an evaluation (the running of a test on a model) is deemed perfectly
stable, if and only if the measurements realized at one time of running it
produces _the same exact values_ when repeated at a later time, when the test
is run under the same conditions. We minimally alter the testing conditions
when we repeat the test to measure robustness—by changing the order of answer
contents—but all other testing parameters remain static. In our setting, we
set the number of test takers, $n$, to 1.

In simple terms, this metric measures how often the model answers the
questions correctly in both the original and the shuffled versions. If the
model is actually robust, it will select the right answer no matter where it
appears, as the answer’s meaning doesn’t change when you merely change its
label and location in the answer string. If the model’s accuracy does change
in this setting, then we can say the model isn’t actually very competent on
the task that the test is testing.

To quantify (non-)robustness to answer order shuffling, we define a new
metric, our metric, which measures how often the model answers the same
question(s) correctly in both the original and in a shuffled version of MMLU.
We take the average over all the shuffles performed as our metric:

$\text{Our
Metric}=\frac{1}{N}\sum_{i=1}^{N}\frac{1}{M}\sum_{j=1}^{M}V_{0}^{i}V_{j}^{i},$
(1)

where $V_{0}^{i}\in\\{0,1\\}$ indicates whether the model answers the $i^{th}$
question correctly in MMLU dataset (1 if correct, 0 if incorrect). $V_{j}^{i}$
indicates whether the model answers $i^{th}$ question correctly in the
$j^{th}$ shuffled version of the answer label content. $M$ is the total number
of shuffles in the scope of the experiment (for us 2) and $N$ is the dataset
size. We then take the average performance across two such shuffles.

As formulated, our metric tries to capture the true capabilities of the model
by reducing the number of questions correctly answered by random chance.
Assuming models do not have external memory of earlier queries, enforcing that
the model correctly identify the answer $M$ times (for us twice), noticeably
lowers the chance of it happening across the correct answer by chance.

###  2.3 Models

In this work, we evaluate 10 state-of-the-art LLMs, ranging in size from 7
billion to 70 billion parameters, most of which have performed very well on
the Hugging Face Open LLM leaderboard. The 10 models we use are: Llama3 70B
Instruct, Llama3 70B, Llama3 8B Instruct (Meta, 2024), Llama2 70B (Touvron et
al., 2023), Yi 34B ($01.$AI et al., 2024), Mixtral 8x7B and Mixtral 8x7B
Instruct (Jiang et al., 2024), Falcon 40B Instruct (Almazrouei et al., 2023),
Mistral 7B Instruct (Jiang et al., 2023), and Gemma 7B Instruct (Team et al.,
2024). All models are openly available, which enables the reproducibility of
our findings.

(a) Category of MMLU most affected

(b) Category of MMLU least affected

Figure 2: The most and least affected categories of MMLU with our proposed
shuffling. The number above each plot signifies percentage change after
shuffling. Here ‘-it’ marks instruction finetuned models.

##  3 Results

We found that all tested models performed worse according to our metric after
answer content shuffling than on the original version of the dataset, as shown
in Table 1. After shuffling, we see that models fail to select the correct
answer for every question it originally selected correctly, as shown by our
metric in Figure 1.

Model Name | MMLU | Our Metric | % Drop
---|---|---|---
Llama-3-70B-it | 80.3 | 75.3 | 6.2
Llama-3-70B | 78.9 | 72.4 | 8.2
Yi-34B | 75.8 | 67.7 | 10.7
Mixtral-8x7B-it | 70.6 | 60.7 | 14.0
Mixtral-8x7B | 70.4 | 60.9 | 13.5
Llama-2-70B | 69.0 | 58.8 | 14.8
Llama-3-8B-it | 66.4 | 58.0 | 12.7
Mistral-7B-it | 59.3 | 46.5 | 21.6
Falcon-40B-it | 54.7 | 39.8 | 27.2
Gemma-7B-it | 51.7 | 38.0 | 26.5
Table 1: Accuracy drop on MMLU due to changing answer order. Here ‘-it’ marks
instruction tuned models.

We find that some models had higher retest accuracy than others. Models from
the Llama-3 family were the most robust, especially Llama-3-70B.
Interestingly, Llama-3-8B model was more robust than larger, generally high
performing models such as Mixtral-8x7B and Llama-2-70B. For Llama3-70B and
Mixtral-8x7B, we also found that their base and instruction finetuned models
were comparably robust. Smaller models, like Mistral-7B and Gemma-7B, were
generally more impacted. This result is consistent with findings in Zhou et
al. (2024), which found more inconsistency for smaller models (less than 8B
parameters), although in a slightly different setting. Some larger models,
such as Falcon-40B-instruct whose score dropped from 54.7 to 39.8 with our
approach, were also strongly impacted.

We also analyzed performance drop by subdataset in Table 2, and discovered
that the models struggled the most with problem-solving subdatasets, such as
high school mathematics. For Gemma-7B and Falcon-40B models, the drop in
accuracy on these categories were as high as 40%. As these subdatasets make up
a significant portion (over 15%) of original MMLU dataset, this analysis
suggests serious robustness issues affecting accuracy scores on problem-
solving categories. Additionally, among most impacted subdatasets, such as
“college mathematics” and “global facts”, we investigated whether the drop may
be due to the fact that shuffling can ablate the logical order of the original
questions. In humans, presenting answer orders in logical order—such as
0,1,2,3 or 3,2,1,0—is recommended by test design research, because random
order may pose unnecessary challenge for lower ability students (Huntley and
Welch, 1993; Haladyna et al., 2002). We discovered that more than 95% of the
original MMLU dataset was presented in logical order, which indicates that
models may be benefiting from logical answer order and perhaps that they
should be seen as lower ability test takers.

Model Name | MMLU | Our Metric | % Drop
---|---|---|---
Llama-3-70B-it | 72.1 | 64.5 | 10.5
Llama-3-70B | 68.7 | 57.7 | 16.0
Yi-34B | 65.6 | 52.9 | 19.4
Mixtral-8x7B-it | 56.9 | 43.4 | 23.7
Mixtral-8x7B | 57.0 | 43.4 | 23.9
Llama-2-70B | 54.6 | 40.4 | 26.0
Llama-3-8B-it | 54.3 | 40.9 | 24.7
Mistral-7B-it | 45.2 | 29.8 | 34.1
Falcon-40B-it | 41.5 | 24.3 | 41.4
Gemma-7B-it | 38.9 | 22.2 | 42.9
Table 2: Accuracy drop on problem solving categories of MMLU dataset due to
option text shuffling.

##  4 Discussion & Conclusion

#### Related Work.

Like all evaluation datasets, validity is important. Several recent works have
discussed MMLU’s validity (Gema et al., 2024; Zheng et al., 2023; Wang et al.,
2024a, b). In particular, Wang et al. (2024b) found trivial and noisy
questions in the dataset and proposed an update, MMLU-Pro, which aims to
mitigate those issues. Concurrent work on model robustness to question-
answering order (Zhou et al., 2024) applies a similar approach to ours that
shuffles answer label content and also explores other possible modes of
interrogating robustness. While they also find non-robustness to question
variants, our work differs from theirs in that our metric can account for the
multiplicity of potential orderings of answer labels; we also provide further
analysis for each category in MMLU in Figure 3 in the appendix.

#### Conclusion.

This work tested the robustness of the evaluation benchmark pipeline for the
popular leaderboard dataset MMLU. To separate out the effect of chance on
model answers, we apply a largely meaningless change to the datasets by
shuffling label contents. We find that this meaning-preserving alteration
resulted in a decrease in MMLU accuracy for all models, but not to the same
degree. We define a new metric that quantifies the effect of chance and
suggest that it is important to take it into consideration during evaluation
and leaderboard rankings of models.

## References

  * $01.$AI et al. (2024) $01.$AI, Alex Young, Bei Chen, Chao Li, Chengen Huang, Ge Zhang, Guanwei Zhang, Heng Li, Jiangcheng Zhu, Jianqun Chen, Jing Chang, Kaidong Yu, Peng Liu, Qiang Liu, Shawn Yue, Senbin Yang, Shiming Yang, Tao Yu, Wen Xie, Wenhao Huang, Xiaohui Hu, Xiaoyi Ren, Xinyao Niu, Pengcheng Nie, Yuchi Xu, Yudong Liu, Yue Wang, Yuxuan Cai, Zhenyu Gu, Zhiyuan Liu, and Zonghong Dai. 2024.  Yi: Open foundation models by 01.ai.
  * Allen-Zhu and Li (2023a) Zeyuan Allen-Zhu and Yuanzhi Li. 2023a.  Physics of language models: Part 3.1, knowledge storage and extraction.  _arXiv preprint arXiv:2309.14316_.
  * Allen-Zhu and Li (2023b) Zeyuan Allen-Zhu and Yuanzhi Li. 2023b.  Physics of language models: Part 3.2, knowledge manipulation.  _arXiv preprint arXiv:2309.14402_.
  * Almazrouei et al. (2023) Ebtesam Almazrouei, Hamza Alobeidli, Abdulaziz Alshamsi, Alessandro Cappelli, Ruxandra Cojocaru, Mérouane Debbah, Étienne Goffinet, Daniel Hesslow, Julien Launay, Quentin Malartic, Daniele Mazzotta, Badreddine Noune, Baptiste Pannier, and Guilherme Penedo. 2023.  The falcon series of open language models.
  * Belinkov and Bisk (2018) Yonatan Belinkov and Yonatan Bisk. 2018.  Synthetic and natural noise both break neural machine translation.  In _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_. OpenReview.net.
  * Berglund et al. (2023) Lukas Berglund, Meg Tong, Max Kaufmann, Mikita Balesni, Asa Cooper Stickland, Tomasz Korbak, and Owain Evans. 2023.  The reversal curse: Llms trained on" a is b" fail to learn" b is a".  _arXiv preprint arXiv:2309.12288_.
  * Bland and Altman (1986) J Martin Bland and DouglasG Altman. 1986.  Statistical methods for assessing agreement between two methods of clinical measurement.  _The lancet_ , 327(8476):307–310.
  * Dunlap (1933) Jack W Dunlap. 1933.  Comparable tests and reliability.  _Journal of Educational Psychology_ , 24(6):442.
  * Ebrahimi et al. (2018) Javid Ebrahimi, Anyi Rao, Daniel Lowd, and Dejing Dou. 2018.  HotFlip: White-box adversarial examples for text classification.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 31–36, Melbourne, Australia. Association for Computational Linguistics.
  * Gan and Ng (2019) Wee Chung Gan and Hwee Tou Ng. 2019.  Improving the robustness of question answering systems to question paraphrasing.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 6065–6075, Florence, Italy. Association for Computational Linguistics.
  * Gao et al. (2023) Leo Gao, Jonathan Tow, Baber Abbasi, Stella Biderman, Sid Black, Anthony DiPofi, Charles Foster, Laurence Golding, Jeffrey Hsu, Alain Le Noac’h, Haonan Li, Kyle McDonell, Niklas Muennighoff, Chris Ociepa, Jason Phang, Laria Reynolds, Hailey Schoelkopf, Aviya Skowron, Lintang Sutawika, Eric Tang, Anish Thite, Ben Wang, Kevin Wang, and Andy Zou. 2023.  A framework for few-shot language model evaluation.
  * Gao et al. (2021) Tianyu Gao, Adam Fisch, and Danqi Chen. 2021.  Making pre-trained language models better few-shot learners.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 3816–3830, Online. Association for Computational Linguistics.
  * Gauthier and Levy (2019) Jon Gauthier and Roger Levy. 2019.  Linking artificial and human neural representations of language.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 529–539, Hong Kong, China. Association for Computational Linguistics.
  * Gema et al. (2024) Aryo Pradipta Gema, Joshua Ong Jun Leang, Giwon Hong, Alessio Devoto, Alberto Carlo Maria Mancino, Rohit Saxena, Xuanli He, Yu Zhao, Xiaotang Du, Mohammad Reza Ghasemi Madani, et al. 2024.  Are we done with mmlu?  _arXiv preprint arXiv:2406.04127_.
  * Golovneva et al. (2024) Olga Golovneva, Zeyuan Allen-Zhu, Jason Weston, and Sainbayar Sukhbaatar. 2024.  Reverse training to nurse the reversal curse.  _arXiv preprint arXiv:2403.13799_.
  * Goodarzi et al. (2023) Saeed Goodarzi, Nikhil Kagita, Dennis Minn, Shufan Wang, Roberto Dessi, Shubham Toshniwal, Adina Williams, Jack Lanchantin, and Koustuv Sinha. 2023.  Robustness of named-entity replacements for in-context learning.  In _Findings of the Association for Computational Linguistics: EMNLP 2023_ , pages 10914–10931, Singapore. Association for Computational Linguistics.
  * Haladyna et al. (2002) Thomas M Haladyna, Steven M Downing, and Michael C Rodriguez. 2002.  A review of multiple-choice item-writing guidelines for classroom assessment.  _Applied measurement in education_ , 15(3):309–333.
  * Hendrycks et al. (2021) Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. 2021.  Measuring massive multitask language understanding.
  * Huntley and Welch (1993) Renee M Huntley and Catherine J Welch. 1993.  Numerical answer options: Logical or random order?.  In _The Annual of Meeting of the American Educational Research Association_.
  * Jiang et al. (2023) Albert Q. Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed. 2023.  Mistral 7b.
  * Jiang et al. (2024) Albert Q. Jiang, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Emma Bou Hanna, Florian Bressand, Gianna Lengyel, Guillaume Bour, Guillaume Lample, Lélio Renard Lavaud, Lucile Saulnier, Marie-Anne Lachaux, Pierre Stock, Sandeep Subramanian, Sophia Yang, Szymon Antoniak, Teven Le Scao, Théophile Gervet, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed. 2024.  Mixtral of experts.
  * Jiang et al. (2020) Zhengbao Jiang, Frank F. Xu, Jun Araki, and Graham Neubig. 2020.  How can we know what language models know? _Transactions of the Association for Computational Linguistics_ , 8:423–438.
  * Kitouni et al. (2024) Ouail Kitouni, Niklas Nolte, Diane Bouchacourt, Adina Williams, Mike Rabbat, and Mark Ibrahim. 2024.  The factorization curse: Which tokens you predict underlie the reversal curse and more.
  * Krosnick and Fabrigar (1991) JA Krosnick and LR Fabrigar. 1991.  The handbook of questionnaire design.
  * Li et al. (2021) Dianqi Li, Yizhe Zhang, Hao Peng, Liqun Chen, Chris Brockett, Ming-Ting Sun, and Bill Dolan. 2021.  Contextualized perturbation for textual adversarial attack.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 5053–5069, Online. Association for Computational Linguistics.
  * Lions et al. (2022) Séverin Lions, Carlos Monsalve, Pablo Dartnell, María Paz Blanco, Gabriel Ortega, and Julie Lemarié. 2022.  Does the response options placement provide clues to the correct answers in multiple-choice tests? a systematic review.  _Applied Measurement in Education_ , 35(2):133–152.
  * Meta (2024) Meta. 2024.  Introducing meta llama 3: The most capable openly available llm to date.
  * Moradi and Samwald (2021) Milad Moradi and Matthias Samwald. 2021.  Evaluating the robustness of neural language models to input perturbations.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 1558–1570, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Papakipos and Bitton (2022) Zoe Papakipos and Joanna Bitton. 2022.  Augly: Data augmentations for robustness.  _arXiv preprint arXiv:2201.06494_.
  * Qian et al. (2022) Rebecca Qian, Candace Ross, Jude Fernandes, Eric Smith, Douwe Kiela, and Adina Williams. 2022.  Perturbation augmentation for fairer nlp.  _arXiv preprint arXiv:2205.12586_.
  * Ribeiro et al. (2020) Marco Tulio Ribeiro, Tongshuang Wu, Carlos Guestrin, and Sameer Singh. 2020.  Beyond accuracy: Behavioral testing of NLP models with CheckList.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 4902–4912, Online. Association for Computational Linguistics.
  * Sinha et al. (2023) Koustuv Sinha, Jon Gauthier, Aaron Mueller, Kanishka Misra, Keren Fuentes, Roger Levy, and Adina Williams. 2023.  Language model acceptability judgements are not always robust to context.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 6043–6063, Toronto, Canada. Association for Computational Linguistics.
  * Sinha et al. (2021a) Koustuv Sinha, Robin Jia, Dieuwke Hupkes, Joelle Pineau, Adina Williams, and Douwe Kiela. 2021a.  Masked language modeling and the distributional hypothesis: Order word matters pre-training for little.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 2888–2913, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Sinha et al. (2022) Koustuv Sinha, Amirhossein Kazemnejad, Siva Reddy, Joelle Pineau, Dieuwke Hupkes, and Adina Williams. 2022.  The curious case of absolute position embeddings.  In _Findings of the Association for Computational Linguistics: EMNLP 2022_ , pages 4449–4472, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Sinha et al. (2021b) Sanchit Sinha, Hanjie Chen, Arshdeep Sekhon, Yangfeng Ji, and Yanjun Qi. 2021b.  Perturbing inputs for fragile interpretations in deep natural language processing.  In _Proceedings of the Fourth BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for NLP_ , pages 420–434, Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Spearman (1910) Charles Spearman. 1910.  Correlation calculated from faulty data.  _British journal of psychology_ , 3(3):271.
  * Team et al. (2024) Gemma Team, Thomas Mesnard, Cassidy Hardin, Robert Dadashi, Surya Bhupatiraju, Shreya Pathak, Laurent Sifre, Morgane Rivière, Mihir Sanjay Kale, Juliette Love, Pouya Tafti, Léonard Hussenot, Pier Giuseppe Sessa, Aakanksha Chowdhery, Adam Roberts, Aditya Barua, Alex Botev, Alex Castro-Ros, Ambrose Slone, Amélie Héliou, Andrea Tacchetti, Anna Bulanova, Antonia Paterson, Beth Tsai, Bobak Shahriari, Charline Le Lan, Christopher A. Choquette-Choo, Clément Crepy, Daniel Cer, Daphne Ippolito, David Reid, Elena Buchatskaya, Eric Ni, Eric Noland, Geng Yan, George Tucker, George-Christian Muraru, Grigory Rozhdestvenskiy, Henryk Michalewski, Ian Tenney, Ivan Grishchenko, Jacob Austin, James Keeling, Jane Labanowski, Jean-Baptiste Lespiau, Jeff Stanway, Jenny Brennan, Jeremy Chen, Johan Ferret, Justin Chiu, Justin Mao-Jones, Katherine Lee, Kathy Yu, Katie Millican, Lars Lowe Sjoesund, Lisa Lee, Lucas Dixon, Machel Reid, Maciej Mikuła, Mateo Wirth, Michael Sharman, Nikolai Chinaev, Nithum Thain, Olivier Bachem, Oscar Chang, Oscar Wahltinez, Paige Bailey, Paul Michel, Petko Yotov, Rahma Chaabouni, Ramona Comanescu, Reena Jana, Rohan Anil, Ross McIlroy, Ruibo Liu, Ryan Mullins, Samuel L Smith, Sebastian Borgeaud, Sertan Girgin, Sholto Douglas, Shree Pandya, Siamak Shakeri, Soham De, Ted Klimenko, Tom Hennigan, Vlad Feinberg, Wojciech Stokowiec, Yu hui Chen, Zafarali Ahmed, Zhitao Gong, Tris Warkentin, Ludovic Peran, Minh Giang, Clément Farabet, Oriol Vinyals, Jeff Dean, Koray Kavukcuoglu, Demis Hassabis, Zoubin Ghahramani, Douglas Eck, Joelle Barral, Fernando Pereira, Eli Collins, Armand Joulin, Noah Fiedel, Evan Senter, Alek Andreev, and Kathleen Kenealy. 2024.  Gemma: Open models based on gemini research and technology.
  * Tellinghuisen and Sulikowski (2008) Joel Tellinghuisen and Michelle M Sulikowski. 2008.  Does the answer order matter on multiple-choice exams?  _Journal of chemical education_ , 85(4):572.
  * Touvron et al. (2023) Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. 2023.  Llama 2: Open foundation and fine-tuned chat models.
  * Wang et al. (2024a) Haochun Wang, Sendong Zhao, Zewen Qiang, Bing Qin, and Ting Liu. 2024a.  Beyond the answers: Reviewing the rationality of multiple choice question answering for the evaluation of large language models.  _arXiv preprint arXiv:2402.01349_.
  * Wang et al. (2024b) Yubo Wang, Xueguang Ma, Ge Zhang, Yuansheng Ni, Abhranil Chandra, Shiguang Guo, Weiming Ren, Aaran Arulraj, Xuan He, Ziyan Jiang, et al. 2024b.  Mmlu-pro: A more robust and challenging multi-task language understanding benchmark.  _arXiv preprint arXiv:2406.01574_.
  * Zheng et al. (2023) Chujie Zheng, Hao Zhou, Fandong Meng, Jie Zhou, and Minlie Huang. 2023.  Large language models are not robust multiple choice selectors.  In _The Twelfth International Conference on Learning Representations_.
  * Zhou et al. (2024) Wenjie Zhou, Qiang Wang, Mingzhou Xu, Ming Chen, and Xiangyu Duan. 2024.  Revisiting the self-consistency challenges in multi-choice question formats for large language model evaluation.  In _Proceedings of the 2024 Joint International Conference on Computational Linguistics, Language Resources and Evaluation (LREC-COLING 2024)_ , pages 14103–14110, Torino, Italia. ELRA and ICCL.

##  Appendix A Appendix

###  A.1 Limitations

While we explore two possible shuffles of the answer label contents, we
restricted ourselves to the $M$ to curtail compute costs. We do acknowledge
that there are many more possible shuffles that might be tested, and more
would doubtless lead to a better approximation of the non-robustness.

###  A.2 Category Wise Analysis

We analyzed how changing the answer order affects each category in the MMLU
dataset. We found that some categories are more sensitive to these changes
than others. Figure 2 shows the impact of answer order changes on eight
randomly selected categories.

The MMLU has 57 subcategories, and we observed that some categories are more
affected by answer order changes than others. For example, categories such as
high school physics, abstract algebra, college mathematics, and moral disputes
witnessed a significant decrease in performance after answer order changes. On
the other hand, categories such as high school us history, econometrics, and
professional law were less affected. In some cases, the impact was highly
significant - for instance, the accuracy for Mistral-7B-instruct model on
moral scenarios category decreased by 77%, from 31.4 to 7.1, after changing
the answer order.

The different plots in Figure 2 highlight that not all categories are equally
affected, some parts of MMLU dataset might be good indicator of model
performance.

Figure 3: Here we show accuracy scores on random categories of MMLU with our
proposed shuffling. The number along with each category name signifies the
number of questions for that category in MMLU.

###  A.3 Computation Resources

For all experiments for this work, we utilized 8 V100 32GB GPUs. These GPUs
were assembled in a cluster of 8 GPUs in a node. The cumulative computing time
required to evaluate all the language models and complete the experiments
amounted to approximately 2000 GPU hours.


# Network manipulation algorithm based on inexact alternating minimization

David Müller Department of Mathematics, Chemnitz University of Technology,
Reichenhainer Str. 41, 09126 Chemnitz, Germany; e-mail:
<EMAIL_ADDRESS>(corresponding author),
<EMAIL_ADDRESS>Vladimir Shikhman11footnotemark: 1

###### Abstract

In this paper, we present a network manipulation algorithm based on an
alternating minimization scheme from [14]. 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 given by 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 do not only improve the rate of convergence, but also
reduce the accumulated errors.

Keywords— network manipulation, inexact alternating minimization, discrete
choice

##  1 Introduction

Networks naturally occur in many areas such as economics, computer science,
chemistry or biology. A common way to model scenarios within networks is to
use Markov chains. For a finite state space, a transition matrix describes the
structure of changes on the chain’s states [7]. Usually, the iterative process
of repeated transitions over the states provides a stationary distribution.
However, if the considered time horizon is short, a question arises on how to
efficiently manipulate the distribution of information within the network. As
an obvious choice for manipulation, each agent may start with an initial
distribution and spread the information by communicating with the neighbors.
But, since the own manipulation power is often limited, it is quite reasonable
for an agent to engage intermediary organizations instead. This could be due
to the restricted access to the parts of the network, revealing the
manipulation interests too apparently, or due to the lack of knowledge about
the network structure. Possible examples include:

  * Influencers. Companies, who want to credibly advertise their products or services via social media channels, pay influencers on social media platforms. They act as a part of the network and spread information on the products or services.

  * Search engines. Web site owners try to increase the visibility of their web sites. In order to find proper content, most of the Internet users enter a query into a web search engine. Thus, these query results strongly influence the short term behavior of the users.

  * Conspiracy theory. Agents try to spread false information for different interests. In order to spread fake news, agents have to rely on different distribution channels, such as groups in social media networks or Internet blogs.

Note that two of our examples are related to the manipulation of information
in a social network. There is a growing literature concerning this topic, see
[1] for an overview. Most of the models describe the update of opinions or
beliefs, see e. g. [4], where the latter is done according to a convex
combination of other network members’ opinions. Applying traditional
techniques from the analysis of Markov chains, the formation of a consensus is
examined. In these approaches, manipulation is modeled by modifying the
transition matrix, e. g. introducing randomness [1]. In [5], manipulation in a
model of opinion formation is studied. There, the weights of the transition
matrices can be changed by agents, while all starting distributions are fixed.
Our model differs from those in the existing literature, since we examine how
the information regarding a topic is distributed among network participants
through intermediaries. Loosely speaking, we analyze who knows how much and
how this information state can be efficiently manipulated by engaging
intermediaries. As mentioned in [1], one central component of opinion
formation is how agents update their prior beliefs based on new information.
In this paper, we also contribute to the opinion formation, because we
investigate a way to manipulate the acquirement of information by employing
the network of information sources. Our goal is not to learn the complete
structure of the network, for which usually hidden Markov models are applied,
see e. g. [19]. Instead, organizations should be able to select a starting
distribution aiming to arrive at a certain information state after a number of
iterations. Agents are choosing among the intermediare organizations to boost
manipulation. This is at the core of our network manipulation algorithm. Note
that a similar problem has been analyzed in [9], where the author applies
decision-theoretic techniques to observe a state at a time and obtain
information about the initial state.

Let us comment on the mathematics behind the proposed network manipulation
algorithm. It is motivated by [14] where a new technique for soft clustering
is introduced. For this, voters and political parties alternately solve their
subproblems, yielding an alternating minimization scheme. The behavior of
voters turns out to be in accordance with the well known multinomial logit
model from discrete choice theory. Namely, the voters choose rationally among
the parties, but are prone to random errors, see e. g. [2]. The parties update
their political positions depending on how many voters they attract. Overall,
the resulting soft clustering is given in terms of probabilities from the
multinomial logit model. In this paper, we generalize the idea suggested in
[14] to a broader class of discrete choice probabilities. This is done by
presenting a network manipulation model based on alternating steps performed
by agents and organizations. Agents try to manipulate a network by choosing
intermediary organizations for helping in that. In order to select among the
organizations, agents observe which of them better manipulate the network in
comparison to agents’ goals. While doing so, agents are prone to random
errors, which lead to choice probabilities following certain discrete choice
models examined in our previous paper [12]. Altogether, we show how the
alternating minimization scheme of [14] can be applied for network
manipulation. Additionally, we present an inexact version of the alternating
minimization scheme introduced in [14]. Inexactness is due to the fact that
the subproblems of agents and/or organizations may not be solved exactly and
may suffer from numerical inaccuracies. Overall, we conclude that the agents’
imperfect behavior and organizations’ conservatism in profit maximization
reduce the accumulated errors.

Notation. In this paper, we mainly focus on subspaces of $\mathbb{R}^{n}$ and
$\mathbb{R}^{m\times n}$, where the former is the space of $n$-dimensional
column vectors

$x=\left(x^{(1)},\dots,x^{(n)}\right)^{T},$

and the latter denotes the linear space of $(m\times n)$-matrices. We denote
by $e_{j}\in\mathbb{R}^{n}$ the $j$-th coordinate vector of $\mathbb{R}^{n}$
and write $e$ for the vector of an appropriate dimension whose components are
equal to one. By $\mathbb{R}^{n}_{+}$ we denote the set of all vectors with
nonnegative components and notation $\Delta_{n}$ is used for the standard
simplex

$\Delta_{n}=\left\\{x\in\mathbb{R}^{n}_{+}:\sum_{i=1}^{n}x^{(i)}=1\right\\}.$

We use the norms for $x\in\mathbb{R}^{n}$:

$\|x\|_{2}=\left[\sum_{i=1}^{n}x^{(i)2}\right]^{\frac{1}{2}},\quad\|x\|_{1}=\sum_{i=1}^{n}\left|x^{(i)}\right|,\quad\|x\|_{\infty}=\max_{i=1,\ldots,n}\left|x^{(i)}\right|.$

For $x,s\in\mathbb{R}^{n}$ we use the standard scalar product:

$\langle x,s\rangle=\sum\limits_{i=1}^{n}x^{(i)}s^{(i)}.$

For matrices $A,B\in\mathbb{R}^{m\times n}$ the inner product is defined via
the trace:

$\langle A,B\rangle=\mbox{Tr}(A^{T}\cdot B).$

A function $F:Q\to\mathbb{R}$ is called $\beta$-strongly convex on a convex
and closed set $Q\subset\mathbb{R}^{n}$ w.r.t. a norm $\|\cdot\|$ if for all
$x,y\in Q$ and $\alpha\in[0,1]$ it holds:

$F(\alpha x+(1-\alpha)y)\leq\alpha
F(x)+(1-\alpha)F(y)-\alpha(1-\alpha)\cdot\frac{\beta}{2}\|x-y\|^{2}.$

The positive constant $\beta$ is called the convexity parameter of $F$. If
$\beta=0$, we call $F$ convex. A function $\pi$ is $\beta$-strongly concave if
$-\pi$ is $\beta$-strongly convex. For a convex function $F:Q\to\mathbb{R}$
the set $\partial F(x)$ represents its subdifferential at $x\in Q$, i.e.

$\partial F(x)=\left\\{g\in\mathbb{R}^{n}:F(y)\geq F(x)+\langle
g,y-x\rangle\,\mbox{for all}\,y\in Q\right\\}.$

Its convex conjugate is

$F^{*}(s)=\underset{x\in\mathbb{R}^{n}}{\sup}\left\\{\left\langle
x,s\right\rangle-F(x)\right\\},$

where $s\in R^{n}$ is a vector of dual variables. We denote by $\nabla F(x)$
the gradient of a differentiable function $F$ at $x$.

##  2 Manipulation Model

Let us introduce our model in order to later construct a manipulation
algorithm based on interaction within a network.

###  2.1 Interaction network

A central aspect in our model is a network with $n$ nodes. The structure of
this network describes how nodes interact among each other, e. g. how persons
receive and exchange information. Thereby, a link from node $j$ to $i$
represents a connection. In the context of an information network, the latter
would depict that person $i$ acquires information from person $j$. We
summarize the data in a transition matrix $M=\left(M_{ij}\right)_{i,j=1}^{n}$,
where $M_{ij}$ denotes the transition probability of node $j$ to node $i$.
Hence, the following holds:

$\sum\limits_{i=1}^{n}M_{ij}=1\quad\text{for}\quad j=1,\ldots,n.$

$M$ is a column stochastic matrix, i.e. $M\geq 0,\;e^{T}\cdot M=e^{T}$. Our
model describes the process of information acquirement rather than the
formation of opinions as e. g. in [5]. We are interested in a few periods of
interactions, thus, we take the transition matrix as fixed. The interaction
causes different states of the network, based on the connections of its nodes.
The state of a network can be represented as an element of the standard
simplex in $\mathbb{R}^{n}$ dependent on time variable. We call a vector
$x(t)\in\Delta_{n}$ a state of a network at time $t$. Such a state reflects
the value each node possesses after an interaction with other nodes. This
could be for example the amount of information a person possesses in relation
to the others or the market share of a company.

The dynamics of interaction can be described by an iterative process. The
latter starts with a vector $x(0)\in\Delta_{n}$ and then the nodes interact
repeatedly with each other. Thus, the iterative process is given by

$x(t)=M\cdot x(t-1)=\ldots=M^{t}\cdot x(0).$ (1)

Obviously, all $x(t)$’s generated according to this process are elements of
$\Delta_{n}$. Our idea is closely related to the concept of network rankings,
such as the famous PageRank [15]. However, we focus on a limited, mostly small
number, of interaction periods. Within an information network, persons would
typically exchange information for a few periods, before they make a decision.
This short term behavior endows the starting vector $x(0)\in\Delta_{n}$ with
importance. For the sake of brevity, we drop the time index by writing
$x=x(0)$.

###  2.2 Agents

Let us assume that agents want to manipulate the resulting state of a network
in favor of their own interests. Though they aspire certain network states,
agents face some challenges by trying to manipulate a network. Often, they do
not have knowledge of the network structure. Additionally, there are many
situations, where the agents can’t participate in the network because they
cannot connect to a node without revealing their intentions, e. g. companies
cannot credibly advertise their products by themselves. There might also be
networks, where an agent could interact in, but is restricted to start with a
fixed vector. In particular, if the information is just spread uniformly.
Instead, agents could instruct organizations to manipulate the interaction in
order to reach an aspired state of the network. The organizations often have
more information or at least experience about the structure of a network. In
fact, they could even operate it. The agents choose among $K$ organizations,
where each organization provides an observable utility $u^{(k)}$. This
discrete choice behaviour we describe by means of the so-called additive
random utility models. The additive decomposition of utility goes back to
psychological experiments accomplished in the 1920’s [18]. A formal
description of this framework has been first introduced in an economic context
[11], where rational decision-makers choose from a finite set of mutually
exclusive alternatives $\\{1,\ldots,K\\}.$ Although the decision rule follows
a rational behavior, agents are prone to random errors. The latter describe
decision-affecting features which cannot be observed. Each alternative
$k=1,\ldots,K$ provides the utility

$u^{(k)}+\epsilon^{(k)},$

where $u^{(k)}\in\mathbb{R}$ is the deterministic utility part of the $k$-th
alternative and $\epsilon^{(k)}$ is its stochastic error. We use the following
notation for the vectors of deterministic utilities and of random utilities,
respectively:

$u=\left(u^{(1)},\ldots,u^{(K)}\right)^{T},\quad\epsilon=\left(\epsilon^{(1)},\ldots,\epsilon^{(K)}\right)^{T}.$

The probabilistic framework yields choice probabilities for each alternative:

$p^{(k)}=\mathbb{P}\left(u^{(k)}+\epsilon^{(k)}=\max_{1\leq m\leq
K}u^{(m)}+\epsilon^{(m)}\right),\quad k=1,\ldots,K.$ (2)

As the consumers behave rationally, their surplus is given by the expected
maximum utility of their decision:

$E(u)=\mathbb{E}_{\epsilon}\left(\max_{1\leq k\leq
K}u^{(k)}+\epsilon^{(k)}\right).$ (3)

It is well known that the surplus function is convex [2]. Additionally we make
a standard assumption concerning the distribution of random errors.

######  Assumption 1.

The random vector $\epsilon$ follows a joint distribution with zero mean that
is absolutely continuous with respect to the Lebesgue measure and fully
supported on $\mathbb{R}^{K}$.

######  Assumption 2.

The differences $\epsilon^{(k)}-\epsilon^{(m)}$ of random errors have finite
modes for all $k,m=1,\ldots,K$.

Assumption 1 guarantees that no ties in occur in (3), which provides
differentiability of the surplus function. Further, the gradient of $E$
corresponds to the vector of choice probabilities, which is known as the
Williams-Daly-Zachary theorem [11], i.e.

$\frac{\partial E}{\partial u^{(k)}}=p^{(k)},\quad k=1,\ldots,K.$ (4)

Hence, each component of the gradient of $E$ yields the probability that
alternative $k$ provides the maximum utility among all alternatives.

Another equivalent representation of choice probabilities can be obtained by
means of the convex conjugate of the surplus function
${E^{*}:\mathbb{R}^{K}\to\mathbb{R}\;\cup\;\left\\{\infty\right\\}}$:

$E^{*}(p)=\sup_{u\in\mathbb{R}^{K}}\left\\{\langle p,u\rangle-E(u)\right\\},$

where $p=\left(p^{(1)},\ldots,p^{(K)}\right)^{T}$ is the vector of dual
variables. In view of conjugate duality and , the vector of choice
probabilities can be derived from an optimization problem of rational
inattention, see e. g. [6] and [12]. Indeed, it has been shown that under
Assumption 2 the vector of choice probabilities $\mathbb{P}$ is the unique
solution of

$\underset{p\in\Delta_{K}}{\max}\left\\{\langle u,p\rangle-E^{*}(p)\right\\}.$
(5)

Now, we assume that there are $N$ agents trying to manipulate the network.
Each agent $i$ has an aspired state of network which we denote by
$v_{i}\in\Delta_{n}$. In order to reach the aspired state, agents can choose
among $K$ organizations. The $k$-th organization is able to manipulate the
interaction dynamics in the network, which yields at time $t$ a state of a
network $x_{k}(t)\in\Delta_{n},\;k=1,\ldots,K$. In general agents prefer
organizations which provide a network state in line with the states they
desire such as an aspired market shares distribution or state of information.
In order to assess the outcome of a manipulation, any agent $i$ has to compare
$K$ distances, i.e.

$\|v_{i}-x_{k}(t)\|_{2},\quad k=1,\ldots,K,$

respectively

$\|v_{i}-M^{t}\cdot x_{k}\|_{2},\quad k=1,\ldots,K.$ (6)

Note that (6) provides a way for agent $i$ to observe the utility of choosing
the $k$-th organization. The network state at time $t$ is observable, so any
agent is able to check, if an organization has manipulated the network
satisfactorily. Let us put all the states in a matrix, which yields a way to
summarize all the states of a network at time $t$ in one variable, i.e.

$X(t)=\left(x_{1}(t),\ldots,x_{K}(t)\right)\in\Delta_{n}^{K}.$

The matrix above can also be expressed in terms of the starting vectors, by
defining

$X=\left(x_{1},\ldots,x_{K}\right)\in\Delta_{n}^{K},$

which enables us to write

$X(t)=M^{t}\cdot X.$ (7)

We define a vector valued function
$g_{i}:\Delta_{n}^{K}\rightarrow\mathbb{R}_{+}^{K}$ for any agent $i$, which
stores all these distances of the $i$-th agent and, hence, depends on a matrix
$X$ as input variable:

$g_{i}(X)=\left(\|v_{i}-M^{t}\cdot x_{1}\|_{2},\ldots,\|v_{i}-M^{t}\cdot
x_{K}\|_{2}\right)^{T},\quad i=1,\ldots,N.$

We write in matrix form:

$G(X)=\left(g_{1}(X),\ldots,g_{N}(X)\right)\in\mathbb{R}^{K\times N}.$

In view of additive random utility models, $g_{i}(\cdot)$ provides a way to
characterize the observable utility $u_{i}$ by setting

$u_{i}=-g_{i}(X),\quad i=1,\ldots,N.$

Hence, the vector of the $i$-th agent choice probabilities has entries

$p_{i}^{(k)}(X)=\mathbb{P}\left(-g_{i}^{(k)}(X)+\epsilon_{i}^{(k)}=\max_{1\leq
m\leq K}-g_{i}^{(m)}(X)+\epsilon_{i}^{(m)}\right),\quad k=1,\ldots,K.$ (8)

Equivalently, $p_{i}(X)$ solves the following rational inattention problem:

$\min_{p\in\Delta_{K}}\langle g_{i}(X),p\rangle+E_{i}^{*}(p).$

Let us stack the choice probabilities of all the agents into a matrix and call
the latter choice matrix:

$P(X)=\left(p_{1}(X),\ldots,p_{N}(X)\right)\in\Delta_{K}^{N}.$ (9)

Similarly to the choice matrix, we write $P\in\Delta_{K}^{N}$ for any matrix
of probability vectors, i.e. $P=\left(p_{1},\ldots,p_{N}\right)$ with
$p_{i}\in\Delta_{K}$, $i=1,\ldots,N$.

###  2.3 Organizations

Let us describe the behavior of advertising organizations. Their goal is to
attract agents as clients by providing them with additional manipulation
power. This is done by choosing an appropriate starting distribution, thus,
the communication process is initialized by organizations. By strategic
decisions, such as substantial alignment, design, product placements or
personal relations, or by direct decisions, such as ranking of a website as
result of a certain query or advertising products directly on a marketplace,
the organizations determine these vectors, which reflect a network state
before interaction starts.

In order to attract the $i$-th agent with aspired state $v_{i}$, the $k$-th
organization selects a starting distribution $x_{k}\in\Delta_{n}$ such that
$\left\|v_{i}-M^{t}\cdot x_{k}\right\|_{2}$ becomes small. The organization’s
goal is to acquire as many agents as possible by simultaneously satisfying the
corresponding aspired states. However, the agents are not necessarily equally
important for the organization. Instead, the latter primary wants to please
agents, who already prefer the organization compared to other competitors. Let
us state these considerations in a formal way. An organization $k$ observes to
which extent the agents choose it, i.e. quantified by choice probabilities
$p_{i}^{(k)}$, $i=1,\ldots,N$. Thus, the $k$-th organization measures its
performance by the following objective:

$\sum_{i=1}^{N}p_{i}^{(k)}\cdot\|v_{i}-M^{t}\cdot x_{k}\|_{2}.$ (10)

Yet, an organization’s choice of the manipulation distribution not only
depends on the agents’ aspired states, but also on its own objectives. This
reflects, that an organization might also aspire a certain state of the
network in order to gain profits from the network participants. Therefore, we
introduce a payoff function for organization $k$, which depends on the
latter’s caused state of manipulation:

$\pi_{k}\left(M^{t}\cdot x_{k}\right).$ (11)

Let us illustrate by examples how a network state could affect the payoff of
the $k$-th organization. Groups in social media platforms might avoid sharing
information with persons who have contrary opinions, such that no arguments
against their theories or fake news are communicated. Prohibiting or
restricting persons’ access to information might be a worthwhile purpose in an
information network. Particularly, this is interesting in situations, where
direct manipulation of opinions is difficult. Since the authors in [1] mention
the source of information as a key component of opinion formation, the
manipulation of the information acquirement process contributes to the
tampering of opinion formation. A social media influencer might loose
credibility of her followers, if the latter find out about an unacceptable
advertise. We state an assumption concerning the payoff functions.

######  Assumption 3.

The payoff function $\pi_{k}$ is $\tau_{k}$-strongly concave w.r.t. the norm
$\|\cdot\|_{2}$ for all $k=1,\ldots,K$.

Altogether, the objective function of the $k$-th organization incorporates the
both goals:

$\sum_{i=1}^{N}p_{i}^{(k)}\cdot\|v_{i}-M^{t}\cdot
x_{k}\|_{2}-\frac{1}{\eta_{k}}\cdot\pi_{k}\left(M^{t}\cdot x_{k}\right),$ (12)

where $\eta_{k}>0$ is a regularization parameter, which shows the importance
of payoffs generated by the network. Note that thereby, small values of
$\eta_{k}$ indicate a more restrictive behavior of the $k$-th organization,
meaning the latter rather focuses on its own interests than to freely adjust
the manipulation distribution according to the agents’ aspired states. For a
given choice matrix $P\in\Delta_{K}^{N}$, network $M$ and time $t$, the $k$-th
organization chooses its optimal starting distribution $x_{k}\in\Delta_{n}$ by
solving

$\min_{x_{k}\in\Delta_{n}}\sum_{i=1}^{N}p_{i}^{(k)}\cdot\|v_{i}-M^{t}\cdot
x_{k}\|_{2}-\frac{1}{\eta_{k}}\cdot\pi_{k}\left(M^{t}\cdot x_{k}\right).$ (13)

For now, we assume that the optimization problems given in (13) have unique
solutions for any choice matrix $P$, which we denote by $x_{k}(P)$,
$k=1,\ldots,K$. We keep these optimal manipulation values in a matrix

$X(P)=\left(x_{1}(P),\ldots,x_{K}(P)\right),$ (14)

and call the latter manipulation matrix.

###  2.4 Network manipulation algorithm

In the preceding section we described the behavior of agents and organizations
when facing the challenge to manipulate a network in favor of agents’ desires.
The key aspect is that their behavior summarized in (8) and (13) suggests an
alternating interaction between both groups. Organizations enter the market
and offering their manipulation distributions. Then, agents observe how
satisfactory organizations would manipulate the network state in view of the
agents aspired states (e. g. by comparing past results caused by an
organization). Based on these observations, agents make their decisions, i.e.
they choose organizations with probability according to equation (8). The
choice probabilities provide feedback to the organizations, which then in turn
adjust their starting distributions following the behavior given in (13). By
using previous notation, we have the following dynamics:

$P_{\ell+1}=P(X_{\ell}),\quad X_{\ell+1}=X(P_{\ell+1}),$

where $X_{0}$ is any feasible starting variable e. g. $X_{0}=\frac{1}{n}\cdot
ee^{T}$.

In what follows, we provide an equivalent description of this network
manipulation algorithm in order to better study its convergence properties.
For that, we define a potential function which incorporates the behavior of
all agents and organizations:

$\Phi(X,P)=\sum_{i=1}^{N}E_{i}^{*}(p_{i})+\sum_{k=1}^{K}\left(\sum_{i=1}^{N}p_{i}^{(k)}\cdot\|v_{i}-M^{t}\cdot
x_{k}\|_{2}-\frac{1}{\eta_{k}}\cdot\pi_{k}\left(M^{t}\cdot
x_{k}\right)\right).$ (15)

Therefore, the choice matrix solves the following minimization problem:

$P(X)=\arg\min_{P\in\Delta_{K}^{N}}\Phi(X,P).$ (16)

Analogously, we have for a manipulation matrix:

$X(P)=\arg\min_{X\in\Delta_{n}^{K}}\Phi(X,P),$ (17)

which means that the network manipulation algorithm can be viewed as an
alternating minimization scheme.

From the viewpoint of computational economics, it seems reasonable to assume
that agents and organizations are not able to solve their corresponding
optimization problems exactly. Rather than that, the solutions can be obtained
up to small errors. This can be for example due to observation errors of the
input parameters given by choice and/or manipulation matrices. Another reason
could be that exact optimization is time-exhaustive or too costly. In order to
incorporate this faulty behavior into our manipulation algorithm, we assume
that just inexact minimization in (16) and (17) is possible. More precisely,
$\delta_{1}$-inexact solutions for (16) and $\delta_{2}$-inexact solutions for
(17) are available, see Section 3 for details. Thus, we are ready to state a
more general network manipulation algorithm, based on an inexact alternating
minimization scheme:

Initialize $\tilde{X}_{0}\in\Delta_{n}^{K}$. For $\ell=0,1,2,\ldots$ update:
$\displaystyle\tilde{P}_{\ell+1}=\arg\min^{\delta_{1}}_{P\in
Q_{2}}\Phi\left(\tilde{X}_{\ell},P\right)$,
$\displaystyle\tilde{X}_{\ell+1}=\arg\min^{\delta_{2}}_{X\in
Q_{1}}\Phi\left(X,\tilde{P}_{\ell+1}\right)$.

The inexact algorithm raises the questions, if the corresponding alternating
behavior converges to a stable equilibrium. Do agents and organizations reach
a state, where their choices do not change anymore no matter what the starting
distributions of the organizations look like? In other words, does a unique
minimizer of the potential function exist and does the algorithm converge to
the latter. Moreover, it is interesting to analyze how the faulty behavior in
terms of the errors impacts the possible convergence. We shall answer these
questions by applying general results on inexact alternating minimization
schemes, which we present in Section 3. This is possible since the potential
function (15) can be suitably decomposed. For that, we define:

$f(X)=-\sum_{k=1}^{K}\frac{1}{\eta_{k}}\cdot\pi_{k}\left(M^{t}\cdot
x_{k}\right),\quad h(P)=\sum_{i=1}^{N}E_{i}^{*}(p_{i}).$ (18)

Using the standard inner product, the potential function in (15) can be
written as follows:

$\Phi(X,P)=f(X)+\langle G(X),P\rangle+h(P).$ (19)

##  3 Inexact alternating minimization

In cases, where the analytical solution of an optimization problem cannot be
derived, it is necessary to solve the latter numerically. Normally, this
numerical solutions are only exact up to a small $\delta$-error. We review
some theoretical aspects of inexact optimization, which we need for
convergence analysis. Let us consider optimization problems of the form

$\min_{z\in Q}\Phi(z),$ (20)

where $\Phi$ is a strongly convex function and $Q$ a closed and convex set. We
denote by $z^{*}$ the solution of problem (20). Recall that for a
$\beta$-strongly convex function $\Phi$ it holds:

$\Phi(z)\geq\Phi(z^{*})+\frac{\beta}{2}\|z-z^{*}\|^{2}\quad\text{for
all}\;z\in Q.$ (21)

For a $\delta$-inexact solution we use the standard definition, see e. g.
[17]:

######  Definition 1.

A point $\tilde{z}$ is a $\delta$-inexact solution with $\delta\geq 0$, i.e.

$\tilde{z}\in\arg\min^{\delta}_{z\in Q}\Phi(z),$

if and only if there exists $g\in\partial\Phi(\tilde{z})$ such that $\langle
g,z^{*}-\tilde{z}\rangle\geq-\delta$.

Due to Definition 1, a point $\tilde{z}$ provides the minimal objective
function value of (20) up to the error $\delta$. This can be easily seen,
because $\Phi$ is convex and therefore it holds for any $z\in Q$:

$\Phi(z^{*})\geq\Phi(\tilde{z})+\langle
g,z^{*}-\tilde{z}\rangle\geq\Phi(\tilde{z})-\delta,$

which is equivalent to

$\Phi(\tilde{z})\leq\Phi(z^{*})+\delta\leq\Phi(z)+\delta.$ (22)

In what follows, we shall focus on decision variables $z$, which can be
separated into two blocks, i.e. $z=(x,p)$. For those situations, alternating
minimization methods can be applied. The block structure enables to minimize
the objective function for each block separately, which is, in particular, a
valuable property for big data applications. Over years, many convergence
results for alternating minimization methods under different assumptions were
shown, see e .g. [8], [10], and [3]. The authors in [16] show, that under
assumptions such as convexity for one and strong convexity for the other
objective term, the inexact alternating minimization algorithm applied to the
primal coincides with the inexact proximal gradient method to the dual
problem. Recently, in [14] an alternating minimization method was used for
soft clustering. There, the objective function additionally includes an
interaction term linking both blocks of variables. Under certain assumptions,
linear convergence was established provided the problem can be solved exactly
in each block. In this chapter, we are interested in an inexact alternating
minimization algorithm for objective functions equipped with the structure
introduced in [14]. Let $Q_{1},Q_{2}$ be closed and convex sets in a finite
dimensional vector spaces, and the objective function is given by

$\Phi(x,p)=f(x)+\langle G_{1}(x),G_{2}(p)\rangle+h(p),\quad x\in Q_{1},p\in
Q_{2},$ (23)

where the functions $f$ and $h$ are $\sigma_{1}$\- and $\sigma_{2}$-strongly
convex, respectively, and the functions $G_{1}$ and $G_{2}$ are Lipschitz-
continuous with moduli $L_{1}$ and $L_{2}$, respectively, such that the
interaction term $\langle G_{1}(x),G_{2}(p)\rangle$ is convex and closed in
$x\in Q_{1}$ for any fixed $p\in Q_{2}$ and vice versa. Further, we assume the
following strict inequality to hold

$L_{1}^{2}\cdot L_{2}^{2}<\sigma_{1}\cdot\sigma_{2},$ (24)

under which the function $\Phi$ is shown to be strongly convex on
$Q=Q_{1}\times Q_{2}$, see [14]. Let the optimal solution of (20) be written
as $z^{*}=(x^{*},p^{*})$. In order to solve (20), an alternating minimization
method has been proposed in [14]. The latter generates sequences
$\\{x_{\ell}\\}_{\ell\geq 0}$ and $\\{p_{\ell}\\}_{\ell\geq 1}$ as follows:

Choose $x_{0}\in Q_{1}$. For $\ell=0,1,2,\ldots$ update: $\displaystyle
p_{\ell+1}=\arg\min_{p\in Q_{2}}\Phi(x_{\ell},p)=u(x_{\ell})$, $\displaystyle
x_{\ell+1}=\arg\min_{x\in Q_{1}}\Phi(x,p_{\ell+1})=v(p_{\ell+1})$.

Convergence analysis in [14] is based on fixed point iteration. For that, the
operators $T:Q_{1}\mapsto Q_{1}$ and $S:Q_{2}\mapsto Q_{2}$ are defined as
follows:

$T(x)=v(u(x)),\quad S(p)=v(u(p)).$ (25)

This enables to write the update step of the alternating minimization scheme:

$\displaystyle x_{\ell+1}=T(x_{\ell}),\quad p_{\ell+1}=S(p_{\ell}).$

Under condition (24), $T(\cdot)$ and $S(\cdot)$ are contraction mappings.
Thus, the linear convergence of the generated sequences to the minimizer
$\left(x^{*},p^{*}\right)$ of $\Phi$ could be shown in [14]:

$\|x_{\ell+1}-x^{*}\|\leq\lambda^{\ell+1}\|x(0)-x^{*}\|,\quad\|p_{\ell+1}-p^{*}\|\leq\lambda^{\ell}\|p(1)-p^{*}\|,$

where

$\lambda=\frac{L_{1}^{2}\cdot L_{2}^{2}}{\sigma_{1}\cdot\sigma_{2}}<1.$

We analyze an inexact version of the alternating minimization method applied
to objective functions in (23), when subproblems are solved inexactly in the
sense of Definition 1. For that, let us adapt the algorithm in the following
way:

Choose $x_{0}\in Q_{1}$. For $\ell=0,1,2,\ldots$ update:
$\displaystyle\tilde{p}_{\ell+1}=\arg\min^{\delta_{1}}_{p\in
Q_{2}}\Phi(\tilde{x}_{\ell},p)=u^{\delta_{1}}(\tilde{x}_{\ell})$,
$\displaystyle\tilde{x}_{\ell+1}=\arg\min^{\delta_{2}}_{x\in
Q_{1}}\Phi(x,\tilde{p}_{\ell+1})=v^{\delta_{2}}(\tilde{p}_{\ell+1})$.

We allow different accuracy for the above subproblems. The equations also
suggest that in iteration $t$ a $\delta$-error is made twice. This can be seen
by looking at the function values evaluated at two consecutive points of the
sequences $\\{\tilde{x}_{\ell}\\}_{t\geq 0}$ and
$\\{\tilde{p}_{\ell}\\}_{t\geq 0}$ generated via the $\delta$-inexact
solutions of the auxiliary optimization problems:

$\displaystyle\Phi(\tilde{x}_{\ell+1},\tilde{p}_{\ell+1})$
$\displaystyle=f(\tilde{x}_{\ell+1})+\langle
G_{1}(\tilde{x}_{\ell+1}),G_{2}(\tilde{p}_{\ell+1})\rangle+h(\tilde{p}_{\ell+1})$
$\displaystyle\leq f(\tilde{x}_{\ell})+\delta_{2}+\langle
G_{1}(\tilde{x}_{\ell}),G_{2}(\tilde{p}_{\ell+1})\rangle+h(\tilde{p}_{\ell+1})$
$\displaystyle\leq f(\tilde{x}_{\ell})+\delta_{2}+\langle
G_{1}(\tilde{x}_{\ell}),G_{2}(\tilde{p}_{\ell})\rangle+h(\tilde{p}_{\ell})+\delta_{1}$
$\displaystyle\leq\Phi(\tilde{x}_{\ell},\tilde{p}_{\ell})+2\cdot\max\\{\delta_{1},\delta_{2}\\}.$

Next, we estimate the distances between $u^{\delta_{1}}(x)$ and $u(x)$ as well
as between $v^{\delta_{2}}(p)$ and $v(p)$.

######  Lemma 3.1.

For any $x\in Q_{1}$ it holds:

$\|u^{\delta_{1}}(x)-u(x)\|\leq\sqrt{\frac{2\delta_{1}}{\sigma_{2}}},$

and for any $p\in Q_{2}$ it holds:

$\|v^{\delta_{2}}(p)-v(p)\|\leq\sqrt{\frac{2\delta_{2}}{\sigma_{1}}}.$

###### Proof.

We apply (21) to derive:

$\begin{array}[]{rcl}h(u^{\delta_{1}}(x))+\langle
G_{1}(x),G_{2}(u^{\delta_{1}}(x))\rangle&\geq&h(u(x))+\langle
G_{1}(x),G_{2}(u(x))\rangle\\\ \\\
&&\displaystyle+\frac{\sigma_{2}}{2}\|u^{\delta_{1}}(x)-u(x)\|^{2}.\end{array}$

Due to (22) we additionally have:

$h(u(x))+\langle G_{1}(x),G_{2}(u(x))\rangle\geq h(u^{\delta_{1}}(x))+\langle
G_{1}(x),G_{2}(u^{\delta_{1}}(x))\rangle-\delta_{1},$

Altogether, we obtain:

$\|u^{\delta_{1}}(x)-u(x)\|^{2}\leq\frac{2\delta_{1}}{\sigma_{2}}.$

The proof for $\|v^{\delta_{2}}(p)-v(p)\|$ follows analogously. ∎

Let us elaborate on the continuity properties for operators
$u^{\delta_{1}}(\cdot)$ and $v^{\delta_{2}}(\cdot)$.

######  Lemma 3.2.

For any $x_{1},x_{2}\in Q_{1}$ it holds:

$\|u^{\delta_{1}}(x_{1})-u^{\delta_{1}}(x_{2})\|\leq
2\cdot\sqrt{\frac{2\delta_{1}}{\sigma_{2}}}+\frac{L_{1}\cdot
L_{2}}{\sigma_{2}}\cdot\|x_{1}-x_{2}\|,$

and for any $p_{1},p_{2}\in Q_{2}$ it holds:

$\|v^{\delta_{2}}(p_{1})-v^{\delta_{2}}(p_{2})\|\leq
2\cdot\sqrt{\frac{2\delta_{2}}{\sigma_{1}}}+\frac{L_{1}\cdot
L_{2}}{\sigma_{1}}\cdot\|p_{1}-p_{2}\|.$

###### Proof.

Applying Lemma 3.1 and the triangle inequality twice yields:

$\displaystyle\|u^{\delta}(x_{1})-u^{\delta}(x_{2})\|$
$\displaystyle\leq\|u^{\delta}(x_{1})-u(x_{1})\|+\|u(x_{1})-u^{\delta_{1}}(x_{2})\|$
$\displaystyle\leq\sqrt{\frac{2\delta_{1}}{\sigma_{2}}}+\|u(x_{1})-u(x_{2})\|+\|u(x_{2})-u^{\delta_{1}}(x_{2})\|$
$\displaystyle\leq\sqrt{\frac{2\delta_{1}}{\sigma_{2}}}+\frac{L_{1}\cdot
L_{2}}{\sigma_{2}}\cdot\|x_{1}-x_{2}\|+\sqrt{\frac{2\delta_{1}}{\sigma_{2}}}.$

The last inequality is due to [14], where it is shown for any $x_{1},x_{2}\in
Q_{1}$:

$\|u(x_{1})-u(x_{2})\|\leq\frac{L_{1}\cdot L_{2}}{\sigma_{2}}\|x_{1}-x_{2}\|.$

Similar reflections yield the result for
$\|v^{\delta_{2}}(p_{1})-v^{\delta_{2}}(p_{2})\|$. ∎

Let us introduce inexact versions of the operators $T$ and $S$:

$T^{\delta}(x)=v^{\delta_{2}}(u^{\delta_{1}}(x)),\quad
S^{\delta}(p)=u^{\delta_{1}}(v^{\delta_{2}}(p)),$

which we use to rewrite the update of the inexact alternating minimization as

$\tilde{x}_{\ell+1}=T^{\delta}(\tilde{x}_{\ell}),\quad\tilde{p}_{\ell+1}=S^{\delta}(\tilde{p}_{\ell}).$
(26)

The following result provides uniform continuity up to an error of the
operators defined in (26).

######  Proposition 3.1.

For any $\tilde{x}_{1},\tilde{x}_{2}\in Q_{1}$ it holds:

$\|T^{\delta}(\tilde{x}_{1})-T^{\delta}(\tilde{x}_{2})\|\leq\lambda\|\tilde{x}_{1}-\tilde{x}_{2}\|+2\cdot\sqrt{\frac{2\delta_{2}}{\sigma_{1}}}+2\cdot\sqrt{\frac{2\delta_{1}}{\sigma_{2}}}\cdot\frac{L_{1}\cdot
L_{2}}{\sigma_{1}},$

and for any $\tilde{p}_{1},\tilde{p}_{2}\in Q_{2}$ it holds:

$\|S^{\delta}(\tilde{p}_{1})-S^{\delta}(\tilde{p}_{2})\|\leq+\lambda\|\tilde{p}_{1}-\tilde{p}_{2}\|+2\cdot\sqrt{\frac{2\delta_{1}}{\sigma_{2}}}+2\cdot\sqrt{\frac{2\delta_{2}}{\sigma_{1}}}\cdot\frac{L_{1}\cdot
L_{2}}{\sigma_{2}}.$

###### Proof.

We apply Lemma 3.2 to derive

$\displaystyle\|T^{\delta}(\tilde{x}_{1})-T^{\delta}(\tilde{x}_{2})\|$
$\displaystyle=\|v^{\delta_{2}}(u^{\delta_{1}}(\tilde{x}_{1}))-v^{\delta_{2}}(u^{\delta_{1}}(\tilde{x}_{2}))\|$
$\displaystyle\leq
2\cdot\sqrt{\frac{2\delta_{2}}{\sigma_{1}}}+\frac{L_{1}\cdot
L_{2}}{\sigma_{1}}\cdot\|u^{\delta_{1}}(\tilde{x}_{1}))-(u^{\delta_{1}}(\tilde{x}_{2}))\|$
$\displaystyle\leq
2\cdot\sqrt{\frac{2\delta_{2}}{\sigma_{1}}}+\frac{L_{1}\cdot
L_{2}}{\sigma_{1}}\cdot
2\sqrt{\frac{2\delta_{1}}{\sigma_{2}}}+\underbrace{\frac{L_{1}^{2}\cdot
L_{2}^{2}}{\sigma_{1}\cdot\sigma_{2}}}_{=\lambda}\cdot\|\tilde{x}_{1}-\tilde{x}_{2}\|.$

Again, the second assertion follows similarly. ∎

Since we cannot rely on the contraction property of $T^{\delta}$ and
$S^{\delta}$, the convergence analysis of the sequences
$\\{\tilde{x}_{\ell}\\}_{\ell\geq 0}$ and $\\{\tilde{p}_{\ell}\\}_{\ell\geq
1}$ becomes involved. For that, we start with the following auxiliary result.

######  Lemma 3.3.

For any $x\in Q_{1}$ it holds:

$\left\|T(x)-T^{\delta}(x)\right\|\leq\sqrt{\frac{2\delta_{2}}{\sigma_{1}}}+\frac{L_{1}\cdot
L_{2}}{\sigma_{1}}\cdot\sqrt{\frac{2\delta_{1}}{\sigma_{2}}},$

and for any $p\in Q_{2}$ it holds:

$\left\|S(p)-S^{\delta}(p)\right\|\leq\sqrt{\frac{2\delta_{1}}{\sigma_{2}}}+\frac{L_{1}\cdot
L_{2}}{\sigma_{2}}\cdot\sqrt{\frac{2\delta_{2}}{\sigma_{1}}}.$

###### Proof.

We show the first part. It follows by means of Lemmata 3.1 and 3.2.

$\displaystyle\left\|T(x)-T^{\delta}(x)\right\|$
$\displaystyle=\left\|v(u(x))-v^{\delta_{2}}(u^{\delta_{1}}(x))\right\|$
$\displaystyle\leq\left\|v(u(x))-v(u^{\delta_{1}}(x))\right\|+\left\|v(u^{\delta_{1}}(x))-v^{\delta_{2}}(u^{\delta_{1}}(x))\right\|$
$\displaystyle\leq\frac{L_{1}\cdot
L_{2}}{\sigma_{1}}\cdot\left\|u(x)-u^{\delta_{1}}(x)\right\|+\sqrt{\frac{2\delta_{2}}{\sigma_{1}}}$
$\displaystyle\leq\frac{L_{1}\cdot
L_{2}}{\sigma_{1}}\cdot\sqrt{\frac{2\delta_{1}}{\sigma_{2}}}+\sqrt{\frac{2\delta_{2}}{\sigma_{1}}}.$

Clearly, the proof of the second part is similar. ∎

Now we are ready to state the main result concerning convergence of the
inexact alternating minimization scheme.

######  Theorem 3.1.

For the inexact alternating minimization scheme holds:

$\left\|\tilde{x}_{\ell+1}-x^{*}\right\|\leq\lambda^{\ell+1}\left\|x_{0}-x^{*}\right\|+\sqrt{\frac{2\delta_{2}}{\sigma_{1}}}+\frac{L_{1}\cdot
L_{2}}{\sigma_{1}}\cdot\sqrt{\frac{2\delta_{1}}{\sigma_{2}}}$ (27)

and

$\left\|\tilde{p}_{\ell+1}-p^{*}\right\|\leq\lambda^{\ell}\left[\left\|p_{1}-p^{*}\right\|+\sqrt{\frac{2\delta_{1}}{\sigma_{2}}}\right]+\sqrt{\frac{2\delta_{1}}{\sigma_{2}}}+\frac{L_{1}\cdot
L_{2}}{\sigma_{2}}\cdot\sqrt{\frac{2\delta_{2}}{\sigma_{1}}}.$ (28)

###### Proof.

We apply Lemma 3.3 to derive:

$\displaystyle\left\|\tilde{x}_{\ell+1}-x_{\ell+1}\right\|$
$\displaystyle\leq\left\|T(x_{\ell})-T(\tilde{x}_{\ell})\right\|+\left\|T(\tilde{x}_{\ell})-T^{\delta}(\tilde{x}_{\ell})\right\|$
$\displaystyle\leq\lambda\cdot\left\|x_{\ell}-\tilde{x}_{\ell}\right\|+\sqrt{\frac{2\delta_{2}}{\sigma_{1}}}+\frac{L_{1}\cdot
L_{2}}{\sigma_{1}}\cdot\sqrt{\frac{2\delta_{1}}{\sigma_{2}}}$
$\displaystyle\leq\ldots\leq\lambda^{\ell+1}\underbrace{\left\|x_{0}-x_{0}\right\|}_{=0}+\sqrt{\frac{2\delta_{2}}{\sigma_{1}}}+\frac{L_{1}\cdot
L_{2}}{\sigma_{1}}\cdot\sqrt{\frac{2\delta_{1}}{\sigma_{2}}}.$

We are therefore able to estimate the distance of the $\left(t+1\right)$-th
iterate to the minimizer:

$\displaystyle\left\|\tilde{x}_{\ell+1}-x^{*}\right\|$
$\displaystyle\leq\left\|\tilde{x}_{\ell+1}-x_{\ell+1}\right\|+\left\|x_{\ell+1}-x^{*}\right\|$
$\displaystyle\leq\sqrt{\frac{2\delta_{2}}{\sigma_{1}}}+\frac{L_{1}\cdot
L_{2}}{\sigma_{1}}\cdot\sqrt{\frac{2\delta_{1}}{\sigma_{2}}}+\lambda^{\ell+1}\|x_{0}-x^{*}\|.$

For the proof of the inequality (28) note that the first iterate of the
algorithm is not chosen freely. Instead it is the solution of the
corresponding optimization problem. Hence, the first iterates of the exact and
inexact version are in general not equal, i.e. $p_{1}\neq\tilde{p}_{1}$, which
provides

$\left\|\tilde{p}_{\ell+1}-p_{\ell+1}\right\|\leq\lambda^{\ell}\left\|\tilde{p}_{1}-p_{1}\right\|+\sqrt{\frac{2\delta_{1}}{\sigma_{2}}}+\frac{L_{1}\cdot
L_{2}}{\sigma_{2}}\cdot\sqrt{\frac{2\delta_{2}}{\sigma_{1}}}.$

It remains to recall that $p_{1}=u(x_{0})$ and
$\tilde{p}_{1}=u^{\delta_{1}}(x_{0})$ and apply Lemma 3.1. The result (28)
follows then in the same manner as for (27). ∎

According to Theorem 3.1 the inexact alternating minimization does not
converge in general. Yet, the distance to the minimizer is bounded by the
resp. second term of the right hand side of inequalities (27) and (28). By
taking the limits, we obtain:

$\lim_{t\to\infty}\left\|\tilde{x}_{\ell+1}-x^{*}\right\|\leq\sqrt{\frac{2\delta_{2}}{\sigma_{1}}}+\frac{L_{1}\cdot
L_{2}}{\sigma_{1}}\cdot\sqrt{\frac{2\delta_{1}}{\sigma_{2}}}$

and

$\lim_{t\to\infty}\left\|\tilde{p}_{\ell+1}-p^{*}\right\|\leq\sqrt{\frac{2\delta_{1}}{\sigma_{2}}}+\frac{L_{1}\cdot
L_{2}}{\sigma_{2}}\cdot\sqrt{\frac{2\delta_{2}}{\sigma_{1}}}.$

Obviously, convergence is guaranteed if the subproblems can be solved exactly,
i.e. if $\delta_{1}=\delta_{2}=0$. This is not surprising as in this case the
inexact alternating minimization scheme coincides the exact method proposed by
[14]. Therefore, the iterates generated by the inexact alternating
minimization scheme (26) coincide withe the those generated by the exact
method. Inequalities (27) and (28) show that the total error of the inexact
alternating minimization scheme can be controlled. Furthermore, large
convexity parameters not only improve the rate of convergence for the exact
version of the algorithm, but also decrease the total accumulated error in the
inexact scenario.

##  4 Convergence Analysis

We analyze the convergence of our network manipulation algorithm by applying
the general theory of inexact alternating minimization from Section 3. First,
we estimate the convexity parameter of

$h(P)=\sum_{i=1}^{N}E_{i}^{*}(p_{i})$

w.r.t. the norm

$\|P\|_{\mathbb{H}}=\left(\sum_{i=1}^{N}\|p_{i}\|_{1}^{2}\right)^{\frac{1}{2}},\quad
P\in\Delta_{K}^{N}.$

It turns out that the strong convexity of $E_{i}^{*}$ holds due to Assumption
2. This has been recently shown in [12].

######  Lemma 4.1 ([12]).

Let the differences $\epsilon^{(k)}_{i}-\epsilon^{(m)}_{i}$ of random errors
have modes $\bar{z}^{k,m}_{i}\in\mathbb{R}$, $k\not=m$. Then, the
corresponding convex conjugate $E^{*}_{i}$ is $\beta_{i}$-strongly convex
w.r.t. the norm $\|\cdot\|_{1}$, where the convexity parameter is given by

$\beta_{i}=\frac{1}{\displaystyle
2\sum_{k=1}^{K}\sum_{m\not=k}g^{k,m}_{i}\left(\bar{z}_{k,m}\right)},$

and $g^{k,m}_{i}$ denotes the density function of
$\epsilon^{(k)}_{i}-\epsilon^{(m)}_{i}$.

Let us review important discrete choice models in accordance with Assumption
2, where convexity parameters can be explicitly estimated.

######  Remark 1.

In the multinomial logit model (MNL), the error terms are IID Gumbel
distributed with zero location parameter and variance
$\frac{\pi\cdot\mu}{\sqrt{6}}$, where $\mu>0$ [2]. The choice probabilities
are:

$\mathbb{P}\left(u^{(k)}+\epsilon^{(k)}=\max_{1\leq m\leq
K}u^{(m)}+\epsilon^{(m)}\right)=\frac{e^{\nicefrac{{u^{(k)}}}{{\mu}}}}{\displaystyle\sum_{m=1}^{K}e^{\nicefrac{{u^{(m)}}}{{\mu}}}},\quad
k=1,\ldots,K.$

From the choice probabilities we can conclude that the parameter $\mu$
reflects the randomness of the decision. If the latter converges to zero, this
would lead to the deterministic decision based on the observable utility. On
the other hand, very large values of the parameter provide very random
choices, tending towards the uniform distribution in the limit. The convex
conjugate of the corresponding surplus function is up to an additive constant:

$E^{*}(p)=\mu\sum_{k=1}^{K}p^{(k)}\cdot\ln p^{(k)}.$

It is well known from Pinsker inequality that this function is $\mu$-strongly
convex w.r.t. the norm $\|\cdot\|_{1}$. Another famous example is the nested
logit model (NL) introduced in [11]. Compared to the MNL, the NL is more
appropriate in situations where some of the alternatives are correlated, i.e.
the axiom of irrelevance of independent alternatives is violated, see e. g.
[2]. In the NL, each alternative $k$ belongs to one of $L$ different nests
$N_{\ell}\subset\\{1,\ldots,K\\}$ for $\ell=1,\ldots,L$. The choice
probabilities for $k\in N_{\ell}$, $\ell\in L$ are

$\mathbb{P}\left(u^{(k)}+\epsilon^{(k)}=\max_{1\leq m\leq
K}u^{(m)}+\epsilon^{(j)}\right)=\frac{e^{\mu_{\ell}\ln\sum_{m\in
N_{\ell}}e^{\nicefrac{{u^{(m)}}}{{\mu_{\ell}}}}}}{\displaystyle\sum_{\ell\in
L}e^{\mu_{\ell}\ln\sum_{m\in
N_{\ell}}e^{\nicefrac{{u^{(m)}}}{{\mu_{\ell}}}}}}\cdot\frac{e^{\nicefrac{{u^{(k)}}}{{\mu_{\ell}}}}}{\displaystyle\sum_{m\in
N_{\ell}}e^{\nicefrac{{u^{(m)}}}{{\mu_{\ell}}}}},$

where the following condition shall be satisfied:

$0<\mu_{\ell}\leq 1,\quad\ell=1,\ldots,L.$

The parameter $\mu_{\ell}$ determines the randomness of choices within the
$\ell$-th nest. Further, the correlation of alternatives within the same
$\ell$-th nest is given by $1-\mu_{\ell}^{2}$. The convex conjugate of the NL
surplus function has been derived up to an additive constant in [6]:

$E^{*}(p)=\sum_{\ell\in L}\mu_{\ell}\sum_{i\in N_{\ell}}p^{(m)}\ln
p^{(m)}+\sum_{\ell\in L}\left(1-\mu_{\ell}\right)\left(\sum_{m\in
N_{\ell}}p^{(m)}\right)\ln\left(\sum_{m\in N_{\ell}}p^{(m)}\right).$

It is $\displaystyle\left(\min_{\ell\in L}\mu_{\ell}\right)$-strongly convex
w.r.t. the norm $\|\cdot\|_{1}$. In [13], analogous results were obtained for
general nested logit models (GNL). ∎

We state Lemma 4.2 concerning the strong convexity of the function $h$ defined
in (18).

######  Lemma 4.2.

Let the functions $E_{i}^{*}$ be $\beta_{i}$-strongly convex w.r.t. the norm
$\|\cdot\|_{1}$, $i=1,\ldots,N$. Then, the function $h$ is
$\sigma_{2}$-strongly convex w.r.t. the norm $\|\cdot\|_{\mathbb{H}}$, where

$\sigma_{2}=\min_{1\leq i\leq N}\beta_{i}.$

###### Proof.

Take any $P,Q\in\Delta_{K}^{N},\alpha\in\left[0,1\right]$. Then the following
holds

$\displaystyle h(\alpha\cdot P+(1-\alpha)\cdot Q)$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{N}E^{*}_{i}\left(\alpha\cdot p_{i}+(1-\alpha)\cdot
q_{i}\right)$ $\displaystyle\leq$
$\displaystyle\alpha\cdot\sum_{i=1}^{N}E^{*}_{i}(p_{i})+(1-\alpha)\cdot\sum_{i=1}^{N}E^{*}_{i}(q_{i})-\alpha\cdot(1-\alpha)\cdot\sum_{i=1}^{N}\frac{\beta_{i}}{2}\|p_{i}-q_{i}\|_{1}^{2}$
$\displaystyle\leq$
$\displaystyle\alpha\cdot\sum_{i=1}^{N}E^{*}(p_{i})+(1-\alpha)\cdot\sum_{i=1}^{N}E^{*}(q_{i})-\alpha\cdot(1-\alpha)\cdot\frac{\sigma_{2}}{2}\cdot\sum_{i=1}^{N}\|p_{i}-q_{i}\|_{1}^{2}$
$\displaystyle=$ $\displaystyle\alpha\cdot h(P)+(1-\alpha)\cdot
h(Q)-\alpha\cdot(1-\alpha)\cdot\frac{\sigma_{2}}{2}\cdot\|P-Q\|^{2}_{\mathbb{H}}.$

∎

Hence, the worst convexity parameter amongst all agents determines the strong
convexity of the function $h(P)$.

In order to apply results from Section 3, we secondly need to show that

$f(X)=-\sum_{k=1}^{K}\frac{1}{\eta_{k}}\cdot\pi_{k}\left(M^{t}\cdot
x_{k}\right)$

is strongly convex w.r.t. the norm

$\|X\|_{\mathbb{F}}=\left[\sum_{k=1}^{K}\|x_{k}\|_{2}^{2}\right]^{\frac{1}{2}},\quad
X\in\Delta_{n}^{K}.$

For that, we need to assume that the underlying network is regular.

######  Assumption 4.

Let for the smallest singular value of $M$ hold
$\sigma_{\min}\left(M\right)>0$.

As a consequence, we are able to estimate the convexity parameter of $f$
w.r.t. the norm $\|\cdot\|_{\mathbb{F}}$.

######  Lemma 4.3.

The function $f$ is $\sigma_{1}$-strongly convex w.r.t. the norm
$\|\cdot\|_{\mathbb{F}}$, where

$\sigma_{1}=\min_{1\leq k\leq
K}\frac{\tau_{k}}{\eta_{k}}\cdot\left[\sigma_{\min}\left(M\right)\right]^{2t}.$

###### Proof.

First, we recall:

$\sigma_{\min}\left(M\right)=\min_{\|x\|_{2}=1}\|M\cdot x\|_{2}.$

Hence, we get:

$\displaystyle\sigma_{\min}\left(M^{t}\right)$
$\displaystyle=\sigma_{\min}\left(M\cdot
M^{t-1}\right)=\min_{\|x\|_{2}=1}\left\|M\cdot M^{t-1}\cdot x\right\|_{2}$
$\displaystyle\geq\sigma_{\min}\left(M\right)\cdot\min_{\|x\|_{2}=1}\left\|M^{t-1}\cdot
x\right\|_{2}\geq\ldots\geq\left[\sigma_{\min}\left(M\right)\right]^{t}.$

For any $\alpha\in[0,1]$ and $X,Z\in\Delta_{n}^{K}$ it holds due to the
$\tau_{k}$-strong convexity of $-\pi_{k}$ w.r.t. the norm $\|\cdot\|_{2}$:

$\displaystyle-\pi_{k}\left(\alpha\cdot M^{t}\cdot
x_{k}+\left(1-\alpha\right)\cdot M^{t}\cdot z_{k}\right)$ $\displaystyle\leq$
$\displaystyle\alpha\cdot\pi_{k}\left(M^{t}\cdot
x_{k}\right)-\left(1-\alpha\right)\cdot\pi_{k}\left(M^{t}\cdot z_{k}\right)$
$\displaystyle-\alpha\cdot\left(1-\alpha\right)\cdot\frac{\tau_{k}}{2}\cdot\|M^{t}x_{k}-M^{t}z_{k}\|_{2}^{2}.$

Further, we have:

$\|M^{t}x_{k}-M^{t}z_{k}\|_{2}\geq\sigma_{\min}\left(M^{t}\right)\cdot\|x_{k}-z_{k}\|_{2}\geq\left[\sigma_{\min}\left(M\right)\right]^{t}\cdot\|x_{k}-z_{k}\|_{2}.$

Hence, the convexity parameter of $-\pi_{k}\left(M^{t}x_{k}\right)$ is
$\tau_{k}\cdot\left[\sigma_{\min}\left(M\right)\right]^{2t}$. The assertion
follows analogously to the proof of Lemma 4.2. ∎

Note that the considerations in the proof of Lemma 4.3 also guarantee the
existence of a unique minimizer $x^{*}_{k}(P)$ for each objective function in
(13), i.e. the manipulation matrix $X_{*}(P)$ is indeed well defined.

It remains to inspect the multiplicative term. We study the Lipschitz-
continuity property of the operator

$G(X)=\left(g_{1}(X),\ldots,g_{N}(X)\right)\in\mathbb{R}^{K\times N},$

where

$g_{i}(X)=\left(\|v_{i}-M^{t}\cdot x_{1}\|_{2},\ldots,\|v_{i}-M^{t}\cdot
x_{K}\|_{2}\right)^{T},\;i=1,\ldots,N.$

For that, the dual norm of $\|\cdot\|_{\mathbb{H}}$ is required, see [14]:

$\|Z\|^{*}_{\mathbb{H}}=\left[\sum_{i=1}^{N}\|z_{i}\|_{\infty}^{2}\right]^{\frac{1}{2}},\quad
Z\in\mathbb{R}^{K\times N}.$

######  Lemma 4.4.

The operator $G$ is Lipschitz-continuous with modulus

$L_{1}=N^{\frac{1}{2}}\cdot\left[\sigma_{\max}\left(M\right)\right]^{t},$

where $\sigma_{\max}$ denotes the largest singular value of $M$. This is to
say that

$\|G(X)-G(Y)\|_{\mathbb{H}}^{*}\leq L_{1}\cdot\|X-Y\|_{\mathbb{F}},\quad
X,Y\in\Delta^{K}_{n}.$

###### Proof.

The Lipschitz-continuity of $G$ follows mainly from [14]. In fact, take any
$X,Y\in\Delta^{K}_{n}$:

$\|G(X)-G(Y)\|_{\mathbb{H}}^{*}=\left[\sum_{i=1}^{N}\|g_{i}(X)-g_{i}(Y)\|_{\infty}^{2}\right]^{\frac{1}{2}}.$

It holds by means of the triangle inequality:

$\begin{array}[]{rcl}\left|g_{i}(X)-g_{i}(Y)\right|&=&\left|\|v_{i}-M^{t}\cdot
x_{k}\|_{2}-\|v_{i}-M^{t}\cdot y_{k}\|_{2}\right|\\\ \\\
&\leq&\|M^{t}x_{k}-M^{t}y_{k}\|_{2}\leq\left[\sigma_{\max}\left(M\right)\right]^{t}\cdot\|x_{k}-y_{k}\|_{2}.\end{array}$

Therefore,

$\displaystyle\|g_{i}(X)-g_{i}(Y)\|_{\infty}^{2}$
$\displaystyle=\left(\max_{1\leq k\leq K}\left|\|v_{i}-M^{t}\cdot
x_{k}\|_{2}-\|v_{i}-M^{t}\cdot y_{k}\|_{2}\right|\right)^{2}$
$\displaystyle\leq\left[\sigma_{\max}\left(M\right)\right]^{2t}\cdot\max_{1\leq
k\leq K}\|x_{k}-y_{k}\|_{2}^{2}$
$\displaystyle\leq\left[\sigma_{\max}\left(M\right)\right]^{2t}\cdot\sum_{k=1}^{K}\|x_{k}-y_{k}\|_{2}^{2},$

and the assertion follows. ∎

Note that all components of $G$ are convex and nonnegative. Moreover, all
entries of the matrices $P$ are nonnegative. Due to Lemmata 4.2 and 4.3,
$\Phi(\cdot,P)$ is strongly convex for any fixed $P\in\Delta_{K}^{N}$ and
$\Phi(X,\cdot)$ is strongly convex for any fixed $X\in\Delta_{n}^{K}$. We
therefore conclude that the alternating update steps of our network
manipulation algorithm are well defined.

Let us finally present our main results on the convergence of the network
manipulation algorithm. Recall that the derived constants are as follows:

$\sigma_{1}=\min_{1\leq k\leq
K}\frac{\tau_{k}}{\eta_{k}}\cdot\left[\sigma_{\min}\left(M\right)\right]^{2t},\quad\sigma_{2}=\min_{1\leq
i\leq N}\beta_{i},$ (29)

and

$L_{1}=N^{\frac{1}{2}}\cdot\left[\sigma_{\max}\left(M\right)\right]^{t},\quad
L_{2}=1.$ (30)

Moreover, for the rate of convergence we have:

$\lambda=\frac{L_{1}^{2}\cdot
L_{2}^{2}}{\sigma_{1}\cdot\sigma_{2}}=\frac{N\cdot\left[\kappa(M)\right]^{2t}}{\displaystyle\min_{1\leq
k\leq K}\frac{\tau_{k}}{\eta_{k}}\cdot\min_{1\leq i\leq N}\beta_{i}},$ (31)

where $\kappa(M)$ denotes the condition number of the matrix $M$. In order to
establish convergence of the network manipulation algorithm, we need an
additional assumption which indicates a certain stability for the model.

######  Assumption 5.

It holds:

$\left[\kappa\left(M\right)\right]^{t}<{\left(\frac{\displaystyle\min_{1\leq
k\leq K}\frac{\tau_{k}}{\eta_{k}}\cdot\min_{1\leq i\leq
N}\beta_{i}}{N}\right)}^{\frac{1}{2}}.$ (32)

Assumption 5 is a version of condition (24), which enforces $\lambda<1$. The
latter guarantees strong convexity of the potential function (19). The
straightforward application of Theorem 3.1 now provides:

######  Theorem 4.1.

Let $\left(X^{*},P^{*}\right)\in\Delta_{n}^{K}\times\Delta_{K}^{N}$ be the
unique minimizer of the potential function (19). Then, for the sequences
$\\{\tilde{X}_{\ell}\\}_{\ell\geq 0}$ and $\\{\tilde{P}_{\ell}\\}_{\ell\geq
1}$ it holds:

$\left\|\tilde{X}_{\ell+1}-X^{*}\right\|_{\mathbb{F}}\leq\lambda^{\ell+1}\left\|X_{0}-X^{*}\right\|_{\mathbb{F}}+\sqrt{\frac{2\delta_{2}}{\sigma_{1}}}+\frac{L_{1}\cdot
L_{2}}{\sigma_{1}}\cdot\sqrt{\frac{2\delta_{1}}{\sigma_{2}}}$ (33)

and

$\left\|\tilde{P}_{\ell+1}-P^{*}\right\|_{\mathbb{H}}\leq\lambda^{\ell}\left[\left\|P_{1}-P^{*}\right\|_{\mathbb{H}}+\sqrt{\frac{2\delta_{1}}{\sigma_{2}}}\right]+\sqrt{\frac{2\delta_{1}}{\sigma_{2}}}+\frac{L_{1}\cdot
L_{2}}{\sigma_{2}}\cdot\sqrt{\frac{2\delta_{2}}{\sigma_{1}}},$ (34)

where $\sigma_{1}$, $\sigma_{2}$, $L_{1}$, $L_{2}$, and $\lambda$ are given in
(29)-(31).

Let us comment on Assumption 5 by elaborating how the model parameters enter
into the inequality (32):

  * Interaction network. The network structure plays a key role in (32). This is reflected by the condition number $\kappa\left(M\right)$. Its large values cause instability of manipulation, since small changes regarding the aspired states could lead to big changes of optimal starting distributions. In other words, a more predictive pattern of network transitions speeds up the convergence. The minimum value of the condition number is attained for permutation matrices. In this case, the network interaction is obviously predictable, i.e. organizations can easily determine how network participants distribute information. For similar reasons, the number of interaction periods $t$ has a negative impact on possibility of manipulation. More periods hamper the influence of the starting distribution on the resulting state. Instead, if time progresses the latter is mainly determined just by the network structure independently of the starting distributions.

  * Agents. Clearly, more agents $N$ slow down the rate, as organizations have to pay attention to more aspired states. Moreover, large values of $\beta_{i}$, $i=1,\ldots,N$, improve the rate of convergence. In order to interpret this fact, we refer to Remark 1. There, it has been shown that $\beta_{i}$’s, can be viewed as measures that agents are still pretty uncertain about their decisions. Due to the duality of discrete choice and rational inattention, agent prone to errors have high information processing costs. Thus, these agent pay less attention to the observable utility, i.e. if their aspired states were reached. The fact that imperfect behavior of agents could help to faster stabilize economic systems was recently also described in [13].

  * Organizations. The parameters $\eta_{k}$, $k=1,\ldots,K$, reflect to which extent organizations take into account their network payoffs. If $\eta_{k}$’s are relatively large, the organizations focus mainly on reaching the agents’ aspired states. It seems surprising that this would not improve the convergence rate of the network manipulation algorithm, but actually worsen it. However, if organizations do not properly act on the network by maximizing their profits, their manipulation power diminishes, since they lose their credibility – e.g., their followers may be disappointed by getting biased information and leave them. Organizations thus become worthless for agents in terms of manipulation and, as consequence, the network manipulation algorithm becomes less efficient. Hence, the parameter mirrors a certain credibility of the organizations. Further, the impact of $\tau_{k}$, $k=1,\ldots,K$, on the convergence rate becomes clear if we interpret the latter as measures of organizations’ reluctance to change their starting distributions. Form this point of view, the conservative behavior of organizations towards profit maximization makes the network manipulation more stable.

Additionally, it is worth to mention that the parameters $\beta_{i}$’s,
$\eta_{k}$’s, and $\tau_{k}$’s, which reflect the behavior of agents and
organizations, also affect the error bounds in (33) and (34). The
corresponding interpretation is similar to that for the convergence rate.
Namely, the agents’ imperfect behavior and organizations’ conservatism in
profit maximization reduce the accumulated errors.

## References

  * [1] Daron Acemoglu and Asuman Ozdaglar, _Opinion dynamics and learning in social networks_ , Dynamic Games and Applications 1 (2011), no. 1, 3–49.
  * [2] S. P. Anderson, A. De Palma, and L.-F. Thisse, _Discrete choice theory of product differentiation_ , MIT press, 1992.
  * [3] Amir Beck, _On the convergence of alternating minimization for convex programming with applications to iteratively reweighted least squares and decomposition schemes_ , SIAM Journal on Optimization 25 (2015), no. 1, 185–209.
  * [4] Morris H DeGroot, _Reaching a consensus_ , Journal of the American Statistical Association 69 (1974), no. 345, 118–121.
  * [5] Manuel Förster, Ana Mauleon, and Vincent J Vannetelbosch, _Trust and manipulation in social networks_ , Network Science 4 (2016), no. 2, 216–243.
  * [6] Mogens Fosgerau, Emerson Melo, Andre De Palma, and Matthew Shum, _Discrete choice and rational inattention: A general equivalence result_ , International Economic Review 61 (2020), no. 4, 1569–1589.
  * [7] Paul A Gagniuc, _Markov chains: from theory to implementation and experimentation_ , John Wiley & Sons, 2017.
  * [8] Luigi Grippof and Marco Sciandrone, _Globally convergent block-coordinate techniques for unconstrained optimization_ , Optimization methods and software 10 (1999), no. 4, 587–637.
  * [9] Bo Lindqvist, _How fast does a markov chain forget the initial state? a decision theoretical approach_ , Scandinavian Journal of Statistics (1977), 145–152.
  * [10] Zhi-Quan Luo and Paul Tseng, _Error bounds and convergence analysis of feasible descent methods: a general approach_ , Annals of Operations Research 46 (1993), no. 1, 157–178.
  * [11] D. McFadden, _Modeling the choice of residential location_ , Transportation Research Record (1978), no. 673, 72–77.
  * [12] David Müller, Yurii Nesterov, and Vladimir Shikhman, _Discrete choice prox-functions on the simplex_ , Mathematics of Operations Research (2021), To appear.
  * [13] , _Dynamic pricing under nested logit demand_ , Journal of Pure and Applied Functional Analysis (2021), To appear.
  * [14] Yurii Nesterov, _Soft clustering by convex electoral model_ , Soft Computing (2020), 1–12.
  * [15] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd, _The pagerank citation ranking: Bringing order to the web._ , Tech. report, Stanford InfoLab, 1999.
  * [16] Y. Pu, M. N. Zeilinger, and C. N. Jones, _Inexact fast alternating minimization algorithm for distributed model predictive control_ , 53rd IEEE Conference on Decision and Control, 2014, pp. 5915–5921.
  * [17] Fedor S Stonyakin, Darina Dvinskikh, Pavel Dvurechensky, Alexey Kroshnin, Olesya Kuznetsova, Artem Agafonov, Alexander Gasnikov, Alexander Tyurin, César A Uribe, Dmitry Pasechnyuk, et al., _Gradient methods for problems with inexact model of the objective_ , International Conference on Mathematical Optimization Theory and Operations Research, Springer, 2019, pp. 97–114.
  * [18] L. Thurstone, _A law of comparative judgment._ , Psychological review 34 (1927), no. 4, 273.
  * [19] Jie Yang, Yangsheng Xu, and Chiou S Chen, _Human action learning via hidden markov model_ , IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans 27 (1997), no. 1, 34–44.