# Machine Comprehension Based on Learning to Rank

Tian Tian  Yuezhang Li
Carnegie Mellon University
ttian1<EMAIL_ADDRESS>
###### Abstract

Machine comprehension plays an essential role in NLP and has been widely
explored with dataset like MCTest. However, this dataset is too simple and too
small for learning true reasoning abilities. [Hermann et al., 2015] therefore
release a large scale news article dataset and propose a deep LSTM reader
system for machine comprehension. However, the training process is expensive.
We therefore try feature-engineered approach with semantics on the new dataset
to see how traditional machine learning technique and semantics can help with
machine comprehension. Meanwhile, our proposed L2R reader system achieves good
performance with efficiency and less training data.

| CNN | Daily Mail
---|---|---
| train | dev | test | train | valid | test
# documents | 90,266 | 1,220 | 1,093 | 196,961 | 12,148 | 10,397
# queries | 380,298 | 3,924 | 3,198 | 879,450 | 64,835 | 53,182
# max entities | 527 | 187 | 396 | 371 | 232 | 245
# avg entities | 26.4 | 26.5 | 24.5 | 26.5 | 25.5 | 26.0
# avg tokens | 762 | 763 | 716 | 813 | 774 | 780
word count | 118,497 | 208,045
Table 1: Dataset Statistics

##  1 Introduction

Machine comprehension, as the central goal in NLP, has been explored with a
variety of methods. Based on the released dataset MCTest [Richardson et al.,
2013], a lexical matching based method is proposed [Smith et al., 2015]. It
applies linguistic features to tackle this problem. However, this method dives
deep into the characteristics of the dataset, and may not generalize well to
other datasets. This problem also goes with the discourse relation model
introduced in [Narasimhan and Barzilay, 2015] that explore causal, temporal
and explanation relationships between two sentences, which does not scale
well. Hence, [Wang and McAllester, 2015] introduced a max-margin learning
frame that incorporates a feature set of frame semantics, syntax, coreference,
and word embeddings. The accuracy of $69.94\%$ was achieved in MC500 of MCTest
dataset. Meanwhile, [Sachan et al., 2015] applied similar loss function,
modeling machine comprehension as textual entailment and solved the problem by
constructing latent answer-entailing structure with an accuracy of $67.83\%$.
Although such good accuracy were achieved, the dataset they worked on has some
limitations in terms of data size and content. Therefore, our work is based on
a much larger news article dataset created by [Hermann et al., 2015].

Different from the MCTest dataset, this news article dataset consists of cloze
style questions, i.e. questions generally generated by removing a phrase from
a sentence [Taylor, 1953]. Since the questions can be formed from a short
summary of the document with condensed form of paraphrase, the dataset is
suitable for testing machine comprehension [Hermann et al., 2015].

To realize machine comprehension, we develop a learning to rank reader (L2R
Reader) system by first exploring features on frequency, word distance, syntax
and semantics. Then, through learning to rank, we construct a ranking model
that can directly pick the answer from the candidate list of answers. Opposed
to the deep LSTM [Hermann et al., 2015] that computes the answer based on
context information of documents, it is more efficient and does not require
much data to reach good performance. Moreover, we incorporate the semantics
into the system to improve comprehension ability.

This article is organized as follows. Section 2 introduces the task and
essential parts of relevant datasets. Section 3 presents related work and
distinguishes our work from them. Section 4 describes our model from aspects
of learning to rank algorithms, features and usage of semantic information.
Section 5 then evaluates our model from performance, semantics analysis and
error analysis. Finally, section 6 summarizes our work and points out
contributions.

Figure 1: A high-level architecture of the L2R reader system

##  2 Task and Datasets

This section gives a brief introduction of the task and the dataset recently
released for this task.

###  2.1 Formal Task Description

This task requires answering a cloze style question based on the understanding
of a context document provided with the question. Along with each question and
document, it also provides the correct answer to the question and a list of
candidate answers. Thus, this can be formalized as follows:

The training data consists of tuples $(d,q,a,A)$, where $d$ is a context
document for answering the question $q$, $a$ is the correct answer to question
$q$, $A$ denotes a set of candidate answers to the question and $a\in A$ as
defined.

###  2.2 Datasets

The dataset [Hermann et al., 2015] we used in this task were constructed from
news article from CNN and Daily Mail websites. The context document of the
dataset is from the main body of the news article while the question is formed
from one top sentence summarized the news article. Specifically, the question
is constructed by replacing the named entity with a placeholder, e.g.
“@placeholder and @entity2 welcome son @entity6” is a question defined in the
dataset.

Table 2: Example of Anonymised version of a data point

Furthermore, to make context information required for answering question, we
use the anonymised version as shown in Figure 2 to eliminate influence of
background knowledge. Thus, we must exploit the context to answer the question
and these two corpora truly measures the capacity of reading comprehension.

The basic statistics of CNN and Daily Mail of dataset are summarized in Table
1.

##  3 Related Work

Machine comprehension generally concentrates on MCTest [Richardson et al.,
2013] and due to the limitation of data size, the state of the arts are mainly
based on traditional machine learning techniques. For example, [Wang and
McAllester, 2015] proposed a max-margin learning framework that combines
features on syntax, coreference, frame semantics and word embeddings, which
achieves significant improvement on the problem of MCTest question answering.
Although recently [Trischler et al., 2016] proposed a parallel-hierarchical
model based on neural network and this method outperforms the previous
feature-engineered approaches, it has reasoning limitation that the reasoning
can only be achieved by stringing important sentences together. Their
experiment proves that MCTest is too simple to learn true reasoning and it is
also too small for that goal.

Considering the limitations of MCTest dataset, [Hermann et al., 2015] provides
a large scale supervised reading comprehension dataset collected from the CNN
and Daily Mail websites. This helps with the bottleneck that large dataset is
missing on machine comprehension evaluation. With this dataset, [Hermann et
al., 2015] propose a deep LSTM reader that achieves an accuracy of $63.8\%$ on
CNN and $69.0\%$ on Daily Mail. However, this deep LSTM reader is time
consuming for training and no explanation can be found on why it works opposed
to traditional approach. Therefore, we propose a traditional machine learning
method on this new dataset to investigate what features can help with this
task.

##  4 Model – Learning to Rank (L2R) Reader

Our model consists of learning to rank algorithms, features and semantics. As
shown in Figure 1, given a document along with a list of queries that have the
placeholder filled with different entities from the list of candidate answers.
Then, through a feature extractor, we get several features for each entity
(i.e. candidate answer). Combining with correct answer, we employ a learning
to rank algorithm (i.e. L2R in Figure 1) to train a ranking model. Based on
the ranking model, we generate ranking lists on new unseen dataset that has
features extracted using feature extractor; from the rank list, we select the
entity with highest ranking score as the predicted answer to the question.

###  4.1 Learning to Rank

Learning to rank is employed in Information Retrieval (IR) and Natural
Language Processing (NLP). Generally, it is defined as follows: given a query,
the ranking algorithm will generate a list of candidate documents with scores
[Hang, 2011]. In this task, we select the entity with the highest score as the
answer to the question. Here, we introduce three different types of learning
to rank algorithms that can help with the task.

Pointwise: In the pointwise approach, the ranking algorithm is transformed
into problems including classification and regression to derive a score for
every pair of document and query [Hang, 2011]. This approach ignores the group
structure of ranking and we do not apply it in this task.

Pairwise: In the pairewise approach, the ranking algorithm is transformed into
problems of pairewise classification or pairwise regression [Hang, 2011]. It
also ignores the group structure of ranking. In this project, we mainly focus
on the pairewise classification that employs a binary classifier in document
pair ranking. We try approaches including RankNet [Burges et al., 2005],
RankBoost [Freund et al., 2003], RankSVM [Herbrich et al., 1999], MART and
LambdaMART [Burges, 2010]

Listwise: In the listwise approach, the ranking problem is addressed by taking
the ranking list as instances in both learning and prediction process [Hang,
2011]. It maintains the group structure and we employ the following listwise
approaches: ListNet [Cao et al., 2007], AdaRank [Xu and Li, 2007], Coordinate
Ascent.

###  4.2 Features

We explore four types of features in this task. We start with the frequency of
entity in both document and cloze-style question. Then we try features on word
distance with different settings of window size. We further investigate
features on syntactics and semantics to see how these affect the model
performance.

####  4.2.1 Frequency

Frequency is explored based on one baseline of [Hermann et al., 2015]. We
simply count the number of entity that is in the candidate answer list
appearing in the document and the question, then the count number works as the
frequency feature of the entity. If this entity does not show in question or
document, we assign a value of $0$. The idea behind is that news article
usually mentions important entities multiple times and cloze-style question is
concerned with such entities.

####  4.2.2 Word Distance

We investigate word distance from three aspects – word alignment, nBOW, and
word mover’s distance (WMD) [Kusner et al., 2015].

Word Alignment (WA): For the word alignment, we first consider the situation
shown in Figure 2.

Figure 2: Example of Word Alignment

According to Figure 2, we first replace the “@placeholder” with one entity in
the candidate answer list and search the document to find one matched sentence
that containing this entity. Then, we align these two entities and set
location index as $0$. Starting with this index, words located left will have
negative index while words located right will have positive index. With index
defined, we align same words of these two sentences and compute the difference
of word indexes. As for words without alignment, a penalty is given. Finally,
the score capture some word information of question and document sentences.

Normalized Bag-Of-Words (nBOW): Furthermore, we consider using normalized bag-
of-words (nBOW) vectors, $d\in R^{n}$, where $d$ denotes the document vector
and $n$ is the vocabulary size. To be precise, if word $i$ appears $c_{i}$
times in the document, we let $d_{i}=\frac{c_{i}}{\sum_{j=1}^{n}c_{j}}$.
Therefore, a sentence is transformed into a vector and we can do similarity
measure accordingly.

Word Mover’s distance (WMD): The WMD [Kusner et al., 2015] measures the
dissimilarity between two text documents using the minimal distance that the
embedded words of one document need to move to the embedded words of another
document. Here, we apply WMD into two sentences after using Mikolov’s word2vec
[Mikolov et al., 2013] to convert words of sentences to embeddings. Different
from the two methods above (WD and nBOW), the WMD can move words to
semantically similar words, thereby capturing semantic information (see Figure
3). It can capture semantic similarity of two sentences with different unique
words. For instance, “The President greets the press in Chicago” and “Obama
speaks to the medis in Illinoirs”.

Figure 3: Example of WMD

Moreover, we try different window size to extract sentences in the document to
optimize our model.

####  4.2.3 Syntactic Features

In this task, we consider syntactic features including part-of-speech (POS)
tags and dependency parsing.

POS tags: Similar to the word alignment defined in Section 4.2.2, we consider
POS tag alignment as one syntactic feature. Specifically, we transform words
into POS tags using NLTK111http://www.nltk.org/ and employ same technology as
word alignment to measure the dissimilarity of two sentences.

Dependency Parsing: If two sentences describe same event, it is likely that
they have dependency overlapping [Wang and McAllester, 2015]. We thus
incorporate dependency parsing to capture such information. To be precise, we
use Stanford Parsing222http://nlp.stanford.edu/software/stanford-
dependencies.shtml to get dependencies of a sentence that are shown as several
triples like ($s$, $t$, $arc$), e.g. (entity, has, nsubj), where $s$ denotes
source word and $t$ is the target word. Then, this dependency-based similarity
is evaluated from these three categories: (1) $s_{d}$ = $s_{q}$ and
$arc_{d}=arc_{q}$ or $t_{d}$ = $t_{q}$ and $arc_{d}=arc_{q}$; (2) $s_{d}$ =
$s_{q}$ and$t_{d}$ = $t_{q}$; (3) $s_{d}$ = $s_{q}$, $t_{d}$ = $t_{q}$ and
$arc_{d}=arc_{q}$, where $d$ denotes document, $q$ denotes question and
$s_{d}$ refers to source word in document sentence while $s_{q}$ represents
the target word in question.

####  4.2.4 Semantic Features

In addition to word embeddings applied in WMD in Section 4.2.2. We adopt the
SEMAFOR Frame Semantic (FS) parser [Das et al., 2014] to extract some semantic
features. Figure 4 gives an example output of the SEMAFOR semantic parser.

Figure 4: Example output from SEMAFOR

In this example, five frames are identified. For example, The word “says” is a
target, which evokes a semantic frame labeled STATEMENT. Each frame has its
own frame elements; e.g., the STATEMENT frame has frame elements of Message
and Speaker. Features from these parsers have been shown to be useful for
machine comprehension task [Wang and McAllester, 2015]. We expect that the
document sentence containing the answer will overlap with the question and
correct answer in terms of targets, frames evoked and frame elements evoked.
Therefore, we design the following features to capture this intuition. To be
precise, after parsing a sentence, we get several triples composed of
$(t,f,e)$, where $t$ denotes the target, $f$ denotes the frame and $e$ denote
a set of elements. Then, the frame semantic based features are derived from
the next seven categories: (1) $t_{q}=t_{d}$ ; (2) $f_{q}=f_{d}$; (3)
$e_{q}=e_{d}$; (4) $t_{q}=t_{d}$ and $f_{q}=f_{d}$ ; (5)$t_{q}=t_{d}$ and
$e_{q}=e_{d}$; (6) $f_{q}=f_{d}$ and $e_{q}=e_{d}$; (7) $t_{q}=t_{d}$ and
$f_{q}=f_{d}$ and $e_{q}=e_{d}$. We count the number of triples satisfying the
above requirements from the document sentence and the query sentence to
generate seven features.

###  4.3 Semantics

Semantics play a significant role in our model. This section summarizes how
our model uses semantics to achieve reading comprehension. In this project, we
use semantics in aspects of WMD, Frame Semantic (FS) and coreference. In WMD,
we use word embeddings to capture word level semantics and FS helps us to
capture sentence level semantics. The coreference is employed to identity
chains of mentions within and across sentences for data pre-processing.

Specifically, word embeddings [Mikolov et al., 2013] project words into a low-
dimensional space and similarity of vectors can capture some word similarity
on semantics. For example, the word “Paris” is close to “Berlin” rather than
“France” and vec(“Paris”) is closest to vec(“Berlin”) - vec(“Germany”) +
vec(“France”), where vec($x$) denotes the word embedding of word $x$. Based on
the word embedding given by [Mikolov et al., 2013], the WMD can align
semantically similar words together using distance measure, for example, it is
much cheaper to transform “Illinois” into “Chicago” than “Japan” into
“Chicago”. Therefore, we incorporate semantics into the model and its
performance is improved.

As for frame semantics, the semantic similarity that two sentences describe
same events but use different words or two sentence have different structures
can be captured by frame semantics parsing. For example, two sentence “the
speaker states that he is innocent.” and “‘I’m innocent’, he says.” would be
parsed to have the same semantic frame of STATEMENT and frame elements of
(Message, Speaker), even they use different words and have inverse sentence
order.

Coreference resolution is achieved using Stanford
CoreNLP333http://stanfordnlp.github.io/CoreNLP/. We try to resolve the pronoun
with the specific description and run the coreference resolution system on
each document. As the coreference system will provide a chain of mentions, we
take the representative mention to resolve pronoun in the document only, i.e.,
replacing the pronoun like “it” with the representative mention of its
coreference chain.

##  5 Evaluation

We evaluate the L2R reader system by comparing with the baselines of [Hermann
et al., 2015]. Moreover, we present the system performance with different
learning to rank algorithms, based on which, we select RankSVM and LamdaMART
as the ranking algorithm for model training. We also evaluate the contribution
of single feature to the system performance for final feature decision. Based
on the final results, we analyze the effect of incorporating semantics into
the system from coreference, word embeddings, and frame semantics. Following
by semantic analysis, we conduct error analysis to see how to improve the
system in the future work.

###  5.1 Experimental Results

Final Results: Table 3 shows the best performance of our model and some
baselines. Our L2R model finally combines all the three kinds of word distance
features and frame semantic features described in section 4.2. Our L2R Reader
outperforms LSTM-based models proposed in [Hermann et al., 2015] on the CNN
dataset and achieves competitive results on the Daily Mail dataset.

| CNN | Daily Mail
---|---|---
| Train | Test | Train | Test
Deep LSTM† | 55 | 57 | 63.3 | 62.2
Attentive Reader† | 61.6 | 63 | 70.5 | 69
Impatient Reader† | 61.8 | 63.8 | 69 | 68
L2R Reader | 64.3 | 65.8 | 69.1 | 67.3
Table 3: Results of our L2R Reader on the CNN and Daily Mail dataset. Results
marked with † are taken from previous paper.

Different L2R Algorithms: Table 4 shows the performance of different learning
to rank algorithms by using the same features. Model parameters are tuned on
the validation set. We found that RankSVM and LambdaMART are two best L2R
algorithms on this task. RankSVM performs best on the CNN dataset while
LambdaMART performs best on the Daily Mail dataset.

| Ranking
---
Model
| CNN
---
Test
| Daily Mail
---
Test
RankSVM | 65.8 | 66.7
MART | 60.4 | 65.3
RankNet | 40.9 | 32.8
RankBoost | 32.0 | 28.4
AdaRank | 18.0 | 12.7
| Coordinate
---
Asecent
59.0 | 54.4
LambdaMART | 64.2 | 67.3
ListNet | 32.7 | 32.3
| Random
---
Forest
63.4 | 65.6
Table 4: Performance of different L2R algorithms on CNN and Daily Mail
dataset.

Single Feature Performance: We evaluate the performance of each single
feature. Table 5 shows the results. We can see that among all single features,
word alignment features perform best and frame semantic features perform
worst. This can be explained by the nature of the dataset.

| CNN | Daily Mail
---|---|---
| Train | Test | Train | Test
Frequency | 33.2 | 35.0 | 33.4 | 32.4
WA | 47.3 | 50.6 | 54.3 | 53.4
nBOW | 40.3 | 43.5 | 48.7 | 47.8
WMD | 41.2 | 44.0 | 49.3 | 48.5
FS | 18.9 | 22.0 | 25.2 | 24.3
Table 5: Single feature performance on CNN and Daily Mail dataset.

Performance vs Size of Training Data: One great advantage of our model is that
it only requires a small set of training data compared with neural network
based models. Table 6 shows the relationship between our model performance and
the number of training data. We can see that our model have a high score given
only about 100 training data. Our model performance improves when giving more
data, but the speed of improvement gets dramatically slow. Figure 5 shows the
trend of the convergence of our model with more data.

| CNN | Dailymail
---|---|---
#Training | Val | Test | Val | Test
10 | 35.2 | 41.6 | 45.7 | 43.6
20 | 57.4 | 55.1 | 57.2 | 56.2
30 | 56.7 | 60.2 | 61.4 | 60.3
40 | 57 | 60 | 62.3 | 61.3
50 | 60.3 | 63.1 | 63.5 | 62.5
100 | 61.5 | 63.9 | 65.4 | 64.6
200 | 62.5 | 64.9 | 67.3 | 65.2
500 | 62.8 | 65 | 67.5 | 66.3
1000 | 62.9 | 65.2 | 68.3 | 66.7
2000 | 63.2 | 65.2 | 69.0 | 67.3
5000 | 64.3 | 65.8 | 69.1 | 67.3
Table 6: Model performance for L2R Reader against different number of training
data on the CNN and Daily Mail dataset. All the statistics are averaged over
10 times of random samples. Parameters are tuned on the validation set and the
best validation model is applied to the test data. Figure 5: Model performance
for L2R Reader against different number of training data on the CNN dataset.

###  5.2 Semantics Analysis

We also test the performance of our semantic components, which are co-
reference, word embeddings and frame semantics.

| CNN | Daily Mail
---|---|---
Models | Val | Test | Val | Test
L2R Reader | 64.3 | 65.8 | 69.1 | 67.3
L2R+Coref | 63.8 | 64.8 | 68.3 | 66.5
L2R-WMD | 60.8 | 61.5 | 63.2 | 61.6
L2R-FS | 61.5 | 62.5 | 65.3 | 63.7
Table 7: Analysis of semantic components of our model. “+”” and “-” refer to
added or ablated components. Coref, WMD and FS denotes coreference system,
word mover’s distance and frame semantics.

Table 7 shows the results of adding co-reference, deleting word mover’s
distance and deleting frame semantics. From the experimental results, we can
see that coreference system does not bring improvement to our system, and even
harm the performance. This might because the coreference system (Stanford
CoNLP) we use in our system cannot have good performance when the sentences
are complicated. We can also find from the results that the word embedding and
frame semantics components plays a vital role in our system, although the
single feature performance of frame semantics is quite low.

###  5.3 Error Analysis

To give insight into our system’s performance and reveal future research
directions, we analyze the errors made by our system. We found that many
queries require text summarization, event detection, background knowledge and
inference. We also found an error on the CNN dataset (refer to Figure 6). We
make some detailed analysis as follows.

Figure 6: Wrong answer in the gold standard data.

Figure 6 shows an example of wrong answer in the gold standard dataset. We can
see from the query that the correct answer should be entity0 rather than
entity6. Our model successfully get the right answer. The error in the dataset
might due to the generation process of the dataset.

Figure 7: Require high level text summarization.

Figure 7 shows an example of requiring high level text summarization. The
phrases “within 10 minutes” and “kick off” do not appear in the document, but
they are high level summarization of the document. Hence, our model lacks the
ability of getting the correct answer in such situation.

Figure 8: Require event detection.

Figure 8 shows an example of requiring event detection in filling the cloze
question. The word “collapse” appears several times in the document, but
describes different events. Our model fails to capture the difference.

Figure 9: Require background knowledge and inference.

Figure 9 shows an example of requiring background knowledge and inference in
filling the cloze question. It can be inferred that “preschool show” is
performed by “children’s performer”. However, this inference require some
background knowledge. Our model cannot perform well in such situation.

##  6 Conclusion

We explored the new cloze style reading comprehension task and designed a
learning to rank (L2R) reader system to provide a solution. We incorporate
semantics such as word embeddings, frame semantics and coreference resolution
into our system and show that they can greatly improve our model performance.
We find that our model is poor at high level text summarization, event
detection and inference through error analysis. We will investigate into how
to solve these kinds of problems by using semantics in the future.

## References

  * [Burges et al., 2005]  Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Greg Hullender.  2005\.  Learning to rank using gradient descent.  In Proceedings of the 22nd international conference on Machine learning, pages 89–96. ACM.
  * [Burges, 2010]  Christopher JC Burges.  2010\.  From ranknet to lambdarank to lambdamart: An overview.  Learning, 11:23–581.
  * [Cao et al., 2007]  Zhe Cao, Tao Qin, Tie-Yan Liu, Ming-Feng Tsai, and Hang Li.  2007\.  Learning to rank: from pairwise approach to listwise approach.  In Proceedings of the 24th international conference on Machine learning, pages 129–136. ACM.
  * [Das et al., 2014]  Dipanjan Das, Desai Chen, André FT Martins, Nathan Schneider, and Noah A Smith.  2014\.  Frame-semantic parsing.  Computational Linguistics, 40(1):9–56.
  * [Freund et al., 2003]  Yoav Freund, Raj Iyer, Robert E Schapire, and Yoram Singer.  2003\.  An efficient boosting algorithm for combining preferences.  The Journal of machine learning research, 4:933–969.
  * [Hang, 2011]  LI Hang.  2011\.  A short introduction to learning to rank.  IEICE TRANSACTIONS on Information and Systems, 94(10):1854–1862.
  * [Herbrich et al., 1999]  Ralf Herbrich, Thore Graepel, and Klaus Obermayer.  1999\.  Large margin rank boundaries for ordinal regression.  Advances in neural information processing systems, pages 115–132.
  * [Hermann et al., 2015]  Karl Moritz Hermann, Tomas Kocisky, Edward Grefenstette, Lasse Espeholt, Will Kay, Mustafa Suleyman, and Phil Blunsom.  2015\.  Teaching machines to read and comprehend.  In Advances in Neural Information Processing Systems, pages 1684–1692.
  * [Kusner et al., 2015]  Matt Kusner, Yu Sun, Nicholas Kolkin, and Kilian Q Weinberger.  2015\.  From word embeddings to document distances.  In Proceedings of the 32nd International Conference on Machine Learning (ICML-15), pages 957–966.
  * [Mikolov et al., 2013]  Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean.  2013\.  Distributed representations of words and phrases and their compositionality.  In Advances in neural information processing systems, pages 3111–3119.
  * [Narasimhan and Barzilay, 2015]  Karthik Narasimhan and Regina Barzilay.  2015\.  Machine comprehension with discourse relations.  In 53rd Annual Meeting of the Association for Computational Linguistics.
  * [Richardson et al., 2013]  Matthew Richardson, Christopher JC Burges, and Erin Renshaw.  2013\.  Mctest: A challenge dataset for the open-domain machine comprehension of text.  In EMNLP, volume 1, page 2.
  * [Sachan et al., 2015]  Mrinmaya Sachan, Avinava Dubey, Eric P Xing, and Matthew Richardson.  2015\.  Learning answerentailing structures for machine comprehension.  In Proceedings of ACL.
  * [Smith et al., 2015]  Ellery Smith, Nicola Greco, Matko Bošnjak, and Andreas Vlachos.  2015\.  A strong lexical matching method for the machine comprehension test.
  * [Taylor, 1953]  Wilson L Taylor.  1953\.  Cloze procedure: a new tool for measuring readability.  Journalism and Mass Communication Quarterly, 30(4):415.
  * [Trischler et al., 2016]  Adam Trischler, Zheng Ye, Xingdi Yuan, Jing He, Phillip Bachman, and Kaheer Suleman.  2016\.  A parallel-hierarchical model for machine comprehension on sparse data.  arXiv preprint arXiv:1603.08884.
  * [Wang and McAllester, 2015]  Hai Wang and Mohit Bansal Kevin Gimpel David McAllester.  2015\.  Machine comprehension with syntax, frames, and semantics.  Volume 2: Short Papers, page 700.
  * [Xu and Li, 2007]  Jun Xu and Hang Li.  2007\.  Adarank: a boosting algorithm for information retrieval.  In Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, pages 391–398. ACM.


# Entropy-driven decision-making dynamics sheds light on the emergence of the
paradox of choice

Manish Gupta  Technische Univesität Dresden, Center for Information Services
and High Performance Computing, Nöthnitzer Straße 46, P.O. Box: 01062,
Dresden, Germany  Arnab Barua  Tata Institute of Fundamental Research,
Hyderabad - 500046, India  Corresponding authors: Arnab Barua,
<EMAIL_ADDRESS>Haralampos Hatzikirou,
<EMAIL_ADDRESS>Haralampos Hatzikirou  Mathematics Department,
Khalifa University, P.O. Box: 127788, Abu Dhabi, UAE  Technische Univesität
Dresden, Center for Information Services and High Performance Computing,
Nöthnitzer Straße 46, P.O. Box: 01062, Dresden, Germany  Corresponding
authors: Arnab Barua<EMAIL_ADDRESS>Haralampos Hatzikirou,
<EMAIL_ADDRESS>
Decision making is the cognitive process of selecting a course of action among
multiple alternatives. As the decision maker belongs to a complex
microenvironment (which contains multiple decision makers), has to make a
decision where multiple options are present which often leads to a phenomenon
known as the "paradox of choices". The latter refers to the case where too
many options can lead to negative outcomes, such as increased uncertainty,
decision paralysis, and frustration. Here, we employ an entropy-driven
mechanism within a statistical physics framework to explain the premises of
the paradox. In turn, we focus on the emergence of a collective "paradox of
choice", in the case of interacting decision-making agents, quantified as the
decision synchronization time. Our findings reveal a trade-off between
synchronization time and the sensing radius, indicating the optimal conditions
for information transfer among group members, which significantly depends the
individual sensitivity parameters. Interestingly, when agents sense their
microenvironment in a biased way or their decisions are influenced by their
past choices, then the collective "paradox of choice" does not occur. In a
nutshell, our theory offers a low-dimensional and unified statistical
explanation of the "paradox of choice" at the individual and at the collective
level.

Keywords: Entropy-driven; Paradox of choice; Collective behavior; Monte-Carlo
method; Decision making

## Introduction

Human decision-making is defined as the result of a thorough evaluation of
alternative choices, considering the likelihood and value of the corresponding
outcomes [1]. Generally, decision-making in organisms ranges from individual
choices influenced by past experiences, perception, and knowledge, to
collective decisions manifested in collective dynamics [2]. This spans from
the microscopic movements of cells [3] to macroscopic behaviors observed in
flocks of birds and schools of fish [4]. Similarly, human make individual
decisions which by virtue of interaction lead to emergent societal changes
[5]. In these processes, individual decision-makers integrate the information
produced by nearby peers, through sensing and interactions [6], demonstrating
how individual actions can aggregate to produce complex collective dynamics.

The presence of extensive information in the local environment introduces a
paradoxical situation, famously known as the “paradox of choice”. Coined by
psychologist Barry Schwartz, this paradox encompasses decision paralysis,
dissatisfaction with choices made, and an overall decrease in the well-being
of decision-makers [7]. A critical question arises: how much information is
too much? As environments have finite sizes, determining the optimal amount of
information necessary for effective global decision-making at the group level
becomes crucial. To quantify this situtation, British and American
psychologists William Edmund Hick and Ray Hyman experimented on this and found
that there exists a crucial relationship between the average reaction time of
each decision-maker and the number of choices[8, 9]. This law is known as
Hick’s Law and states that the average reaction time is a logarithmic function
of a number of options. the decision-making process becomes more complex and
time-consuming, which can lead to frustration, being overwhelmed with
information, and decreased satisfaction at the personal level. To understand
the “paradox of choice”, we employ the LEUP theory or Least Environmental
Uncertainty Principle [10] , which posits that individual agents or organisms
strive to reduce their microenvironmental entropy over time as they assimilate
knowledge from their surroundings. This principle has been applied to various
biological systems such as cell migration [11], Epithelial-Mesenchymal-
Transition [12], and cell differentiation [13].

In this paper, we first define an internal variable reflecting individual
choices, driven by the entropic gradient within the microenvironment, and
hypothesize that discontent arises as the variance/uncertainty of this
variable increases over time. Using mean-field calculations, we derive a
formula quantifying the variance rate relative to the number of choices,
revealing an optimal number of choices that minimizes this rate. We then
analyze decision-making dynamics using a Metropolis-Hastings Monte Carlo
method within an individual-based model, identifying a trade-off between
convergence time and sensing radius that optimizes information transfer among
group members based on individual sensitivity parameters. Furthermore, we
explore weighted decision-making influenced by the Von-Mises distribution,
showing that this approach can accelerate group decisions depending on weight
variance, and investigate trend-setting behaviors leading to micro-level
community formation. Comparing our findings with the Vicsek Model[14], we show
that low weight variance yields similar outcomes, while high variance offers
insights into the paradox of choice.

## Mathematical modeling of interacting decision makers

Moving and interacting agents are modeled by a two-dimensional self-propelled
particle model (SPP). In this model, N $\in\mathbb{N}$ cells move on a two-
dimensional space. The n-th agent is characterized by its position,
$\mathbf{r}_{n}\in\mathbb{R}^{2}$, speed,
$v_{n}\in[0,\infty)\subset\mathbb{R}$, and an orientation
$\theta_{n}\in[0,2\pi)\subset\mathbb{R}$. Here for simplicity, we assume that
all the agents are moving with the same constant speed with time. The change
in orientation of each agent results from the interaction potential
$U(\mathbf{r}_{m},\theta_{m})$, which depends on the positions and orientation
of other agents within the interaction radius $R\in\mathbb{R}_{+}$. This
interaction potential dictating the dynamics of orientation is specified using
the LEUP theory that states an individual updates its decision in such as way
that it minimizes the entropy of its micro-environment, i.e.
$S(\Theta|\theta_{n})$ where
$\Theta=\\{\theta_{m}:||\mathbf{r}_{m}-\mathbf{r}_{n}||\leq R\\}$ the
collection of microenvironmental orientations. Assuming this the rate of
change in the orientation can be expressed as depicted in Eq.(1). The
microenvironmental entropy $S(\Theta|\theta_{n})$ term acts as interaction
potential. Please note that we calculate microenvironmental entropy
numerically using the histogram to obtain the probability distribution of the
orientations of neighbourhood decision makers. The responsiveness of the agent
to follow the potential gradients is regulated by the parameter
$\beta\in\mathbb{R}$, called angular sensitivity. This parameter is associated
with the sensed information processing since it leads to decisions that either
decrease ($\beta>0$) or increase ($\beta<0$) microenvironmental entropy.
Additionally, orientation fluctuations occur due to stochastic noise terms
$\xi_{n}(t)$ where $t\in\mathbb{R}_{\\+}$ denotes time. The noise $\xi_{n}(t)$
will be assumed to follow a normal distribution, which has the statistical
properties $\langle\xi_{n}\left(t\right)\rangle=0$ and
$\langle\xi_{n}\left(t_{1}\right)\xi_{m}\left(t_{2}\right)\rangle=2D\delta\left(t_{1}-t_{2}\right)\delta_{nm}$,
where $t_{1}$ and $t_{2}$ are two-time points.

$\frac{d\theta_{n}}{dt}=-\beta\frac{\partial
S(\Theta|\theta_{n})}{\partial\theta_{n}}+\xi_{n}(t)$ (1)

Further, we assume that the decision-making process is at a steady state.
Accordingly, the steady-state probability distribution of the orientation of
n-th agent is given as,

$P(\theta_{n})\propto e^{-\beta S(\Theta|\theta_{n})}$ (2)

The decision-making step for an agent is initialized by randomly choosing an
orientation from its micro-environment and proposing this to be its new
orientation state. The Metropolis-Hastings algorithm will decide whether to
accept or reject this proposed state. If the choice results in a decrease of
the microenvironmental entropy $\Delta S<0$, the proposed state is accepted.
If the choice results in an increase of the entropy $\Delta S>0$ then the
proposed state is accepted with probability $e^{-\beta\Delta S}$, where
$\Delta S$ is the change of the entropy before and after the update. These
steps are repeated and the system is allowed to reach steady state, after
which the properties of the system are measured. Now, Let us define the
normalized complex orientation of the n-th cell, $z_{n}\in C$ as
$z_{n}=e^{i\theta_{n}}$, where $i$ is the imaginary unit. The k-th moment of
the orienation over an area A is given by $\langle
z_{k}\rangle_{A}=\frac{1}{N_{A}}\Sigma_{m\in A}z^{k_{m}}$, where the sum is
over all cells in area $A$, and $N_{A}$ is the total number of cells in $A$.
The polar order parameter in the area $A$ is given by

${S_{A}}^{1}=\mid\langle z\rangle_{A}\mid$ (3)

Based on the polar order parameter, we define the group level decision making
as the collective orientation. Please note that, we define individual agent’s
decision as the orientation $\theta_{n}$. So in the macrocopic level when the
order parameter reaches a steady state we define that a group level decision
has been made. When system agents make a flock then the polar or global order
parameter converges to the value $1$. We characterise this value as the
maximally learned state as they are ordered and the for the whole system
microenvironmental entropy reaches close to $0$ or the information gain is
maximum. On the other hand, for the random or disorder macroscopic state the
${S_{A}}^{1}=0$, where the for the system microenvironmental entropy increases
to a particular maximal value or the information gain is minimum. The decision
making time at the group level is defined by the synchronization time $(\tau)$
at which the polar order parameter reaches $0.9$ value. In the next section,
we have analyze our model based on the variations two parameters i.e, (i)
polar order parameter and (ii) the synchronization time. Later, we include a
finite memory (i.e., an array of orientations stored of memory capacity $m$
depicted by last $m$ time steps) for each decision maker to provide further
realism in the decision making process. Finally, we compare our model results
to the standard Vicsek model in the zero noise case where the decision on
angles of the $n$-th decision maker at the next time step $t+\Delta t$ is
given by the average angular decision in the microenvironment (i.e.,
$\langle\Theta(t)_{r}\rangle$) in the previous time $t$ step [15].

$\theta_{n}(t+\Delta t)=\langle\Theta(t)_{r}\rangle,$ (4)

where
$\langle\Theta(t)_{r}\rangle=\tan^{-1}(\langle\sin(\Theta)\rangle/\langle\cos(\Theta)\rangle$
and $\Delta t$ the corresponding time step.

## The “paradox of choice” as a minimum in the decision uncertainty rate for
individual decision-makers

In this section, we attempt to understand why we can observe the “paradox of
choice” in individual decision-making using LEUP dynamics. Here, we model
decision-maker’s satisfaction with the uncertainty rate of the decision
(internal) variable when the number of choices is fixed.

Let us consider a microenvironment consisting of total $N$ decision-makers,
focusing on the $n$-th decision-maker at the center. At time $t$, this
decision-maker samples all microenvironmental decisions in a Gaussian manner,
where the mean value of the collected decisions is defined as $\mu_{n}$ and
the sample variance is denoted as $\sigma_{n}^{2}$. For simplicity we define
the angular decisions lies on the interval $(0,2\pi)$. To evaluate the average
decision-making at the group level, we adopt a mean-field approach, utilizing
the Central Limit Theorem (CLT) to obtain the scaling of the quantities of
interest with $N$. Assuming the Gaussian form of the microenvironmental
entropy $S(\Theta|\theta_{n})=\frac{1}{2}\ln{(2\pi e\sigma_{n}^{2})}$ and
using Eq.(1), we can express the rate of change of decisions as follows:

$\frac{d\theta_{n}}{dt}=-\frac{\beta}{\sigma_{n}^{2}}\left({\frac{\theta_{n}}{N}-\frac{\sum_{i\neq
n}^{N}\theta_{i}}{N^{2}}}\right)+\xi_{n}(t)=-\beta f+\xi_{n}(t)$ (5)

where $\xi_{n}(t)$ is a noise following Normal distribution $\mathcal{N}(0,D)$
and the force term $f$ reads

$f=\frac{1}{\sigma_{n}^{2}}\left({\frac{\theta_{n}}{N}-\frac{\sum_{i\neq
n}^{N}\theta_{i}}{N^{2}}}\right)$ (6)

Now, as we already consider that the decision making occurs inside a local
environment close to the steady state, one can use a mean-field approach to
illustrate the temporal evolution of variance for each average individual.
Using the previous dynamical equation of decisions, one can write the dynamics
of variance [16]:

$\frac{d\Sigma}{dt}=D-2\beta\Sigma\frac{\partial
f}{\partial\theta_{n}}=D-2\beta\Sigma R$ (7)

The macroscopic variance of the random variable has been defined by
$\Sigma=\frac{N}{N+1}\sigma_{n}^{2}$ (for details see SI) and the variance of
the Gaussian noise is define by $D$ and the $R$ drift term reads as

$\frac{df}{d\theta_{n}}=\frac{1}{\sigma^{2}_{n}N}-\frac{\theta_{n}}{N(\sigma_{n}^{2})^{2}}\frac{d\sigma^{2}_{n}}{d\theta_{n}}+\frac{\mu_{n}}{N(\sigma_{n}^{2})^{2}}\frac{d\sigma^{2}_{n}}{d\theta_{n}}-\frac{\theta_{n}}{(\sigma_{n}^{2})^{2}N^{2}}\frac{d\sigma^{2}_{n}}{d\theta_{n}}$
(8)

Using the above expression of $\frac{df}{d\theta_{n}}$, one can find the rate
of the change of variance over time $t$ with respect to number of the agents
in the environment $N$ and sensitivity $\beta$ as (please see SI for details)

$\frac{d\Sigma}{dt}=-2\beta R(\Sigma,\mu,N)\Sigma$ (9)
$\frac{d\Sigma}{dt}=-\frac{2\beta}{(1+N)}+\frac{4\beta}{(1+N)^{2}}+\frac{8\beta}{N(1+N)^{2}}=-\frac{2\beta\left(N^{2}-N-4\right)}{N(1+N)^{2}}$
(10)

For negative $\beta$, the variance will always increase over time as the
corresponding rate is positive, converging to zero. However, for $\beta>0$,
the variance rate’s dependence on $N$ is non-monotonic, exhibiting a minimum.
This suggests that the decision-maker experiences increased satisfaction with
a small increase in the number of options $N$, but beyond a certain point, the
“paradox of choice” emerges. According to our theory, a low $N$ results in
poor sampling of the microenvironment, leading to unsatisfactory decision-
making. While increasing $N$ initially improves decision-making to an optimal
value, surpassing this point causes the variance to scale increasingly with a
larger number of options. In the following, we will explore the emergence of
this paradox during collective migration.

Figure 1: Mean field result for the rate of change in the variance of decision
x in the system vs number of agents (N) in the microenvironment.

Another manifestation of the “paradox of choice” could be measured via the
convergence time to equilibrium $\tau$, just like in Hick’s law. In
particular, we can calculate that the individual state dynamics follows the
eq. (5). The factor next to the drift term denotes the relaxation rate to
equilibrium, implying that

$\tau\propto\frac{\sigma_{n}^{2}}{\beta}.$

This suggests that the decision uncertainty increases the relaxation time of
the state variable towards its equilibrium value. The latter observable will
be used to assess the emergence of the collective “paradox of choice”.

## The emergence of the collective “paradox of choice”

We postulate that the “paradox of choice” is an environment-driven phenomenon,
where individuals make decisions in response to their surroundings. In this
section, we aim to understand how a system of individual decision-makers can
arrive at faster group-level decisions despite the presence of this paradox.
In particular, we will focus on the synchronization time where in the mean-
field should coincide with the mean orientation relaxation time. It is
expected a minimum synchronization time for an increasing sensing radius, and
fixed sensitivity parameter, will be interpreted as a collective manifestation
of the paradox.

### Interplay between interaction radius and the sensitivity in the dynamics
of polar order

Sensing the microenvironment is the first step in decision-making. In a
multiagent microenvironments, agents sense and interact with other agent
states within an interaction radius $R$. A large interaction radius will
provide the agent with a better picture of the microenvironment, since the
number of agents $N\propto R^{d}$ where $d$ is the system dimension. At the
same time sampling noise scales with number of agents as $\sim\sqrt{N}$. This
raises the question: does it exist an optimal sensing radius? Once an agent
has information about the microenvironment, the next step is to process that
information to make a decision, i.e., altering its internal state. Here, we
assume that the underlying principle for decision-making is the Least
Environmental Uncertainty Principle (LEUP). As discussed in the methods
section, the sensitivity parameter $\beta$ associated with this decision-
making principle controls the response of a decision-maker and the type of
information processing. For instance, if the sensitivity is $\beta=0$, then
decisions are rendered randomly. However, higher $\beta$ indicates increased
responsiveness of the agent to the environment. Additionally, one can think of
the sensitivity parameter $\beta$ as a coupling parameter that can help the
total system reach a synchronized or desynchronized state [17].

To this end, we investigated the interplay between interaction radius ($R$)
and sensitivity ($\beta$) on the synchronization of the system for three
different cases. The radius $R$ controls the capacity of the options (agents)
number. These cases differ in the level of selection of one of the states from
the microenvironment. In the case of random sampling, an agent will randomly
sample a state from the microenvironment and then, according to the entropy
based Monte Carlo rule, the orientation state will be accepted or rejected.
However, in realistic scenarios, agents do not randomly sample their
microenvironment; instead, they sense it in a weighted manner. Here agents use
a biased sampling, where an agent samples the interaction neighborhood using a
Von Mises distribution mean the corresponding to the average orientation in
the microenvironment (for an illustration of the sampling methods see Fig.
(2). We study both cases: (i) random and (ii) biased/weighted sampling. Later,
we investigate the role of trends in group-level decision-making in the (iii)
effect of decision memory on the "paradox of choice".

Figure 2: Figuring out decisions based on random selection and biased or
weighted selection through a schematic image. In the weighted selection case,
the sampling of neighboring agents is biased by the mean orientation of the
interaction neighborhood. Here $R$ is the sensing radius.

#### Random sampling

As mentioned above, in our work, agent decision-making is governed by the
LEUP. According to Eq. (1), setting $\beta<0$ results in decisions that
maximize the microenvironmental entropy. As expected, maximizing entropy at
the mesoscopic scale fails in leading to global synchronization. Conversely,
minimizing entropy at the mesoscopic scale (i.e., $\beta>0$) leads to
synchronization beyond a threshold interaction radius. The existence of this
threshold radius, beyond which synchronization occurs, is consistent with the
previously studied multi-decision-maker model [11]. Agents need a minimum
level of interaction to synchronize their decisions. For a radius below this
threshold, the number of particles in the neighborhood is sparse, causing weak
interaction and, hence, failure to synchronize. So far, we have shown the
conditions necessary for the system’s synchronization. Now, we will
investigate the impact of $\beta$ and $R$ on the synchronization time $\tau$.
Synchronization time is defined as the time taken by the decision-makers in
the system to synchronize their orientation i.e., the global polar order
reaches 0.9.

In the Vicsek model, an increase in interaction radius decreases the
synchronization time, as shown in Fig. (3 A). Interestingly, in contrast to
the Vicsek model, our model shows that there is an optimal interaction radius
for a given $\beta$, at which $\tau$ is minimized, as shown in Fig. (3 A).
This phenomenon is counter-intuitive, as we would expect that increasing the
radius enhances interactions, thereby decreasing synchronization time. This
behavior is consistent with the "paradox of choice", where an agent exposed to
too much information becomes paralyzed, leading to deterioration in decision-
making.

Furthermore, we investigate how this decision paradox is affected by
sensitivity $\beta$. To understand this, we plotted a phase diagram, shown in
Fig. (3B), which represents the relationship of the synchronization time with
respect to $\beta$ and $R$. Along the $\beta$ axis, the synchronization time
always decreases, implying that increasing sensitivity for a fixed $R$
enhances the system’s decision rate. As shown above, for a fixed $\beta$, the
synchronization time first decreases and then increases, indicating that
increasing the amount of information does not necessarily improve decision
making. Most importantly, the synchronization time always decreases along the
left-to-right diagonal. Thus, if an agent acquires more information, it needs
to increase its sensitivity as well to maintain the rate of synchronization.

This finding reveals a trade-off in collective decision-making that strictly
depends on sensitivity and interaction radius. We show that decision making is
indeed a complex process that relies not only on the volume of information
available but also on the individual information processing as quantified by
the sensitivity parameter $\beta$. When a certain level of sensitivity is
present, an overload of information can impair decision-making, a phenomenon
often referred to as the paradox of choice. This highlights the importance of
balancing information intake and processing to make effective decisions, as
shown in Fig.(2).

#### Biased sampling

Now we employ the biased or weighted sampling scenario for agent decision-
making. We calculated the weight for each possible decision using the Von-
Mises distribution, which is equivalent to the normal distribution for any
wrapped random variables. The mean of the distribution is set as the average
orientation of the agents in the neighborhood, representing the maximum
likelihood estimation of the Von-Mises distribution [18]. The distribution
parameter $\kappa=\frac{1}{\sigma^{2}}$ where $\sigma$ is the variance of the
sampled neighborhood.

One might wonder how weighted decision-making can impact synchronization. Our
simulation shows that for lower value of $\kappa$ implying weak bias, the
dependence of synchronization time on interaction radius exhibits similar
behavior to the random selection case. As shown in Fig. (3 C), the
synchronization time decreases to $R=2.5$, after which it starts to increase.
Therefore, the “paradox of choice” emerges in this case.

For higher $\kappa$, corresponding to strong bias, we observe a markedly
different behavior. As shown in Fig.(3 C), biased agents do not suffer from
information overload due to an increased interaction radius. The excess
information does not seem to significantly change synchronization time. This
observation is qualitatively similar to what is seen in the Vicsek Model. This
indicates that entropy-driven decision-making, when combined with some
additional knowledge, reproduces the results of the Vicsek Model. Furthermore,
we demonstrate that the paradox of choice, when presented with numerous
options, can be mitigated by educating decision-makers with prior knowledge.

#### Memory effect

So far, we have assumed that agents do not remember any of their past
decisions and hence are memoryless. However, in reality, a decision maker’s
choice is influenced by previous decisions. It is intriguing to study how the
implementation of memory alters synchronization in the system. Does the
introduction of memory change the nature of “paradox of choice”?

We incorporate the function of memory by adjusting decisions based on the
surrounding environment, allowing memory to motivate agents to choose
decisions that have been previously selected. Each agent possesses restricted
memory, meaning that they can only recall their last $m$ decisions with equal
intensity. Interestingly, we discovered that an excess of information does not
hinder the agent decision-making process. In fact, agents become more
proficient when they possess memory compared to when they are devoid of
memory(4). This implies that the paradox of choice is hindered in the case of
decision-makers with memory.

Figure 3: Synchronization time vs interaction radius (A) and (C) represent the
mean synchronization time of the system for 20 simulations on varying sensing
radius for random ($\beta=2$) and Von Mises distribution respectively. The
comparison of synchronization time with the Vicsek Model is also shown for
each figure. (B) and (D) shows the phase diagram with synchronization time
averaged over 20 simulations, plotted against $\beta$ and R for random and Von
Mises distributions ($\kappa=0.1$) respectively. Synchronization is defined by
achieving a global polar order greater than 0.9. The red region in the phase
diagram corresponds to the regime where the system fails to synchronize. All
the simulations were done for the speed $0.1\,unit/sec$ Figure 4: Memory
effect on synchronization for agents with memory capacity m =1 and without
memory. The simulation is done for $\beta=2$ and 250 agents moving at the
speed 0.1 unit/sec.

## Discussion

In this article, we attempted to provide an alternative explanation of the
“paradox of choice” based on statistical mechanics arguments. In particular,
we have assumed that agents are employing the LEUP as a mechanism of decision-
making. According to LEUP, we have defined an internal variable that reflects
the choice/state of the individual. The corresponding dynamics is driven by an
entropic gradient of choices found in the respective microenvironment. In
order to explain the “paradox of choice”, we made the assumption that
individual feel discontent when the uncertainty of this internal variable
increases in time. Using a mean-field calculation, we provide a closed formula
that quantifies the rate of variance against the number of choices. Even in
this simplifying setting, we find an optimum for a number number of choices
that minimizes the variance rate of the intrinsic variable. Above the optimal
value of $N$, the decision-maker experiences the frustration due to the
overwhelming amount of choices. On the other hand, when number of choices are
too few, then decisions are almost random since the deterministic entropic
drift is very weak.

Figure 5: A schematic way understand how our theory contributes to the
understanding of the “paradox of choice”. On the left vertical axis, we
indicate the relevant observable regarding individual decision making being
the decision uncertainty rate $\frac{d\sigma^{2}}{dt}$. On the right, with
blue, we depict the collective variable being the synchronization time $\tau$.
The x-axis represents the number of choices $N$. More information in the text.

In turn, we analyzed the microenvironmental entropy of orientation in
decision-makers, using an individualized-based model to study group-level
decision-making dynamics. Our findings reveal a trade-off between
synchronization time and the sensing radius, indicating the optimal conditions
for information transfer among group members, which significantly depends on
the individual information processing (sensitivity parameter). Fig. (5)
illustrates the main conclusions of our study.

In realistic scenarios, decision-makers observe and respond to their local
environments not randomly but in a weighted manner, potentially reinterpreting
the “paradox of choice”. By assigning weightages visualized from the Von-Mises
distribution, decision-makers realistically adapt to the orientations of local
agents, leading to shifts in critical timeframes for decision-making. These
shifts suggest that weighted decision-making processes can accelerate group-
level decisions depending on the variance of the assigned weights. Moreover,
we explore the phenomenon of trend-setting among decision-makers, akin to the
Hipsters effect, where anti-conformists seeking uniqueness paradoxically end
up appearing similar [19]. This setup led us to discover the emergence of
micro-level communities based on orientations and delays in group decision-
making as memory sizes increased.

This interpretation of “paradox of choice” might be relevant for Cell Biology.
LEUP theory has been developed in the context of cell decision-making in
multicellular systems [10, 11, 12, 20]. Cell fate determination is a cell
decision-making mechanism related to cell differentiation and development.
Stem cells differentiated to more specified phenotypes when they find
themselves in well-defined niches [21]. Stem cell niches are composed by a
specific variety of relevant determinants, such as nutrients, chemical cues,
ECM molecules, biophysical conditions and other cell types, that drive stem
cells to acquire a specific phenotype. Each tissue has a uniquely defined
niche. Having to few determinants stem cells are not able to initiate
proliferation and/or differentiation programs. On the other hand, having more
components has lead to impaired differentiation e.g. by excessive signaling
and oversaturation of receptors, overcrowding of niche cells leading to low
proliferative potential or excess ECM components putting physical barriers to
differentiation processes. Regarding cell fate decisions, we postulate that
there is a trade-off between the information processing capacities of the stem
cell and the available microenvironmental information [22].

In our model, we assumed that each individual decision maker seeks to minimize
their microenvironment entropy, treating it as a cost function that we
computed numerically. It will be interesting to explore how our model can be
applied to various systems as a utility or cost function with different
constraint setups, which can be validated using experimental evidence. In
addition, we can observe the behavior of decision makers under these
conditions. This framework is crucial not only for understanding paradoxes,
but also for comprehending the macroscopic phenomena of group-level decision-
making based on local influence. Upon further consideration, we can also
evnision the application of this framework within the context of opinion
dynamics or voting dynamics, where individual agents share their opinions in a
closed community, potentially leading to normative social influence driven by
conformity [23]. When the order parameter is close to 1, it can indicate a
unique group-level decision, reflecting a democratic consensus.

In future work, this framework can serve as a benchmark or training model
(similar to the bootstrap method), where individual agents train their sensing
radius and sensitivity based on the local density of microenvironmental agents
and neighborhood dynamics. This trained model can then be applied to new
environmental setups, allowing individual agents, as a group, to enhance
decision-making time at the group level based on different utilities or goals.

## Acknowledgements and funding

HH, MG and AB would like to thank Volkswagenstiftung for its support of the
"Life?" program (96732). HH has received funding from the Bundes Ministeriums
für Bildung und Forschung under grant agreement No. 031L0237C (MiEDGE project/
ERACOSYSMED). Finally, HH acknowledges the support of the RIG-2023-051 grant
from Khalifa University and the UAE-NIH Collaborative Research grant AJF-
NIH-25-KU. AB would like to thank Tata Institute of Fundamental Research
Hyderabad for the fellowship.

## Declaration of competing interests

The authors declare no competing interests.

## Data availability

This paper does not report either data generation or analysis.

## References

  * [1] J. van der Pligt  “Decision Making, Psychology of”  In _International Encyclopedia of the Social and Behavioral Sciences_ Oxford: Pergamon, 2001, pp. 3309–3315  DOI: https://doi.org/10.1016/B0-08-043076-7/01750-2
  * [2] Evan L. MacLean et al.  “How does cognition evolve? Phylogenetic comparative psychology”  In _Animal Cognition_ 15.2, 2012, pp. 223–238  DOI: 10.1007/s10071-011-0448-8
  * [3] Előd Méhes and Tamás Vicsek  “Collective motion of cells: from experiments to models”  In _Integrative Biology_ 6.9, 2014, pp. 831–854  DOI: 10.1039/c4ib00115j
  * [4] Andreas Deutsch, Guy Theraulaz and Tamas Vicsek  “Collective motion in biological systems”  In _Interface Focus_ 2.6, 2012, pp. 689–692  DOI: 10.1098/rsfs.2012.0048
  * [5] Josué Manik Nava-Sedeño et al.  “Modelling collective cell motion: Are on- And off-lattice models equivalent?: Equivalent on- And off-lattice models”  In _Philosophical Transactions of the Royal Society B: Biological Sciences_ 375.1807, 2020  DOI: 10.1098/rstb.2019.0378
  * [6] Tamás Vicsek and Anna Zafeiris  “Collective motion” Collective motion  In _Physics Reports_ 517.3, 2012, pp. 71–140  DOI: https://doi.org/10.1016/j.physrep.2012.03.004
  * [7] Barry Schwartz  “The paradox of choice: why more is less”  New York, NY: Harper Perennial, 2007, pp. 265
  * [8] W.. Hick  “On the Rate of Gain of Information”  In _Quarterly Journal of Experimental Psychology_ 4.1, 1952, pp. 11–26  DOI: 10.1080/17470215208416600
  * [9] Ray Hyman  “Stimulus information as a determinant of reaction time.”  In _Journal of Experimental Psychology_ 45.3 US: American Psychological Association, 1953, pp. 188–196  DOI: 10.1037/h0056940
  * [10] Haralampos Hatzikirou  In _Journal of the Mechanical Behavior of Materials_ 27.1-2, 2018, pp. 20180001  DOI: doi:10.1515/jmbm-2018-0001
  * [11] Arnab Barua, Josue M. Nava-Sedeño, Michael Meyer-Hermann and Haralampos Hatzikirou  “A least microenvironmental uncertainty principle (LEUP) as a generative model of collective cell migration mechanisms”  In _Sci. Rep._ 10 Nature Research, 2020, pp. 22371  DOI: 10.1038/s41598-020-79119-y
  * [12] Arnab Barua et al.  “Entropy-driven cell decision-making predicts ‘fluid-to-solid’ transition in multicellular systems”  In _New J. Phys._ 22 IOP Publishing, 2020, pp. 123034  DOI: 10.1088/1367-2630/abcb2e
  * [13] Arnab Barua, Alireza Beygi and Haralampos Hatzikirou  “Close to Optimal Cell Sensing Ensures the Robustness of Tissue Differentiation Process: The Avian Photoreceptor Mosaic Case”  In _Entropy_ 23.7, 2021, pp. 1099–4300  DOI: 10.3390/e23070867
  * [14] Tamás Vicsek et al.  “Novel Type of Phase Transition in a System of Self-Driven Particles”  In _Phys. Rev. Lett._ 75 American Physical Society, 1995, pp. 1226–1229  DOI: 10.1103/PhysRevLett.75.1226
  * [15] Tamás Vicsek et al.  “Novel type of phase transition in a system of self-driven particles”  In _Physical review letters_ 75.6 APS, 1995, pp. 1226
  * [16] Makito Oku and Kazuyuki Aihara  “On the covariance matrix of the stationary distribution of a noisy dynamical system”  In _Nonlinear Theory and Its Applications, IEICE_ 9.2, 2018, pp. 166–184  DOI: 10.1587/nolta.9.166
  * [17] Hyunsuk Hong and Steven H. Strogatz  “Kuramoto Model of Coupled Oscillators with Positive and Negative Coupling Parameters: An Example of Conformist and Contrarian Oscillators”  In _Phys. Rev. Lett._ 106 American Physical Society, 2011, pp. 054102  DOI: 10.1103/PhysRevLett.106.054102
  * [18] S. Abeyasekera and D. Collett  “On the estimation of the parameters of the von mises distribution”  In _Communications in Statistics - Theory and Methods_ 11.18 Taylor and Francis, 1982, pp. 2083–2090  DOI: 10.1080/03610928208828371
  * [19] Jonathan D. Touboul  “The hipster effect: When anti-conformists all look the same”  In _Discrete and Continuous Dynamical Systems - B_ 24.8, 2019, pp. 4379–4415  DOI: 10.3934/dcdsb.2019124
  * [20] Arnab Barua and Haralampos Hatzikirou  “Cell decision-making through the lens of Bayesian learning”  arXiv, 2023  DOI: 10.48550/ARXIV.2301.06941
  * [21] Michael R. Hicks and April D. Pyle  “The emergence of the stem cell niche”  In _Trends in Cell Biology_ 33.2 Elsevier Ltd, 2023, pp. 112–123  DOI: 10.1016/j.tcb.2022.07.003
  * [22] Christina J. Su et al.  “Ligand-receptor promiscuity enables cellular addressing”  In _Cell Systems_ 13.5, 2022, pp. 408–425.e12  DOI: https://doi.org/10.1016/j.cels.2022.03.001
  * [23] Claudio Castellano, Santo Fortunato and Vittorio Loreto  “Statistical physics of social dynamics”  In _Rev. Mod. Phys._ 81 American Physical Society, 2009, pp. 591–646  DOI: 10.1103/

## Supporting material

#### Polar order

Figure 6:  Polar order of the system averaged over 20 simulations under the
random choice-making strategy. Figure 7: Polar order of the system averaged
over 20 simulations under the biased strategy. Figure 8: Optimal Radius vs
Number of agents As we talked before there is an optimal radius at which
synchroniation is fastest. As we increase the radius it increases the number
of decision-makers in the neighborhood. Expectedly increasing the density of
the agents decreases the optimal radius.

#### Analytical proof for the emergence of non-monotonic behavior of the
variance of decisions with respect to synchroniation time and radius

1\. Derivation of sample variance in terms of population variance and size of
the sample
In this section, we shall try to understand why we can observe the paradox of
choices in decision-making. Let’s consider the microenvironment consists of
$N$ decision makers and at the center $n$-th decision maker is collecting all
the microenvironmental decision making in a Gaussian manner at time $t$ where
the mean value of every decision collected from the environment is defined by
$\mu_{n}$ and the variance is defined by $\sigma_{n}^{2}$. Here we assumed for
simplicity that the angular decisions lies on the interval $(0,2\pi)$.
Furthermore, to evaluate average decision-making at the group level we assume
a mean-field approach where we use the Central Limit Theorem (CLT) to neglect
the correlation among the population. So, the mean value and standard
deviation of decision maker $n$ for each local environment can be written
(using CLT) as

$\mu_{n}=\mu+\frac{\xi}{\sqrt{N}}$ (11)
$\frac{1}{N}\sum_{i=1}^{N}\left(\mu_{n}-\theta_{i}\right)^{2}=\frac{1}{N}\sum_{i=1}^{N}\left(\mu-\theta_{i}+\frac{\xi}{\sqrt{N}}\right)^{2}$
(12)
$\sigma^{2}_{n}=\frac{1}{N}\sum_{i=1}^{N}\left(\left(\mu-\theta_{i}\right)^{2}+\frac{\xi^{2}}{N}+\frac{2}{N}(\mu-\sum_{i}\frac{\theta_{i}}{N})\frac{\xi}{\sqrt{N}}\right)$
(13)

Please note that $\xi$ is the Gaussian noise $\mathcal{N}(0,\Sigma)$ and $\mu$
is the population average of all decision-making in the system. Now, we shall
calculate the variance of $n$-th decision maker to do that we shall take the
average over the decision-making $\theta$ present in the environment $N$,

$\sigma^{2}_{n}=\Sigma+\frac{\Sigma}{N}=\Sigma\left(1+\frac{1}{N}\right)$ (14)

where, $\Sigma$ is the population variance of all decision making in the
system.

2\. Derivation of the rate of change in the mean value decisions at the
population level

To calculate the evolution of the mean value at the population level we shall
use Eq.(1) and assume the Gaussian form of the microenvironmental entropy. So,
the rate of change of decisions can be written as

$\frac{d\theta_{n}}{dt}=\frac{\beta}{\sigma^{2}_{n}}\left({\frac{\theta_{n}}{N}-\frac{\sum_{i\neq
n}^{N}\theta_{i}}{N^{2}}}\right)$ (15)
$\frac{d\theta_{n}}{dt}=\frac{\beta}{\sigma^{2}_{n}}\left({\frac{\theta_{n}}{N}-\frac{\sum_{i\neq
n}^{N}\theta_{i}+\theta_{n}-\theta_{n}}{N^{2}}}\right)$ (16)
$\frac{d\theta_{n}}{dt}=\frac{\beta}{\sigma^{2}_{n}}\left({\frac{\theta_{n}}{N}-\frac{\mu_{n}}{N}+\frac{\theta_{n}}{N^{2}}}\right)$
(17)

here, $S_{n}$, and $\mu_{n}$ are the variance and mean of the sample
respectively. Under the central limit theorem, the mean and variance of the
sample can be written in terms of the population mean and variance.

$\mu_{n}=\mu+\frac{\xi}{\sqrt{N}}\And\sigma^{2}_{n}=\Sigma\left(1+\frac{1}{N}\right)$
(18)

Therefore under the mean-field limit the rate of change of one particle
represents a change of the average particle, hence:

$\frac{d\theta_{n}}{dt}=\frac{N}{N+1}\frac{\beta}{\Sigma}\left({\frac{\theta_{n}}{N}-\frac{\mu+\frac{\xi}{\sqrt{N}}}{N}+\frac{\theta_{n}}{N^{2}}}\right)$
(19)
$\frac{d\langle\theta_{n}\rangle}{dt}=\frac{N}{N+1}\frac{\beta}{\Sigma}\left({\frac{\langle\theta_{n}\rangle}{N}-\frac{\mu+\frac{\xi}{\sqrt{N}}}{N}+\frac{\langle\theta_{n}\rangle}{N^{2}}}\right)$
(20)
$\frac{d\mu}{dt}=\frac{N}{N+1}\frac{\beta}{\Sigma}\left({\frac{\mu}{N}-\frac{\mu+\frac{\xi}{\sqrt{N}}}{N}+\frac{\mu}{N^{2}}}\right)=\frac{1}{N+1}\frac{\beta}{\Sigma}\left(\frac{\mu}{N}-\frac{\xi}{\sqrt{N}}\right)$
(21)

3\. Derivation of the rate of change of variance of the orientation of the
population

Similarly, we shall calculate the evolution of the variance at the population
level using the mean-field approach. Using the previous dynamical equation of
decisions one can write

$\frac{d\Sigma}{dt}=D-\beta\frac{\partial}{\partial\theta_{n}}\left(\frac{1}{\sigma^{2}_{n}}\left({\frac{\theta_{n}}{N}-\frac{\sum_{i\neq
n}^{N}\theta_{i}+\theta_{n}-\theta_{n}}{N^{2}}}\right)\right)\Sigma=D+2R\Sigma$
(22)

The variance of the random variable has been defined by $\Sigma$ the variance
of the Gaussian noise is defined by $D$ and the $R$ term can be seen as

$\frac{df}{d\theta_{n}}=\frac{1}{\sigma^{2}_{n}N}-\frac{\theta_{n}}{N(\sigma_{n}^{2})^{2}}\frac{d\sigma^{2}_{n}}{d\theta_{n}}+\frac{\mu_{n}}{N(\sigma_{n}^{2})^{2}}\frac{d\sigma^{2}_{n}}{d\theta_{n}}-\frac{\theta_{n}}{(\sigma_{n}^{2})^{2}N^{2}}\frac{d\sigma^{2}_{n}}{d\theta_{n}}$
(23)

If we substitute the derivative of variance as
$\frac{d\sigma^{2}_{n}}{d\theta_{n}}$ with $\frac{2(\theta_{n}-\mu_{n})}{N}$
it looks as

$\frac{df}{d\theta_{n}}=\frac{1}{\sigma^{2}_{n}N}-\frac{2\theta_{n}(\theta_{n}-\mu_{n})}{N^{2}(\sigma_{n}^{2})^{2}}+\frac{2\mu_{n}(\theta_{n}-\mu_{n})}{N^{2}(\sigma_{n}^{2})^{2}}-\frac{2\theta_{n}(\theta_{n}-\mu_{n})}{(\sigma_{n}^{2})^{2}N^{3}}$
(24)

$\frac{df}{d\theta_{n}}=\frac{1}{\sigma^{2}_{n}N}-\frac{2(\theta_{n}^{2}-\theta_{n}\mu_{n})}{N^{2}(\sigma_{n}^{2})^{2}}+\frac{2(\theta_{n}\mu_{n}-\mu_{n}^{2})}{N^{2}(\sigma_{n}^{2})^{2}}-\frac{2(\theta_{n}^{2}-\mu_{n}\theta_{n})}{(\sigma_{n}^{2})^{2}N^{3}}$
(25)

Furthermore, we replace the term $\mu_{n}$ with $\mu+\frac{\Sigma}{\sqrt{N}}$
(using CLT) which further simplifies the expression of
$\frac{df}{d\theta_{n}}$ as

$\frac{df}{d\theta_{n}}=\frac{1}{\sigma^{2}_{n}N}-\frac{2(\theta_{n}^{2}-\mu\theta_{n}+\theta_{n}\frac{\xi}{\sqrt{N}})}{N^{2}(\sigma_{n}^{2})^{2}}+\frac{2(\theta_{n}\mu+\frac{\theta_{n}\xi}{\sqrt{N}}-(\mu+\frac{\xi}{\sqrt{N}})^{2})}{N^{2}(\sigma_{n}^{2})^{2}}-\frac{2(\theta_{n}^{2}-(\mu\theta_{n}+\frac{\theta_{n}\xi}{\sqrt{N}}))}{(\sigma_{n}^{2})^{2}N^{3}}$
(26)

taking an average over the population,

$\frac{df}{d\theta_{n}}=\frac{1}{\sigma^{2}_{n}N}-\frac{2(\langle\theta_{n}^{2}\rangle-\mu^{2})}{N^{2}(\sigma_{n}^{2})^{2}}+\frac{2(\mu^{2}-\mu^{2}-\frac{\langle\xi^{2}\rangle}{N})}{N^{2}(\sigma_{n}^{2})^{2}}-\frac{2(\langle\theta_{n}^{2}\rangle-\mu^{2})}{(\sigma_{n}^{2})^{2}N^{3}}$
(27)

in the final step we do a population average as
$\langle\theta_{n}^{2}\rangle-\mu^{2}=\Sigma$ and $\langle\xi^{2}\rangle$=
$\Sigma$

$\frac{df}{d\theta_{n}}=\frac{1}{\sigma^{2}_{n}N}-\frac{2\Sigma}{N^{2}(\sigma_{n}^{2})^{2}}-\frac{2(\frac{\Sigma}{N})}{N^{2}(\sigma_{n}^{2})^{2}}-\frac{2\Sigma}{(\sigma_{n}^{2})^{2}N^{3}}$
(28)

now, from Eq.(14), finally replace the $\sigma^{2}_{n}$ as
$\Sigma(1+\frac{1}{N})$ we get

$\frac{df}{d\theta_{n}}=\frac{1}{\Sigma(1+N)}-\frac{2\Sigma}{\Sigma^{2}(1+N)^{2}}-\frac{2(\frac{\Sigma}{N})}{\Sigma^{2}(1+N)^{2}}-\frac{2\Sigma}{\Sigma^{2}N(1+N)^{2}}$
(29)

and as we know that from the mean-field equation [16] one can compare the
above expression and can write the variance evolution in the equation zero
noise case using eq. $\frac{d\Sigma}{dt}=-2\beta R(\Sigma,\mu,N)\Sigma$ as

$\frac{d\Sigma}{dt}=-\beta\left(\frac{2}{(1+N)}-\frac{4}{(1+N)^{2}}-\frac{8}{N(1+N)^{2}}\right)=-\frac{2\beta\left(N^{2}-N-4\right)}{N(1+N)^{2}}$
(30)