# AskYourDB: An end-to-end system for querying and visualizing relational
databases using natural language

Manu Joseph  Applied Research, ThoucentricBangaloreIndia
<EMAIL_ADDRESS>,  Harsh Raj  Applied Research,
ThoucentricBangaloreIndia<EMAIL_ADDRESS>,  Anubhav Yadav  Applied
Research, ThoucentricBangaloreIndia and  Aaryamann Sharma  Applied Research,
ThoucentricBangaloreIndia<EMAIL_ADDRESS>
(2023)

###### Abstract.

Querying databases for the right information is a time consuming and error-
prone task and often requires experienced professionals for the job.
Furthermore, the user needs to have some prior knowledge about the database.
There have been various efforts to develop an intelligence which can help
business users to query databases directly. However, there has been some
successes, but very little in terms of testing and deploying those for real
world users. In this paper, we propose a semantic parsing approach to address
the challenge of converting complex natural language into SQL and institute a
product out of it. For this purpose, we modified state-of-the-art models, by
various pre and post processing steps which make the significant part when a
model is deployed in production. To make the product serviceable to businesses
we added an automatic visualization framework over the queried results.

NL2SQL, SQL, NLP, Machine Translation, Automatic Visualization

††copyright: acmcopyright††doi: xx.xxx/xxx_x††isbn:
978-1-4503-9517-5/23/03††conference: ACM SAC Conference; March 27 –April 2,
2023; Tallinn, Estonia††journalyear: 2023††article: 4††price: 15.00††ccs:
Computing methodologies Natural language processing††ccs: Information systems
Sentiment analysis††ccs: Computing methodologies Ensemble methods††ccs: Theory
of computation Unsupervised learning and clustering††ccs: Human-centered
computing Natural language interfaces††ccs: Human-centered computing
Visualization systems and tools††ccs: Human-centered computing Natural
language interfaces††ccs: Computing methodologies Machine translation

##  1\. Introduction

With the advancement in data storage and analysis technologies there has been
an exponential increase in the amount of data generated on the web. In 2020 it
was estimated that 2.5 quintillion bytes of data (qui, [n. d.]) was generated
everyday with 4.66 billion active Internet users worldwide (soc, [n. d.]).
This calls for efficient tools for parsing through the data for a sound
analysis. To improve accessibility, most of this data generated is stored in
databases of large companies. Various Relational Databases are developed for
this purpose, with SQL being widely used. But writing efficient SQL queries is
a task to learn and might be a hurdle for a person belonging to non-technical
domains.

Search analytics and AI-enabled solutions A self-service AI enabled analytics
can help business stakeholders to explore data, ask questions and obtain
answers to them in the same way as they would run a search on google. They
require users to have zero technical training and provide instant access to
information with the help of a search bar. These intelligent solutions can
access numerous datasets stored in databases, analyze huge volumes of data,
spot hidden trends and return personalized insights in a matter of few
seconds.

The first goal of the suggested effort is to close the communication gap
between technical and nontechnical users or users not very well versed in
writing efficient codes to query large databases using SQL. In other words,
facilitating computer-human connection without any programming experience.
Similarly, the second goal is to understand and visualize the dynamics of the
data being stored in large databases. This is a tough challenge due to the
vastness of the data and the complexity of the queries. It is just not
possible for nontechnical users to comprehend the visualizations of the data
in large databases using SQL. However, using the proposed solution described
below, it is possible to overcome these problems.

The solution proposed is to use a natural language processing (NLP) based
method to automatically generate SQL queries from the questions asked in plain
English. The results obtained after parsing the generated SQL query are then
sent through an automatic visualization pipeline. This advances the product
towards a sophisticated tool for AI driven large database analytics.

The major contributions of this paper are:

  1. (1)

An end-to-end system which goes from natural language queries to retrieved
data and automatically generated visualization

  2. (2)

A pre-processing system to maximize the effectiveness of the trained model.

  3. (3)

A robust post-processing system which provides guard-rails to the model-
generated SQL queries and make it useful

  4. (4)

An interactive visualization system which starts with automatically generated
visualizations and then allow the user to change them as necessary.

##  2\. Related Work

####  2.0.1. Natural Language to SQL Translation

There has been previous work in text-to-SQL systems ranging from rule-based
systems to more advanced and accurate techniques involving state-of-the-art
algorithms. Prior works like TableQA (Sun et al., 2020) uses a combination of
deep learning-enabled entity extractor and aggregate clause classifier to
build the SQL query. The entity extractor matches the conditions by mapping
the columns with their respective values if there are any in the question. It
uses a pre-trained question answering model trained on SQuAD (Rajpurkar et
al., 2016) to help easily locate the column’s value from the input question.
This has an advantage in the usage of heuristics, since the heuristics can be
modified in order to improve performance on the solution in most cases without
having to re-train the deep learning model. But as the natural language gets
more complex, more errors occur in the retrieval of information from the
table.

With the advent of Transformer (Vaswani et al., 2017) architectures there has
been a rapid growth in sequence to sequence (Yousuf et al., 2020) modelling
which is the motivation for text-to-SQL systems. To build such systems it
needs to have a joint reasoning of the Natural Language utterances and the
structured database schema information. These systems can be recognized as a
type of domain-specific semantic parsers.

There is a class of methods where querying tabular data is done without
generating logical forms and targets to get the answer to the question
directly from the model. One such method is TAPAS (Herzig et al., 2020), which
extends the Masked Language Modeling (MLM) approach to structured data. Like
BERT (Devlin et al., 2018), TAPAS (Herzig et al., 2020) uses features which
have to encode the tabular input. It then initializes a joint pre-training of
text sequences and tables trained end to end and is successfully able to
restore masked words and table cells. It can infer from a query by selecting a
subset of table cells. If available, aggregate operations are also performed
on top of them. However, it comes with concerns over memory issues and
expensive compute requirements because the entire table has to be fed in as
context.

The other paradigm uses an intermediate logical representation (like SQL) to
go from natural language queries to its corresponding logical forms and then
use the logical form to query the answer. Recent work (Guo et al., 2019; Wang
et al., 2019; Bogin et al., 2019) shows that using powerful pre-trained
language models can further improve these highly specific parsers, even though
these language models are trained for pure text encoding.

There are several datasets for evaluation systems like WIKISQL (Zhong et al.,
2017) which has a significantly large number of SQL queries and tables. But
all SQL queries are simple, and each database is only a simple table without
any foreign key. More such datasets include ATIS (Dahl et al., 1994), Geo
(Zelle and Mooney, 1996), Academic (Li and Jagadish, 2014) but each of them
contains only a single database with a limited number of SQL queries, and has
exact same SQL queries in train and test splits. Recently released SPIDER
dataset spans the largest range in types of queries. It is comparatively
complex and cross-domain offering a critical model evaluation towards
generalizability.

The recent state-of-the-art models evaluated on Spider use various attentional
architectures for question/schema encoding and AST-based structural
architectures for query decoding. IRNet (Guo et al., 2019) encodes the
question and schema separately with Long Short Term Memory (LSTM) (Hochreiter
and Schmidhuber, 1997) and self-attention respectively. Abstract Syntax Tree
(AST) based decoder as described in (Yin and Neubig, 2017) is further used to
decode a query in an intermediate representation (IR) that exhibits higher-
level abstractions than SQL. Previous works has used several encoding schemes
including GNN in (Bogin et al., 2019). These works emphasize schema encoding
and schema linking, but design separate featurization techniques to augment
word vectors (as opposed to relations between words and columns) to resolve
it. Moreover, RAT-SQL (Wang et al., 2019) framework jointly encodes pre-
existing relational structure in the input as well as induced “soft” relations
between sequence elements in the same embedding.

The current state-of-the-art on SPIDER (Yu et al., 2018) dataset are PICARD
(Scholak et al., 2021) and SADGA (Cai et al., 2021). SADGA is built on
pretrained GAP (Shi et al., 2020) model which is in turn a modification of
RAT-SQL (Wang et al., 2019) framework. While PICARD (Scholak et al., 2021) is
a text-to-SQL semantic parser built upon pre-trained encoder-decoder models.
It constrains the decoder through SQL Abstract Syntax Tree (AST) to produce
valid SQL queries after fine-tuning the model on the text-to-SQL task.

####  2.0.2. Automatic Visualization

Automatic visualization is a widely researched topic in analytics, but
introducing robust and efficient automation has always been a hurdle for
researchers. This is hard, if not impossible, since among numerous issues, no
consensus has emerged to quantify the goodness of a visualization that
captures human perception.

Efforts to produce automatic visualization tools started with building semi-
automatic tools with minimal human-interactions such as SAGE (Roth et al.,
1995) and BDVR (Gotz and Wen, 2009). Text-to-Viz (Cui et al., 2019) and
Click2Annotate (Chen et al., 2010) are designed for no-human interaction and
efficiently recommend visualizations. Tools built on rule-based algorithms are
prone to errors, but with the success of machine learning reliable systems are
possible. With proper combination of machine learning, visual elements and
user defined rules (Chen et al., 2019) developed automated infographics.

Turning the visuals into vector representations is the foremost challenge in
efficient usage of machine learning techniques. (Wang et al., 2020) listed
some challenges of using machine learning in automatic visualization setup. It
concluded that it is difficult and error-prone to organize visual’s
characteristics into unique vectors. However, Deepeye (Luo et al., 2018) led
improvements to standardize featurization process. It produces representations
which are simple yet effective to drive machine learning algorithms. It uses
these features to learn to rank from a pool various probable visualization a
dataset can produce. Recent techniques also try to model automatic
visualization as a recommendation system (Lin et al., 2020). The problem
objective of ranking task is simpler than building a recommendation system
whose data collection is difficult. Additionally, recommendation systems
perform best with online learning which is difficult to deploy.

##  3\. Solution Overview

We have designed an end-to-end system (Figure: 1) using state-of-the-art
methods in processing natural language to SQL and automated visualization to
develop a user-ready product. The key differentiating factor of our approach
is the ability to translate business queries into data and visualizations
automatically.

Figure 1. End-to-end System

State-of-the-art systems for translating natural language to SQL are still not
usable out-of-the-box. They still need quite a bit of hand holding by ways of
pre-processing the inputs and post-processing the outputs to have better user
experience and reliability. The business usability of the product is also
enhanced with the Automatic Visualization tool built to analyze the results
extracted from the database. The product is an integrated solution that can be
easily deployed by businesses without the need for additional training or
support. The search and query algorithms are optimized for easy scalability to
businesses working with large databases. The product is deployed with a simple
yet sophisticated interface for the users and it is an easily accessible
solution that can be used by businesses, marketing firms, and data scientists
to perform rapid market study, analysis, and real time querying the database
with just a few lines of Language.

The product is composed of the following three modules:

1\. Natural Language to SQL Translation

2\. Automatic Visualization

3\. User Interface Module

The first module is responsible for connecting the user uploaded database and
the Natural Language query to the Machine Learning pipeline. The deployed
model then produces the resulting SQL code and the answer with a simple
parsing of the database. The next module deals with analyzing the result using
autonomous visualization techniques. The visualization method stands out
because of its ability to automatically detect the type of data and
relationship between different attributes. This module also detects the
outliers and produces visualizations accordingly with an intelligence built to
rank various possible types of visuals (like graphs and charts) based on
insightfulness. The User Interface Module is the last module which takes care
of providing an interface to the user which is both simple and sophisticated
at the same time. It is designed keeping in mind the user experience and
business needs. The user interface is interactive and allows the user to
perform various tasks such as uploading database, querying the database, and
visualizing the results.

###  3.1. Natural Language to SQL Translation

In our experiments we used variants of SADGA (Cai et al., 2021) model and
experimented it variants – SADGA + Glove, SADGA + Bert-large and SADGA + GAP.
As reported in their paper and observed from our experiments we concluded that
SADGA + GAP has the highest accuracy in producing correct SQL queries. SADGA
(Cai et al., 2021) adopt the graph structure to provide a unified encoding
model for both the natural language question and database schema. Based on the
proposed unified modelling, SADGA (Cai et al., 2021) devise a structure-aware
aggregation method to learn the mapping between the question-graph and schema-
graph. The structure-aware aggregation method is featured with Global Graph
Linking, Local Graph Linking, and Dual-Graph Aggregation Mechanism. To
initialize the input embedding of question words and tables/column, the
authors use pre-trained embedding techniques. Glove (Pennington et al., 2014)
is a common choice for embedding initialization whereas BERT, a transformer-
based framework is a mainstream embedding initialization method. Moreover,
domain specific pre-trained models like GAP (Shi et al., 2020) is also applied
to take advantage of the prior text-to-SQL knowledge. GAP (Shi et al., 2020)
is a model pre-training framework that jointly learns representations of
natural language utterances and table schemas. It is trained on 2M utterance-
schema pairs and 30K utterance-schema-SQL triples, whose utterances are
produced by generative models. SADGA +GAP achieved 2nd place on the
challenging Text-to-SQL benchmark SPIDER (Yu et al., 2018) at the time of
writing. However, variants of PICARD (Scholak et al., 2021) model is on the
top of the SPIDER (Yu et al., 2018) benchmark we didn’t use it for our case
because in comparison to models like SADGA (Cai et al., 2021) and GAP (Shi et
al., 2020) it is difficult to setup and is heavier to run inference, also it
does not add much accuracy improvements w.r.t. the requirements it adds up.

After comparative study and evaluation, we found that our chosen model – SADGA
+ GAP (Shi et al., 2020) is competitive on industry standards queries and
databases. We probed the model on various complex queries and databases which
use a mix of various operators like JOIN, ORDER BY, GROUP BY, etc. Overall,
the models performed well on most of the queries but failing on more advanced
types of queries like the one using Window functions. We chose SADGA (Shi et
al., 2020) with a GAP (Shi et al., 2020) backbone because not only was the
accuracy higher, but also it generated more succinct SQL queries.

###  3.2. Pre Processing

The underlying LLM-based model which translates English queries to SQL
queries, while being state-of-the-art, still has some rough edges which makes
it difficult to use it in an application without some guardrails. We have
designed a pre-processing pipeline (Figure 2) that smooths out the rough
edges. These pre-processing steps is strictly related to the initial on-
boarding of a dataset and is a one-time activity.

Figure 2. Pre-Processing Work Flow

####  3.2.1. Enforce English Schema

We rely on large language models (LLM) as a backbone to derive semantic
relationships between the query and the schema and construct a SQL query. And
the LLM’s are typically trained in English. Therefore, it is important for the
SQL schema to be as close to English as possible. Our experiments also
confirmed the fact that SQL schema being close to English and having
meaningful column names drastically impact the accuracy of the conversion. We
ensure that any dataset that is on-boarded into the system has plain English
column names and those column names rightly represent the content of those
columns. For instance, a SQL table of invoices has a column called, _PCs_
which denote the number of items ordered. Our pre-processing would change it
to _quantity_ so that the column name rightly represents the content of the
column. This is conceived as a manual process which needs to be done once on
on-boarding a new database into the system.

####  3.2.2. Boost Semantic Meaning using Synonyms

Although the LLM based approach try to capture semantically similar words, we
found that concatenating meaningful synonyms to a column name increases the
accuracy of the underlying model. For instance, if we have a column named
heading, we can add title, and headline to the column name so that the new
column name is _heading_title_headline_. But before introducing such synonyms
we should also make sure the newly introduced terms do not create ambiguity
with other columns in the database. This is another manual process where the
data scientists can inject specific domain knowledge into the system.

####  3.2.3. Removing Punctuation and Spaces Cleaning the Schema entries

When there is spaces between column name or table name our model consider it
as part of string and will produce SQL query in which table/column name will
be as it is (with spaces). And without sufficient safeguards, this will cause
syntax errors in SQL execution. For instance, if the column name is _toss
winner_ , the resulting query would have SELECT match.toss winner from match
which would throw a syntax error. Therefore, to avoid such problems, we
replace the spaces with underscores and remove all the punctuation to get
SELECT match.toss_winner from match

####  3.2.4. Special Processing of Datetime Columns

Many databases having datetime information as a timestamp or date. But when
the user queries something like _what is the total revenue in year 2020_ , the
model will struggle to extract the meaning out of randomly formatted datetime
column and add the right filter to select the year 2020. During the database
on-boarding, our system asks the user about datetime columns and the format in
which the datetime is represented. And using this information, the system
generates different columns for the day, month, year and so on. If the date
column is named _invoice_date_ , these additional columns would be named
_invoice_date_day_ , _invoice_date_month_ , _invoice_date_year_ , and so on.
To have more variety in the way we capture datetime information, we include
separate columns for month in short and long forms so that both Oct and
October are recognized equally well. In our experiments, this kind of
splitting of the datetime information led to much better responses regarding
dates.

####  3.2.5. Runtime Processing of queries for standardizing Datetime

In spite of the additional datetime columns we created in 3.2.4, it was
observed that when datetime or variations of date is present in in the natural
language query as is, the SADGA model can get confused and gives out erroneous
SQL queries. This can be because the model doesn’t have an inherent
understanding of time and the various ways humans talk about date and time.
For instance, humans can refer to time as an exact date (4th July), or at a
higher granularity (June, 2021), or in relative terms (last month). Therefore,
we have designed a preprocessing step to capture all such variations and
standardize them into a form the model understands. We use SUTime from
Stanford CoreNLP (Manning et al., 2014) to perform named entity recognition on
dates and subsequent conversion of dates into standard python format. Once we
have identified the dates, we replace them using one of the two formats:

If the datetime utterance in the query does not mention the specific date then
we replace it with _Month:¡Month¿, Year: ¡Year¿_

If the datetime utterance mentions a specific date, then we replace it with
the date in _yyyymmdd_ format.

###  3.3. Post Processing

The SQL query that the model generates still needs to be processed to make it
usable and explainable to the end user.

####  3.3.1. Terminal Word Disambiguation

To copy instances of text (like cell values) directly into the generated SQL
query the model needs to possess a copying mechanism. Despite a few like
finetuned T5 (Raffel et al., 2019), most of the current state-of-the-art
models are not trained to copy cell values from the text. By design the
authors of the chosen model have evaluated the model on Component Matching (Yu
et al., 2018) over Exact Match (Yu et al., 2018), thus the query contains
ambiguous word _Terminal_ as a placeholder for the actual cell value. For
instance, the natural language query _How many times have earthquakes occur in
Colorado?_ gets correctly translated into a valid SQL, but instead of
Colorado, the generated query has _Terminal_ Therefore, we have designed a
pipeline (Figure 3) which uses the schema information along with the natural
query to replace _Terminal_ words with the correct value.

Figure 3. Post-Processing Work Flow

From the generated SQL query, we first identify all the Terminal’s that we
need to replace. And for each terminal, we find out the corresponding column
it refers to. This is a trivial task using a SQL Parser (Albrecht, 2009)
111https://pypi.org/project/sqlparse/. Once we identify the column and the
table, we process the _Terminal_ string separately for each data type.

If the datatype is textual, we use a heuristic-based search to pick the right
word from the query to insert in place of _Terminal_. This is not trivial
because there are many possible causes of ambiguity. The user may not have
spelled the term correctly. The term that we are looking for can be a
combination of words instead of a single word.

  1. (1)

We start off by extracting the unique values from the column from the
database.

  2. (2)

Now both the user query and the extracted unique values go through a bit of
basic cleaning where we convert everything to lowercase and remove
punctuation.

  3. (3)

After the cleaning, we do a spell check based on edit distances between the
words in the user query and the words in the English dictionary and words in
the unique values extracted from that particular column.

  4. (4)

After the spell check, we generate unigrams and bigrams from the user query
and do a word matching search with the unique values in the extracted column.

  5. (5)

If we find a match, we replace the _Terminal_ with the matched value and if
not, we send a warning to the UI to urge the user to check the query again.

If the datatype of the column is numeric, we extract all the numbers from the
user query. We also pre-process the user query to convert any numbers which
are in the English form to numbers. For instance, if the user query is _show
me the number of customers who clicked on the ad at least two times_ we pre-
process it to make it _show me the number of customers who clicked on the ad
at least 2 times_. In cases where there are multiple numbers in the user query
and the multiple numeric _Terminal_ , the assignment becomes non-trivial.
After experimenting with multiple ways of resolving the ambiguity, we found
that the order in which the numbers appear in the user query will be the same
order in which the SQL query would be generated by the model. Therefore,
keeping that principle in mind, we assign the numeric values using the order
that it occurred in the user query.

If the datatype of the column is _datetime_ , we replace the terminal value
with date in a standard datetime format _yyyymmdd_. The datetime text
utterance is converted to the standard format through pre-processing (sec)

####  3.3.2. Simplified and User-Friendly Representation for SQL

In addition to the data we retrieve using the SQL query, we also wanted to
show the salient points from the SQL query in plain English without the syntax
of SQL. Instead of relying on heuristics based on string matching the raw SQL
query, we first used a SQL parser (Albrecht, 2009) which does syntax-aware
parsing of the SQL query into different tokens like DML, Whitespace,
Identifier, Keywords, Where, etc. And over these parsed tokens, we implemented
a heuristic to reduce the SQL query into something more simpler:

  1. (1)

Using the schema, we pick up all the table names which the query is addressing

  2. (2)

Conditions in the SQL query are extracted using the Where keyword

  3. (3)

If keywords like INTERSECT and UNION are present in the, we split the query in
two and use the same process to generate English representation for each part
and then join using intersect or union.

The whole system works to extract key information from the SQL query and
represent it in a format that is easy for a non-technical user to read and
understand. For instance the query - SELECT * from customers where
customers.region = ’INDIA’ – would be represented as Column(s): All Table(s):
customers, Filtered on: customers.region = ’INDIA’.

####  3.3.3. Automatic Visualization

We enable the user with an automatic visualization tool on top of the data the
SQL query fetches from the database. For this we have used an open-source
software, Deepeye (Luo et al., 2018) which organizes different visualization
charts and graphs into graph-based structure with a specific hierarchy based
on their rank. The query result is passed to the automatic visualization
pipeline based on Deepeye (Luo et al., 2018). The performance of machine
learning algorithms depends heavily on the choice of features. Using metrics
like correlation, ratio, etc, features are built on a given combination of
columns and visualization types. These features are represented in a graph
with each node representing a visualization. Now Deepeye (Luo et al., 2018)
ranks them based on their quality. Deepeye (Luo et al., 2018) uses a ranking
based model which is trained with a set of labeled data. Deepeye (Luo et al.,
2018) supports three types of ranking approaches -

  * •

Learning-to-rank: It is a supervised learning task that takes the input space
X as lists of feature vectors, and Y the output space consisting of grades (or
ranks). The goal is to learn a function $F(\textperiodcentered)$ from the
training examples, such that given two input vectors $x1$ and $x2$, it can
determine which one is better, $F(x1)$ or $F(x2)$.

  * •

Partial Order-based approach: it defines some partial orders which are used to
decide which visualization node is better. A graph based on the partial orders
is built, where each vertex is a visualization node and the directed edge
between two nodes are decided by the partial order. Finally, the graph is used
to compute a score for each visualization node based on topology sorting,
i.e., the smaller the topology order is, the larger the score is.

  * •

Diversified Ranking: it selects diversified top-k visualization nodes since
there may be many similar visualizations showing redundant information. For
example, $v1>v2$ and $v2>v3$ do not necessarily mean that $v1+v2>v1+v3$, since
$v1$ and $v2$ might be very “similar”. It mainly constructs a graph in which
nodes are visualizations, and weight of the edge between two nodes denotes the
distance between them. Then the graph is used to define relevance and
diversity measurement to calculate diversified top-k visualizations.

After some experiments with all the above type of techniques we found that
_Diversified Ranking_ is the most apt for this task as it is better in
producing visuals of varied range, hence useful for multi-purpose analytics.

One of the major challenges in automatic visualization is the ambiguity in the
user intent. There are many ways a particular data can be plotted and to
exactly specify what is in the user’s mind is typically challenging. Although
DeepEye (Luo et al., 2018) goes a long way towards making those decisions
automated, we still may have ambiguity. What each user wants is subjective to
his views and aesthetics. For instance, the query returned data of total
revenue per region for the last year. And suppose, DeepEye (Luo et al., 2018)
suggested a pie chart as the best visualization for this data. But what if the
user hates pie-charts and wants to view it as a bar chart? On the other hand,
if we ask the end-user to decide what visualization he wants to generate, it
will put unnecessary cognitive load on him as well. Therefore, we have taken a
hybrid approach, where we use DeepEye (Luo et al., 2018) to generate the most
likely visualization and then leave the control to the user where he can
either cycle between the different options suggested by DeepEye (Luo et al.,
2018) or even take matters into his own hands and select the kind of
visualization he wants.

####  3.3.4. User Interface Module

We have developed the user interface as a web application using Django
framework (Adrian Holovaty, 2013). There are a few databases pre-loaded, but
the user interface (UI) also enables the user to upload various data sources
in SQLite, _csv_ or _xlsx_ file formats (multi-table databases are only
supported in SQLite) through the Upload page. The upload process will also
carry out the sufficient pre-processing and tokenization of the schema to make
it ready for inference. Once the upload finishes, the user will get a
notification and the new database is ready to use.

The user can then head to the _Search_ page and select the dataset he wants to
analyse. Using a simple search box, we enable the user to ask questions in
English which is then relayed to the backend system which generates the right
SQL query for the English query by the user. This query is then used to
retrieve the data from the database. This data is displayed as a table in the
UI and along with it the automatically generated visualization is also
displayed to the user. The user can also choose between different
visualization options based on their preference. The user can then download
the results generated by the SQL query in form a downloadable _csv_ by
clicking on the download button next to the results. The user can also save
the visualizations generated by right clicking on charts and saving them to
their system. We are also saving all the user searches and the corresponding
queries in a cache so that we need not do model inferencing for queries which
the model has already generated the query for. The history of user searches is
also found in the _History_ page as well as in the side bar on the _Search_
page. The visual of the UI can be seen in Figure 4.

Figure 4. User Interface

###  3.4. Evaluation

Since a quantitative evaluation for the end-to-end system wasn’t possible, we
present key insights of both success and failure models in Table 1. Most of
the normal use-cases the system is able to handle and generate the right
queries.Misspelled queries (Jhonny instead of Johnny) are handled by the
system in a robust manner (Query 4 in Table 1)

Table 1. Sample Queries processed through the system QUERY |  SQL CODE |  COMMENTS
---|---|---
Which brand car has the most customers? |  SELECT Brands.brand_name FROM Dealer_Brand JOIN Brands ON Dealer_Brand.brand_id = Brands.brand_id GROUP BY Brands.brand_name ORDER BY Count(*) Desc LIMIT 1 |  The query is right
What are the email addresses of the customer whose first name is MARY? |  SELECT customer.email FROM customer WHERE customer.first_name = ’MARY’ |  The query is right
Name all movies starring Johnny Cage OR Name all movies starring Jhonny Cage |  SELECT film.title FROM actor JOIN film JOIN film_actor ON actor.actor_id = film_actor.actor_id AND film_actor.film_id = film.film_id AND actor.actor_id = film_actor.actor_id WHERE actor.first_name = ’JOHNNY’ |  Was able to identify Johnny even though misspelled, but wasn’t able to link ”Cage” to the last name in the schema
Give the top 2 places with maximum depth of earthquake |  SELECT quakes.place FROM quakes ORDER BY quakes.depth Desc LIMIT 1 |  Was able to generate the right query, but selected top 1 instead of 2
Which places had a positive longitude value? OR Which places in the western hemisphere? |  SELECT DISTINCT quakes.place FROM quakes WHERE quakes.longitude = ’Terminal’ |  The system does not have an understanding of complex concepts like positive (0) or western and eastern hemispheres
Which team won the most number of matches? |  SELECT matches.team1 FROM matches GROUP BY matches.team1 ORDER BY Count(*) Desc LIMIT 1 |  The query is right

###  3.5. Discussion and future work

####  3.5.1. Current Problems

For a reliable deployment of the SOTA Machine Learning techniques for SQL to
Natural Language translation it needs to be robust to wide range of advanced
SQL structures which currently the models are uncertain. We introduced various
pre- and post-processing steps to the system and added a human-computer
interface to not totally rely on the system and be free from unprecedented
failure. We also considered the business perspective of such systems and added
Automatic visualization techniques over it with a User Interactive Interface.
Below are few areas where the current systems lack -

  1. (1)

The system has some difficulty in completely picking up the required filtering
as evidenced by Query 4 in Table 1

  2. (2)

The model does have an affinity towards more popular use cases like Top 1,
even though the query mentioned Top 2 (Query 5 in Table 1. But these are
sporadic instances.

  3. (3)

For larger databases (with many tables and relationships) the system is not
effectively able to produce results, this might be because of question the
user is giving is difficult to understand as many synonyms can be used to for
the name of column or feature of database

  4. (4)

The system has no understanding of complex concepts as evidenced by Query 6 in
Table 1.

  5. (5)

It is not able to process advanced SQL queries such as those which contains
_Window functions_ like PARTITION BY, RANK and MERGE.

  6. (6)

The system is not constrained to produce efficient SQL codes for memory and
time complexity optimization.

  7. (7)

Time complexity of the terminal disambiguation is a challenge.

####  3.5.2. Possible Solutions and future work

Below are few possible possible solutions to the above issues and future work
directions -

  1. (1)

More robust models which can perform a wider variety of SQL operations
efficiently.

  2. (2)

Efficient copying mechanism in the query generation phase to generate terminal
values in an end-to-end fashion.

  3. (3)

Reducing the time complexity of Terminal Disambiguation.

## References

  * (1)
  * qui ([n. d.]) [n. d.].  Data never sleeps 5.0.  https://www.domo.com/learn/infographic/data-never-sleeps-5.  Accessed: 2022-10-16.
  * soc ([n. d.]) [n. d.].  Digital 2022: Global Overview Report.  https://datareportal.com/reports/digital-2022-global-overview-report.  Accessed: 2022-10-16.
  * Adrian Holovaty (2013) et al. Adrian Holovaty, Simon Willison. 2013\.  Django (Version 4.1.2).  https://www.djangoproject.com.
  * Albrecht (2009) Andi Albrecht. 2009\.  python-sqlparse v4.3.  https://github.com/andialbrecht/sqlparse.
  * Bogin et al. (2019) Ben Bogin, Matt Gardner, and Jonathan Berant. 2019.  Representing Schema Structure with Graph Neural Networks for Text-to-SQL Parsing.  https://doi.org/10.48550/ARXIV.1905.06241
  * Cai et al. (2021) Ruichu Cai, Jinjie Yuan, Boyan Xu, and Zhifeng Hao. 2021\.  SADGA: Structure-Aware Dual Graph Aggregation Network for Text-to-SQL.  https://doi.org/10.48550/ARXIV.2111.00653
  * Chen et al. (2010) Yang Chen, Scott Barlowe, and Jing Yang. 2010.  Click2Annotate: Automated Insight Externalization with rich semantics. In _2010 IEEE Symposium on Visual Analytics Science and Technology_. 155–162.  https://doi.org/10.1109/VAST.2010.5652885
  * Chen et al. (2019) Zhutian Chen, Yun Wang, Qianwen Wang, Yong Wang, and Huamin Qu. 2019.  Towards Automated Infographic Design: Deep Learning-based Auto-Extraction of Extensible Timeline.  _IEEE Transactions on Visualization and Computer Graphics_ (2019), 1–1.  https://doi.org/10.1109/tvcg.2019.2934810
  * Cui et al. (2019) Weiwei Cui, Xiaoyu Zhang, Yun Wang, He Huang, Bei Chen, Lei Fang, Haidong Zhang, Jian-Guan Lou, and Dongmei Zhang. 2019\.  Text-to-Viz: Automatic Generation of Infographics from Proportion-Related Natural Language Statements.  https://doi.org/10.48550/ARXIV.1907.09091
  * Dahl et al. (1994) Deborah A. Dahl, Madeleine Bates, Michael Brown, William Fisher, Kate Hunicke-Smith, David Pallett, Christine Pao, Alexander Rudnicky, and Elizabeth Shriberg. 1994.  Expanding the Scope of the ATIS Task: The ATIS-3 Corpus. In _Human Language Technology: Proceedings of a Workshop held at Plainsboro, New Jersey, March 8-11, 1994_.  https://aclanthology.org/H94-1010
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.  https://doi.org/10.48550/ARXIV.1810.04805
  * Gotz and Wen (2009) David Gotz and Zhen Wen. 2009.  Behavior-Driven Visualization Recommendation. In _Proceedings of the 14th International Conference on Intelligent User Interfaces_ _(IUI ’09)_. Association for Computing Machinery, New York, NY, USA, 315–324.  https://doi.org/10.1145/1502650.1502695
  * Guo et al. (2019) Jiaqi Guo, Zecheng Zhan, Yan Gao, Yan Xiao, Jian-Guang Lou, Ting Liu, and Dongmei Zhang. 2019.  Towards Complex Text-to-SQL in Cross-Domain Database with Intermediate Representation.  https://doi.org/10.48550/ARXIV.1905.08205
  * Herzig et al. (2020) Jonathan Herzig, Pawel Krzysztof Nowak, Thomas Müller, Francesco Piccinno, and Julian Eisenschlos. 2020.  TaPas: Weakly Supervised Table Parsing via Pre-training. In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_. Association for Computational Linguistics.  https://doi.org/10.18653/v1/2020.acl-main.398
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long Short-Term Memory.  _Neural Comput._ 9, 8 (nov 1997), 1735–1780.  https://doi.org/10.1162/neco.1997.9.8.1735
  * Li and Jagadish (2014) Fei Li and H. V. Jagadish. 2014.  Constructing an Interactive Natural Language Interface for Relational Databases.  _Proceedings of the VLDB Endowment_ 8, 1 (September 2014), 73–84.  http://dx.doi.org/10.14778/2735461.2735468
  * Lin et al. (2020) Halden Lin, Dominik Moritz, and Jeffrey Heer. 2020\.  Dziban: Balancing Agency & Automation in Visualization Design via Anchored Recommendations. In _Proceedings of the 2020 CHI Conference on Human Factors in Computing Systems_ _(CHI ’20)_. Association for Computing Machinery, New York, NY, USA, 1–12.  https://doi.org/10.1145/3313831.3376880
  * Luo et al. (2018) Yuyu Luo, Xuedi Qin, Nan Tang, and Guoliang Li. 2018\.  DeepEye: Towards Automatic Data Visualization. In _2018 IEEE 34th International Conference on Data Engineering (ICDE)_. 101–112.  https://doi.org/10.1109/ICDE.2018.00019
  * Manning et al. (2014) Christopher Manning, Mihai Surdeanu, John Bauer, Jenny Finkel, Steven Bethard, and David McClosky. 2014\.  The Stanford CoreNLP Natural Language Processing Toolkit. In _Proceedings of 52nd Annual Meeting of the Association for Computational Linguistics: System Demonstrations_. Association for Computational Linguistics, Baltimore, Maryland, 55–60.  https://doi.org/10.3115/v1/P14-5010
  * 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)_. Association for Computational Linguistics, Doha, Qatar, 1532–1543.  https://doi.org/10.3115/v1/D14-1162
  * Raffel et al. (2019) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2019.  Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer.  https://doi.org/10.48550/ARXIV.1910.10683
  * Rajpurkar et al. (2016) Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. 2016.  SQuAD: 100,000+ Questions for Machine Comprehension of Text. In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics, Austin, Texas, 2383–2392.  https://doi.org/10.18653/v1/D16-1264
  * Roth et al. (1995) Steven F. Roth, John Kolojejchick, Joe Mattis, and Mei C. Chuah. 1995.  SageTools: An Intelligent Environment for Sketching, Browsing, and Customizing Data-Graphics. In _Conference Companion on Human Factors in Computing Systems_ _(CHI ’95)_. Association for Computing Machinery, New York, NY, USA, 409–410.  https://doi.org/10.1145/223355.223751
  * Scholak et al. (2021) Torsten Scholak, Nathan Schucher, and Dzmitry Bahdanau. 2021\.  PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models.  https://doi.org/10.48550/ARXIV.2109.05093
  * Shi et al. (2020) Peng Shi, Patrick Ng, Zhiguo Wang, Henghui Zhu, Alexander Hanbo Li, Jun Wang, Cicero Nogueira dos Santos, and Bing Xiang. 2020.  Learning Contextual Representations for Semantic Parsing with Generation-Augmented Pre-Training.  https://doi.org/10.48550/ARXIV.2012.10309
  * Sun et al. (2020) Ningyuan Sun, Xuefeng Yang, and Yunfeng Liu. 2020.  TableQA: a Large-Scale Chinese Text-to-SQL Dataset for Table-Aware SQL Generation.  https://doi.org/10.48550/ARXIV.2006.06434
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017\.  Attention Is All You Need.  https://doi.org/10.48550/ARXIV.1706.03762
  * Wang et al. (2019) Bailin Wang, Richard Shin, Xiaodong Liu, Oleksandr Polozov, and Matthew Richardson. 2019.  RAT-SQL: Relation-Aware Schema Encoding and Linking for Text-to-SQL Parsers.  https://doi.org/10.48550/ARXIV.1911.04942
  * Wang et al. (2020) Yun Wang, Zhida Sun, Haidong Zhang, Weiwei Cui, Ke Xu, Xiaojuan Ma, and Dongmei Zhang. 2020.  DataShot: Automatic Generation of Fact Sheets from Tabular Data.  _IEEE Transactions on Visualization and Computer Graphics_ 26, 1 (2020), 895–905.  https://doi.org/10.1109/TVCG.2019.2934398
  * Yin and Neubig (2017) Pengcheng Yin and Graham Neubig. 2017.  A Syntactic Neural Model for General-Purpose Code Generation. In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_. Association for Computational Linguistics, Vancouver, Canada, 440–450.  https://doi.org/10.18653/v1/P17-1041
  * Yousuf et al. (2020) Hana Yousuf, Michael Gaid, Said Salloum, and Khaled Shaalan. 2020.  A Systematic Review on Sequence to Sequence Neural Network and its Models.  _International Journal of Electrical and Computer Engineering_ 11 (10 2020).  https://doi.org/10.11591/ijece.v11i3.pp2315-2326
  * Yu et al. (2018) Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingning Yao, Shanelle Roman, Zilin Zhang, and Dragomir Radev. 2018\.  Spider: A Large-Scale Human-Labeled Dataset for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Task.  https://doi.org/10.48550/ARXIV.1809.08887
  * Zelle and Mooney (1996) John M. Zelle and Raymond J. Mooney. 1996.  Learning to Parse Database Queries Using Inductive Logic Programming. In _Proceedings of the Thirteenth National Conference on Artificial Intelligence - Volume 2_ _(AAAI’96)_. AAAI Press, 1050–1055.
  * Zhong et al. (2017) Victor Zhong, Caiming Xiong, and Richard Socher. 2017\.  Seq2SQL: Generating Structured Queries from Natural Language using Reinforcement Learning.  https://doi.org/10.48550/ARXIV.1709.00103


# Security Investment Over Networks with Bounded Rational Agents: Analysis and
Distributed Algorithm

Jason Hughes and Juntao Chen The authors are with the Department of Computer
and Information Sciences, Fordham University, New York, NY, 10023 USA. E-mail:
<EMAIL_ADDRESS>
###### Abstract

This paper considers the security investment problem over a network in which
the resource owners aim to allocate their constrained security resources to
heterogeneous targets strategically. Investing in each target makes it less
vulnerable, and thus lowering its probability of a successful attack. However,
humans tend to perceive such probabilities inaccurately yielding bounded
rational behaviors; a phenomenon frequently observed in their decision-making
when facing uncertainties. We capture this human nature through the lens of
cumulative prospect theory and establish a behavioral resource allocation
framework to account for the human’s misperception in security investment. We
analyze how this misperception behavior affects the resource allocation plan
by comparing it with the accurate perception counterpart. The network can
become highly complex with a large number of participating agents. To this
end, we further develop a fully distributed algorithm to compute the
behavioral security investment strategy efficiently. Finally, we corroborate
our results and illustrate the impacts of human’s bounded rationality on the
resource allocation scheme using cases studies.

##  I Introduction

An efficient allocation of limited security resources to protect targeted
assets from malicious attacks is a critical problem faced by security
professionals. This problem becomes increasingly challenging as the modern
systems adopted in our society become more complex. For example, the societal
cyber-physical systems, such as industrial control systems and power grids,
consist of heterogeneous components including sensors, controllers, and
actuators, which are required to be jointly secured to achieve a desired
performance. Thus, it is important for the system operator to allocate the
available security resources strategically to enhance the holistic security.
Previous studies have investigated how a centralized system operator can
maximally reduce the vulnerability of assets from adversaries through security
investment [1, 2]. However, such a centralized paradigm, i.e., using a single-
source model, is insufficient to capture the emerging scenarios where multiple
resource owners111The resource owner also refers to the system
operator/planner, and they are used interchangeably in the paper. participate
in securing the targets collaboratively. To this end, this paper aims to
develop a framework and investigate the security investment problem over a
network with multiple sources (security resource investors) and a variety of
targets (valuable assets to be protected).

To develop an effective security investment scheme, it is necessary to
understand how the risks of targets change over the investment strategy. A
larger security investment amount will lower the probability of a successful
attack. However, human’s perception of such probabilistic events is
subjective, a commonly observed behavior when facing uncertainties.
Psychological studies have shown that humans often misperceive probabilities
on gains and losses by over-weighting low probabilities and under-weighting
high probabilities which lead to bounded rational behavior, a subject
receiving significant attention in prospect theory [3, 4]. Such behavioral
misperception plays an essential role in the focused security investment
problem where the resource owners need to evaluate the likelihood of
successful compromise of the targets under a given resource allocation scheme.
To this end, we incorporate this bounded rational consideration into our model
by developing a new behavioral decision-making framework for security
investment over networks. Under this paradigm, the resource owner perceives
the target having a relatively low chance of being compromised as more
vulnerable than it is, and a target with a high probability of being attacked
as less vulnerable than it is. We analyze the impact of attack success
misperception on the optimal resource allocation strategy and identify that
the bounded rational operator will prefer more to secure those targets with
higher values. In other words, the investors tend to pay more attention to
higher-valued assets as they become more behavioral, yielding a discriminative
distribution scheme comparing with the one without behavioral consideration.

Additionally, when more and more participating agents/nodes (resource owners
and targets) are introduced into the network, the computational complexity of
the resource allocation problem increases drastically [5]. Solving the
security investment problem with a massive number of networked sources and
targets in a centralized manner may be impractical or extremely
computationally expensive. In addition, the centralized approach requires the
planner to have complete information on the source and target agents,
including their utility parameters, supply and demand upper bounds, degree of
misperception on attack success, and value of targets. Thus, it does not
preserve a high level of privacy for participants. To this end, we propose a
distributed algorithm based on the alternating direction method of multipliers
(ADMM) [6], where the central resource transport planner is not needed and
each node solves its own simpler optimization problem and communicates its
decisions with the connected nodes in the network. Each pair of source and
target nodes will then negotiate to reach a consensus on how many security
resources should be transported. The proposed distributed algorithm converges
to the same optimal solution obtained under the centralized optimization
paradigm.

The contributions of this paper are summarized as follows:

  1. 1.

We develop a bounded rational security investment framework over a network.
The model captures the decision-makers’ misperception of security resources’
effectiveness on protecting the targets, and it facilitates the analysis of
behavioral impacts on the resource allocation plan.

  2. 2.

We discover a sequential water-filling nature of the optimal security resource
allocation over the targets and identify that the transport planners become
more discriminative by investing in a smaller set of higher-valued targets as
they tend to be more behavioral.

  3. 3.

We further develop a distributed algorithm based on ADMM to compute the
optimal resource investment strategy for large-scale networks. We also
corroborate our algorithm and analytical results using case studies.

Related Works: Optimal security investment for defending assets has been
studied extensively in literature [7, 8, 9, 10]. Previous studies have also
considered the behavioral impacts on security investment. For example, the
authors in [11] have studied the interplay between the strategic defender and
the bounded rational adversary through a game-theoretic framework. [12] has
investigated the optimal investment strategies under a misperceived security
risk model based on prospect theory, in which the authors have focused on a
single decision maker investing on heterogeneous assets. Our work pays
attention to the resource transport in a multi-source multi-target framework.
Prospect theory has also been used to guide the optimal resource
allocation/decision-making in various applications, including water
infrastructures [13], communication networks [14], and the Internet of things
[15]. Our work is also related to the decision-making of resource allocation
over large-scale networks, in which efficient algorithms for computing the
optimal schemes have been proposed in different contexts, including in
consideration of efficiency [5, 16], fairness [17], and security and
resiliency [18, 19].

The rest of this paper is organized as follows. In Section II, we formulate
the security investment problem over a network that considers human
misperception on attack success rate. We characterize the optimal security
investment strategy and analyze how the behavioral consideration affects such
solutions in Sections III and IV. We further develop a distributed algorithm
to compute the behavioral security investment strategy in Section V and
corroborate our findings in Section VI.

##  II Problem Formulation

In this section, we establish a framework for security investment over a
network with behavioral participants.

###  II-A Security Resource Transport Network

In a network, we denote by $\mathcal{X}:=\\{1,...,|\mathcal{X}|\\}$ the set of
destinations/targets that receive the security resources, and
$\mathcal{Y}:=\\{1,...,|\mathcal{Y}|\\}$ the set of origins/sources that
distribute security resources to the targets. Specifically, each source node
$y\in\mathcal{Y}$ is connected to a number of target nodes denoted by
$\mathcal{X}_{y}$, representing that $y$ has choices in allocating its
resources to a specific group of destinations $\mathcal{X}_{y}$ in the
network. Similarly, it is possible that each target node $x\in\mathcal{X}$
receives resources from multiple source nodes, and this set of suppliers to
node $x$ is denoted by $\mathcal{Y}_{x}$. Note that $\mathcal{X}_{y}$,
$\forall y$ and $\mathcal{Y}_{x}$, $\forall x$ are nonempty. It is
straightforward to see that the security resources are transported over a
bipartite network, where one side of the network consists of all source nodes
and the other includes all destination nodes. This bipartite graph may not be
complete due to constrained matching policies between participants. For
convenience, we denote by $\mathcal{E}$ the set including all feasible
transport paths in the network, i.e.,
$\mathcal{E}:=\\{(x,y)|x\in\mathcal{X}_{y},y\in\mathcal{Y}\\}$. Note that
$\mathcal{E}$ also refers to the set of all edges in the established bipartite
graph for security resource transportation.

We next denote by $\pi_{xy}\in\mathbb{R}_{+}$ the amount of security resources
transported from the origin node $y\in\mathcal{Y}$ to the destination node
$x\in\mathcal{X}$, where $\mathbb{R}_{+}$ is the set of nonnegative real
numbers. Let $\Pi:=\\{\pi_{xy}\\}_{x\in\mathcal{X}_{y},y\in\mathcal{Y}}$ be
the designed resource transport plan. Furthermore, the security resources at
each source node $y\in\mathcal{Y}$ is upper bounded by
$\bar{q}_{y}\in\mathbb{R}_{+}$, i.e.,
$\sum_{x\in\mathcal{X}_{y}}\pi_{xy}\leq\bar{q}_{y}$.

###  II-B Bounded Rational Security Investment

Each target node in the network faces threats and could be compromised by an
attacker. If target node $x\in\mathcal{X}$ is attacked, the induced loss is
$U_{x}>0$. The attacker’s probability of successfully compromising the target
node is related to the amount of security resources received. For each target
node $x\in\mathcal{X}$, defined by
$p_{x}:\mathbb{R}_{+}^{|\mathcal{Y}_{x}|}\rightarrow[0,1]$ a function that
maps the received security resources $\Pi_{x}$ to a successful attack
probability. It is natural to see that such probability should be related to
the aggregated resource received by node $x$ captured by
$\sum_{y\in\mathcal{Y}_{x}}\pi_{xy}$. Thus, with a slightly abuse of notation,
$p_{x}(\Pi_{x})$ can be expressed by
$p_{x}(\sum_{y\in\mathcal{Y}_{x}}\pi_{xy})$, where the later one shows more
explicitly the relationship between the successful attack probability and the
total received resources at node $x\in\mathcal{X}$.

Each target node $x\in\mathcal{X}$ minimizes its cost $U_{x}p_{x}(\Pi_{x})$.
To this end, the central planner aims to minimize the following aggregated
loss $L(\Pi)$ at all targets under attacks:

$L(\Pi)=\sum_{x\in\mathcal{X}}U_{x}p_{x}(\Pi_{x}).$ (1)

It has been shown that humans tend to misperceive probabilities by over-
weighing low probabilities and under-weighing high probabilities during
decision-making under uncertainties. For a true probability $p\in[0,1]$,
humans will perceive it as $w(p)\in[0,1]$, where $w$ is a probability
weighting function. One such commonly used weighting function is given by [20]

$w(p)=\exp({-(-\log(p))^{\gamma}}),\ p\in[0,1],$ (2)

where $\gamma\in(0,1]$ is a parameter capturing the degree of misperception.
When $\gamma$ is closer to 0, it leads to a larger distortion of the
probability function $p$. In comparison, when $\gamma=1$, $w(p)=p$, indicating
there is no probability misperception.

Under the perceived probability, the target node $x$’s cost function becomes
$U_{x}w\left(p_{x}(\Pi_{x})\right)$. Thus, the cost function for the transport
planner under the perceived attack probability is

$\tilde{L}(\Pi)=\sum_{x\in\mathcal{X}}U_{x}w(p_{x}(\Pi_{x})).$ (3)

The security resource allocation strategies with bounded rational behavioral
consideration can be obtained by solving the following optimization problem:

$\displaystyle\mathrm{(OP-A):}\quad\min_{\Pi}$
$\displaystyle\sum_{x\in\mathcal{X}}U_{x}w(p_{x}(\Pi_{x}))$ (4)
$\displaystyle\mathrm{s.t.}$ $\displaystyle
0\leq\sum_{x\in\mathcal{X}_{y}}\pi_{xy}\leq\bar{q}_{y},\ \forall
y\in\mathcal{Y},$ $\displaystyle\pi_{xy}\geq 0,\
\forall\\{x,y\\}\in\mathcal{E}.$

Note that (OP-A) is solved for a distribution of resources across the source
nodes at a given time. If the amount of resources at each node changes, a new
optimal strategy can be obtained by solving (OP-A) repeatedly in a moving
horizon fashion. Extending (OP-A) to dynamic resource allocation over a period
a time is possible and left as subsequent work.

##  III Preliminary Analysis

The successful attack probability function $p_{x}$ should capture the fact
that a larger security investment lowers the likelihood of attack. In
addition, the marginal benefit of security resource decreases for each target
node. To this end, we have the following assumption.

######  Assumption 1.

The successful attack probability function $p_{x}(\Pi_{x})$ satisfies the
following: 1) $p_{x}(\Pi_{x})\in[0,1]$ with
$\lim_{||\zeta||_{1}\rightarrow\infty}p_{x}(\zeta)$ = 0, where $||\cdot||_{1}$
denotes the $l_{1}$ norm, and is twice differentiable, 2) $p_{x}(\Pi_{x})$ is
strictly monotonic decreasing and log-convex with respect to $\pi_{xy}$, for
$y\in\mathcal{Y}_{x}$, and 3) $\frac{\partial p_{x}}{\partial\pi_{xy}}/p_{x}$
is bounded with respect to $\pi_{xy}$, for $y\in\mathcal{Y}_{x}$.

There are a number of functions of interest that satisfy the properties in
Assumption 1. For example,

$p_{x}(\Pi_{x})=\exp({-\sum_{y\in\mathcal{Y}_{x}}\pi_{xy}-r_{x}}),$ (5)

where $r_{x}>0$ represents the existing security investment at node $x$ before
resource transport.

As another example,
$p_{x}(\Pi_{x})=\frac{1}{\sum_{y\in\mathcal{Y}_{x}}\pi_{xy}+r_{x}}$, where
$r_{x}>1$ has a similar meaning as in the previous case. Both examples
indicate that the security resources can effectively decrease the attack
likelihood.

######  Lemma 1.

Under Assumption 1, the perceived probability of successful attack at node
$x$, $w(p_{x}(\Pi_{x}))$, is strictly convex in $\pi_{xy}$, $\forall
x\in\mathcal{X},\ y\in\mathcal{Y}_{x}$.

###### Proof.

See Appendix -A. ∎

##  IV Analysis of Bounded Rational Security Investment Strategies

This section characterizes the bounded rational security investment strategies
and analyzes the impacts of behavioral considerations on such decision-making
outcomes.

###  IV-A Security Resource Allocation Preferences

We first have the following assumption to facilitates the analysis.

######  Assumption 2.

Assume that the values of induced loss due to successful attack are ordered as
follows: $U_{1}>U_{2}>...>U_{|\mathcal{X}|}>0$. Furthermore, each target node
admits a same successful attack probability function, i.e., $p_{x}$, $\forall
x\in\mathcal{X}$, share a same form.

We next have the following result on the marginal cost associated with the
target nodes.

######  Lemma 2.

The following inequality holds for each pair of target nodes $i\in\mathcal{X}$
and $j\in\mathcal{X}$ with $i<j$,

$U_{i}\frac{\partial w(p_{i}(\Pi_{i}))}{\partial\pi_{iy}}<U_{j}\frac{\partial
w(p_{j}(\Pi_{j}))}{\partial\pi_{jy}},\ \forall
y\in\mathcal{Y}_{i}\cap\mathcal{Y}_{j}.$ (6)

And the marginal cost $U_{i}\frac{\partial
w(p_{i}(\Pi_{i}))}{\partial\pi_{iy}}$ is negative and continuously increasing
to 0 in $\pi_{iy}$, $\forall i\in\mathcal{X}$.

###### Proof.

First, we have, $\forall x\in\mathcal{X}$ and $\forall y\in\mathcal{Y}_{x}$,

$\displaystyle U_{x}\frac{\partial w(p_{x}(\Pi_{x}))}{\partial\pi_{xy}}=$
$\displaystyle U_{x}\gamma(-\log(p_{x}(\Pi_{x})))^{(\gamma-1)}$ (7)
$\displaystyle\cdot\frac{\partial
p_{x}(\Pi_{x})}{\partial\pi_{xy}}\Big{/}p_{x}(\Pi_{x})\cdot
w(p_{x}(\Pi_{x})).$

Based on Assumption 1, $\frac{\partial p_{x}(\Pi_{x})}{\partial\pi_{xy}}$ is
negative. In addition, $-\log(p_{x}(\Pi_{x}))$, $p_{x}(\Pi_{x})$ and
$w(p_{x}(\Pi_{x}))$ are all positive. Thus, $U_{x}\frac{\partial
w(p_{x}(\Pi_{x}))}{\partial\pi_{xy}}<0$. Lemma 1 shows that
$\frac{\partial}{\partial\pi_{xy}}(\frac{\partial
w(p_{x}(\Pi_{x}))}{\partial\pi_{xy}})>0$, indicating that the marginal cost is
monotonically increasing. In addition,
$\lim_{||\Pi_{x}||_{1}\rightarrow\infty}\left|U_{x}\frac{\partial
w(p(\Pi_{x}))}{\partial\pi_{xy}}\right|=\lim_{||\Pi_{x}||_{1}\rightarrow\infty}\left|\gamma
U_{x}(-\log(p_{x}(\Pi_{x})))^{\gamma-1}w(p_{x}(\Pi_{x}))\right|\left|\frac{\partial
p_{x}(\Pi_{x})}{\partial\pi_{xy}}\big{/}p_{x}(\Pi_{x})\right|.$ From
Assumption 1, we know that as $p_{x}(\Pi_{x})=0$ and thus
$w(p_{x}(\Pi_{x}))\rightarrow 0$ and $-\log(p_{x}(\Pi_{x}))\rightarrow\infty$
as $||\Pi_{x}||_{1}\rightarrow\infty$. Since $\frac{\partial
p_{x}}{\partial\pi_{xy}}/p_{x}$ is bounded,
$\lim_{||\Pi_{x}||_{1}\rightarrow\infty}|U_{x}\cdot\frac{\partial
w(p(\Pi_{x}))}{\partial\pi_{xy}}|=0$. Finally, to show the inequality between
the marginals, we note that based on Assumption 2, $U_{i}>U_{j}$ and thus

$\begin{split}&U_{i}(-\log(p(\Pi_{i})))^{\gamma-1}w(p(\Pi_{i}))\frac{\partial
p_{i}(\Pi_{i})}{\partial\pi_{iy}}\Big{/}p_{i}(\Pi_{i})\\\
&<U_{j}(-\log(p(\Pi_{i})))^{\gamma-1}w(p(\Pi_{i}))\frac{\partial
p_{j}(\Pi_{i})}{\partial\pi_{jy}}\Big{/}p_{j}(\Pi_{i}),\end{split}$

$\forall\Pi_{x}\in\mathbb{R}_{+}^{|\mathcal{Y}_{x}|},\forall x\in\mathcal{X}$
which yields (6) because $\frac{\partial p_{j}(\Pi_{i})}{\partial\pi_{jy}}$ is
negative. ∎

The following proposition characterizes the total amount of security resources
received by the target nodes from sources under some general assumptions.

######  Proposition 1.

Under Assumption 2 and a complete resource transport network, the optimal
strategy $\\{\Pi_{x}^{*}\\}_{x\in\mathcal{X}}$ satisfies the following
inequality
$||\Pi_{1}^{*}||_{1}\geq||\Pi_{2}^{*}||_{1}\geq...\geq||\Pi_{|\mathcal{X}|}^{*}||_{1}$,
and the $l_{1}$ norm $||\Pi_{x}||_{1}=\sum_{y\in\mathcal{Y}_{x}}\pi_{xy}$ is
the total amount of security resources received by the target node
$x\in\mathcal{X}$.

###### Proof.

As each source can transfer resources to every target and the qualities of
resources are the same supplied by all source nodes, it is equivalent to
aggregate all the source nodes as a single super node that has a capacity
$\sum_{y\in\mathcal{Y}}\bar{q}_{y}$ managed by a central planner. Thus, the
transport network can be seen consisting of a single source connected to a set
of targets, i.e., $\mathcal{Y}=\\{1\\}$, $\mathcal{Y}_{x}=\mathcal{Y}$, and
$\Pi_{x}=\pi_{x1}$, $\forall x\in\mathcal{X}$. Based on the KKT condition, for
each pair of target nodes $i\in\mathcal{X}$ and $j\in\mathcal{X}$ receiving
nonzero security resources from the source node, we have $U_{i}\frac{\partial
w(p_{i}(\Pi_{i}))}{\partial\pi_{i1}}|_{\pi_{i1}=\pi_{i1}^{*}}=U_{j}\frac{\partial
w(p_{i}(\Pi_{j}))}{\partial\pi_{j1}}|_{\pi_{j1}=\pi_{j1}^{*}}$. Assumptions 1
and 2 indicate that $\gamma
U_{i}(-\log(p_{i}(\pi_{i1}^{*})))^{\gamma-1}w(p_{i}(\pi_{i1}^{*}))\frac{\partial
p_{i}(\pi_{i1}^{*})}{\partial\pi_{i1}}/p_{i}(\pi_{i1}^{*})=\gamma
U_{j}(-\log(p_{j}(\pi_{j1}^{*})))^{\gamma-1}w(p_{j}(\pi_{j1}^{*}))\frac{\partial
p_{j}(\pi_{j1}^{*})}{\partial\pi_{j1}}/p_{j}(\pi_{j1}^{*})$, which yields

$\displaystyle(-\log(p_{i}(\pi_{i1}^{*})))^{\gamma-1}w(p_{i}(\pi_{i1}^{*}))\frac{\partial
p_{i}(\pi_{i1}^{*})}{\partial\pi_{i1}}\frac{1}{p_{i}(\pi_{i1}^{*})}$
$\displaystyle=\frac{U_{j}}{U_{i}}(-\log(p_{j}(\pi_{j1}^{*})))^{\gamma-1}w(p_{j}(\pi_{j1}^{*}))\frac{\partial
p_{j}(\pi_{j1}^{*})}{\partial\pi_{j1}}\frac{1}{p_{j}(\pi_{j1}^{*})}$
$\displaystyle>(-\log(p_{j}(\pi_{j1}^{*})))^{\gamma-1}w(p_{j}(\pi_{j1}^{*}))\frac{\partial
p_{j}(\pi_{j1}^{*})}{\partial\pi_{j1}}\frac{1}{p_{j}(\pi_{j1}^{*})}.$

The inequality in the last step above is due to $U_{j}<U_{i}$ for $j>i$ and
the negative marginal cost of target node on the received security resources.
Based on Lemma 2, the marginal cost is continuously increasing. Thus, we can
conclude $\pi_{i1}^{*}>\pi_{j1}^{*}$, where $\pi_{i1}^{*}$ is the total amount
of resources received by target node $i$. Equivalently speaking, target node
$i$ receives more security resources than target node $j$ at the optimal
solution, for $i<j\in\mathcal{X}$. ∎

Remark: Proposition 1 indicates that, under some quite general conditions,
target node $i$ (higher-valued) receives more resources than target node $j$
(lower-valued) under the optimal allocation plan, $\forall i<j\in\mathcal{X}$.
This result is consistent with the objective of the system planner in
minimizing the aggregated expected loss of assets.

###  IV-B Sequential Water-Filling of Security Investment

The transport network is still considered to be complete. Thus, it is
equivalent to combine all source nodes and regard them as a super source node
with capacity $\sum_{y\in\mathcal{Y}}\bar{q}_{y}$. For convenience, we denote
by $\tilde{\pi}_{i}$ the total amount of resources that target node $i$
received from the super source node, i.e.,
$\tilde{\pi}_{i}=\sum_{y\in\mathcal{Y}_{i}}\pi_{iy}$ in the original
framework. With a slight abuse of notation, $p_{x}$ can be seen as a single-
variable function on $\tilde{\pi}_{i}$. For all target nodes $i\in\mathcal{X}$
and $j\in\mathcal{X}$ with $i<j$, we define $\tilde{\pi}_{i}^{j*}$ as a
quantity that satisfies

$U_{i}\frac{\partial
w(p_{i}(\tilde{\pi}_{i}))}{\partial\tilde{\pi}_{i}}\Bigg{|}_{\tilde{\pi}_{i}=\tilde{\pi}_{i}^{j*}}=U_{j}\frac{\partial
w(p_{j}(\tilde{\pi}_{j}))}{\partial\tilde{\pi}_{j}}\Bigg{|}_{\tilde{\pi}_{j}=0}.$
(8)

######  Proposition 2.

Under Assumption 2 and a complete transport network, the resources received by
target node $j$ from the super source node, $\tilde{\pi}_{j}$, will be nonzero
at the optimal solution if and only if
$\sum_{y\in\mathcal{Y}}\bar{q}_{y}>\sum_{i=1}^{j-1}\tilde{\pi}_{i}^{j*}$,
where $\tilde{\pi}_{i}^{j*}$ is defined in (8).

###### Proof.

Suppose that $\tilde{\pi}_{j}^{*}>0$ for some target node $j$. Also suppose by
contradiction that
$\sum_{y\in\mathcal{Y}}\bar{q}_{y}\leq\sum_{i=1}^{j-1}\tilde{\pi}_{i}^{j*}$.
Then, $\exists m\in\\{1,...,j-1\\}$ such that
$\tilde{\pi}_{m}^{*}<\tilde{\pi}_{m}^{j*}$. This indicates that it is
infeasible to allocate $\tilde{\pi}_{m}^{j*}$ or more resources to node $m$
without exceeding the upper bound. By definition of $\tilde{\pi}_{m}^{j*}$,

$\displaystyle U_{m}\frac{\partial
w(p_{m}(\tilde{\pi}_{m}))}{\partial\tilde{\pi}_{m}}\bigg{\rvert}_{\tilde{\pi}_{m}=\tilde{\pi}_{m}^{j*}}<U_{j}\frac{\partial
w(p_{j}(\tilde{\pi}_{j}))}{\partial\tilde{\pi}_{j}}\bigg{\rvert}_{\tilde{\pi}_{j}=0}$
$\displaystyle<U_{j}\frac{\partial
w(p_{j}(\tilde{\pi}_{j}))}{\partial\tilde{\pi}_{j}}\bigg{\rvert}_{\tilde{\pi}_{j}=\tilde{\pi}_{j}^{*}},$

which yields a contradiction, since the marginals must coincide at the optimal
solution. Thus, $\tilde{\pi}_{j}^{*}>0$ leads to
$\sum_{y\in\mathcal{Y}}\bar{q}_{y}>\sum_{i=1}^{j-1}\tilde{\pi}_{i}^{j*}$ under
the optimal resource allocation.

To prove the other direction, we first suppose that
$\sum_{y\in\mathcal{Y}}\bar{q}_{y}>\sum_{i=1}^{j-1}\tilde{\pi}_{i}^{*}$ and
suppose by contradiction $\tilde{\pi}_{j}=0$. Then we have
$\tilde{\pi}_{k}=0,\forall k>j$, and thus
$\sum_{k=1,2,...,j-1}\tilde{\pi}_{k}=\sum_{y\in\mathcal{Y}}\bar{q}_{y}$ and
$\exists i\in\\{1,...,j-1\\}$ such that
$\tilde{\pi}_{i}>\tilde{\pi}_{i}^{j*}$. A sufficiently small amount of
resource, $\epsilon\in\mathbb{R}_{+}$ is transferred from target $i$ to $j$
which will lead to a net cost reduction in (OP-A), and thus the resource
allocation is no longer optimal. Starting with non-zero resource allocation to
the target nodes $\\{1,...,j-1\\}$, the total cost is
$\sum_{x\in\mathcal{X}}U_{x}w(p_{x}(\tilde{\pi}_{x})).$ From target $i$ that
has $\tilde{\pi}_{i}^{*}=||\Pi_{i}^{*}||_{1}>\tilde{\pi}_{i}^{j*}$, remove a
sufficiently small amount of resource $\epsilon$ and add a resource amount of
$\epsilon$ to target $j$. Denote the modified resource transport plan as
$\pi^{(\epsilon)}$. The total cost after perturbation becomes

$\displaystyle\tilde{L}(\pi^{(\epsilon)})=\sum_{z\in\mathcal{X}\setminus\\{i,j\\}}U_{z}w(p_{z}(\tilde{\pi}_{z}^{*}))+U_{i}w(p_{i}(\tilde{\pi}_{i}-\epsilon))$
$\displaystyle+U_{j}w(p_{j}(\epsilon)).$

We next define
$g(\epsilon)=U_{i}w(p_{i}(\tilde{\pi}_{i}-\epsilon))+U_{j}w(p_{j}(\epsilon))$.
Then,
$\tilde{L}(\pi^{*})=\sum_{z\in\mathcal{X}\setminus\\{i,j\\}}U_{z}w(p_{z}(\tilde{\pi}_{z}))+g(0),\
\tilde{L}(\pi^{(\epsilon)})=\sum_{z\in\mathcal{X}\setminus\\{i,j\\}}U_{z}w(p_{z}(\tilde{\pi}_{z}))+g(\epsilon).$
If $g(\epsilon)<g(0)$, then
$\tilde{L}(\pi^{(\epsilon)})<\tilde{L}(\tilde{\pi}^{*})$, which yields a
positive net cost reduction, meaning that the resource allocation strategy
after perturbation is worse off. It is clear that

$\frac{dg}{d\epsilon}=-U_{i}\frac{\partial
w(p_{i}(\pi_{i}))}{\partial\tilde{\pi}_{i}}\bigg{\rvert}_{\pi_{i}=\tilde{\pi}_{i}-\epsilon}+U_{j}\frac{\partial
w(p_{j}(\pi_{j}))}{\partial\tilde{\pi}_{j}}\bigg{\rvert}_{\pi_{j}=\epsilon}.$

Based on $\tilde{\pi}_{i}^{*}>\tilde{\pi}_{i}^{j*}$ and Lemma 2,

$U_{i}\frac{\partial
w(p_{i}(\tilde{\pi}_{i}))}{\partial\tilde{\pi}_{i}}\bigg{\rvert}_{\tilde{\pi}_{i}=\tilde{\pi}_{i}^{*}}>U_{j}\frac{\partial
w(p_{j}(\tilde{\pi}_{j}))}{\partial\tilde{\pi}_{j}}\bigg{\rvert}_{\tilde{\pi}_{j}=0}.$

Thus, $\lim_{\epsilon\rightarrow 0}\frac{dg}{d\epsilon}$ is negative,
indicating that $g(\epsilon)$ is decreasing for a sufficiently small
$\epsilon$. Therefore, we obtain
$\tilde{L}(\pi^{(\epsilon)})<\tilde{L}(\tilde{\pi}^{*})$ which is a
contradiction. ∎

Remark: Proposition 2 implies that the super source node first allocates
$\tilde{\pi}_{1}^{2*}$ security resources to target node 1, and then starts to
transfer resources to both target nodes 1 and 2 while maintaining a same
marginal cost until reaching $\tilde{\pi}_{1}^{3*}$ and
$\tilde{\pi}_{2}^{3*}$, respectively. Afterward, in addition to target nodes 1
and 2, target node 3 starts to receive resources, and the marginal costs at
all nodes are kept the same during security resource investment. The resource
allocation scheme will follow this fashion until all resources are
transferred. The above discussion leads to sequential water-filling of
security resource transport over networks.

As the original transport network includes multiple source nodes, we need to
determine the strategy for each of them. The above discussion indicates that
the optimal resource allocation plan can be obtained sequentially, i.e., each
source node completes allocating its security resources to the targets in
sequential order. Specifically, source node 1 will first transfer its resource
to target node 1. If $\bar{q}_{1}<\tilde{\pi}_{1}^{2*}$, then the next source
nodes (node 2, 3, etc) will continue allocate resource to target node 1 until
it receives $\tilde{\pi}_{1}^{2*}$ amount of resources. If
$\bar{q}_{1}>\tilde{\pi}_{1}^{2*}$, then source node 1 first allocates
$\tilde{\pi}_{1}^{2*}$ amount of resources to the target node 1, and then
start transferring the remaining resources to both targets 1 and 2 while
maintaining a same marginal cost at both nodes. After source node 1 completes
its resource transport, source node 2 starts to transfer its resources to the
appropriate targets in a similar manner. This process terminates until all
source nodes finish their resource allocation to the targets.

###  IV-C Behavioral Impacts on Security Resource Allocation

The impact of incorporating the behavioral element to probability perception
is captured by the parameter $\gamma$. Clearly, there is no behavioral
consideration when $\gamma=1$, and the probabilities are perceived as their
actual values. When $\gamma\in(0,1)$, we have the following result on the
behavioral impacts on the resource allocation plan.

######  Proposition 3.

Under Assumptions 1 and 2, $p_{x}(0)<\frac{1}{e}$, $\forall x\in\mathcal{X}$,
and a complete transport network, ${d\tilde{\pi}_{i}^{j*}}/{d\gamma}<0$ for
$i<j$, $\forall i,j\in\mathcal{X}$, with $\tilde{\pi}_{i}^{j*}$ defined in
(8).

###### Proof.

Based on (2) and (8), we have

$\displaystyle
U_{i}\gamma(-\log(p_{i}(\tilde{\pi}_{i}^{j*})))^{(\gamma-1)}w(p_{i}(\tilde{\pi}_{i}^{j*}))\frac{\partial
p_{i}(\tilde{\pi}_{i})}{\partial\tilde{\pi}_{i}}\bigg{\rvert}_{\tilde{\pi}_{i}=\tilde{\pi}_{i}^{j*}}\frac{1}{p_{i}(\tilde{\pi}_{i}^{j*})}$
(9)
$\displaystyle=U_{j}\gamma(-\log(p_{j}(0)))^{(\gamma-1)}w(p_{j}(0))\frac{\partial
p_{j}(\tilde{\pi}_{j})}{\partial\tilde{\pi}_{j}}\bigg{\rvert}_{\tilde{\pi}_{j}=0}\frac{1}{p_{j}(0)}.$

Based on (9), we can characterize the sensitivity of the amount of security
resources transported to each target over the behavioral parameter $\gamma$.
Taking log of each side of (9) and differentiating with respect to $\gamma$
yield

$\displaystyle\frac{d\tilde{\pi}_{i}^{j*}}{d\gamma}=\frac{((-\log(p_{i}(\tilde{\pi}_{i}^{j*})))^{\gamma}-1)\log(-\log(p_{i}(\tilde{\pi}_{i}^{j*})))}{\Lambda_{i}^{j}}$
(10)
$\displaystyle-\frac{((-\log(p_{j}(0)))^{\gamma}-1)\log(-\log(p_{j}(0)))}{\Lambda_{i}^{j}},$

where
$\Lambda_{i}^{j}=(\gamma-1-\gamma(-\log(p_{i}(\tilde{\pi}_{i}^{j*})))^{\gamma})\frac{\partial
p_{i}(\tilde{\pi}_{i})}{\partial\tilde{\pi}_{i}}\bigg{\rvert}_{\tilde{\pi}_{i}=\tilde{\pi}_{i}^{j*}}\cdot\frac{1}{p_{i}(\tilde{\pi}_{i}^{j*})}\\\
\log(p_{i}(\tilde{\pi}_{i}^{j*}))+\frac{p_{i}(\tilde{\pi}_{i}^{j*})\frac{\partial^{2}p_{i}(\tilde{\pi}_{i})}{\partial\tilde{\pi}_{i}^{2}}\big{\rvert}_{\tilde{\pi}_{i}=\tilde{\pi}_{i}^{j*}}-\big{(}\frac{\partial
p_{i}(\tilde{\pi}_{i})}{\partial\tilde{\pi}_{i}}\big{\rvert}_{\tilde{\pi}_{i}=\tilde{\pi}_{i}^{j*}}\big{)}^{2}}{\frac{\partial
p_{i}(\tilde{\pi}_{i})}{\partial\tilde{\pi}_{i}}\big{\rvert}_{\tilde{\pi}_{i}=\tilde{\pi}_{i}^{j*}}\cdot
p_{i}(\tilde{\pi}_{i}^{j*})}.$ Under the assumption that
$p_{j}(0)<\frac{1}{e}$ and $p_{i}(\tilde{\pi}_{i}^{j*})<p_{j}(0)$ for
$\tilde{\pi}_{i}^{j*}>0$, we have
$-\log(p_{i}(\tilde{\pi}_{i}^{j*}))>-\log(p_{j}(0))>1$ and thus
$\log(-\log(p_{i}(\tilde{\pi}_{i}^{j*})))>\log(-\log(p_{j}(0)))>0$ and
$(-\log(p_{i}(\tilde{\pi}_{i}^{j*})))^{\gamma}-1>(-\log(p_{j}(0)))^{\gamma}-1$.
Hence, the numerator of (10) is positive. From Assumption 1, we have
$\frac{\partial
p_{i}(\tilde{\pi}_{i})}{\partial\tilde{\pi}_{i}}\bigg{\rvert}_{\tilde{\pi}_{i}=\tilde{\pi}_{i}^{j*}}<0$
and because $p_{i}(\tilde{\pi}_{i})$ is log-convex,
$p_{i}(\tilde{\pi}_{i}^{j*})\frac{\partial^{2}p_{i}(\tilde{\pi}_{i})}{\partial\tilde{\pi}_{i}^{2}}\big{\rvert}_{\tilde{\pi}_{i}=\tilde{\pi}_{i}^{j*}}\geq\big{(}\frac{\partial
p_{i}(\tilde{\pi}_{i})}{\partial\tilde{\pi}_{i}}\big{\rvert}_{\tilde{\pi}_{i}=\tilde{\pi}_{i}^{j*}}\big{)}^{2}$.
Thus, the denominator of (10) negative, which yields
${d\tilde{\pi}_{i}^{j*}}/{d\gamma}<0$. ∎

Remark: The above analysis, together with Proposition 1 indicate that when the
behavioral misperception on the attack success probability is considered, the
sources will supply security resources to fewer target nodes than the optimal
strategy obtained under the non-behavioral counterpart. In other words, the
behavioral security resource owners prefer to secure higher-valued assets
while paying less attention to those relatively lower-valued targets, and it
leads to a discriminative resource allocation scheme comparing with the one
developed under fully rational scenario.

##  V Distributed Algorithm for Bounded Rational Security Investment

This section aims to develop a distribution computational scheme to obtain the
behavioral security investment scheme.

In the established framework, the objective function can also incorporate the
preferences of the source nodes in the security resource transport design in
addition to the cost of the target nodes. The utility function of source node
$y$ on transferring $\pi_{xy}$ security resources to target node $x$ is
denoted by $s_{xy}:\mathbb{R}_{+}\rightarrow\mathbb{R}$. In addition, to
balance the security resource allocation, the planner considers an upper bound
of each target node $x\in\mathcal{X}$ on the received security resources from
connected sources, captured by $\bar{p}_{x}\in\mathbb{R}_{+}$, i.e.,
$\sum_{y\in\mathcal{Y}_{x}}\pi_{xy}\leq\bar{p}_{x}$. To this end, the system
planner aims to address:

$\displaystyle\mathrm{(OP-B):}\quad\min_{\Pi}$
$\displaystyle\sum_{x\in\mathcal{X}}U_{x}w(p_{x}(\Pi_{x}))-\sum_{y\in\mathcal{Y}}\sum_{x\in\mathcal{X}_{y}}\tau_{y}s_{xy}(\pi_{xy})$
$\displaystyle\mathrm{s.t.}$ $\displaystyle
0\leq\sum_{y\in\mathcal{Y}_{x}}\pi_{xy}\leq\bar{p}_{x},\ \forall
x\in\mathcal{X},$ $\displaystyle
0\leq\sum_{x\in\mathcal{X}_{y}}\pi_{xy}\leq\bar{q}_{y},\ \forall
y\in\mathcal{Y},$ $\displaystyle\pi_{xy}\geq 0,\
\forall\\{x,y\\}\in\mathcal{E},$

where $\tau_{y}\in\mathbb{R}_{+}$ is a positive weighting factor balancing the
loss of the targets and the utility of the sources under a given security
allocation strategy. It is straightforward to observe that as
$\tau_{y}\rightarrow 0,\ \forall y$, the solution to (OP-B) will converge to
the one of (OP-A), given that the targets have no constraint on the maximum
received security resources.

As the resource transport network becomes complex with a large number of
participating nodes, a centralized scheme to compute the optimal solution to
(OP-B) can be computationally expensive. In addition, the centralized
optimization paradigm requires the planner to collect heterogeneous
information from all source and target nodes, including their utility
parameters, supply and demand upper bounds, degree of misperception on attack
success, and value of targets, which does not preserve a desirable level of
privacy. Due to the above two concerns, it is necessary to devise a
distributed and privacy-preserving scheme to obtain the behavioral resource
allocation strategy over a large-scale network.

To facilitate the development of such an algorithm, we first introduce two
ancillary variables $\pi_{xy}^{t}$ and $\pi_{xy}^{s}$. The superscripts $t$
and $s$ indicate that the corresponding parameter belongs to a target and
source node, respectively. We then set $\pi_{xy}=\pi_{xy}^{t}$ and
$\pi_{xy}=\pi_{xy}^{s}$, indicating that the solutions proposed by the targets
and sources are consistent. This reformulation facilitates the design of a
distributed algorithm which allows us to iterate to obtain the optimal
strategy. To this end, the reformulated problem is presented as follows:

$\displaystyle\min_{\Pi^{t}\in\mathcal{F}^{t},\Pi^{s}\in\mathcal{F}^{s},\Pi}$
$\displaystyle\sum_{x\in\mathcal{X}}U_{x}w(p_{x}(\Pi_{x}^{t}))-\sum_{y\in\mathcal{Y}}\sum_{x\in\mathcal{X}_{y}}\tau_{y}s_{xy}(\pi_{xy}^{s})$
(11) $\displaystyle\mathrm{s.t.}$ $\displaystyle\pi_{xy}^{t}=\pi_{xy},\
\forall\\{x,y\\}\in\mathcal{E},$ $\displaystyle\pi_{xy}^{s}=\pi_{xy},\
\forall\\{x,y\\}\in\mathcal{E},$

where $\Pi^{t}:=\\{\pi_{xy}^{t}\\}_{x\in\mathcal{X}_{y},y\in\mathcal{Y}}$,
$\Pi^{s}:=\\{\pi_{xy}^{s}\\}_{x\in\mathcal{X},y\in\mathcal{Y}_{x}}$,
$\mathcal{F}^{t}:=\\{\Pi^{t}|\pi_{xy}^{t}\geq
0,\underline{p}_{x}\leq\sum_{y\in\mathcal{Y}_{x}}\pi_{xy}^{t}\leq\bar{p}_{x},\
\\{x,y\\}\in\mathcal{E}\\}$, and $\mathcal{F}^{s}:=\\{\Pi^{s}|\pi_{xy}^{s}\geq
0,\underline{q}_{y}\leq\sum_{x\in\mathcal{X}_{y}}\pi_{xy}^{s}\leq\bar{q}_{y},\
\\{x,y\\}\in\mathcal{E}\\}$.

We resort to alternating direction method of multipliers (ADMM) [6] to develop
a distributed computational algorithm. First, let $\alpha_{xy}^{s}$ and
$\alpha_{xy}^{t}$ be the Lagrangian multipliers associated with the constraint
$\pi_{xy}^{s}=\pi_{xy}$ and $\pi_{xy}^{t}=\pi_{xy}$, respectively. The
Lagrangian function associated with the optimization problem (11) can then be
written as follows:

$\displaystyle\mathcal{L}$
$\displaystyle(\Pi^{t},\Pi^{s},\Pi,\alpha_{xy}^{t},\alpha_{xy}^{s})$ (12)
$\displaystyle=\sum_{x\in\mathcal{X}}U_{x}w(p_{x}(\Pi_{x}^{t}))-\sum_{y\in\mathcal{Y}}\sum_{x\in\mathcal{X}_{y}}\tau_{y}s_{xy}(\pi_{xy}^{s})$
$\displaystyle+\sum_{x\in\mathcal{X}}\sum_{y\in\mathcal{Y}_{x}}\alpha_{xy}^{t}\left(\pi_{xy}^{t}-\pi_{xy}\right)+\sum_{y\in\mathcal{Y}}\sum_{x\in\mathcal{X}_{y}}\alpha_{xy}^{s}\left(\pi_{xy}-\pi_{xy}^{s}\right)$
$\displaystyle+\frac{\eta}{2}\sum_{x\in\mathcal{X}}\sum_{y\in\mathcal{Y}_{x}}\left(\pi_{xy}^{t}-\pi_{xy}\right)^{2}+\frac{\eta}{2}\sum_{x\in\mathcal{X}}\sum_{y\in\mathcal{Y}_{x}}\left(\pi_{xy}-\pi_{xy}^{s}\right)^{2},$

where $\eta$ is a positive constant controlling the convergence. We have the
following result on the distributed algorithm.

######  Proposition 4.

The iterative steps of ADMM to solve (OP-B) are summarized as follows:

$\begin{split}\Pi_{x}^{t}(k+1)&\in\arg\min_{\Pi_{x}^{t}\in\mathcal{F}_{x}^{t}}U_{x}w(p_{x}(\Pi_{x}^{t}))\\\
&+\sum_{y\in\mathcal{Y}_{x}}\alpha_{xy}^{t}(k)\pi_{xy}^{t}+\frac{\eta}{2}\sum_{y\in\mathcal{Y}_{x}}(\pi_{xy}^{t}-\pi_{xy}(k))^{2},\end{split}$
(13) $\displaystyle\Pi_{y}^{s}(k+1)$
$\displaystyle\in\arg\min_{\Pi_{y}^{s}\in\mathcal{F}_{y}^{s}}-\sum_{x\in\mathcal{X}_{y}}\tau_{y}s_{xy}(\pi_{xy}^{s})$
(14)
$\displaystyle-\sum_{x\in\mathcal{X}_{y}}\alpha_{xy}^{s}(k)\pi_{xy}^{s}+\frac{\eta}{2}\sum_{x\in\mathcal{X}_{y}}(\pi_{xy}(k)-\pi_{xy}^{s})^{2},$
$\begin{split}\pi_{xy}(&k+1)=\arg\min_{\pi_{xy}}-\alpha_{xy}^{t}(k)\pi_{xy}+\alpha_{xy}^{s}(k)\pi_{xy}\\\
&+\frac{\eta}{2}(\pi_{xy}^{t}(k+1)-\pi_{xy})^{2}+\frac{\eta}{2}(\pi_{xy}-\pi_{xy}^{s}(k+1))^{2},\end{split}$
(15)
$\begin{split}\alpha_{xy}^{t}(k+1)=\alpha_{xy}^{t}(k)+\eta(\pi_{xy}^{t}(k+1)-\pi_{xy}(k+1))^{2},\end{split}$
(16)
$\begin{split}\alpha_{xy}^{s}(k+1)=\alpha_{xy}^{s}(k)+\eta(\pi_{xy}(k+1)-\pi_{xy}^{s}(k+1))^{2},\end{split}$
(17)

where
$\Pi_{\tilde{x}}^{t}:=\\{\pi_{xy}^{t}\\}_{y\in\mathcal{Y}_{x},x=\tilde{x}}$
represents the solution at target node $\tilde{x}\in\mathcal{X}$, and
$\Pi_{\tilde{y}}^{s}:=\\{\pi_{xy}^{s}\\}_{x\in\mathcal{X}_{y},y=\tilde{y}}$
represents the proposed solution at source node $\tilde{y}\in\mathcal{Y}$. In
addition, $\mathcal{F}_{x}^{t}:=\\{\Pi_{x}^{t}|\pi_{xy}^{t}\geq
0,y\in\mathcal{Y}_{x},\underline{p}_{x}\leq\sum_{y\in\mathcal{Y}_{x}}\pi_{xy}^{t}\leq\bar{p}_{x}\\}$,
and $\mathcal{F}_{y}^{s}:=\\{\Pi_{y}^{s}|\pi_{xy}^{s}\geq
0,x\in\mathcal{X}_{y},\underline{q}_{y}\leq\sum_{x\in\mathcal{X}_{y}}\pi_{xy}^{s}\leq\bar{q}_{y}\\}$.

###### Proof.

The proof follows similarly to the proof of Proposition 1 in [17]. ∎

The iterations in (13)-(17) can be further simplified to four iterations.

######  Proposition 5.

The iterations (13)-(17) can be simplified as follows:

$\begin{split}\Pi_{x}^{t}(k+1)&\in\arg\min_{\Pi_{x}^{t}\in\mathcal{F}_{x}^{t}}U_{x}w(p_{x}(\Pi_{x}^{t}))\\\
&+\sum_{y\in\mathcal{Y}_{x}}\alpha_{xy}(k)\pi_{xy}^{t}+\frac{\eta}{2}\sum_{y\in\mathcal{Y}_{x}}(\pi_{xy}^{t}-\pi_{xy}(k))^{2},\end{split}$
(18) $\displaystyle\Pi_{y}^{s}(k+1)$
$\displaystyle\in\arg\min_{\Pi_{y}^{s}\in\mathcal{F}_{y}^{s}}-\sum_{x\in\mathcal{X}_{y}}\tau_{y}s_{xy}(\pi_{xy}^{s})$
(19)
$\displaystyle-\sum_{x\in\mathcal{X}_{y}}\alpha_{xy}(k)\pi_{xy}^{s}+\frac{\eta}{2}\sum_{x\in\mathcal{X}_{y}}(\pi_{xy}(k)-\pi_{xy}^{s})^{2},$
$\begin{split}\pi_{xy}(k+1)=\frac{1}{2}\left(\pi_{xy}^{t}(k+1)+\pi_{xy}^{s}(k+1)\right),\end{split}$
(20)
$\begin{split}\alpha_{xy}(k+1)=\alpha_{xy}(k)+\frac{\eta}{2}\left(\pi_{xy}^{t}(k+1)-\pi_{xy}^{s}(k+1)\right).\end{split}$
(21)

###### Proof.

The proof follows similarly to the proof of Proposition 2 in [17]. ∎

We summarize the results into the following Algorithm 1.

Algorithm 1 Distributed Algorithm

1:while $\Pi_{x}^{t}$ and $\Pi_{y}^{s}$ not converging do

2: Compute $\Pi_{x}^{t}(k+1)$ using (18), for all $x\in\mathcal{X}_{y}$

3: Compute $\Pi_{y}^{s}(k+1)$ using (19), for all $y\in\mathcal{Y}_{x}$

4: Compute $\pi_{xy}(k+1)$ using (20), for all $\\{x,y\\}\in\mathcal{E}$

5: Compute $\alpha_{xy}(k+1)$ using (21), for all $\\{x,y\\}\in\mathcal{E}$

6:end while

7:return $\pi_{xy}(k+1)$, for all $\\{x,y\\}\in\mathcal{E}$

Remark: The developed algorithm can be interpreted as a negotiation process
between each pair of connected resource owner and target node on the security
resource allocation scheme, which does not require a central planner. The
final outcome indicates that the negotiation reaches a consensus.

##  VI Case Studies

In this section, we corroborate the developed results by focusing on the
impacts of the behavioral consideration on the security investment decision-
making. We investigate a transport network consisting of two source nodes
(security resource owners) and five target nodes (assets to protect). We
define the loss parameter at each target as $U_{1}=12$, $U_{2}=9$, $U_{3}=5$,
$U_{4}=3$, and $U_{5}=2$. Additionally, we use Prelec’s probability weighting
function defined in (2) and the probability function shown in (5). We set the
upper bound of security resources to $\bar{q}_{1}=10$ units and
$\bar{q}_{2}=4$ units, meaning the maximum amount of security resources the
sources can invest. The utility functions of $s_{xy}$ are considered to be
linear.

###  VI-A Impact of Behavioral Consideration

We first examine how incorporating the behavioral considerations will impact
the transportation of security resources from the sources to targets. This
involves looking at how the parameter $\gamma$ affects the outcome of the
resource allocation. We expect that as the parameter $\gamma$ goes to one, the
amount of resources received at each target should be the same as when
misperception is not considered, i.e., the objective function would be
$U_{x}(p_{x}(\Pi_{x}))$. Fig. 1 corroborates this result. We can also observe
that the target node with a larger value $U_{x}$ receives more resources,
indicating that the system planner prefers to secure more valuable targets
under a constrained budget. The relationship between the amount of received
resources at targets follows from the order of node’s value $U_{x}$ in
Assumption 2. Additionally, as the behavioral parameter $\gamma$ goes to 1,
the aggregated loss at the targets converges to the same value when
misperception is not considered, as shown in Fig. 1. It can also be seen that
the bounded rational security investment strategy is not as efficient as the
one under the accurate perception.

Figure 1: Impact of behavioral misperception on the security resource
allocation plan. (a): Impact of $\gamma$ on the amount of resources received
at each target node. The solution converges to the one without misperception
as $\gamma$ goes to 1. (b): Aggregated loss of the targets with varying
$\gamma$. A larger degree of misperception yields a less efficient resource
transport strategy.

###  VI-B Performance of Distributed Algorithm

We next show the performance of the proposed distributed algorithm in
Algorithm 1. We use Algorithm 1 to solve the optimization problem in (OP-B).
Fig. 2 shows that the distributed algorithm can efficiently converge to the
centralized optimal solution. We also examine how the parameter $\tau_{y}$
influences the outcome of the transport plan. In the case study, $\tau_{y}$ is
set to be the same at every source node, i.e., $\tau_{y}=\tau,\ \forall
y\in\mathcal{Y}$. We leverage the developed distributed algorithm to compute
the optimal strategy for various $\tau\in[0,1]$, and Fig. 2 depicts the
results. We can observe that when $\tau$ goes to zero in (OP-B), the
aggregated loss of target nodes under the obtained strategy coincides with the
one to (OP-A). This result makes sense as the utility term $s_{xy}$ no longer
plays a role in (OP-B) when $\tau=0$. Another remark is that when $\tau<0.5$,
the loss of targets under the solution to (OP-B) is smaller than the (OP-A)
counterpart. This phenomenon is due to the system planner pays more attention
to minimize the risks of targets when $\tau$ is small. As $\tau$ increases,
the system planner cares more about maximizing the utility of resource owners,
and thus it yields a larger loss of targets as shown in Fig. 2.

Figure 2: (a): Effectiveness of the distributed algorithm 1. The distributed
algorithm converges to the centralized optimal solution to problem (OP-B).
(b): Impact of weighting constant $\tau$ on the aggregated loss of the
targets. The solution degenerates to the one to problem (OP-A) as $\tau$ goes
to 0.

##  VII Conclusion

This paper has developed a behavioral framework for security investments over
a network consisting of multiple source nodes and heterogeneous target nodes.
The behavioral element captures human’s misperception of the successful attack
probabilities at targets under a given level of security investment. The
analysis has shown that the bounded-rational optimal resource allocation
admits a sequential water-filling nature. In addition, we have discovered that
fewer targets will receive security resources under the behavioral paradigm
compared with the non-behavioral setting, revealing the sub-optimal feature of
the strategy due to the behavioral misperception. We have further developed an
efficient distributed algorithm to compute the resource allocation plan with a
convergence guarantee which enjoys advantages when the transport network
becomes enormous and complex. The case studies have corroborated that the
system planner favors the higher-valued targets in bounded rational security
investment, often resulting in lower-valued targets receiving smaller amounts
or no resources. Future works include extending the current framework to an
adversarial setting and develop resilient security investment strategies.
Another direction is to investigate dynamic resource allocation over a time-
horizon with bounded rational agents.

## References

  * [1] W. T. Yue, M. Çakanyıldırım, Y. U. Ryu, and D. Liu, “Network externalities, layered protection and IT security risk management,” _Decision Support Systems_ , vol. 44, no. 1, pp. 1–16, 2007.
  * [2] Z. Su and Q. Xu, “Security-aware resource allocation for mobile social big data: A matching-coalitional game solution,” _IEEE Transactions on Big Data_ , vol. 7, no. 4, pp. 632–642, 2021.
  * [3] D. Kahneman and A. Tversky, “Prospect theory: An analysis of decision under risk,” _Econometrica_ , vol. 47, no. 2, pp. 263–291, 1979.
  * [4] A. Tversky and D. Kahneman, “Advances in prospect theory: Cumulative representation of uncertainty,” _Journal of Risk and Uncertainty_ , vol. 5, no. 4, pp. 297–323, 1992.
  * [5] R. Zhang and Q. Zhu, “Consensus-based distributed discrete optimal transport for decentralized resource matching,” _IEEE Transactions on Signal and Information Processing over Networks_ , vol. 5, no. 3, pp. 511–524, 2019.
  * [6] S. Boyd, N. Parikh, and E. Chu, _Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers_. Now Publishers, 2011.
  * [7] M. Azaiez and V. M. Bier, “Optimal resource allocation for security in reliability systems,” _European Journal of Operational Research_ , vol. 181, no. 2, pp. 773–786, 2007.
  * [8] M. M. Khalili, X. Zhang, and M. Liu, “Resource pooling for shared fate: Incentivizing effort in interdependent security games through cross-investments,” _IEEE Transactions on Control of Network Systems_ , 2020\.
  * [9] L. Huang and Q. Zhu, “Adaptive strategic cyber defense for advanced persistent threats in critical infrastructure networks,” _ACM SIGMETRICS Performance Evaluation Review_ , vol. 46, no. 2, pp. 52–56, 2019.
  * [10] W. Xing, X. Zhao, T. Basar, and W. Xia, “Security investment in cyber-physical systems: Stochastic games with asymmetric information and resource constrained players,” _IEEE Transactions on Automatic Control_ , vol. 67, no. 10, pp. 5384–5391, 2022.
  * [11] R. Yang, C. Kiekintveld, F. Ordóñez, M. Tambe, and R. John, “Improving resource allocation strategies against human adversaries in security games: An extended study,” _Artificial Intelligence_ , vol. 195, pp. 440–469, 2013\.
  * [12] M. Abdallah, P. Naghizadeh, T. Cason, S. Bagchi, and S. Sundaram, “Protecting assets with heterogeneous valuations under behavioral probability weighting,” in _IEEE Conference on Decision and Control_ , 2019.
  * [13] H. He, A. Chen, M. Yin, Z. Ma, J. You, X. Xie, Z. Wang, and Q. An, “Optimal allocation model of water resources based on the prospect theory,” _Water_ , vol. 11, no. 6, p. 1289, 2019.
  * [14] P. Vamvakas, E. E. Tsiropoulou, and S. Papavassiliou, “Exploiting prospect theory and risk-awareness to protect uav-assisted network operation,” _EURASIP Journal on Wireless Communications and Networking_ , vol. 2019, no. 1, pp. 1–20, 2019.
  * [15] W. Tian, M. Du, X. Ji, G. Liu, Y. Dai, and Z. Han, “Honeypot detection strategy against advanced persistent threats in industrial Internet of things: a prospect theoretic game,” _IEEE Internet of Things Journal_ , vol. 8, no. 24, pp. 17 372–17 381, 2021.
  * [16] Z. Xiong, S. Feng, D. Niyato, P. Wang, and Z. Han, “Optimal pricing-based edge computing resource management in mobile blockchain,” in _IEEE International Conference on Communications (ICC)_ , 2018, pp. 1–6.
  * [17] J. Hughes and J. Chen, “Fair and distributed dynamic optimal transport for resource allocation over networks,” in _55th Annual Conference on Information Sciences and Systems (CISS)_ , 2021.
  * [18] ——, “Resilient and distributed discrete optimal transport with deceptive adversary: A game-theoretic approach,” in _IEEE Control System Letters_ , 2022, pp. 1166–1171.
  * [19] M. J. Farooq and Q. Zhu, “Adaptive and resilient revenue maximizing dynamic resource allocation and pricing for cloud-enabled iot systems,” in _American Control Conference (ACC)_ , 2018, pp. 5292–5297.
  * [20] D. Prelec, “The probability weighting function,” _Econometrica_ , vol. 66, no. 3, pp. 497–527, 1998.

###  -A Proof of Lemma 1

Here, we show that the second derivative of $w(p_{x}(\Pi_{x}))$ with respect
to $\pi_{xy}$, $\forall y\in\mathcal{Y}_{x}$, is positive. Using the
probability function in (2), we have

$\displaystyle\frac{\partial^{2}w(p_{x}(\Pi_{x}))}{\partial\pi_{xy}^{2}}=-\gamma(\gamma-1)(-\log(p_{x}(\Pi_{x})))^{\gamma-2}w(p_{x}(\Pi_{x}))$
$\displaystyle\cdot\left(\frac{\partial
p_{x}(\Pi_{x})}{\partial\pi_{xy}}\Big{/}p_{x}(\Pi_{x})\right)^{2}+\gamma(-\log(p_{x}(\Pi_{x})))^{\gamma-1}w(p_{x}(\Pi_{x}))$
$\displaystyle\cdot\frac{p_{x}(\Pi_{x})\cdot\frac{\partial^{2}p_{x}(\Pi_{x})}{\partial\pi_{xy}^{2}}-\big{(}\frac{\partial
p_{x}(\Pi_{x})}{\partial\pi_{xy}}\big{)}^{2}}{(p_{x}(\Pi_{x}))^{2}}+\Big{(}\gamma(-\log(p_{x}(\Pi_{x})))^{\gamma-1}$
$\displaystyle\cdot\frac{\partial
p_{x}(\Pi_{x})}{\partial\pi_{xy}}\Big{/}p_{x}(\Pi_{x})\Big{)}^{2}w(p_{x}(\Pi_{x})).$

The first and third terms multiply out to be positive, because of Assumption
1. The second term may or may not be positive depending on
$(p_{x}(\Pi_{x})\cdot\frac{\partial^{2}p_{x}(\Pi_{x})}{\partial\pi_{xy}^{2}}-\big{(}\frac{\partial
p_{x}(\Pi_{x})}{\partial\pi_{xy}}\big{)}^{2})/(p_{x}(\Pi_{x}))^{2}$. If the
second term term is positive than the second derivative is positive and thus
the function is convex. If the term is negative we need to show that:

$\displaystyle\Big{[}-\gamma(\gamma-1)(-\log(p_{x}(\Pi_{x})))^{\gamma-2}\left(\frac{\partial
p_{x}(\Pi_{x})}{\partial\pi_{xy}}\Big{/}p_{x}(\Pi_{x})\right)^{2}$
$\displaystyle+\Big{(}\gamma(-\log(p_{x}(\Pi_{x})))^{\gamma-1}\cdot\frac{\partial
p_{x}(\Pi_{x})}{\partial\pi_{xy}}\Big{/}p_{x}(\Pi_{x})\Big{)}^{2}\Big{]}$
$\displaystyle\cdot
w(p_{x}(\Pi_{x}))>\gamma(-\log(p_{x}(\Pi_{x})))^{\gamma-1}w(p_{x}(\Pi_{x}))$
$\displaystyle\cdot\frac{p_{x}(\Pi_{x})\cdot\frac{\partial^{2}p_{x}(\Pi_{x})}{\partial\pi_{xy}^{2}}-\big{(}\frac{\partial
p_{x}(\Pi_{x})}{\partial\pi_{xy}}\big{)}^{2}}{(p_{x}(\Pi_{x}))^{2}}.$

With cancellation and some algebraic manipulation, it is easy to see that the
statement is true. Thus, the objective function is strictly convex.