# Feature extraction and evaluation for BioMedical Question Answering

Ankit Shah, Srishti Singh, Shih-Yen Tao
<EMAIL_ADDRESS>
Course Instructor - Prof.Eric Nyberg

## Abstract

In this paper, we present our work on the BioASQ pipeline. The goal is to
answer four types of questions: summary, yes/no, factoids, and list. Our goal
is to empirically evaluate different modules involved: the feature extractor
and the sentence selection block. We used our pipeline to test the
effectiveness of each module for all kind of question types and perform error
analysis. We defined metrics which are useful for future research related to
the BioASQ pipeline critical to improve the performance of the training
pipeline.

##  1 Introduction

The biomedical semantic question answering task - task 6b comprises a large
scale question answering challenge, which is given for a systems answer at all
stages of question answering task. There are four types of bio medical
questions - yes/no, factoid, list and summary questions. The system under test
is provided with English questions written by biomedical experts which reflect
real-life information requirements.

The overall pipeline is described in Fig 1. For each question, a list of
supporting documentations are also given. At first, a snippets ranker is used
to select snippets which are relevant to the question. Secondly, a sentence
ranker along with the feature extractor module perform ranking algorithm to
choose top $k$ candidate sentences for the final summary. In the end, the
tiler module gather all sentences and compress them into the final result.

To be more specific, the snippets ranker use the Indri algorithm Sharma et al.
(2018) to choose relevant snippets, and the tiler module used quadratic
programming to predict the final output. As for the feature extractor module,
which we test in this project, use either Jaccard, Dice, Tf cosine similarity
Achananuparp et al. (2008), dependency parser Chen and Manning (2014) or the
combined feature. For the sentence selection module, we used a greedy approach
as the baseline and compared it with the MMR algorithm Carbonell and Goldstein
(1998).

Figure 1: The Overall Pipeline based on important modules needed for question
answering

##  2 Dataset Description

In this section we introduce the details of the BioASQ dataset. In order to
evaluate our pipeline, we divided the training data provided by the BioASQ
challenge into training/dev/test set with the ratio of $7:2:1$. The whole
dataset consists of four sub-types of questions: list, factoid,yes/no, and
summary. The first three come along with one ideal answer and one exact
answer, while the summary question only have an ideal answer. Note that in our
project, we evaluate the ideal answer for the summary question and the exact
answer for the other three types of questions. The overall statistics and the
distribution of the questions are summarized in Table 1 and Fig 2,
respectively.

Table 1: Dataset Statistics.

Question Types | Training | Dev | Test
---|---|---|---
Total | 1259 | 359 | 181
Summary | 274 | 81 | 45
List | 285 | 81 | 47
Factoid | 358 | 86 | 42
Yes/No | 342 | 111 | 47

Figure 2: Distribution of Questions in the Dataset.

##  3 Similarity evaluation metrics

Jaccard Similarity: - We calculate the Jaccard similarity, which is the
intersection over union and it is a statistic used for comparison of the
similarity and diversity of the sample sets.

TF-IDF with word embeddings : - Ontologies like WordNet and UMLS/SNOMEDCT are
used in biomedical domain for concept expansion for incorporating the
semantics while computing the sentence similarity is not sufficient due to the
nature of the ontologies. Thus, semantic information is more controlled and
updated with a similarity metric inspired by TF-IDF Chandu et al. (2017). This
similarity metric uses the symmetric word to word similarity matrix and the
tf-idf vectors for the sentences among which the similarity is computed.

Dice coefficient : - Dice coefficient is similar to the Jaccard index however
one takes the string measure as - say there are two strings x and y then using
the bigrams the string similarity is computed as s = 2*$n_{t}$/$n_{x}$ \+
$n_{y}$

Cosine correlation similarity :- Cosine similarity has an interpretation of
the angle between the two vectors.

##  4 Approach

We aim to address the research questions on comparing different feature
extractor and sentence ranking algorithm for the Biomedical question answering
system. We run our pipeline on both ideal and exact question evaluation. The
details of each component is introduced in the following.

The feature extractor can be interpreted as a similarity function in fact.
Given two sentences $A,B$, the module $f(A,B)$ output a similarity score of
the pair. The Jaccard feature extractor Kobayakawa et al. (2009) computes the
score by $f(A,B)=\frac{|A\cap B|}{|A\cup B|}$, which computes the overlapping
ratio of two sentences. The Dice feature extractor Albertsson et al. (2016)
does a similar thing by computing $f(A,B)=\frac{2|A\cup B|}{|A|+|B|}$. On the
other hand, the TF module first convert each sentence into a TF feature
representation $tf(A),tf(B)$, and computes the cosine similarity between them.
The above three module ends up with three scores, the combined feature
extractor simply outputs the score sum.

A dependency parser analyzes the grammatical structure of a sentence,
establishing relationships between ”head” words and words which modify those
heads. Such relations are important to establish to understand the extent to
which a head word is affected by words surrounding them. The use of such a
dependency parser is missing in BioMedical question answering literature.
Since uncovering the semantic structure and extent of dependencies is critical
to answer questions when humans perform question answering, we think it will
improve and play a critical role in the BioMedical Question answering
pipeline, thus we experiment using the dependency parser. We implemented the
dependency parser as a feature in combination with Jaccard, cosine and tf-idf
similarity. The parser works with sentence roots to draw similarity between
question and candidate sentences Fig 3.

Figure 3: Dependency Parsed Sentence Structure

For the sentence selection module, the baseline we are going to try is the
greedy selections. That is to say, given we can at most select $k$ sentence
for final summary, we greedily select top-k sentences with highest score. Or
course, this naive strategy results in poor summary result, since it
introduces lots of redundancy, which is certainly not a desirable property for
high quality summary. As the result, our main goal for this particular module
is to reduce the sentence redundancy.

As the result, we leveraged Maximal Marginal Relevance Carbonell and Goldstein
(1998) as the additional approach. In a nutshell, a candidate is selected
based on the similarity score with _B_ OTH question sentence and another
candidate sentences which were already selected as answer. As shown in
previous literature, MMR could effectively reduce the redundancy.

##  5 Error analysis and metrics

We use the standard ROUGE scores Lin (2004) for evaluating the pipeline.
Recall-Oriented Understudy for Gisting Evaluation (ROUGE) has various types of
performance analysis metrics. For our task we use ROUGE-l as the metric for
evaluation. ROUGE-l is the longest common subsequence based statistics where
the longest common subsequence takes into account sentence level structures
similarity naturally and identifies the co-occuring sequence n-grams
automatically. Such a metric will enable us to answer the questions and thus
it is useful for the BioASQ question answering summary evaluation task where
the predicted answer and the ideal answer will be used as references to
evaluate the ROUGE metric. In order to understand the accuracy of the system
and post process the output, we defined two new metrics to evaluate the end to
end system. We know that there are questions such as yesno question type, list
question type and factoid question types whose ideal answer as well as exact
answers are defined in the system. We want our system to not only perform well
on not only the summary type questions but also all other types of questions.
This is mainly a post processing step which will enable further understanding
of the system and can be applied for the cases where the questions with exact
answer information is already available. These metrics are as follows.

  * •

Soft exact answer based accuracy measure - This measure is defined to
calculate accuracy of the system when any of the exact answers is found in the
predicted answer in the overall system.

  * •

Hard exact answer based accuracy measure - This measure is defined to
calculate accuracy of the system when all of the exact answers is found and
predicted in the overall system.

##  6 Experimental Design

Our design would be based on the OAQA system extension as well as using the
BioASQ - Rabbit pipeline in order to use the overall pipeline and extend the
same by adding functionality for each module namely, Feature Extractor and
Sentence selection. In doing so, we hope to standardize our scores in order to
not get bogged down by redundancies. We will draw upon Vasu et all’s paper on
BioAMA[5] and possibly collaborate with them to find possibilities to enhance
their pipeline.

In particular, we test on the ideal answer and exact answer separately. The
ideal answer type will evaluated by the question level ROUGE scores using the
different combinations ranking functions at the ranker level as well as
different methodology of the sentence selection procedure. As for the exact
answer which is described in the below section. Finally, we use statistics
significant test to analysis the error.

We designed a new accuracy metric based on hard and soft measure to define the
number of exact answers which were found in the predicted answer. This
analysis was done for yes-no, list and factoid type questions.

##  7 Analysis for Summary Type Question

In this part, we test our pipeline for the summary type question. We will
first show the results on both different sentence selection modules and
feature extractors, and then perform error analysis.

First, we show our results on different sentence selection modules; the greedy
selection serves as the baseline, which greedily selects top $k$ sentences
according to their similarity score between the question. We compare the
baseline with MMR Module. Note that in this part we fixed the feature
selection module to the Jaccard similarity feature. The results are shown in
Table 2. We could clearly see that MMR Module is better than the greedy
baseline, which verify our hypothesis that reducing the redundancy is
important for the summary questions.

Table 2: Greedy Selection vs MMR. k | Precision | Recall | F1 |
---|---|---|---|---
1 | 0.784 | 0.222 | 0.292 |
2 | 0.623 | 0.373 | 0.38 |
3 | 0.522 | 0.485 | 0.398 |
4 | 0.469 | 0.553 | 0.407 |
5 | 0.415 | 0.612 | 0.415 |
6 | 0.388 | 0.658 | 0.406 |
7 | 0.376 | 0.671 | 0.409 |
8 | 0.366 | 0.662 | 0.396 |
9 | 0.358 | 0.674 | 0.392 |
10 | 0.362 | 0.657 | 0.385 |

Secondly, we show the results on different feature extractor modules: Jaccard
similarity, Dice similarity, Tf-Idf similarity and the combined feature. The
results are shown in Table 4. It could be observed that overall the Jaccard
feature has the best Rouge score. Our experiment with the pre-trained
Dependency Parser resulted in increase in precision of the Rouge Score,
however, it did not result in improvement in Rouge-F1 score. We attribute this
result to cosine and td-idf bringing semantic similarity into picture which is
more effective than syntactical similarity as offered by the parser, as shown
in Table 3.

Table 3: Results on Dependency Parser. Method | Precision | Recall | F1
---|---|---|---
Original | 0.415 | 0.612 | 0.415
Parser | 0.422 | 0.591 | 0.405
Table 4: Comparison of Feature Extractors.

k | Jaccard | Dice | Tf-Idf | Combined
---|---|---|---|---
1 | 0.292 | 0.321 | 0.327 | 0.307
2 | 0.38 | 0.379 | 0.386 | 0.374
3 | 0.398 | 0.4 | 0.403 | 0.391
4 | 0.407 | 0.412 | 0.396 | 0.412
5 | 0.415 | 0.397 | 0.396 | 0.409
6 | 0.406 | 0.4 | 0.394 | 0.404
7 | 0.409 | 0.398 | 0.388 | 0.399
8 | 0.396 | 0.394 | 0.393 | 0.398
9 | 0.392 | 0.395 | 0.389 | 0.398
10 | 0.385 | 0.393 | 0.388 | 0.402

Now we take a deeper look in our experiments. The first question raised is how
we choose the number of candidate sentences. In order to choose the best $k$,
we resort to the Wilcoxon significance test to determine under which number
our experiment has statistics significance. We first test on the sentence
selection experiment and show the results in Table 5. Obviously, we can see
that we have experiment significant when $k$ is range from $4$ to $7$.

After we decide $k$, we could also use significant test to justify our results
on the feature extractor experiments. To be more specific, we compare the best
feature: Jaccard with the others in Table 6, Table 7, and Table 8.

Table 5: Wilcoxon Significant Test on Sentence Selection.

k | Greedy | MMR | Mean-diff | Wilcoxon
---|---|---|---|---
2 | 0.36 | 0.374 | 0.014 | 0.379
3 | 0.459 | 0.485 | 0.026 | 0.069
4 | 0.528 | 0.553 | 0.025 | 0.17
5 | 0.573 | 0.612 | 0.039 | 0.018
6 | 0.623 | 0.658 | 0.035 | 0.02
7 | 0.635 | 0.671 | 0.036 | 0.005
8 | 0.653 | 0.662 | 0.009 | 0.652
9 | 0.651 | 0.674 | 0.023 | 0.039
10 | 0.654 | 0.6 | -0.054 | 0.517

Table 6: Jaccard vs Dice.

k | Dice | Jaccard | Mean-diff | Wilcoxon
---|---|---|---|---
4 | 0.513 | 0.553 | 0.04 | 0.004
5 | 0.571 | 0.612 | 0.041 | 0.003
6 | 0.614 | 0.658 | 0.044 | 0.001
7 | 0.635 | 0.671 | 0.036 | 0.002

Table 7: Jaccard vs Tf. k | Tf | Jaccard | Mean-diff | Wilcoxon
---|---|---|---|---
4 | 0.55 | 0.553 | 0.003 | 0.982
5 | 0.594 | 0.612 | 0.018 | 0.192
6 | 0.63 | 0.658 | 0.028 | 0.043
7 | 0.648 | 0.671 | 0.023 | 0.036
Table 8: Jaccard vs Combined.

k | Combined | Jaccard | Mean-diff | Wilcoxon
---|---|---|---|---
4 | 0.522 | 0.553 | 0.031 | 0.01
5 | 0.593 | 0.612 | 0.019 | 0.136
6 | 0.635 | 0.658 | 0.023 | 0.121
7 | 0.652 | 0.671 | 0.019 | 0.15

We could see that the Jaccard indeed is supported by the significant test for
its better performance against others. However, we note that it becomes more
unstable for the combine feature, we think it is due to the high variance of
the experiment results.

##  8 Analysis of Exact answer based evaluation metric

The table 9 shows results for the yesno type questions across different
similarity metrics such as cosine, dice, jaccard and all combined for k value
ranging from 4-7. We notice that all of the metrics indicate that yesno
questions dont find yes or no in the predicted answer. Jaccard similarity
measure on the other hand does a better job of predicting the yes or no in the
predicted answer on 2 out of the 21 questions which were analyzed in the
validation set.

Table 9: Results for Yes/No type questions

k |  Cosine soft measure |  Cosine hard measure |  Dice soft measure |  Dice hard measure |  Jaccard Soft measure |  Jaccard hard measure |  All Soft measure |  All Hard measure
---|---|---|---|---|---|---|---|---
4 | 0.021 | 0.021 | 0.021 | 0.021 | 0 | 0 | 0.021 | 0.021
5 | 0.021 | 0.021 | 0.021 | 0.021 | 0.04 | 0.04 | 0.021 | 0.021
6 | 0.021 | 0.021 | 0.021 | 0.021 | 0.042 | 0.042 | 0.021 | 0.021
7 | 0.021 | 0.021 | 0.021 | 0.021 | 0.042 | 0.042 | 0.021 | 0.021

The table 10 shows results for the list type questions across different
similarity metrics and for k value ranging from 4-7. We observe a huge gap in
the hard measure and soft measure metrics scores. This can be due to the fact
that the list type question has many options of the exact answer present as
compared to other type questions. Cosine measure performs well for k = 4 and 6
whereas Jaccard soft measure performs well for k = 5 and 7. The ratio of the
number of questions getting atleast one of the output correct is greater than
50 percent most of all the cases which is a very good indicator of correct
output for such question types.

Table 10: Results for List type questions

k |  Cosine soft measure |  Cosine hard measure |  Dice soft measure |  Dice hard measure |  Jaccard Soft measure |  Jaccard hard measure |  All Soft measure |  All Hard measure
---|---|---|---|---|---|---|---|---
4 | 0.61 | 0.1 | 0.51 | 0.085 | 0.57 | 0.085 | 0.55 | 0.085
5 | 0.59 | 0.106 | 0.531 | 0.106 | 0.61 | 0.106 | 0.48 | 0.045
6 | 0.578 | 0.085 | 0.55 | 0.085 | 0.55 | 0.106 | 0.53 | 0.063
7 | 0.591 | 0.106 | 0.55 | 0.085 | 0.61 | 0.107 | 0.55 | 0.085

The table 11 shows results for the factoid type questions across different
similarity metrics such as cosine, dice, jaccard and all combined for k value
ranging from 4-7. The factoid type questions has a value of the soft and hard
measure very close to each other for a given type of similarity metric. This
could be due to the fact that exact answer has only one exact answer in most
of these type of questions. Further, cosine measure and all measure perform
well on 3 of the 4 different k values we tested indicating that the factoid
type questions can we answered reasonably well with exact type present in the
predicted answers.

Table 11: Results for Factoid type questions

k |  Cosine soft measure |  Cosine hard measure |  Dice soft measure |  Dice hard measure |  Jaccard Soft measure |  Jaccard hard measure |  All Soft measure |  All Hard measure
---|---|---|---|---|---|---|---|---
4 | 0.66 | 0.52 | 0.61 | 0.47 | 0.61 | 0.5 | 0.64 | 0.47
5 | 0.59 | 0.45 | 0.61 | 0.136 | 0.54 | 0.42 | 0.64 | 0.54
6 | 0.61 | 0.5 | 0.61 | 0.121 | 0.61 | 0.47 | 0.61 | 0.52
7 | 0.61 | 0.45 | 0.61 | 0.15 | 0.57 | 0.452 | 0.61 | 0.5

##  9 Results analysis - Sample output

###  9.1 Sample - 1

Question\- What colonoscopy findings have been reported in autism?

Ground Truth Answer \- Endoscopy trials have demonstrated a higher prevalence
of nonspecific colitis, lymphoid hyperplasia and focally enhanced gastritis
compared with controls.

Predicted answer (Greedy Approach) \- Intestinal mucosal pathology,
characterized by ileo-colonic lymphoid … variant of inflammatory bowel and
stomach, has been reported in children with developmental disorders. Autistic
enterocolitis : fact or fiction?

Predicted answer (MMR) \- Developmental diagnoses were autism ( 50 patients )
… and bowel symptoms endoscopy trials have demonstrated a higher prevalence of
nonspecific colitis, lymphoid hyperplasia and focally enhanced gastritis
compared with controls.

In this particular example, we compare the summary generated from the Greedy
sentence selection module and the MMR module: We note that the summary
generated by the MMR algorithm is more linguistically reasonable, while the
one from greedy approach is like a random combination of sentences. This
interesting phenomenon supports the hypothesis that MMR can effectively reduce
the redundancy of the candidates, which is beneficial for the tiler module
afterward. Moreover,the Rouge score (recall) for them are $0.84$ and $0.97$,
respectively. The reason is that MMR could select more diverse candidates,
which actually enhances the probability for including the golden answer. On
the other hand, the sentences select by Greedy approach is similar to each
other, which predicts highly unstable results.

###  9.2 Sample - 2

Question \- GV1001 vaccine targets which enzyme?
Predicted answer \- Background : we aimed to assess the efficacy and safety of
sequential or simultaneous telomerase ( htert ) derived peptide, gv1001, has
been developed as a vaccine against various cancers.A study was conducted to
investigate safety and immunogenicity in non-resectable pancreatic carcinoma
patients using a 16-amino acid telomerase peptide ( GV1001 ) for vaccination
in combination with GM-CSF and gemcitabine as first line treatment.Gemcitabine
and capecitabine with or without telomerase peptide vaccine GV1001 in patients
with locally advanced or metastatic pancreatic cancer ( TeloVac ) : an open-
label, randomised, phase 3 trial.Peptide GV1001 is a peptide vaccine
representing a 16-amino acid human telomerase reverse transcriptase sequence,
which has been reported to possess potential antineoplastic and anti-
inflammatory activity.A reverse-transcriptase-subunit of telomerase
vaccination ( gv1001 ) in combination with chemotherapy appeared to be safe
but the immune responses were weak and transient.GV1001 is a 16-amino-acid
vaccine peptide derived from the human telomerase reverse transcriptase
sequence.
Exact answer \- human telomerase reverse transcriptase

We observe that the answer generated in our case is consisting of on an
average 200 words which is large as compared with the ideal answer word count.
This provides us insights into having a better tiling module as the tiler
currently is concatenating the outputs or just using a LSTM network Hochreiter
and Schmidhuber (1997) output to generate the final output. Having constraints
on the number of words one can expect for this question would help improve the
quality of the predicted answer.

###  9.3 Sample - 3

Question Is mitofusin 2 a receptor for parkin?
Ideal answer Yes, Mfn2 functions as a mitochondrial receptor for Parkin.
Predicted answer Mfn2 functions as a mitochondrial fusion protein mitofusin 2
serves as a receptor for parkin translocation to damaged mitochondria.Mfn2
functions as a mitochondrial receptor for Parkin and is required for quality
control of cardiac mitochondria.Recent work demonstrates that a phosphorylated
form of the mitochondrial fusion protein mitofusin 2 serves as a receptor for
parkin recruitment to damaged mitochondria.Mitofusin 1 and mitofusin 2 are
ubiquitinated in a PINK1 manner upon induction of mitophagy we show that the
mitochondrial outer membrane guanosine triphosphatase mitofusin ( Mfn ) 2
mediates Parkin recruitment to damaged mitochondria.
Exact answer Yes
For this question, we notice a useful trend which is predicted in the
predicted answer from our pipeline. We observe that the predicted answer
contains the words Mitofusin 2 serves as a receptor for mitochondrial
receptor. This means that the pipeline is understanding the question which is
being asked and infact this predicted answer is close to ideal answer. Despite
the question of yesno answer type not being able to predict exact answer of
yes or no, one can easily infer that the answer being predicted correctly in
our pipeline. Thus, work is needed here to understand the meaning of the
predicted answer and also append yes or no to the predicted answer as a post
processing step to predict yes or no. Such examples indicate that our pipeline
is indeed working well for the summary type questions. We notice here as well
the length of the ideal answer is very small as compared to our answer which
prints out a summary producing content which is logical but not concise.

###  9.4 Sample - 4

Question Which are the DNA (cytosine-5-)-methyltransferases inhibitors?
Ideal answer DNA (Cytosine-5-)-methyltransferases are a family of enzymes that
methylate DNA at the C5 position of cytosine residues. Given that methylation
of tumour suppressor gene promoters leads to carcinogenesis, inhibition of DNA
(Cytosine-5-)-methyltransferases is a promising strategy for the treatment of
cancer. There are several inhibitors of DNA (Cytosine-5-)-methyltransferases
that uses different modes of action: 5-azacytidine (5-aza-CR, Vidaza®),
5-azadeoxycytidine (5-aza-CdR, decitabine, Dacogen®), 5-azacytosine (ZCyt),
5-fluorodeoxycytidine (FdC), 5,6-dihydro-5-azacytosine (DZCyt),
4’-thio-2’-deoxycytidine, hydralazine, 2-(1H)-pyrimidinone riboside
(zebularine), 2-(1H)-pyrimidinone (zebularine aglycon), procaine,
procainamide, psammaplin A, and RSC133, a new synthetic derivative of
indoleacrylic acid/indolepropionic acid.”
Predicted answer A number of dna ( cytosine-5- ) -methyltransferases by
5-azacytosine is likely to involve methyl transfer to the inhibitor.Although
5-Aza-CdR is known to be incorporated into DNA and inhibit DNA ( cytosine-5 )
-methyltransferases, the precise mechanisms underlying the drug’s
antineoplastic activity remain unclear.The inhibitors showed selectivity for
c5 dna ( cytosine-c5 ) methyltransferase containing 5-azacytosine residues at
specific sites.Although 5-aza-cdr is known to be incorporated into dna (
cytosine-c5 ) methyltransferase containing 5-azacytosine residues at specific
sites.Cooperative action of hdaci and dna methylation inhibitors ( dnmti ) has
been reported, making combined treatment an attractive choice for cancer
therapy.The mechanism of inhibition of dna methyltransferase inhibitors are
known to reactivate silenced genes; including 5-azacytidine and 2- ( 1h )
-pyrimidinone riboside ( zebularine ).Synthesis of oligonucleotide inhibitors
of dna ( cytosine-c5 ) methyltransferase containing 5-azacytosine is likely to
involve methyl transfer to the inhibitor.
Exact Answer’5-azacytidine’, ’5-aza-CR’, ’Vidaza®’, ’5-azadeoxycytidine’,
’5-aza-CdR’, ’Dacogen®’, ”5-aza-2’-deoxycytidine”, ’Decitabine’,
’5-azacytosine’, ’ZCyt’, ’5-fluorodeoxycytidine’, ’FdC’,
’5,6-dihydro-5-azacytosine’, ’DZCyt’, ”4’-thio-2’-deoxycytidine”,
’hydralazine’, ’2-(1H)-pyrimidinone riboside’, ’zebularine’,
’2-(1H)-pyrimidinone’, ’zebularine aglycon’, ’procaine’, ’procainamide’,
’RSC133’, ’Psammaplin A’

For the above difficult question, we notice that there lots of exact answer
samples captured in the predicted answer which implies our model pipeline is
performing well. Further the sentence meaning of the predicted answer is close
to the ideal answer. We have highlighted the exact answer which are found in
our predicted answer for reader to evaluate the prediction received. Ideal
answer is predicting a list of DNA inhibitors in this case and one can account
for that fact in the text and search for such key phrases on what to look for
can be critical for developing a better list type question answering model.

##  10 Lessons Learned

We had several positive results from this project. First outcome was that we
understood the BioASQ challenge task and built an end to end pipeline for
predicting the ideal answer for it. We utilized the software engineering
concepts which were taught in class to present our results at various stages:
pipeline design, error analysis, and code refine. Moreover, by using
statistics significant test to analyze our results, We discover that Wilcoxon
test is the most suited significance test for this particular task. Our
comparative analysis also provided insights into the different types of
questions as well - for instance, we conclude that this pipeline is not
suitable for yes/no question answering and more work needs to be done to
provide a predicted answer which is more closer to the ideal answer. Most
importantly, We worked on developing a modular designed code which was also
taught concept during class and will be beneficial in our future career, too.

##  11 Future Work/Extensions

There are a few directions we think are important to pursue in future. First
is to improve the ranker module with additional ranker pipelines. Fusion based
approaches could be useful to apply on this task and see the results which can
be provided by the late fusion approach on not only the final sentence tiling
output but to the output of the ranker module as well. Moreover, including
word representation like word2vec Mikolov et al. (2013) or Glove vector
Pennington et al. (2014) as the additional feature is also a direction that we
will try in the future. Furthermore, yes no questions needs to be addressed
differently using methods where one can convert the question into a assertion
statement and view the output differences between the ideal answer and
predicted answer. One possible solution is to train a binary classifier, whose
inputs are the question along with the predicted summary, while the output is
Yes/No. With the development of recurrent neural network Wu et al. (2016);
Arora et al. (2016), we are looking forward to exploring this pipeline in the
future.

##  12 Summary

We designed an end-to-end pipeline improving upon a reference implementation
of the BioASQ pipeline. Our experiments were focussed towards improving the
feature extractor part of the pipeline and improving the understanding of
overall pipeline. We obtained a significant result conclusion such as range of
k value which is statistically significant. Our results provided insights into
using wilcoxon test for significance testing in this task. Further, we
developed and analyzed exact answer based accuracy metric to evaluate
performance of our pipeline. We recommend future directions for using our work
to develop better systems on BioASQ challenge tasks and draw conclusions from
the question answering task.

## References

  * Achananuparp et al. (2008) Palakorn Achananuparp, Xiaohua Hu, and Xiajiong Shen. 2008.  The evaluation of sentence similarity measures.  volume 5182, pages 305–316.
  * Albertsson et al. (2016) Sarah Albertsson, Evelina Rennes, and Arne Jonsson. 2016.  Similarity-based alignment of monolingual corpora for text simplification purposes.  In Proceedings of the Workshop on Computational Linguistics for Linguistic Complexity (CL4LC). The COLING 2016 Organizing Committee, pages 154–163.  http://aclweb.org/anthology/W16-4118.
  * Arora et al. (2016) Sanjeev Arora, Yingyu Liang, and Tengyu Ma. 2016.  A simple but tough-to-beat baseline for sentence embeddings .
  * Carbonell and Goldstein (1998) Jaime Carbonell and Jade Goldstein. 1998.  The use of mmr, diversity-based reranking for reordering documents and producing summaries.  In Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval. ACM, pages 335–336.
  * Chandu et al. (2017) Khyathi Chandu, Aakanksha Naik, Aditya Chandrasekar, Zi Yang, Niloy Gupta, and Eric Nyberg. 2017.  Tackling biomedical text summarization: Oaqa at bioasq 5b.  BioNLP 2017 pages 58–66.
  * Chen and Manning (2014) Danqi Chen and Christopher D Manning. 2014.  A fast and accurate dependency parser using neural networks.  In Empirical Methods in Natural Language Processing (EMNLP).
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long short-term memory.  Neural computation 9(8):1735–1780.
  * Kobayakawa et al. (2009) Michihiro Kobayakawa, Shigenao Kinjo, Mamoru Hoshi, Tadashi Ohmori, and Atsushi Yamamoto. 2009.  Fast computation of similarity based on jaccard coefficient for composition-based image retrieval.  In Proceedings of the 10th Pacific Rim Conference on Multimedia: Advances in Multimedia Information Processing. Springer-Verlag, Berlin, Heidelberg, PCM ’09, pages 949–955.
  * Lin (2004) Chin-Yew Lin. 2004.  Rouge: A package for automatic evaluation of summaries.  page 10.
  * 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.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher Manning. 2014.  Glove: Global vectors for word representation.  In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP). pages 1532–1543.
  * Sharma et al. (2018) Vasu Sharma, Nitish Kulkarni, Srividya Pranavi, Gabriel Bayomi, Eric Nyberg, and Teruko Mitamura. 2018.  Bioama: Towards an end to end biomedical question answering system.  In Proceedings of the BioNLP 2018 workshop. Association for Computational Linguistics, pages 109–117.  http://aclweb.org/anthology/W18-2312.
  * Wu et al. (2016) Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al. 2016.  Google’s neural machine translation system: Bridging the gap between human and machine translation.  arXiv preprint arXiv:1609.08144 .


# Game-Theoretic Model Based Resource Allocation During Floods

Rudrashis Majumder  Ph.D. Student, Department of Aerospace Engineering, Indian
Institute of Science, Bangalore<EMAIL_ADDRESS>Rakesh R Warier
Post-doctoral Fellow, Department of Aerospace Engineering, Indian Institute of
Science, Bangalore<EMAIL_ADDRESS>Debasish Ghose  Professor,
Department of Aerospace Engineering, Indian Institute of Science, Bangalore,
<EMAIL_ADDRESS>
###### Abstract

For multiple emergencies caused by natural disasters, it is crucial to
allocate resources equitably to each emergency location, especially when the
availability of resources is limited in quantity. This paper has developed a
multi-event crisis management system using a non-cooperative, complete
information, strategic form game model. In the proposed system, each emergency
event is assumed to occur in different locations simultaneously. These
locations are represented as the players in the game, competing with the other
players for an optimal allocation of scarce resources available at different
resource stations. The players incur a non-monetary cost for obtaining
resource units. The objective of the proposed game is to derive optimal
strategies for an effective and fair allocation of resources to the respective
players.

_Keywords:_ Disaster response; Resource allocation; Game theory; Non-
cooperative game; Nash equilibrium

##  1 Introduction

The efficient and quick response towards natural disasters involves a set of
activities that help in reducing the after-effect of the disasters. The
occurrence of floods causes casualties and infrastructure damage. Search and
rescue operations, evacuation of affected people, medical assistance,
providing food, pure water, and other essential materials are a few activities
that should start as soon as possible to minimize the damage caused by a
flood. Delayed and unplanned response by the disaster management authority
makes the situation worse for the inhabitants of the flood-affected area.

Various types of resources are required in the emergency sites to deal with
the circumstances caused by a flood. Faster rescue operations, food
distribution, medicine, etc., are critical requirements in flood-affected
areas. When more than one crisis occurs at different locations simultaneously
due to a natural disaster, each crisis location needs a specific type and
certain amount of resources in a time-overlapping manner. So, it is vital to
fairly allocate resource units to each crisis location, particularly when the
available resources are limited in quantity.

Game theory is concerned with the analysis of strategic relations between
rational agents and is functional in a variety of applications (Roger, 1991).
Pioneering findings of Von Neumann and Morgenstern (2007); Nash (1951) have
made game theory an irreplaceable tool for decision-making. Multiple
collaborators, including various government and non-government agencies,
private organizations, citizens, and others, must interact and coordinate for
achieving effective disaster response. Since disaster management consists of
strategic interactions of different decision-makers, game theory becomes a
viable option for modeling disaster response. Recent research in disaster
management indicates the growing use of game-theoretic models (Seaberg et al.,
2017). Gupta and Ranganathan (2006); Ranganathan et al. (2007); Gupta and
Ranganathan (2007); Wang et al. (2009) use a non-cooperative game model where
the game is played between crisis locations as each location aspires to have
the most resources possible. The authors consider a multi-event emergency
management system based on a strategic game where the cost matrix for the game
is computed based on the criticality of the events and the response time of
the resources to reach the crisis location. Ranganathan et al. (2007) refer to
social fairness as the metric for the utility model. Wang et al. (2009) use a
complete information game model, and the Nash equilibrium is attained by using
an improved Ant Colony optimization-based computational algorithm. A
sequential game proposed by Yang and Xu (2012) considers decision-makers and
emergency as two players. A dynamic game model with incomplete and complete
information is used in this paper. There is a substantial amount of research
work that addresses various problems related to flood-affected areas.
Balasubramaniam et al. (2019) addresses the objective of land-water boundary
identification based on information from LiDAR mounted on UAV. Shriwastav and
Ghose (2019) present an approach for detection of land-water boundaries using
UAV-acquired images of the area. Kashyap and Ghose (2019) present an approach
to reroute the resource traffic based on instantaneous inundation information
of the flooded region, and Ravichandran et al. (2019) present an approach for
detection and tracking of survivors in the flooded region by using UAV-based
information.

The difficulty of responding to several crises that occur at the same time by
allocating appropriate resources is examined in this study. A real-life
scenario has been converted into a non-cooperative game to find the optimal
solution to a resource allocation problem in a situation where resource
quantity is limited. The floods in the Indian state of Kerala in 2018, which
stranded thousands of people in several areas, inspired our research. It was
critical to allocate resources such as rescue helicopters, boats, relief
supplies, and medical assistance to different crisis regions. We analyze the
distribution of rescue helicopters as a non-cooperative game between crisis
areas and propose an equilibrium solution as an efficient resource
distribution method.

The paper models the problem of resource allocation with insufficient resource
units using a non-cooperative game. A novel aspect of the proposed approach
includes a strategy to select an equilibrium solution when there are multiple
Pure Strategy Nash equilibria (PSNE) of the game. Additionally, our choice of
the cost function can allocate the responsibility of conflict caused by
individual players by the demands they make on available resources.

The paper is organized as follows. Section 2 introduces the basic concepts of
game theory. The concept of equilibrium solution and two important criteria
useful for the selection of a particular equilibrium solution from a set of
equilibria are defined. The resource allocation game from a real-life scenario
is modeled here. The choice and decisions to be taken by the players are
explained in Section 3. In Section 4, we discuss the work and the findings
briefly. Section 5 gives the concluding remarks.

##  2 Game Formulation and Nash equilibrium

Game theory studies the strategic interaction between several rational and
intelligent decision-makers. In the case of non-cooperative games, players
will try to improve their utility or payoff (or reduce the cost incurred by
them) individually. Here, we use a non-cooperative strategic form game model.
These are also called matrix games, and we represent these types of games
through a payoff or cost matrix.

A strategic form game can be represented as $G=\left\langle
N,{(S_{i})}_{\forall i\in N},{(U_{i})}_{\forall i\in N}\right\rangle$ where

  1. (i)

$N=\\{1,2,...,n\\}$ is a set of players

  2. (ii)

$S_{1},S_{2},...,S_{n}$ are the strategy sets of the players
$i=\\{1,2,...,n\\}$ respectively

  3. (iii)

$U_{i}:S_{1}\times S_{2}\times...\times S_{n}\rightarrow\mathbb{R}$ for
$i={1,2,...,n}$ are the utility, or cost functions.

Given a strategic form game $G=\left\langle N,(S_{i}),(U_{i})\right\rangle$, a
strategy profile $s^{*}=({s_{1}}^{*},{s_{2}}^{*},...,{s_{n}}^{*})$ is called a
pure strategy Nash equilibrium (PSNE) of game $G$ if

$U_{i}({s_{i}}^{*},s_{-i})\leqslant U_{i}(s_{i},s_{-i}),\forall s_{i}\in
S_{i},\forall i\in N$ (1)

Actions of the players other than the $i$-th player are denoted as $s_{-i}$.

###  2.1 Payoff and Risk Dominance

A pure-strategy Nash equilibrium (PSNE) is an action profile such that no
single player can obtain a better incentive by deviating unilaterally from
this profile. If solving a game leads to multiple PSNEs, we have to choose one
PSNE out of the set for implementation. To find a unique PSNE, we leverage two
properties: payoff and risk dominance. The matrix below shows the cost
matrices for a two player-two strategy game. The row player P1 chooses between
rows $X$ and $Y$. Player P2 is the column player choosing columns $X$ and $Y$.

|  $X$ |  $Y$
---|---|---
$X$ |  $A,a$ |  $C,b$
$Y$ |  $B,c$ |  $D,d$

Assuming that the above game has two PSNE: $(X,X)$ and $(Y,Y)$, their
corresponding outcomes are $(A,a)$ and $(D,d)$. With $A\leqslant D$ and
$a\leqslant d$, and at least one strict equality, the PSNE $(X,X)$ is payoff
dominant (Harsanyi and Selten, 1988).

Now, if $(A-B)(a-b)\geqslant(D-C)(d-c)$ then $(X,X)$ is the risk dominant PSNE
with the outcome $(A,a)$ (Harsanyi and Selten, 1988). Otherwise $(Y,Y)$ is the
risk dominant solution. $(A-B)(a-b)$ and $(D-C)(d-c)$ are called the Nash
product, or the product of gains for unilateral deviations of the equilibrium
$(X,X)$ and $(Y,Y)$, respectively.

###  2.2 A Realistic Example

There was a devastating flood that occurred in Kerala during July-August 2018
(Mishra and Shah, 2018). The main reason behind this was unusually high
rainfall during the monsoon season. The rivers overflowed, and water was
released from the dams. Some districts in the hilly region were also paralyzed
by the repeated occurrence of landslides caused by floodwaters eroding the
landmass. Most parts of Kerala were under high alert for an extended period of
time. The rescue work was conducted by the Military, Army, Navy, NDRF, NDMA,
Coastal Guards, BSF, and many non-government volunteers. Nearly one million
people were evacuated from flood-affected areas to the relief camps. Army and
Navy used their helicopters for the rescue and relief operation in flood and
landslide affected areas. However, multiple disaster events co-occurring at
different locations made the resource allocation and other disaster responses
extremely difficult.

Figure 1: Crisis locations (red dots) and Resource stations (green dots)
(Image from Wikimedia commons)

As a case study of our framework, we consider a few districts of Kerala as the
players affected by the flood and landslides (for example, Alappuzha, Idukki,
Malappuram, and Wayanad). Here onwards, we will use the words “crisis
locations” and “players” synonymously. Alappuzha and Malappuram were affected
by the flood, while Idukki and Wayanad were affected mainly by landslides.
Primarily, Navy helicopters were used for rescue and relief operations.
Helicopters getting dispatched from different Naval basecamps for rescue
operations are considered as the resources for which the players or disaster
locations compete. We use the words “resource” and “helicopters” synonymously
in our discussion.

We consider two Naval Base stations Cochin (RS1) and Ezhimala (RS2), as the
resource stations in Kerala. However, as shown in Table 1, Arakkonam (RS3) in
Tamilnadu is the third resource station that will act as a backup and send
helicopters in case the resources are available in Kerala resource stations
RS1 and RS2 are not sufficient to meet the need of the players. We formulate
this problem as a noncooperative game and show that the solution to the game
leads to a fair allocation of resources.

Table 1: Resource stations (RS) Naval Base Stations in Kerala | Naval Base Stations in Tamilnadu
---|---
Cochin (RS1) in Ernakulam | Arakkonam (RS3)
Ezhimala (RS2) in Kannur |

The requirement of the helicopters for a particular crisis location is
calculated as a function of:

  1. 1.

Area of the crisis location, ( $A$ ).

  2. 2.

Criticality of the crisis location ($\rho$).

  3. 3.

Resources needed per unit area (sq. km) of the crisis location ($N$).

The number of helicopters needed for a particular crisis location is
calculated as the product $A\rho N$. In the crisis locations, we assume that
the number of helicopters required is equal to one per $400$ sq. km. The total
number of helicopters required for the players is calculated in Table 2.

Table 2: Computation of requirements of helicopters Crisis location/ Players |  Area (in sq. km.) |  Criticality factor |  Helicopters needed
---|---|---|---
P1: Alappuzha |  $1414$ |  $0.8$ |  $3$
P2: Idukki |  $4358$ |  $0.6$ |  $7$
P3: Malappuram |  $3550$ |  $0.75$ |  $7$
P4: Wayanad |  $2132$ |  $0.65$ |  $4$

The players Alappuzha and Idukki are closer to the resource station RS1
whereas players Malappuram and Wayanad are closer to the resource station RS2.
Table 3 shows the sorted order of distances of resource stations from the
players.

Table 3: Distances from the resource stations and Sorted order of distances Players |  Approx. distance from RS1 (in km) |  Approx. distance from RS2 (in km) |  Approx. distance from RS3 (in km) |  Sorted order of resource stations in terms of distance
---|---|---|---|---
P1 |  $70$ |  $375$ |  $650$ |  RS1 $<$ RS2 $<$ RS3
P2 |  $100$ |  $350$ |  $500$ |  RS1 $<$ RS2 $<$ RS3
P3 |  $186$ |  $150$ |  $560$ |  RS2 $<$ RS1 $<$ RS3
P4 |  $200$ |  $130$ |  $530$ |  RS2 $<$ RS1 $<$ RS3

However, the requirement of resources may not be satisfied from the nearest
resource stations. We assume that the number of helicopters available to the
resource stations is as given in Table 4.

Table 4: Availability of helicopters in the resource stations Naval Air Stations |  Units available
---|---
Cochin (RS1) |  $8$
Ezhimala (RS2) |  $9$
Arakkonam (RS3) |  $6$

From the availability of resources in the considered resource stations, we can
see a conflict situation in sharing the resources. From Table 5, we see that
the total requirement of the players exceeds the number of available resources
in RS1 and RS2. Since P1 and P2 are nearer to RS1, first, they will try to get
their needed resources from RS1. If the resources available to RS1 are not
sufficient for them, they will see the status in RS2. Since RS2 is already in
a resource-constraint situation (to serve P3 and P4), they will take RS3 as a
backup resource station. Similarly, P3 and P4 will first try to get their
resources from RS2 and then from RS3. As Table 5 shows, RS3 has adequate
resources to fulfill the deficiencies of the players.

Table 5: Conflict between total requirement and availability Players |  RS1 |  RS2 |  RS3
---|---|---|---
P1 |  $3$ |  $0$ |  $0$
P2 |  $7$ |  $0$ |  $0$
P3 |  $0$ |  $7$ |  $0$
P4 |  $0$ |  $4$ |  $0$
Total requirement |  $10$ |  $11$ |  $0$
Availability |  $8$ |  $9$ |  $6$

For effective disaster response, the players need a certain number of
helicopters. However, helicopters in the nearest resource stations are
insufficient to fulfill the requirement of both the players. In this
situation, P1 and P2 play a two-player game to divide resources available in
RS1 fairly. In the same way, P3 and P4 play a two-player game to divide
resources of RS2. A general cost function model is proposed for the players,
which calculates the cost or penalty charged for requesting several resource
units. The entries of the game matrices are derived from this cost function.
Each player has the intention to reduce the cost being charged on them for
their own choices. The Nash equilibrium of the game identifies an optimal
strategy for the players to choose.

####  2.2.1 Cost in terms of response time

Mostly Sea King helicopters from the Indian Navy were used for the rescue
operations, with an average speed of 210 km per hour. We can calculate the
time required for the helicopters to reach the crisis location from the
resource stations from this data. Table 6 gives the cost in terms of response
time. If the resource is coming from a nearer resource station, the response
time will be less. If the player is forced to bring resources from a distant
location, the response time will increase accordingly.

Table 6: Cost in terms of response time Players |  Resource Stations |  Distance (km) |  $\bf P_{t}(hr.)$
---|---|---|---
P1 |  RS1 |  $70$ |  $0.33$
P1 |  RS3 |  $650$ |  $3.1$
P2 |  RS1 |  $100$ |  $0.48$
P2 |  RS3 |  $500$ |  $2.4$
P3 |  RS2 |  $150$ |  $0.71$
P3 |  RS3 |  $560$ |  $2.67$
P4 |  RS2 |  $135$ |  $0.64$
P4 |  RS3 |  $530$ |  $2.52$

####  2.2.2 Cost in terms of fuel consumption

For Sea King Helicopters, 3700 liters of fuel gives a range of 1500 km. Thus
fuel consumption rate is approximately 0.0025 kilolitre/km. Table 7 shows the
fuel consumption amount for bringing just one helicopter from the respective
resource locations.

Table 7: Cost in terms of fuel consumption Player |  Resource stations |  Distance (in km.) |  $\bf P_{c}(kilolitre)$
---|---|---|---
P1 |  RS1 |  $70$ |  $0.175$
P1 |  RS3 |  $650$ |  $1.625$
P2 |  RS1 |  $100$ |  $0.250$
P2 |  RS3 |  $500$ |  $1.250$
P3 |  RS2 |  $150$ |  $0.375$
P3 |  RS3 |  $560$ |  $1.4$
P4 |  RS2 |  $135$ |  $0.3375$
P4 |  RS3 |  $530$ |  $1.325$

####  2.2.3 Penalty based on their mutual actions

Players will always try to take the maximum possible resources from the
nearest resource stations. However, since this may demand more than the number
of available resources, another penalty is charged on the players so that they
are not inclined to take all their required resources from the nearest
resource station. For a two-player game, (2) and (3) gives this penalty for P1
and P2.

$\displaystyle P_{l_{1}}=$
$\displaystyle~{}f(A_{1},d_{1},d_{2})\bigg{[}\frac{n_{1}-d_{1}}{n_{1}}\bigg{]}+\frac{n_{1}-d_{1}}{n_{1}}+\frac{n_{2}-(A_{1}-d_{1})}{n_{2}}+g(A_{1},d_{1},d_{2})\bigg{[}\frac{\frac{d_{1}}{n_{1}}}{\frac{d_{1}}{n_{1}}+\frac{d_{2}}{n_{2}}}\bigg{]}$
(2) $\displaystyle P_{l_{2}}=$
$\displaystyle~{}f(A_{1},d_{1},d_{2})\bigg{[}\frac{n_{2}-d_{2}}{n_{2}}\bigg{]}+\frac{n_{2}-d_{2}}{n_{2}}+\frac{n_{1}-(A_{1}-d_{2})}{n_{1}}+g(A_{1},d_{1},d_{2})\bigg{[}\frac{\frac{d_{2}}{n_{2}}}{\frac{d_{1}}{n_{1}}+\frac{d_{2}}{n_{2}}}\bigg{]}$
(3)

where $f(.)$ and $g(.)$ functions are defined as follows:

$\displaystyle f(x,y,z)$ $\displaystyle=$
$\displaystyle\begin{cases}x-y-z&\text{\text{if }}(x-y-z)\geq 0\\\
0&\text{otherwise}\end{cases}$ (4) $\displaystyle g(x,y,z)$ $\displaystyle=$
$\displaystyle\begin{cases}y+z-x&\text{\text{if }}(x-y-z)\leq 0\\\
0&\text{otherwise}\end{cases}$ (5)

Here, $n_{1}$ and $n_{2}$ are number of resources needed by players P1 and P2,
respectively. $d_{1}$ and $d_{2}$ are number of resources requested by players
P1 and P2, respectively. The number of resources available to RS1 is denoted
by $A_{1}$.

In (2) and (3), the first term corresponds to the under-utilization by the
players, penalizing players when the total demand is less than the available
number of resources. This term is nonzero when the total number of resource
units requested by two players is less than the availability. The second term
corresponds to the dissatisfaction due to the player’s own choice. The second
term penalizes the player when the demand $d_{i}$ is less than $n_{i}$. The
third term indicates how much restriction one player puts on the other player.
The fourth term penalizes the conflict created by two players. This term
becomes nonzero if the total number of units requested by the players exceeds
the availability. The fourth term tries to allocate the responsibility of
conflict between players fairly.

For P3 and P4 in RS2, we get:

$\displaystyle P_{l_{3}}=$
$\displaystyle~{}f(A_{2},d_{3},d_{4})\bigg{[}\frac{n_{3}-d_{3}}{n_{3}}\bigg{]}+\frac{n_{3}-d_{3}}{n_{3}}+\frac{n_{4}-(A_{2}-d_{3})}{n_{4}}+g(A_{2},d_{3},d_{4})\bigg{[}\frac{\frac{d_{3}}{n_{3}}}{\frac{d_{3}}{n_{3}}+\frac{d_{4}}{n_{4}}}\bigg{]}$
(6) $\displaystyle P_{l_{4}}=$
$\displaystyle~{}f(A_{2},d_{3},d_{4})\bigg{[}\frac{n_{4}-d_{4}}{n_{4}}\bigg{]}+\frac{n_{4}-d_{4}}{n_{4}}+\frac{n_{3}-(A_{2}-d_{4})}{n_{3}}+g(A_{2},d_{3},d_{4})\bigg{[}\frac{\frac{d_{4}}{n_{4}}}{\frac{d_{3}}{n_{3}}+\frac{d_{4}}{n_{4}}}\bigg{]}$
(7)

where $f(.)$ and $g(.)$ functions are defined similarly as (4) and (5).

Here, $n_{3}$ and $n_{4}$ are the number of resources needed by players P3 and
P4, respectively. $d_{3}$ and $d_{4}$ are the number of resources requested by
P3 and P4, respectively. The number of resources available to RS2 is denoted
by $A_{2}$.

####  2.2.4 Total cost

The total cost incurred by the $i^{\text{th}}$ player is given as follows:

$P_{i}=\alpha_{t}P_{t_{i}}+\alpha_{c}P_{c_{i}}+\alpha_{l}P_{l_{i}}$ (8)

where, $\alpha_{t},\alpha_{c},\alpha_{l}$ are positive scalar values and
$\alpha_{t}+\alpha_{c}+\alpha_{l}=1$. The total cost gives the entries of the
payoff or cost matrices for all the players.

##  3 Choice and decisions

From the cost matrix, we calculate the Nash equilibrium for P1 and P2 in RS1
and for P3 and P4 in RS2. All the players will have the objective to reduce
the cost incurred on them.

Case 1: When $\alpha_{t}=0.05,\alpha_{c}=0.05,\alpha_{l}=0.9$, we get multiple
pure strategy Nash equilibria (Table 8).

Table 8: Nash Equilibrium for $\alpha_{t}=0.05,\alpha_{c}=0.05,\alpha_{l}=0.9$ NE at RS1 |  Costs on P1 and P2 |  NE at RS2 |  Costs on P3 and P4
---|---|---|---
$(1,7)$ |  $(0.92601,0.71131)$ |  $(5,4)$ |  $(0.62423,0.3531)$
$(2,6)$ |  $(0.68208,0.68512)$ |  $(6,3)$ |  $(0.6694,0.59476)$
$(3,5)$ |  $(0.30006,0.56369)$ |  $(7,2)$ |  $(0.61696,0.74119)$

All the solutions we obtain for this set of $\alpha$-values are obvious
solutions. Payoff and risk dominance defined in Section 2 helps us to choose a
unique PSNE as the intended solution. In the above case, (3, 5) is both payoff
and risk dominant solution for P1 and P2. However, in RS2, there is no payoff-
dominant solution. However, equilibrium (5, 4) is the risk-dominant solution.

The interpretation of the solution is that in RS1, the optimal strategy for P1
is to choose three units of helicopters, and the optimal strategy for P2 is to
choose five units of helicopters. This is the way to allocate all the eight
units of helicopters available in RS1 among P1 and P2. Similarly, in RS2, with
nine helicopters available, the optimal strategy for P3 is to choose five
units of helicopters, and the optimal strategy for P4 is to choose four units
of helicopters. RS3 being a backup resource station, will supply the
additional resources needed by the players. However, since it is far away from
the crisis locations, fair allocation of resources from the nearby resource
location is necessary for immediate initiation of disaster response.

Case 2: When $\alpha_{t}=0.2,\alpha_{c}=0.05,\alpha_{l}=0.75$, we get unique
PSNE (3, 5) in RS1 and two PSNE in RS2 (Table 9):

Table 9:  Nash Equilibrium for $\alpha_{t}=0.2,\alpha_{c}=0.05,\alpha_{l}=0.75$ NE at RS1 |  Costs on P1 and P2 |  NE at RS2 |  Costs on P3 and P4
---|---|---|---
$(3,5)$ |  $(0.3072,0.87798)$ |  $(5,4)$ |  $(0.98137,0.4031)$
|  |  $(7,2)$ |  $(0.64911,1.0448)$

In RS2, none of the equilibrium solutions is payoff dominant. However, (5, 4)
is the risk-dominant solution, and it risk-dominates (7, 2). We can interpret
these solutions in the same way as we have done in Case 1.

Case 3: When $\alpha_{t}=0.1,\alpha_{c}=0.25,\alpha_{l}=0.65$, we get unique
PSNE for both RS1 and RS2 (Table 10):

Table 10:  Nash Equilibrium for $\alpha_{t}=0.1,\alpha_{c}=0.25,\alpha_{l}=0.65$ NE at RS1 |  Costs on P1 and P2 |  NE at RS2 |  Costs on P3 and P4
---|---|---|---
$(3,5)$ |  $(0.3503,1.3613)$ |  $(5,4)$ |  $(1.6211,0.57262)$

##  4 Discussions

The example in Section 2 demonstrates how a game theory-based solution can be
used to solve a resource allocation problem in a resource-constrained
environment after a natural disaster. The game has been formulated to study
resource allocation after the Kerala flood in 2018. The crisis locations are
the players, and they incur some cost for availing resources. For different
values of the $\alpha$-set in (8), we get different pure strategy Nash
equilibria (PSNE). The Nash equilibrium is the best strategy for each player
when the other players take their best strategies. The PSNE can be interpreted
as the way of allocating resources fairly and optimally.

However, depending on the chosen values of the $\alpha$-set, sometimes
multiple Nash equilibria may come into the picture. In the case of a single
unique PSNE, the allocation of resources becomes straightforward. However, in
the case of multiple PSNE, selecting a single solution is taken based on
payoff dominance and risk dominance properties of the obtained equilibria. If
a particular PSNE payoff-dominates the others, we select it as the desirable
PSNE. If payoff dominance fails, the decision is taken based on risk
dominance.

The chosen $\alpha$-values give PSNE for all Case 1-3. However, if PSNE does
not exist, we can find mixed strategy Nash equilibria (MSNE) as it will always
exist (Nash, 1951). In the case of MSNE, the players choose their actions with
some probability, not deterministically. MSNE solutions tell how the resources
can be allocated to the crisis locations by imposing probabilistic notions.

##  5 Conclusions

In this paper, a game-theoretic solution for multi-event crisis management has
been proposed. This method identifies the crisis locations as the players. The
resources are available in a limited quantity; hence, one player’s choice
directly impacts the choices made by the other players. A non-cooperative game
is formulated between the concerned players for a socially fair distribution
of resources. The players compete for a near-optimal allocation of resource
units. The Nash equilibrium-based optimization is implemented in the game to
derive a desirable allocation of resources. The entire idea has been explained
using a practical example based on the recent Kerala flood in India. The
results produced in this paper show that, in a resource-constrained situation,
suitably designed game-theoretic algorithms can provide a potential and
efficient solution for resource allocation.

## Acknowledgement

This work is supported by an EPSRC-GCRF project ‘Emergency Flood Planning and
Management using Unmanned Aerial Systems’ through an international multi-
institutional grant. The authors would like to thank their colleagues in the
EPSRC-GCRF project partner institutes, University of Exeter, Indian Institute
of Science, Indraprastha Institute of Information Technology Delhi, University
of Cranfield, and the Tata Consultancy Services, for their help and
assistance.

## References

  * Balasubramaniam et al. (2019) Balasubramaniam S, Kashyap A, Shriwastav S, Majumder R, Abhinay NS, Ghose D (2019) Lidar based land-water boundary identification during floods. In: to appear in the Proceedings of 4th World Congress on Disaster Management
  * Gupta and Ranganathan (2006) Gupta U, Ranganathan N (2006) Social fairness in multi-emergency resource management. In: Technology and Society, 2006. ISTAS 2006. IEEE International Symposium on, pp 1–9
  * Gupta and Ranganathan (2007) Gupta U, Ranganathan N (2007) Multievent crisis management using noncooperative multistep games. IEEE Transactions on Computers 56(5):577–589
  * Harsanyi and Selten (1988) Harsanyi JC, Selten R (1988) A general theory of equilibrium selection in games, vol 1. The MIT Press
  * Kashyap and Ghose (2019) Kashyap A, Ghose D (2019) Planning of alternative street routes in urban areas during floods. In: to appear in the Proceedings of 4th World Congress on Disaster Management
  * Mishra and Shah (2018) Mishra V, Shah HL (2018) Hydroclimatological perspective of the kerala flood of 2018\. Journal of the Geological Society of India 92(5):645–650
  * Nash (1951) Nash J (1951) Non-cooperative games. Annals of mathematics pp 286–295
  * Ranganathan et al. (2007) Ranganathan N, Gupta U, Shetty R, Murugavel A (2007) An automated decision support system based on game theoretic optimization for emergency management in urban environments. Journal of Homeland Security and Emergency Management 4(2)
  * Ravichandran et al. (2019) Ravichandran R, Abhinay NS, Ghose D, Das K (2019) Searching for survivors in a flood scenario using uavs and ground based observers. In: to appear in the Proceedings of 4th World Congress on Disaster Management
  * Roger (1991) Roger BM (1991) Game theory: analysis of conflict. The President and Fellows of Harvard College, USA
  * Seaberg et al. (2017) Seaberg D, Devine L, Zhuang J (2017) A review of game theory applications in natural disaster management research. Natural Hazards 89(3):1461–1483
  * Shriwastav and Ghose (2019) Shriwastav S, Ghose D (2019) Detection and tracking of land-water boundary in flooded region using uav based images. In: to appear in the Proceedings of 4th World Congress on Disaster Management
  * Von Neumann and Morgenstern (2007) Von Neumann J, Morgenstern O (2007) Theory of games and economic behavior (commemorative edition). Princeton university press
  * Wang et al. (2009) Wang Z, Xu W, Yang J, Peng J (2009) A game theoretic approach for resource allocation based on ant colony optimization in emergency management. In: Information Engineering and Computer Science, 2009. ICIECS 2009. International Conference on, pp 1–4
  * Yang and Xu (2012) Yang JJ, Xu CH (2012) Emergency decision engineering model based on sequential games. Systems Engineering Procedia 5:276–282