# Improving Entity Linking through Semantic Reinforced
Entity Embeddings

Feng Hou♯†, Ruili Wang♯†, Jun He‡, Yi Zhou♮†
♯School of Computer and Information Engineering, Zhejiang Gongshang
University, Hangzhou, China
†School of Natural and Computational Sciences, Massey University, New Zealand
‡School of Information Communication, National University of Defense
Technology, China
♮Shanghai Research Center for Brain Science and Brain-Inspired Intelligence,
Zhangjiang Lab, China
{f.hou<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>Corresponding author

###### Abstract

Entity embeddings, which represent different aspects of each entity with a
single vector like word embeddings, are a key component of neural entity
linking models. Existing entity embeddings are learned from canonical
Wikipedia articles and local contexts surrounding target entities. Such entity
embeddings are effective, but too distinctive for linking models to learn
contextual commonality. We propose a simple yet effective method, FGS2EE, to
inject fine-grained semantic information into entity embeddings to reduce the
distinctiveness and facilitate the learning of contextual commonality. FGS2EE
first uses the embeddings of semantic type words to generate semantic
embeddings, and then combines them with existing entity embeddings through
linear aggregation. Extensive experiments show the effectiveness of such
embeddings. Based on our entity embeddings, we achieved new state-of-the-art
performance on entity linking.

##  1 Introduction

Entity Linking (EL) or Named Entity Disambiguation (NED) is to automatically
resolve the ambiguity of entity mentions in natural language by linking them
to concrete entities in a Knowledge Base (KB). For example, in Figure 1,
mentions “Congress” and “Mr. Mueller” are linked to the corresponding
Wikipedia entries, respectively.

Figure 1: Entity linking with embedded fine-grained semantic types

Neural entity linking models use local and global scores to rank and select a
set of entities for mentions in a document. Entity embeddings are critical for
the local and global score functions. But the current entity embeddings (Ganea
and Hofmann, 2017) encoded too many details of entities, thus are too
distinctive for linking models to learn contextual commonality.

We hypothesize that fine-grained semantic types of entities can let the
linking models learn contextual commonality about semantic relatedness. For
example, rugby related documents would have entities of rugby player and rugby
team. If a linking model learns the contextual commonality of rugby related
entities, it can correctly select entities of similar types using the similar
contextual information.

In this paper, we propose a method FGS2EE to inject fine-grained semantic
information into entity embeddings to reduce the distinctiveness and
facilitate the learning of contextual commonality. FGS2EE uses the word
embeddings of semantic words that represent the hallmarks of entities (e.g.,
writer, carmaker) to generate semantic embeddings. We find that the training
converges faster when using semantic reinforced entity embeddings.

Our proposed FGS2EE consists of four steps: (i) creating a dictionary of fine-
grained semantic words; (ii) extracting semantic type words from each entity’s
Wikipedia article; (iii) generating semantic embedding for each entity; (iv)
combining semantic embeddings with existing embeddings through linear
aggregation.

##  2 Background and Related Work

###  2.1 Local and Global Score for Entity Linking

The local score $\Psi(e_{i},c_{i})$ (Ganea and Hofmann, 2017) measures the
relevance of entity candidates of each mention independently.

$\Psi(e_{i},c_{i})=\mathbf{e}^{\top}_{i}\mathbf{B}\ f(c_{i})$

where $\mathbf{e}_{i}\in\mathbb{R}^{d}$ is the embedding of candidate entity
$e_{i}$; $\mathbf{B}\in\mathbb{R}^{d\times d}$ is a diagonal matrix;
$f(c_{i})\in\mathbb{R}^{d}$ is a feature representation of local context
$c_{i}$ surrounding mention $m_{i}$.

In addition to the local score, the global score adds a pairwise score
$\Phi(e_{i},e_{j},D)$ to take the coherence of entities in document $D$ into
account.

$\Phi(e_{i},e_{j},D)=\frac{1}{n-1}\mathbf{e}_{i}^{\top}\mathbf{C}\
\mathbf{e}_{j}$

where $\mathbf{e}_{i}$ and $\mathbf{e}_{j}\in\mathbb{R}^{d}$ are the
embeddings of entities $e_{i}$, $e_{j}$, which are candidates for mention
$m_{i}$ and $m_{j}$ respectively; $\mathbf{C}\in\mathbb{R}^{d\times d}$ is a
diagonal matrix. The pairwise score of (Le and Titov, 2018) considers $K$
relations between entities.

$\Phi(e_{i},e_{j},D)=\sum\limits_{k=1}^{K}\alpha_{ijk}\
\mathbf{e}_{i}^{\top}\mathbf{R}_{k}\ \mathbf{e}_{j}$

where $\alpha_{ijk}$ is the weight for relation $k$, and $\mathbf{R}_{k}$ is a
diagonal matrix for measuring relations $k$ between two entities.

###  2.2 Related Work

Our research focuses on improving the vector representations of entities
through fine-grained semantic types. Related topics are as follows.

Entity Embeddings Similar to word embeddings, entity embeddings are the vector
representations of entities. The methods of Yamada et al. (2016), Fang et al.
(2016), Zwicklbauer et al. (2016), use data about entity-entity co-occurrences
to learn entity embeddings and often suffer from sparsity of co-occurrence
statistics. Ganea and Hofmann (2017) learned entity embeddings using words
from canonical Wikipedia articles and local context surrounding anchor links.
They used Word2Vec vectors (Mikolov et al., 2013) of positive words and random
negative words as input to the learning objective. Thus their entity
embeddings are aligned with the Word2Vec word embeddings.

Fine-grained Entity Typing Fine-grained entity typing is a task of classifying
entities into fine-grained types (Ling and Weld, 2012) or ultra fine-grained
semantic labels (Choi et al., 2018). Bhowmik and de Melo (2018) used a memory-
based network to generate a short description of an entity, e.g. “Roger
Federer” is described as ‘Swiss tennis player’. In this paper, we
heuristically extract fine-grained semantic types from the first sentence of
Wikipedia articles.

Embeddings Aggregation Our research is closely related to the work on
aggregation and evaluation of the information content of embeddings from
different sources (e.g., polysemous words have multiple sense embeddings), and
fusion of multiple data sources Wang et al. (2018). Arora et al. (2018)
hypothesizes that the global word embedding is a linear combination of its
sense embeddings. They showed that senses can be recovered through sparse
coding. Mu et al. (2017) showed that senses and word embeddings are linearly
related and sense sub-spaces tend to intersect over a line. Yaghoobzadeh et
al. (2019) probe the aggregated word embeddings of polysemous words for
semantic classes. They created a WIKI-PSE corpus, where word and semantic
class pairs are annotated using Wikipedia anchor links, e.g., “apple” has two
semantic classes: food and organization. A separate embedding for each
semantic class was learned based on the WIKI-PSE corpus. They found that the
linearly aggregated embeddings of polysemous words represent well their
semantic classes.

The most similar work is that of Gupta et al. (2017), but there are many
differences: (i) they use the FIGER (Ling and Weld, 2012) type taxonomy that
contains manually curated 112 types organized into 2 levels; we employ over
3000 vocabulary words as type, and we treat them as a flat list; (ii) they
mapped the Freebase types to FIGER types,but this method is less credible, as
noted by Daniel Gillick et al. (2014); we extract type words directly from
Wikipedia articles, which is more reliable. (iii) their entity vectors and
type vectors are learned jointly on a limited corpus. Ours are linear
aggregations of existing entity vectors, and word vectors learned from a large
corpus, such fine-grained semantic word embeddings are helpful for capturing
informative context.

###  2.3 Motivation

Coarse-grained semantic types (e.g. person) have been used for candidate
selection (Ganea and Hofmann, 2017). We observe that fine-grained semantic
words appear frequently as apposition (e.g., Defense contractor Raytheon),
coreference (e.g., the company) or anonymous mentions (e.g., American defense
firms). These fine-grained types of entities can help capture local contexts
and relations of entities.

Some of these semantic words have been used for learning entity embeddings,
but they are diluted by other unimportant or noisy words. We reinforce entity
embeddings with such fine-grained semantic types.

##  3 Extracting Fine-grained Semantic Types

We first create a dictionary of fine-grained semantic types, then we extract
fine-grained types for each entity.

###  3.1 Semantic Type Dictionary

We select those words that can encode the hallmarks of individual entities.
Desiderata are as follows:

  * •

profession/subject, e.g., footballer, soprano, biology, rugby.

  * •

title, e.g., president, ceo, head, director.

  * •

industry/genre, e.g., carmaker, manufacturer, defense contractor, hip hop.

  * •

geospatial, e.g., canada, asian, australian.

  * •

ideology/religion, e.g., communism, buddhism.

  * •

miscellaneous, e.g., book, film, tv, ship, language.

We extract noun frequency from the first sentence of each entity in the
Wikipedia dump. Then some seed words are manually selected from frequent
nouns. We use word similarity to extend these seed words and finally got a
dictionary with 3,227 fine-grained semantic words.

Specifically, we use spaCy to compute the similarity between words. For each
seed word, we find the top 100 similar words that also appear in Wikipedia
articles. We then manually select semantic words from these extended words.

###  3.2 Extracting Semantic Types

For each entity, we extract at most 11 dictionary words (phrases) from its
Wikipedia article. For example, “Robert Mueller” in Figure 1 will be typed as
[american, lawyer, government, official, director].

###  3.3 Remapping Semantic Words

For some semantic words (e.g., conchologist) or semantic phrases (e.g., rugby
league), there are no word embeddings available for generating the semantic
entity embeddings. We remap these semantic words to semantically similar words
that are more common. For example, the conchologist is remapped to zoologist,
and rugby league is remapped to rugby_league.

##  4 FGS2EE: Injecting Fine-Grained Semantic Information into Entity
Embeddings

FGS2EE first uses semantic words of each entity to generate semantic entity
embeddings, then combine them with existing entity embeddings to generate
semantic reinforced entity embeddings.

###  4.1 Semantic Entity Embeddings

Based on the semantic words of each entity, we can produce a semantic entity
embedding. We treat each semantic word as a sense of an entity. The embedding
of each sense is represented by the Word2Vec embedding of the semantic word.
Suppose we only consider $T$ semantic words for each entity, and the set of
entity words of entity $e$ is denoted as $S_{e}$. Then the semantic entity
embedding $\mathbf{e}^{s}$ of entity $e$ is generated as follows:

$\mathbf{e}^{s}=\frac{1}{T}\sum\limits^{T}_{i=1}\mathbf{e}_{w_{i}}$ (1)

where $w_{i}\in S_{e}$ is the $i$th semantic word, $\mathbf{e}_{w_{i}}$ is the
Word2Vec embedding111https://code.google.com/archive/p/word2vec/ of semantic
word $w_{i}$. If $|S_{e}|<T$, then $T=|S_{e}|$.

Entity Embeddings | Linking Methods | AIDA-B | MSNBC | AQUAINT | ACE2004 | CWEB | WIKI | Avg
---|---|---|---|---|---|---|---|---
Wikipedia |  |  |  |  |  |  |
- | (Milne and Witten, 2008) | - | 78 | 85 | 81 | 64.1 | 81.7 | 77.96
- | (Ratinov et al., 2011) | - | 75 | 83 | 82 | 56.2 | 67.2 | 72.68
- | (Hoffart et al., 2011) | - | 79 | 56 | 80 | 58.6 | 63 | 67.32
- | (Cheng and Roth, 2013) | - | 90 | 90 | 86 | 67.5 | 73.4 | 81.38
- | (Chisholm and Hachey, 2015) | 84.9 | - | - | - | - | - | -
Wiki + Unlabelled documents |  |  |  |  |  |  |
- | (Lazic et al., 2015) | 86.4 | - | - | - | - | - | -
(Ganea and Hofmann, 2017) | (Le and Titov, 2019) | 89.66$\pm$0.16 | 92.2$\pm$0.2 | 90.7$\pm$0.2 | 88.1$\pm$0.0 | 78.2$\pm$0.2 | 81.7$\pm$0.1 | 86.18
$T=6,\alpha=0.1$ | (Le and Titov, 2019) | 89.58$\pm$0.2 | 92.3$\pm$0.1 | 90.93$\pm$0.2 | 87.88$\pm$0.17 | 78.47$\pm$0.11 | 81.71$\pm$0.21 | 86.26
$T=11,\alpha=0.2$ | (Le and Titov, 2019) | 89.23$\pm$0.31 | 92.15$\pm$0.24 | 91.22$\pm$0.18 | 88.02$\pm$0.15 | 78.29$\pm$0.17 | 81.92$\pm$0.36 | 86.32
Wiki + Extra supervision |  |  |  |  |  |  |
- | (Chisholm and Hachey, 2015) | 88.7 | - | - | - | - | - | -
Fully-supervised(Wiki+ AIDA train) |  |  |  |  |  |  |
- | (Guo and Barbosa, 2018) | 89.0 | 92 | 87 | 88 | 77 | 84.5 | 85.7
- | (Globerson et al., 2016) | 91.0 | - | - | - | - | - | -
(Yamada et al., 2016) | (Yamada et al., 2016) | 91.5 | - | - | - | - | - | -
(Ganea and Hofmann, 2017) | (Ganea and Hofmann, 2017) | 92.22$\pm$0.14 | 93.7$\pm$0.1 | 88.5$\pm$0.4 | 88.5$\pm$0.3 | 77.9$\pm$0.1 | 77.5$\pm$0.1 | 85.22
(Ganea and Hofmann, 2017) | (Le and Titov, 2018) | 93.07$\pm$0.27 | 93.9$\pm$0.2 | 88.3$\pm$0.6 | 89.9$\pm$0.8 | 77.5$\pm$0.1 | 78.0$\pm$0.1 | 85.5
(Ganea and Hofmann, 2017) | DCA (Yang et al., 2019) | 93.73$\pm$0.2 | 93.80$\pm$0.0 | 88.25$\pm$0.4 | 90.14$\pm$0.0 | 75.59$\pm$0.3 | 78.84$\pm$0.2 | 85.32
$T=6,\alpha=0.1$ | (Le and Titov, 2018) | 92.29$\pm$0.21 | 94.1$\pm$0.24 | 88.0$\pm$0.38 | 90.14$\pm$0.32 | 77.23$\pm$0.18 | 77.16$\pm$0.43 | 85.33
$T=11,\alpha=0.2$ | (Le and Titov, 2018) | 92.63$\pm$0.14 | 94.26$\pm$0.17 | 88.47$\pm$0.23 | 90.7$\pm$0.28 | 77.41$\pm$0.21 | 77.66$\pm$0.23 | 85.7
Table 1: F1 scores on six test sets. The last column is the average of F1
scores on the five out-domain test sets.

###  4.2 Semantic Reinforced Entity Embeddings

We create a semantic reinforced embedding for each entity by linearly
aggregating the semantic entity embeddings and Word2Vec style entity
embeddings (Ganea and Hofmann, 2017) (hereafter referred to as “Wikitext
entity embeddings”).

Our semantic entity embeddings tend to be homogeneous. If we average them with
the Wikitext embeddings, the aggregated embeddings would be homogeneous too.
Thus the entity linking model would not be able to distinguish between those
similar candidates. Our semantic reinforced entity embedding is a weighted sum
of semantic entity embedding and Wikitext entity embedding, similar to
(Yaghoobzadeh et al., 2019). We use a parameter $\alpha$ to control the weight
of semantic entity embeddings. Thus the aggregated (semantic reinforced)
entity embeddings achieve a trade-off between homogeneity and heterogeneity.

$\mathbf{e}^{a}=(1-\alpha)\ \mathbf{e}^{w}+\alpha\ \mathbf{e}^{s}$ (2)

where $\mathbf{e}^{w}$ is the Wikitext entity embedding of entity $e$.

##  5 Experiments

###  5.1 Datasets and Evaluation Metric

We use the Wikipedia dump 20190401 to extract fine-grained semantic type
dictionary and semantic types for entities. We use the Wikitext entity
embeddings shared by Le and Titov (2018, 2019). For entity linking corpora, we
use the datesets shared by Ganea and Hofmann (2017) and Le and Titov (2018,
2019).

We use the standard micro F1-score as evaluation metric. Our data and source
code are publicly available at github 222https://github.com/fhou80/EntEmb/.

###  5.2 Experimental Settings

The parameters $T$ in Equation (1) and $\alpha$ in Equation (2) are critical
for the effectiveness of our semantic reinforced entity embeddings. We got two
sets of entity embeddings with two combinations of parameters:
$T=6,\alpha=0.1$ and $T=11,\alpha=0.2$

To test the effectiveness of our semantic reinforced entity embeddings, we use
the entity linking models mulrel (Le and Titov, 2018) (ment-norm $K=3$) and
wnel (Le and Titov, 2019) that are publicly available. We do not optimize
their entity linking code. We just replace the entity embeddings with our
semantic reinforced entity embeddings.

Similar to Ganea and Hofmann (2017) and Le and Titov (2018, 2019), we run our
system 5 times for each combination of entity embeddings and linking model,
and report the mean and 95% confidence interval of the micro F1 score.

###  5.3 Results

Figure 2: Learning curves of mulrel (Le and Titov, 2018) using two different
sets of entity embeddings. Figure 3: T-SNE visualization of two sets of entity
embeddings. Suffix “_wiki” denotes the Wikitext entity embeddings, while
suffix “_sri” denotes the semantic reinforced entity embeddings
($T=11,\alpha=0.2$).

The results on six testing datasets are shown in Table 1. For the mulrel
model, our entity embeddings ($T=11,\alpha=0.2$) improved performance
drastically on MSNBC, ACE2004 and average of out-domain test sets. Be aware
that CWEB and WIKI are believed to be less reliable (Ganea and Hofmann, 2017).
For the wnel model, our both sets of entity embeddings are more effective for
four of the five out-domain test sets and the average.

Our entity embeddings are better than that of Ganea and Hofmann (2017) when
tested on the mulrel (Le and Titov, 2018) (ment-norm $K=3$) and wnel (Le and
Titov, 2019) entity linking models. Ganea and Hofmann (2017) showed that their
entity embeddings are better than that of Yamada et al. (2016) using the
entity relatedness metrics.

One notable thing for our semantic reinforced entity embeddings is that the
training using our entity embeddings converges much faster than that using
Wikitext entity embeddings, as shown in Figure 2. One reasonable explanation
is that the fine-grained semantic information lets the linking models capture
the commonality of semantic relatedness between entities and contexts, hence
facilitate the training.

The properties of two different sets of entity embeddings can be visually
manifested in Figure 3. Our semantic reinforced entity embeddings draw
entities of similar types closer, and entities of different types further. For
example, our semantic reinforced embeddings of “John F. Kennedy University”
and “Harvard University” are closer than the Wikitext embeddings, while our
embeddings of “John F. Kennedy International Airport” and “John F. Kennedy”
are further. We believe this property contributes to the faster convergence.

##  6 Conclusion

In this paper, we presented a simple yet effective method, FGS2EE, to inject
fine-grained semantic information into entity embeddings to reduce the
distinctiveness and facilitate the learning of contextual commonality. FGS2EE
first uses the word embeddings of semantic type words to generate semantic
embeddings, and then combines them with existing entity embeddings through
linear aggregation. Our entity embeddings draw entities of similar types
closer, while entities of different types are drawn further. Thus can
facilitate the learning of semantic commonalities about entity-context and
entity-entity relations. We have achieved new state-of-the-art performance
using our entity embeddings.

For the future work, we are planning to extract fine-grained semantic types
from unlabelled documents and use the relatedness between the fine-grained
types and contexts as distant supervision for entity linking.

## References

  * Arora et al. (2018) Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma, and Andrej Risteski. 2018.  Linear algebraic structure of word senses, with applications to polysemy.  _Transactions of the Association for Computational Linguistics_ , 6:483–495.
  * Bhowmik and de Melo (2018) Rajarshi Bhowmik and Gerard de Melo. 2018.  Generating fine-grained open vocabulary entity type descriptions.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics_.
  * Cheng and Roth (2013) Xiao Cheng and Dan Roth. 2013.  Relational inference for wikification.  In _Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing_ , pages 1787–1796.
  * Chisholm and Hachey (2015) Andrew Chisholm and Ben Hachey. 2015.  Entity disambiguation with web links.  _Transactions of the Association for Computational Linguistics_ , 3:145–156.
  * Choi et al. (2018) Eunsol Choi, Omer Levy, Yejin Choi, and Luke Zettlemoyer. 2018.  Ultra-fine entity typing.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics_ , pages 87–96. Association for Computational Linguistics.
  * Daniel Gillick et al. (2014) Daniel Gillick, Nevena Lazic, Kuzman Ganchev, Jesse Kirchner, and David Huynh. 2014.  Contextdependent fine-grained entity type tagging.  _arXiv preprint arXiv:1412.1820_.
  * Fang et al. (2016) Wei Fang, Jianwen Zhang, Dilin Wang, Zheng Chen, and Ming Li. 2016.  Entity disambiguation by knowledge and text jointly embedding.  In _Proceedings of The 20th SIGNLL Conference on Computational Natural Language Learning_ , pages 260–269, Berlin, Germany. Association for Computational Linguistics.
  * Ganea and Hofmann (2017) Octavian-Eugen Ganea and Thomas Hofmann. 2017.  Deep joint entity disambiguation with local neural attention.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 2619–2629, Copenhagen, Denmark. Association for Computational Linguistics.
  * Globerson et al. (2016) Amir Globerson, Nevena Lazic, Soumen Chakrabarti, Amarnag Subramanya, Michael Ringaard, and Fernando Pereira. 2016.  Collective entity resolution with multi-focal attention.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 621–631.
  * Guo and Barbosa (2018) Zhaochen Guo and Denilson Barbosa. 2018.  Robust named entity disambiguation with random walks.  _Semantic Web (Preprint)_ , 9(4):459–479.
  * Gupta et al. (2017) Nitish Gupta, Sameer Singh, and Dan Roth. 2017.  Entity linking via joint encoding of types, descriptions, and context.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 2681–2690, Copenhagen, Denmark. Association for Computational Linguistics.
  * Hoffart et al. (2011) Johannes Hoffart, Mohamed Amir Yosef, Ilaria Bordino, Hagen Fürstenau, Manfred Pinkal, Marc Spaniol, Bilyana Taneva, Stefan Thater, and Gerhard Weikum. 2011\.  Robust disambiguation of named entities in text.  In _Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing_ , pages 782–792. Association for Computational Linguistics.
  * Lazic et al. (2015) Nevena Lazic, Amarnag Subramanya, Michael Ringgaard, and Fernando Pereira. 2015\.  Plato: A selective context model for entity resolution.  _Transactions of the Association for Computational Linguistics_ , 3:503–515.
  * Le and Titov (2018) Phong Le and Ivan Titov. 2018.  Improving entity linking by modeling latent relations between mentions.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1595–1604, Melbourne, Australia. Association for Computational Linguistics.
  * Le and Titov (2019) Phong Le and Ivan Titov. 2019.  Boosting entity linking performance by leveraging unlabeled documents.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 1935–1945, Florence, Italy. Association for Computational Linguistics.
  * Ling and Weld (2012) Xiao Ling and Daniel S. Weld. 2012.  Fine-grained entity recognition.  In _Proceedings of Association for the Advancement of Artificial Intelligence_.
  * Mikolov et al. (2013) Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013.  Distributed representations of words and phrases and their compositionality.  In _Advances in Neural Information Processing Systems_ , pages 3111–3119.
  * Milne and Witten (2008) David Milne and Ian H Witten. 2008.  Learning to link with wikipedia.  In _Proceedings of the 17th ACM conference on Information and knowledge management_ , pages 509–518. ACM.
  * Mu et al. (2017) Jiaqi Mu, Suma Bhat, and Pramod Viswanath. 2017.  Geometry of polysemy.  In _Proceedings of the 5th International Conference on Learning Representations_.
  * Ratinov et al. (2011) Lev Ratinov, Dan Roth, Doug Downey, and Mike Anderson. 2011.  Local and global algorithms for disambiguation to wikipedia.  In _Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1_ , pages 1375–1384. Association for Computational Linguistics.
  * Wang et al. (2018) Ruili Wang, Wanting Ji, Mingzhe Liu, Xun Wang, Jian Weng, Song Deng, Suying Gao, and Chang-an Yuan. 2018.  Review on mining data from multiple data sources.  _Pattern Recognition Letters_ , 109:120–128.
  * Yaghoobzadeh et al. (2019) Yadollah Yaghoobzadeh, Katharina Kann, T. J. Hazen, Eneko Agirre, and Hinrich Schütze. 2019.  Probing for semantic classes: Diagnosing the meaning content of word embeddings.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 5740–5753, Florence, Italy. Association for Computational Linguistics.
  * Yamada et al. (2016) Ikuya Yamada, Hiroyuki Shindo, Hideaki Takeda, and Yoshiyasu Takefuji. 2016.  Joint learning of the embedding of words and entities for named entity disambiguation.  In _Proceedings of The 20th SIGNLL Conference on Computational Natural Language Learning_ , pages 250–259, Berlin, Germany. Association for Computational Linguistics.
  * Yang et al. (2019) Xiyuan Yang, Xiaotao Gu, Sheng Lin, Siliang Tang, Yueting Zhuang, Fei Wu, Zhigang Chen, Guoping Hu, and Xiang Ren. 2019.  Learning dynamic context augmentation for global entity linking.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 271–281, Hong Kong, China. Association for Computational Linguistics.
  * Zwicklbauer et al. (2016) Stefan Zwicklbauer, Christin Seifert, and Michael Granitzer. 2016.  Robust and collective entity disambiguation through semantic embeddings.  In _Proceedings of the 39th International ACM SIGIR conference_ , pages 425–434. ACM.


# Let’s Share VMs: Optimal Placement and Pricing across Base Stations in MEC
Systems

Marie Siew†, Kun Guo†, Desmond Cai§, Lingxiang Li∗, Tony Q.S. Quek† This work
was supported in part by the National Natural Science Foundation of China
under Grants 61901528, 62001254 and 61771263, and in part by the Hunan Natural
Science Foundation under Grant 2020JJ5769. (Corresponding author: Kun Guo).
†Information Systems Technology and Design Pillar, Singapore University of
Technology and Design
§Institute of High Performance Computing, Singapore
$*$University of Electronic Science and Technology of China, China
<EMAIL_ADDRESS><EMAIL_ADDRESS>desmond-
<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

In mobile edge computing (MEC) systems, users offload computationally
intensive tasks to edge servers at base stations. However, with unequal demand
across the network, there might be excess demand at some locations and
underutilized resources at other locations. To address such load-unbalanced
problem in MEC systems, in this paper we propose virtual machines (VMs)
sharing across base stations. Specifically, we consider the joint VM placement
and pricing problem across base stations to match demand and supply and
maximize revenue at the network level. To make this problem tractable, we
decompose it into master and slave problems. For the placement master problem,
we propose a Markov approximation algorithm MAP on the design of a continuous
time Markov chain. As for the pricing slave problem, we propose OPA - an
optimal VM pricing auction, where all users are truthful. Furthermore, given
users’ potential untruthful behaviors, we propose an incentive compatible
auction iCAT along with a partitioning mechanism PUFF, for which we prove
incentive compatibility and revenue guarantees. Finally, we combine MAP and
OPA or PUFF to solve the original problem, and analyze the optimality gap.
Simulation results show that collaborative base stations increases revenue by
up to 50$\%$.

###### Index Terms:

Edge Computing, Network Economics

##  I Introduction

Mobile Edge Computing (MEC) is an enabler of exciting new technologies and
applications like deep learning on devices, virtual and augmented reality, and
smart city data analytics. These exciting new technologies and applications
have high computation requirements. MEC enables them by allowing users to
offload computationally intensive tasks to the network edge (e.g., base
stations in cellular networks and access points in WiFi networks), which are
equipped with computing capability by connecting to the edge servers [1]. With
servers placed at the network edge near the end users, Wide-area-network (WAN)
delay is avoided, allowing it to meet the stringent latency requirements of
delay sensitive tasks, that cloud computing is unable to [2].

Unlike cloud computing, the computational resources at the edge server are
limited. Hence optimizing resource allocation in MEC is an important research
question. In particular, demand for computation is uneven across the network.
Leading to excess demand at some coverage areas, and underutilized resources
at others. In this load-unbalanced scenario, there are users not being served,
and from the network operator’s perspective, resources are not efficiently
utilized and revenue is not maximized. This prompts a global optimization and
organization of resources over the network, to place resources more
effectively in light of the network’s demand pattern.

Virtual machine (VM) migration is perceived as a promising way to solve the
load-unbalanced scenario [3]. There have been works on VM migration in MEC [4,
5, 6, 7, 8]. These works investigate at the level of a single user, in
response to user mobility. In contrast, there has been a lack of work from the
global perspective. To this end, we propose the idea of “Collaborative Base
Stations”, where base stations share their VMs with each other. This involves
the migration of VMs, in accordance with the relative demand across base
stations. In particular, we consider a joint optimization of VM placement and
pricing at base stations to match the demand and supply from the network
level. A joint formulation is used because on one hand, the price at one base
station has an impact on users’ demand, which affects the VM placements. On
the other hand, VM placement determines the resource supply at one base
station. This way, users’ demand will be satisfied as much as possible and the
revenue across the network is maximized.

However, some difficulties arise when solving the formulated joint VM
Migration and Pricing for Profit maximization problem (MPP). Firstly, there is
a sophisticated coupling of the price and VM placement variables, making it
difficult to solve MPP directly. Secondly, MPP is a combinatorial optimization
problem, with the number of VMs deployed at each base station being integers.
It could be intractable, when the number of base stations increases and the
total number of VMs deployed at the edge increases. Thirdly, the pricing at
one base station is affected by the demand and bid information reported by the
user. Users’ potential untruthful behaviors make pricing at base stations
challenging.

To tackle these difficulties, we first use primal decomposition to decouple
the variables, decomposing MPP into the slave problem NP \- Normalized Pricing
problem, and master problem VP \- VM Placement problem. Next, we propose an
online Markov approximation enabled algorithm which solves the combinatorial
VP in a distributed manner. This helps to deal with the potential
intractability when the problem size gets large. It does so by modelling the
different VM configurations as states of a Continuous Time Markov Chain
(CTMC). The VM migrations happen according to the transition rate of the CTMC,
which is in turn dependent on the performance level (revenue) of the placement
configurations. How is the revenue of the VM placement configurations
obtained? We solve NP to obtain the optimal revenue for each placement
configuration. Specifically, at each base station we conduct either OPA - the
Optimal Pricing Auction, or iCAT - an incentive CompAtible Truthful auction,
which ensures users are truthful. iCAT guarantees the revenue $R$, when $R$ is
less than or equal to the optimal. To successfully estimate $R$, we further
present a user partitioning mechanism. The results of the auction will be fed
back to the base station and network operator, directly influencing the
transition rates of the CTMC.

Our contributions are summarized as follows:

  * •

To deal with unequal demand across the MEC coverage areas, we formulate a
joint VM migration and pricing problem across base stations to match demand
and supply at the network level. This works towards ensuring that user demand
is met, resource placement is optimized globally, and the operator’s revenue
is maximized.

  * •

Due to 1) the combinatorial nature of the problem, 2) the coupling of price
and placement variables, and 3) users having the incentive to hide their true
valuations, we use primal decomposition to decompose the problem into a master
and slave problem. For the master VM placement problem, we present MAP, a
Markov approximation-enabled algorithm which solves the combinatorial problem
in a distributed manner at individual base stations.

  * •

To solve the pricing problem, we present an optimal pricing auction OPA, and
prove that it is optimal. Besides, as users might have an incentive to hide
their true valuations, we present an incentive compatible auction iCAT, prove
that it is dominant strategy incentive compatible and that its revenue is $R$,
when $R$ is less than or equal to the optimal. To estimate the target $R$, we
present a user partitioning algorithm PUFF, and prove that its competitive
ratio is 4.

  * •

We present the combined algorithm cMAP which solves our original joint VM
placement and pricing problem, with an optimality gap of
$\frac{1}{\beta}\log|\mathbb{V}|$. Following which, we conduct a perturbation
analysis and show that the optimality gap of the stationary distribution
caused by potential perturbations is bounded by
$1-\exp(-2\beta\psi_{\text{max}})$, where $\psi_{\text{max}}$ is the
perturbation error.

  * •

Finally, we provide simulation results which show that our proposed solution
cMAP: MAP \+ OPA converge to optimality, and analyze the impact of $\beta$.
While the performance of cMAP: MAP \+ PUFF is not optimal, it has a
competitive ratio of $4$, as we have proved. Results show that our mechanism
cMAP increases revenue by up to 50$\%$, compared to the baseline where base
stations do not collaborate and VMs are not migrated.

The rest of this paper is organized as follows. In Section II, we introduce
related works. The system model and problem formulation are given in Section
III, which is followed by the optimal VM placement algorithm and the auction
pricing algorithms in Sections IV and V. In Section VI, we give the complete
implementation and analysis. In Section VII we discuss simulations results and
in Section VIII we conclude.

##  II Related Works

There are two mainstream ways to address the load-unbalanced problems for
efficient resource utilization in MEC systems. On this basis we introduce the
related works.

The first way is to optimize users’ task offloading decisions, i.e. whether or
not to offload, and which base station the user offloads to [1, 3]. In this
way, the computing resources at base stations are fixed and the users are
handovered among base stations. For instance, [9, 10, 11] have optimized task
offloading to strike a balance between energy consumption and delay from the
perspective of users. [12] studied the static edge server placement problem.
[13, 14, 15] aimed to maximize the network revenue through task offloading.

This paper considers an alternative way, in which the computing resources are
migrated among base stations to serve the associated users. Particularly, VM
migration in MEC draws attention in industry and academic fields [3, 16, 17].
(Note that while there has been work on VM placement or migration for revenue
maximization in clouds [18, 19], these works are specific with respect to data
center topologies.) Most of the work on VM or service migration in MEC focus
on improving user experience (e.g. reducing delay), in light of user mobility
[4, 5, 6, 8, 7]. For example in [4] Plachy et al. proposed a dynamic VM
placement and communication path selection algorithm. In [5] Taleb et al.
optimized a policy on the service migration decision, given the user’s
distance. In [6], Ouyang et al. used Lyapunov optimization to optimize the
placements over different timeslots. Another line of research regarding VM
migration looks at how it can maximize network profit or revenue. In [20], Sun
et al. optimized the tradeoff between maximizing the migration gain and
minimizing the migration cost. In this work, we investigate from a novel
perspective. We look at VM migration in MEC at a global level, in light of the
network’s demand patterns, for revenue maximization. And we formulate a joint
VM migration and pricing problem because the price and migration decisions
have a coupled impact on revenue. To the best of our knowledge, we do not know
of many other works which take this approach.

Our proposed incentive compatible auctions and their proofs borrow from, but
are different from the Profit Extractor and Random Sampling Auction in [21,
22]. Profit Extractor and Random Sampling Auction cater to fully digital
goods, with zero marginal cost of producing the next good, and hence an
infinite supply. Unlike this, our network has a limited supply of VMs,
resulting in unique novel algorithms and proofs.

##  III System Model and Problem Formulation

Consider an MEC system with $K$ base stations with heterogeneous computing
capability. Each base station $k$ is equipped with an edge server containing
$v_{k}$ VMs. These are virtualised computing resources which users can offload
their computationally intensive tasks to, at a price of $p_{k}$. Since the
base stations are controlled by the same network operator, these VMs can be
migrated from one base station to another, to optimize the utilization of
resources. This global coordination of resources will help to deal with load-
unbalanced scenarios where there are excess demands in one coverage area, and
underutilized resources in another part of the network.

Each base station $k$ has a set of users $[1,...,i,...,n_{k}]\in U_{k}$ which
are associated with it. Each user $i$ offloads its computationally intensive
tasks to the edge server for auxiliary processing. Different users require
different number of VMs, with user $i$ at base station $k$ requiring $r_{k,i}$
VMs. At base station $k$, different users respond differently to the price
$p_{k}$.

A user $i$ at base station $k$ has willingness to pay $u_{k,i}$. The
willingness to pay can be viewed as the utility a user gets from job
computation using the VM. Different users have different willingness to pay.
For example, a user with a more urgent job would have a higher willingness to
pay than a user who is not as urgent. A user who will execute the job no
matter what, with less regard of the price would have a higher willingness to
pay (e.g., IoT sensors’ periodic data analytics). A user will decide to
execute its job if its payoff $\pi_{k,i}=u_{k,i}-p_{k}$ is non-negative, i.e.
if utility minus payment is greater than 0 $(\pi_{k,i}\geq 0)$. Therefore, the
demand (total number of VM requests) at base station $k$ will be $\sum_{i\in
U_{k}}r_{k,i}\mathds{1}_{\\{u_{k,i}>p_{k}\\}}$, where
$\mathds{1}_{\\{u_{k,i}>p_{k}\\}}$ is the indicator function representing
whether user $i$’s willingness to pay is higher than $p_{k}$.

The demand for VMs at each base station $k$ could be higher or lower than the
supply $v_{k}$. Hence, the network operator would perform a global
optimization of VMs, shifting them to locations with higher demand, to achieve
a higher utilization of resources and to optimize its profit. At the same
time, the network operator sets prices $p_{k}$ differently across coverage
areas, to obtain the highest possible revenue, in light of the varying demand
across the network. The joint Migration and Pricing for Profit maximization
problem (MPP) is as follows:

$\displaystyle\textbf{MPP}:\max_{\textbf{p},\textbf{v}}$
$\displaystyle\quad\sum_{k=1}^{K}p_{k}\min\left\\{\sum_{i\in
U_{k}}r_{k,i}\mathds{1}_{\\{u_{k,i}\geq p_{k}\\}},v_{k}\right\\}$ (1) s.t.
$\displaystyle\quad v_{k}\in\mathbb{Z}_{0}^{+},k=1,...,K$
$\displaystyle\quad\sum_{k=1}^{K}v_{k}=V,$

where $V$ is the total number of VMs, placed by the network operator across
$K$ base stations. Besides, $\mathbb{Z}_{0}^{+}$ indicates the set of non-
negative integers. In MPP, the decision variables are the prices across the
various base stations $\textbf{p}=[p_{1},...,p_{k},...,p_{K}]$, in which each
element is normalized (i.e., $p_{k}\in[0,1]$) without loss of generality, and
the VM placements across the network $\textbf{v}=[v_{1},...,v_{k},...,v_{K}]$.
The objective function is the sum of the revenue obtained across base
stations. In particular, it is the price multiplied by the number of units of
demand which is met with supply.

Some difficulties arise when solving MPP. Firstly, MPP is a combinatorial
optimization problem, with $v_{k}$ being integers. It could be intractable,
when the number of base stations increases and the total number of VMs
increases. Even if we relax $v_{k}$ to continuous values, the problem is still
non-convex. Secondly, there is a coupling of p and v in the objective
function, making it difficult to solve MPP directly.

To tackle the difficulties in solving MPP, firstly we use primal decomposition
[23], such that MPP is decomposed into slave problem NP \- Normalized Pricing
problem, and master problem VP \- VM Placement problem. Specifically, fixing
v, the slave problem is as follows:

$\textbf{NP}:\max_{\textbf{p}}\quad\sum_{k=1}^{K}p_{k}\min\left\\{\sum_{i\in
U_{k}}r_{k,i}\mathds{1}_{\\{u_{k,i}\geq p_{k}\\}},v_{k}\right\\}.$ (2)

Given the optimal solution from the slave problem, the master problem updates
the VM migration decisions:

$\displaystyle\textbf{VP}:\max_{\textbf{v}}$
$\displaystyle\quad\Phi^{*}_{\textbf{v}}$ (3) s.t.
$\displaystyle\quad\textbf{v}\in\mathbb{V},$

where $\Phi^{*}_{\textbf{v}}$ is the optimal value of NP for the given v and
$\mathbb{V}=\\{\textbf{v}|\sum_{k=1}^{K}v_{k}=V\bigcap
v_{k}\in\mathbb{Z}_{0}^{+},k=1,...,K\\}$ is the set of all possible VM
placements across the network, with size $|\mathbb{V}|$.

Following this, we propose a distributed Markov Approximation implementation
to solve VP. And finally, we propose both optimal and incentive compatible
auction mechanisms to solve NP. We discuss the details in the following
sections.

##  IV The optimal VM placement algorithm

In this section, we will show how we solve the master problem VP.
Particularly, we first reformulate and approximate VP and then, propose a
Markov approximation-enabled algorithm, named MAP \- Markov Approx VM
Placement algorithm.

###  IV-A Reformulating and Approximating VP

The master problem VP can be rewritten as

$\displaystyle\textbf{VP-EQ}:\max_{\pi_{\textbf{v}}}$
$\displaystyle\quad\sum_{\textbf{v}\in\mathbb{V}}\pi_{\textbf{v}}\Phi^{*}_{\textbf{v}}$
(4) s.t. $\displaystyle\quad 0\leq\pi_{\textbf{v}}\leq
1,\forall\textbf{v}\in\mathbb{V}$
$\displaystyle\quad\sum_{\textbf{v}\in\mathbb{V}}\pi_{\textbf{v}}=1,$

where $\pi_{\textbf{v}}$ could be seen as the proportion of time spent in
configuration v.

VP is an NP hard combinatorial optimization problem, and hence challenging to
solve, even for a centralized implementation. Even if we relax $v_{k}$ to
continuous values, the problem is still non-convex. Therefore, we use the log-
sum-exp approximation
$f(\Phi^{*}_{\textbf{v}})=\frac{1}{\beta}\log(\sum_{{\textbf{v}}\in\mathbb{V}}\exp(\beta\Phi^{*}_{\textbf{v}}))$
to approximate VP-EQ. This approximation allows for a distributed
implementation at individual base stations. This is useful when the system
dynamics change - when new users enter, or when users move from coverage area
to area. This approximation is upper bounded by
$\frac{1}{\beta}\log|\mathbb{V}|$, following Proposition 5 [24]:

######  Proposition 1.

For $\beta>0$, we have

$\max_{\emph{{v}}}\Phi^{*}_{\emph{{v}}}\leq\frac{1}{\beta}\log(\sum_{\emph{{v}}\in\mathbb{V}}\exp(\beta\Phi^{*}_{\emph{{v}}}))\leq\max_{\emph{{v}}}\Phi^{*}_{\emph{{v}}}+\frac{1}{\beta}\log|\mathbb{V}|.$
(5)

Therefore,
$\max_{\textbf{v}}\Phi^{*}_{\textbf{v}}=\lim_{\beta\rightarrow\infty}\frac{1}{\beta}\log(\sum_{\textbf{v}\in\mathbb{V}}\exp(\beta\Phi^{*}_{\textbf{v}}))$,
i.e., the approximation tends towards VP-EQ for large $\beta$. As the log-sum-
exp function is a closed and convex function, the conjugate of its conjugate
is itself, and hence we have
$\frac{1}{\beta}\log(\sum_{\emph{{v}}\in\mathbb{V}}\exp(\beta\Phi^{*}_{\emph{{v}}}))=\sum_{\textbf{v}}\pi_{\textbf{v}}\Phi^{*}_{\textbf{v}}-\frac{1}{\beta}\sum_{\textbf{v}}\pi_{\textbf{v}}\log\pi_{\textbf{v}}$,
according to [24, 25]. Therefore the log-sum-exp approximation of VP-EQ is
equivalent to the following problem

$\displaystyle\textbf{VP-approx}:\max_{\pi_{\textbf{v}}}$
$\displaystyle\quad\sum_{\textbf{v}}\pi_{\textbf{v}}\Phi^{*}_{\textbf{v}}-\frac{1}{\beta}\sum_{\textbf{v}}\pi_{\textbf{v}}\log\pi_{\textbf{v}}$
(6) s.t. $\displaystyle\quad 0\leq\pi_{\textbf{v}}\leq
1,\forall\textbf{v}\in\mathbb{V}$
$\displaystyle\quad\sum_{\textbf{v}\in\mathbb{V}}\pi_{\textbf{v}}=1.$

By solving the KKT conditions of VP-approx, the optimal solution is achieved
in Theorem 1.

######  Theorem 1.

The optimal solution to VP-approx is

$\pi_{\emph{{v}}}^{*}=\frac{\exp(\beta\Phi^{*}_{\emph{{v}}})}{\sum_{\emph{{v}}\in\mathbb{V}}\exp(\beta\Phi^{*}_{\emph{{v}}})}.$
(7)

Proof. Let $\lambda$ be the Lagrange multiplier associated with the constraint
$\sum_{\textbf{v}\in\mathbb{V}}\pi_{\textbf{v}}=1$. The Lagrangian of VP-
approx will then be

$L(\pi_{\textbf{v}},\lambda)=\sum_{\textbf{v}\in\mathbb{V}}\pi_{\textbf{v}}\Phi^{*}_{\textbf{v}}-\frac{1}{\beta}\sum_{\textbf{v}\in\mathbb{V}}\pi_{\textbf{v}}\log\pi_{\textbf{v}}-\lambda(\sum_{\textbf{v}\in\mathbb{V}}\pi_{\textbf{v}}-1).$
(8)

Therefore, the KKT conditions will be:

$\displaystyle\Phi_{\textbf{v}}^{*}-\frac{1}{\beta}(\log\pi_{\textbf{v}}^{*}+1)-\lambda=0,\>\forall\textbf{v}\in\mathbb{V},$
(9) $\displaystyle\sum_{\textbf{v}\in\mathbb{V}}\pi_{\textbf{v}}=1,$ (10)
$\displaystyle\lambda\geq 0.$ (11)

Solving the KKT conditions for the primal and dual optimal points
$\pi_{\textbf{v}}^{*}$ and $\lambda^{*}$, we obtain
$\pi_{\textbf{v}}^{*}=\exp(\beta(\Phi_{\textbf{v}}^{*}-\lambda)-1)$. Using the
constraint $\sum_{\textbf{v}\in\mathbb{V}}\pi_{\textbf{v}}=1$, we obtain
$\lambda^{*}=\frac{1}{\beta}\log\sum_{\textbf{v}}\exp(\beta\Phi_{\textbf{v}}^{*}-1)$.
Finally, substituting $\lambda^{*}$ into
$\pi_{\textbf{v}}^{*}=\exp(\beta(\Phi_{\textbf{v}}^{*}-\lambda)-1)$, we obtain
(7). ∎

Therefore, by time-sharing among VM placement configurations according to the
probability distribution $\pi_{\textbf{v}}^{*}$, we are able to solve VP-
approx, and hence VP-EQ, VP, and MPP approximately.

###  IV-B Solving VP: Algorithm design

The idea consists of designing a Markov Chain, in which the state space is the
space of possible VM placement configurations $|\mathbb{V}|$, and the
stationary distribution is $\pi_{\textbf{v}}^{*}$, the optimal solution to VP-
approx. This would allow us to solve the joint VM placement and pricing
problem MPP with an optimality gap of $\frac{1}{\beta}\log|\mathbb{V}|$. To
help us in the construction of the Markov chain, we use the following result
from [25]:

######  Lemma 1.

For any distribution of the form $\pi_{\textbf{v}}^{*}$ in (7), there exists
at least one continuous-time time-reversible ergodic Markov chain whose
stationary distribution is $\pi_{\textbf{v}}^{*}$.

A continuous time-reversible markov chain (CTMC) is completely defined by its
state space and transition rate. We let the state space be the space of
possible VM placement configurations $\mathbb{V}$. The transition rate
$q_{\textbf{vv\textprime}}$ indicates the rate at which the CTMC shifts from
placement configuration v to v´. According to [25], for the CTMC to converge
to stationary distribution $\pi_{\textbf{v}}^{*}$, it needs to satisfy the
following two conditions: 1) Irreducibility, meaning that any two states of
the CTMC are reachable from each other. 2) Satisfaction of the detailed
balanced equation: for any $\textbf{v},\textbf{v}\textprime\in\mathbb{V}$,
$\pi^{*}_{\textbf{v}}q_{\textbf{vv\textprime}}=\pi^{*}_{\textbf{v\textprime}}q_{\textbf{v\textprime
v}}$. In other words,
$\exp(\beta\Phi^{*}_{\textbf{v}})q_{\textbf{vv\textprime}}=\exp(\beta\Phi^{*}_{\textbf{v\textprime}})q_{\textbf{v\textprime
v}}$ based on (7).

Condition 1 can be satisfied because any two states (placement configurations)
are reachable from each other. For Condition 2, let us set
$q_{\textbf{vv\textprime}}=0$ for any two states which involve the migration
of more than one VM from one base station to another. This is done to reduce
the computation required, especially when the network is large. For states
which involve the migration of only one VM, we have

$q_{\textbf{v}\textbf{v}^{\prime}}=\exp(\frac{1}{2}\beta(\Phi^{*}_{\textbf{v}^{\prime}}-\Phi^{*}_{\textbf{v}})).$
(12)

The detailed balance equation will be satisfied. The transition rate
$q_{\textbf{v}\textbf{v}^{\prime}}$ is exponentially proportional to the
performance of the target minus current VM placement configuration. Therefore,
when the performance (optimal revenue) of the target configuration is
relatively higher than the current, there will be a higher transition rate,
and vice versa.

The performance of each configuration v is equivalent to its revenue obtained.
In the next section, we show how to obtain the optimal revenue given a VM
placement configuration v. In particular, we propose auction mechanisms to
solve the slave problem NP. Following which, we will show how the algorithms
solving the master problem VP and slave problem NP are combined to solve the
original problem MPP.

##  V The Auction Pricing Mechanisms

In this section, we show how the slave problem NP can be solved. Specifically,
NP defined in (2), can be decomposed into individual pricing problems for each
base station, where each base station $k$ solves the following problem:

$\textbf{NP-k}:\max_{p_{k}}\quad p_{k}\min\left\\{\sum_{i\in
U_{k}}r_{k,i}\mathds{1}_{\\{u_{k,i}\geq p_{k}\\}},v_{k}\right\\}.$ (13)

NP-k can be solved by an auction. We provide two solutions, firstly OPA \-
Optimal Pricing Auction, which assumes the users are truthful, submitting bids
$b_{k,i}$ equal to their true valuations $u_{k,i}$, and then PUFF \-
Partitioning Users For truthFulness mechanism, which includes an incentive
CompAtible Truthful auction iCAT. Our auction mechanisms are prior free, since
they can be carried out without knowledge on the distribution of users’
valuations $u_{k,i}$ .

###  V-A The Optimal Pricing Auction (OPA)

The mechanics behind OPA are as follows: users submit tuple
$(r_{k,i},b_{k,i})$ to base station $k$, where $r_{k,i}$ is the amount of VMs
requested by user $i$ at base station $k$, and $b_{k,i}$ is the bid indicating
the user’s willingness to pay for one VM. Since all users are truthful, the
bid reported by the user is equal to its valuation (i.e., $b_{k,i}=u_{k,i}$).
At price $p_{k}$, all users with valuation $u_{k,i}\geq p_{k}$ will be willing
to participate in the auction. Then, we prove the optimal price will be
$p_{k}^{*}\in\mathbb{B}_{k}=U_{k}$ in Theorem 2, where $\mathbb{B}_{k}$ and
$U_{k}$ are the set of bids and valuations for users at base station $k$,
respectively.

######  Theorem 2.

When all users are truthful, the optimal price of NP-k, termed as $p_{k}^{*}$,
is found in $\mathbb{B}_{k}=U_{k}$.

Proof. When all users are truthful, we have $\mathbb{B}_{k}=U_{k}$. Then, we
prove that $p_{k}^{*}$ is found in $\mathbb{B}_{k}$.

For the case with $p_{k}>\text{max}_{i\in U_{k}}b_{k,i}=\text{max}_{{i\in
U_{k}}}u_{k,i}$, $\mathds{1}_{\\{b_{k,i}\geq
p_{k}\\}}=\mathds{1}_{\\{u_{k,i}\geq p_{k}\\}}=0$ holds, such that all users
would reject to rent the VMs at base station $k$. Therefore, the revenue
attained at base station $k$ is $\textit{Rev}(p_{k})=p_{k}\min\\{\sum_{i\in
U_{k}}r_{k,i}\mathds{1}_{\\{u_{k,i}\geq p_{k}\\}},v_{k}\\}=0$.

Then, we analyse the case with $p_{k}<\text{max}_{i\in U_{k}}b_{k,i}$.
Rearrange $\mathbb{B}_{k}$ in descending order  and denote the set of ordered
bids by $\\{b_{1},b_{2},...,b_{n_{k}}\\}$, where $b_{i}$ represents the $i$-th
highest bid. Using the fact that $b_{k,i}=u_{k,i}$, we have

$\displaystyle\textit{Rev}(p_{k}=b_{i}-\epsilon)$
$\displaystyle=(b_{i}-\epsilon)\>\min\left\\{\\!\sum_{i\in
U_{k}}r_{k,i}\mathds{1}_{\\{b_{k,i}\geq(b_{i}-\epsilon)\\}},v_{k}\\!\right\\}$
(14) $\displaystyle<b_{i}\>\min\left\\{\sum_{i\in
U_{k}}r_{k,i}\mathds{1}_{\\{b_{k,i}\geq b_{i}\\}},v_{k}\right\\}$
$\displaystyle=\textit{Rev}(p_{k}=b_{i}),$

where $\epsilon<b_{i}-b_{i-1}$, no new users rent the VMs at base station $k$
by changing the price from $p_{k}=b_{i}$ to $p_{k}=b_{i}-\epsilon$, that is,
$\min\left\\{\sum_{i\in
U_{k}}r_{k,i}\mathds{1}_{\\{b_{k,i}\geq(b_{i}-\epsilon)\\}},v_{k}\right\\}=\min\left\\{\sum_{i\in
U_{k}}r_{k,i}\mathds{1}_{\\{b_{k,i}\geq b_{i}\\}},v_{k}\right\\}$ hold. Based
on (14), we thus conclude that $p_{k}^{*}$ lies in $\mathbb{B}_{k}$. ∎

Using this insight that the optimal price belongs to the set of bids, the
structure of our proposed OPA is summarized in Algorithm 1. In detail, after
receiving the tuple $(r_{k,i},b_{k,i})$ from all the users, base station $k$
will sort them into descending order with respect to $b_{k,i}$. For each
unique bid $b_{k,i}$, the platform will set $\bar{p}_{k}=b_{k,i}$, and
calculate the revenue $\textit{Rev}(\bar{p}_{k})=\bar{p}_{k}\min\\{\sum_{i\in
U_{k}}r_{k,i}\mathds{1}_{\\{u_{k,i}\geq\bar{p}_{k}\\}},v_{k}\\}$. Following
which, it will optimize over $\bar{p}_{k}$ and achieve
$p_{k}^{*}=\text{argmax}_{\bar{p}_{k}=b_{k,i},\forall i\in
U_{k}}\textit{Rev}(\bar{p}_{k})$.

Algorithm 1 OPA: Optimal Pricing Auction

1:Input: Tuple $(r_{k,i},b_{k,i}),\forall i\in U_{k}$

2:Sort $(r_{k,i},b_{k,i})$ according to descending order with respect to
$b_{k,i}$.

3:for all unique $b_{k,i}$ do

4: Set $\bar{p}_{k}=b_{k,i}$

5: $\textit{Rev}(\bar{p}_{k})\leftarrow\bar{p}_{k}\min\\{\sum_{i\in
U_{k}}r_{k,i}\mathds{1}_{\\{u_{k,i}\geq\bar{p}_{k}\\}},v_{k}\\}$
$\triangleright$ By Eq. (13)

6:end for

7:Output: $p_{k}^{*}\leftarrow\text{argmax}_{\bar{p}_{k}=b_{k,i},\forall i\in
U_{k}}\textit{Rev}(\bar{p}_{k})$

8:end

###  V-B The Incentive CompAtible Truthful Auction (iCAT)

In reality, users may have an incentive to submit bids unequal to their true
valuations (i.e. $b_{k,i}\neq u_{k,i}$), hoping to achieve a higher payoff.
Therefore, we present incentive compatible auction mechanism iCAT, by which
the user’s dominant strategy is to be truthful.

Given a target revenue $R$, the auction mechanism will post price
$p_{k}=\frac{R}{\min\\{\sum_{i\in U_{k}}r_{k,i},v_{k}\\}}$, where $\sum_{i\in
U_{k}}r_{k,i}$ is the total demand of the users currently in the auction.
Users will decide whether or not to accept the offer by weighing if their
payoff $p_{k}-u_{k,i}$ is not lesser than $0$ (individual rationality met). If
any user $i$ rejects the offer, he is removed from future rounds of the
auction. Then, the set of users in the auction is updated as $U_{k}\leftarrow
U_{k}\setminus\\{i\\}$. The process repeats: base station $k$ obtains the new
demand $\sum_{i\in U_{k}}r_{k,i}$ of users currently in the auction, and
broadcasts the new price $p_{k}=\frac{R}{\min\\{\sum_{i\in
U_{k}}r_{k,i},v_{k}\\}}$. If all users remaining in the auction accept the
offer, they will be the winners, paying the last offer price $p_{k}$.
Therefore, base station $k$ would rent
$\min\\{\sum_{i}r_{k,i}\mathds{1}_{\\{u_{k,i}\geq p_{k}\\}},v_{k}\\}$ units of
VMs to users with bids in the set $U_{k}$ at price
$p_{k}=\frac{R}{\min\\{\sum_{i\in U_{k}}r_{k,i}\mathds{1}_{\\{u_{k,i}\geq
p_{k}\\}},v_{k}\\}}$.

The complete iCAT is summarized in Algorithm 2. The main idea behind this
mechanism is that it prunes the set of auction users until it obtains a set
$U_{k}$ where: the users in $U_{k}$ are willing to pay
$p_{k}=\frac{R}{\min\\{\sum_{i\in U_{k}}r_{k,i},v_{k}\\}}$, the price at which
the base station obtains revenue $R$ given demand $\sum_{i\in U_{k}}r_{k,i}$.
Note that our auction mechanism does not involve the users submitting any bids
$b_{k,i}$. Truthfulness is ensured via the structure of the mechanism, as
proved in Theorem 3. In particular, we prove that iCAT is dominant strategy
incentive compatible, meaning that being truthful gives the users a higher
payoff compared to any other strategy.

Algorithm 2 iCAT: incentive CompAtible Truthful Auction

1:Input: Initialize $U_{k}$, the number of VMs required by user $i$
($r_{k,i}$), and target revenue $R$ at base station $k$.

2:while $U_{k}$ is not empty do

3: Base station $k$ posts price $p_{k}=\frac{R}{\min\\{\sum_{i\in
U_{k}}r_{k,i},v_{k}\\}}$;

4: if $u_{k,i}<p_{k}$ for any user $i\in U_{k}$ then

5: User $i$ rejects to join in the auction;

6: Base station $k$ updates $U_{k}\leftarrow U_{k}\setminus\\{i\\}$;

7: else

8: All users in $U_{k}$ would join in the auction;

9: Exit while loop;

10: end if

11:end while

12:Output: $p_{k}\leftarrow\frac{R}{\min\\{\sum_{i\in
U_{k}}r_{k,i},\>v_{k}\\}}$ and $\textit{Rev}(p_{k})\leftarrow R$ with $U_{k}$
not empty, otherwise, $p_{k}\leftarrow 0$ and $\textit{Rev}(p_{k})\leftarrow
0$.

13:end

######  Theorem 3.

Mechanism iCAT is dominant strategy incentive compatible.

Proof. If a user rejects an offer, he will be out of the auction and unable to
participate in the next round, hence getting a payoff of $0$. Therefore
rejecting $p_{k}$, when $p_{k}<u_{k,i}$, is a dominated strategy.

Likewise, accepting $p_{k}>u_{k,i}$ is a dominated strategy, since prices will
rise the next round. Therefore the dominant strategy for every user $i$ is to
report his true value $u_{k,i}$. ∎

The following theorem provides an optimality guarantee for iCAT. It uses the
benchmark $\text{OptRev}^{\geq
2}(U_{k}^{all})=\text{max}_{p_{k}}\>p_{k}\>\min\\{\sum_{i\in
U_{k}^{all}}r_{k,i}\mathds{1}_{\\{u_{k,i}\geq p_{k}\\}},v_{k}\\}$, which has a
requirement of at least two users being in the market. This is not a serious
constraint in light of the number of users at one base station. Besides, we
use $U_{k}^{all}$ to indicate the initial $U_{k}$ in iCAT, that is, the total
number of users at base station $k$.

######  Theorem 4.

The mechanism iCAT achieves a revenue of $R$ if $\text{OptRev}^{\geq
2}(U_{k}^{all})\geq R$, and a revenue of $0$ otherwise.

Proof. According to Theorem 2, we have

$\text{OptRev}^{\geq 2}(U_{k}^{all})=u_{k,x}^{*}\>\min\left\\{\sum_{i\in
U_{k,x}^{*}}r_{k,i},v_{k}\right\\},$ (15)

for some $u_{k,x}^{*}$ and $U_{k,x}^{*}=\\{i|u_{k,i}\geq u_{k,x}^{*}\\}$.

If $\text{OptRev}^{\geq 2}(U_{k}^{all})>R$, then some $u_{k,x}$ not equal to
$u_{k,x}^{*}$ could be found to obtain a revenue $\textit{Rev}(u_{k,x})$ equal
to $R$. On the contrary, if $\text{OptRev}^{\geq 2}(U_{k}^{all})<R$, by (15)
we will not be able to find any $u_{k,x}$ satisfying
$u_{k,x}\geq\frac{R}{\min\\{\sum_{i\in U_{k}^{all}}r_{k,i},v_{k}\\}}$.
According to line 12 in Algorithm 2, a revenue of 0 is obtained in this case.
Besides, for the case with $\text{OptRev}^{\geq 2}(U_{k}^{all})=R$, the
revenue of $R$ is achieved naturally. ∎

Intuitively, the target revenue $R$ plays a key role in iCAT. How shall the
base station estimate $R$? For truthfulness, we want $R$ to be estimated
independently of the bidders we run auction iCAT on. Hence, we further propose
a partitioning mechanism PUFF \- Partitioning Users For truthFulness, for the
base station to estimate $R$ while preserving truthfulness.

###  V-C Partitioning Users For Truthfulness (PUFF)

The operations of PUFF are as follows: We partition the set of all users into
two sets. Following which, we calculate the optimal revenues $R_{1}$ and
$R_{2}$ for each set. Next, we use the optimal revenues as ’estimates of $R$’
for the opposing set and run iCAT in each set. Note that when the total supply
is less than the total demand, we will run the separate auctions using
$\lfloor v_{k}/2\rfloor$ and $\lceil v_{k}/2\rceil$ number of VMs. The
complete PUFF is summarized in Algorithm 3.

Algorithm 3 PUFF: Partitioning Users For truthFulness Mechanism

1:Input: Initialize $U_{k}$ and the number of VMs required by user $i$
($r_{k,i}$).

2:Randomly partition $U_{k}$ into two sets $S_{1}$ and $S_{2}$ of equal size.

3:if $\sum_{i\in U_{k}}r_{k,i}>v_{k}$ then

4: Calculate $R_{1}=$ optimal revenue of $S_{1}$ given $\lfloor
v_{k}/2\rfloor$ VMs, and $R_{2}=$ optimal revenue of $S_{2}$ given $\lceil
v_{k}/2\rceil$ VMs;

5: Run auction iCAT($S_{1},\lfloor v_{k}/2\rfloor,R_{2}$) on set $S_{1}$, and
iCAT($S_{2},\lceil v_{k}/2\rceil,R_{1}$) on set $S_{2}$.

6:else

7: Calculate $R_{1}=$ optimal revenue of $S_{1}$ given $v_{k}$ VMs, and
$R_{2}=$ optimal revenue of $S_{2}$ given $v_{k}$ VMs.

8: Run auction iCAT($S_{1},v_{k},R_{2}$) on set $S_{1}$, and
iCAT($S_{2},v_{k},R_{1}$) on set $S_{2}$.

9:end if

10:end

In the following theorem, we show that PUFF is truthful.

######  Theorem 5.

Mechanism PUFF is dominant strategy truthful.

Proof. Auction iCAT is truthful when implemented with an $R$ estimated
independently of the users it is run on. ∎

Next, we state a lemma which helps us towards proving lower bounds on the
performance of PUFF.

######  Lemma 2.

The revenue of PUFF is at least $\min(R_{1},R_{2})$.

Proof. Either $R_{1}>R_{2}$, $R_{2}>R_{1}$, or $R_{1}=R_{2}$ holds in the
PUFF. Therefore, at least one auction out of iCAT($S_{1},R_{2}$) and
iCAT($S_{2},R_{1}$) succeeds, i.e. gets a revenue of above 0, giving a revenue
of $\min(R_{1},R_{2},R_{1}+R_{2})$. ∎

Following which, we prove bounds on the optimality gap of PUFF, proving that
its competitive ratio is $4$, in a special case where all users $i$ request
one VM, i.e., $r_{k,i}=1$.

######  Theorem 6.

Assume $r_{k,i}=1$ for all users. Let $Rev$ be the expected revenue of PUFF.
We will have $\frac{\text{Rev}}{\text{OptRev}^{\geq
2}(U_{k}^{all})}\geq\frac{1}{4}$.

Proof. We know from Theorem 2 that $\text{OptRev}^{\geq
2}(U_{k}^{all})=u_{k,x}^{*}\>\min\\{\sum_{i\in U_{k,x}^{*}}r_{k,i},v_{k}\\}$
for some $u_{k,x}^{*}$ and $U_{k,x}^{*}=\\{i|u_{k,i}\geq u_{k,x}^{*}\\}$.  Let
$D=\sum_{i\in U_{k}^{all}}r_{k,i}$ and $S=v_{k}$. Further, we first analyse
the case where $D\geq S$. Given this $u_{k,x}^{*}$, we will have $R_{1}\geq
u_{k,x}\>\min\\{\sum_{i\in U_{k,x}^{*}\cap S_{1}}r_{k,i},\lfloor
v_{k}/2\rfloor\\}$ and $R_{2}\geq u_{k,x}\>\min\\{\sum_{i\in U_{k,x}^{*}\cap
S_{2}}r_{k,i},\lceil v_{k}/2\rceil\\}$. Therefore, we deduce that

$\displaystyle\frac{Rev}{\text{OptRev}^{\geq
2}(U_{k}^{all})}\stackrel{{\scriptstyle(a)}}{{\geq}}\frac{\mathbb{E}[\min(R_{1},R_{2})]}{u_{k,x}^{*}\>\min\\{\sum_{i\in
U_{k,x}^{*}}r_{k,i},v_{k}\\}}$ (16)
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\geq}}\frac{\mathbb{E}[\min(u_{k,x}^{*}\>\min\\{A,\lfloor
v_{k}/2\rfloor\\},u_{k,x}^{*}\>\min\\{B,\lceil
v_{k}/2\rceil\\})]}{u_{k,x}^{*}\>\min\\{\sum_{i\in
U_{k,x}^{*}}r_{k,i},v_{k}\\}}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\geq}}\frac{\min(\lfloor
v_{k}/2\rfloor,\mathbb{E}[\min\\{A,B\\}]}{\min\\{\sum_{i\in
U_{k,x}^{*}}r_{k,i},v_{k}\\}}$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\geq}}\frac{\min\\{\lfloor
v_{k}/2\rfloor,1/4\sum_{i\in U_{k,x}^{*}}r_{k,i}\\}}{\min\\{\sum_{i\in
U_{k,x}^{*}}r_{k,i},v_{k}\\}}\geq\frac{1}{4}.$

In inequality $(b)$, we have $A=\sum_{i\in U_{k,x}^{*}\cap S_{1}}r_{k,i}$ and
$B=\sum_{i\in U_{k,x}^{*}\cap S_{2}}r_{k,i}$. Note that the transition from
inequality $(c)$ to $(d)$ is due to the fact that if we flip $k\geq 2$ coins
(corresponding to partitioning the winners into the 2 sets),
$\mathbb{E}[\min(H,T)]\geq\frac{1}{4}$ [22], Chapter 13.

Likewise, for the case where $D\leq S$, following the same logic we have

$\frac{Rev}{\text{OptRev}^{\geq
2}(U_{k}^{all})}\geq\frac{\min\\{v_{k},1/4\sum_{i\in
U_{k,x}^{*}}r_{k,i}\\}}{\min\\{\sum_{i\in
U_{k,x}^{*}}r_{k,i},v_{k}\\}}\geq\frac{1}{4}.\qed$ (17)

It is emphasized that, iCAT, PUFF and their proofs borrow from, but are
different from the Profit Extractor and Random Sampling Auction in [21, 22].
Profit Extractor and Random Sampling Auction cater to fully digital goods,
with 0 marginal cost of producing the next good, and hence an infinite supply.
Unlike this, our network has a limited supply of VMs, resulting in unique
novel algorithms and proofs.

##  VI Combined Algorithm and Analysis

In this section, we present the combined VM placement and pricing mechanism,
describing its implementation. Next, we analyse its performance, termed cMAP,
and prove bounds on the optimality gap caused by potential perturbations on
$\Phi^{*}_{\textbf{v}}$.

###  VI-A Algorithm Implementation

The distributed and combined Markov Approx VM Placement and Pricing Algorithm
(cMAP) is summarized in Algorithm 4 and works as follows: Each round, we
randomly select a base station. The base station $k$ considers potential
configurations $\textbf{v}^{\prime}$ in which it has gained one VM, or sent
one VM to elsewhere. The network operator obtains the target revenue
$\Phi_{\textbf{v}^{\prime}}$ using OPA,PUFF, or via historical data. The base
station then starts exponential clocks for each of these configurations,
following the transition rate
$q_{\textbf{v}\textbf{v}^{\prime}}\leftarrow\exp(0.5\beta(\Phi^{*}_{\textbf{v}^{\prime}}-\Phi^{*}_{\textbf{v}}))$.
When the performance of the target configuration is relatively higher (or
lower) than the current, there will be a higher (or lower) rate of switching.
The process repeats until convergence to the stationary distribution, the
optimal point of VP-approx. This point approximates the optimal point of MPP
with an optimality gap of $\frac{1}{\beta}\log|\mathbb{V}|$, according to
Proposition 5. Note that due to its distributed nature, our algorithm is able
to handle the dynamic scenarios when new users enter the system, or when users
shift from region to region.

Algorithm 4 cMAP: Combined Markov Approx VM Placement and Pricing Algorithm

1:Input: $V$, the total number of VMs across the network, $\\{U_{k}\\}$, the
set of users across all base stations, and $\\{r_{k,i}\\}$, the number of VMs
required by all users.

2:Initialise a configuration v.

3:Network operator calculates $\Phi^{*}_{\textbf{v}}\leftarrow$
OPA(v,$\\{U_{k}\\}$, $\\{r_{k,i}\\}$) or PUFF(v,$\\{U_{k}\\}$,
$\\{r_{k,i}\\}$);

4:while True do

5: Randomly select a base station $k$.

6: Consider configurations $\textbf{v}^{\prime}$ with $v_{k}\pm 1$ VMs at $k$.

7: for all configurations $\textbf{v}^{\prime}$ do

8: Network operator obtains the target revenue
$\Phi^{*}_{\textbf{v}^{\prime}}\leftarrow$ OPA(v′,$\\{U_{k}\\}$,
$\\{r_{k,i}\\}$) or PUFF(v′,$\\{U_{k}\\}$, $\\{r_{k,i}\\}$);

9: Set clocks with transition rate
$q_{\textbf{v}\textbf{v}^{\prime}}\leftarrow$
$\exp(0.5\beta(\Phi^{*}_{\textbf{v}^{\prime}}-\Phi^{*}_{\textbf{v}}))$;

10: end for

11: The CTMC transits to the next state according to
$q_{\textbf{v}\textbf{v}^{\prime}}$;

12:end while

###  VI-B Algorithm Analysis

Our combined mechanism cMAP attains an optimality gap of
$\frac{1}{\beta}\log|\mathbb{V}|$ for the original problem MPP. In practice,
the system may obtain an inaccurate value of $\Phi_{\textbf{v}}^{*}$, the
optimal revenue under configuration v. This may occur when we implement the
incentive compatible auction mechanism PUFF and estimate $R$.

In light of this we analyse the impact of the perturbations, by bounding the
optimality gap caused by the perturbations, on problem VP-approx. To this end,
we construct a new CTMC which takes into account the perturbations, and
characterize its stationary distribution, in the following.

For each state v with optimal revenue $\Phi_{\textbf{v}}^{*}$, we let
$\overline{\Phi}_{\textbf{v}}$ be its corresponding perturbed inaccurate
revenue. The perturbation error
$\epsilon_{\textbf{v}}=\overline{\Phi}_{\textbf{v}}-\Phi_{\textbf{v}}^{*}$
lies in the range $[-\psi_{\textbf{v}},\psi_{\textbf{v}}]$. For each state v,
we quantize the error into $2a_{\textbf{v}}+1$ potential values
$[-\psi_{\textbf{v}},...,-\psi_{\textbf{v}}/a_{\textbf{v}},0,...,\psi_{\textbf{v}}/a_{\textbf{v}},...,\psi_{\textbf{v}}]$,
where the error
$\epsilon_{\textbf{v}}=\frac{n}{a_{\textbf{v}}}\psi_{\textbf{v}}$ with
probability $\rho_{\textbf{v}_{n}},n=0,\pm 1,..\pm a_{\textbf{v}}$, and
$\sum_{n=-a_{\textbf{v}}}^{a_{\textbf{v}}}\rho_{\textbf{v}_{n}}=1$. This means
that we have constructed a new CTMC in which each state v of the original CTMC
is now expanded into $2a_{\textbf{v}}+1$ states. The transition rate follows
the following equation:

$q_{\textbf{v}_{n}\textbf{v}_{n^{\prime}}^{{}^{\prime}}}=\exp(0.5\beta(\Phi_{\textbf{v}^{\prime}_{n^{\prime}}}^{*}-\Phi_{\textbf{v}_{n}}^{*}))\rho_{\textbf{v}^{\prime}_{n^{\prime}}}.$
(18)

Based on the detailed balanced equation
$\pi_{\textbf{v}_{n}}q_{\textbf{v}_{n}\textbf{v}^{\prime}_{n^{\prime}}}=\pi_{\textbf{v}^{\prime}_{n^{\prime}}}q_{\textbf{v}^{\prime}_{n^{\prime}}\textbf{v}_{n}}$,
we have

$\pi_{\textbf{v}_{n}}\\!\exp(\frac{1}{2}\beta(\Phi_{\textbf{v}^{\prime}_{n^{\prime}}}^{*}-\Phi_{\textbf{v}_{n}}^{*}))\rho_{\textbf{v}^{\prime}_{n^{\prime}}}\\!=\\!\pi_{\textbf{v}^{\prime}_{n^{\prime}}}\\!\exp(\frac{1}{2}\beta(\Phi_{\textbf{v}_{n}}^{*}-\Phi_{\textbf{v}^{\prime}_{n^{\prime}}}^{*}))\rho_{\textbf{v}_{n}},$
(19)

which results in

$\pi_{\textbf{v}_{n}}\exp(\beta\Phi_{\textbf{v}^{\prime}_{n^{\prime}}}^{*})\rho_{\textbf{v}^{\prime}_{n^{\prime}}}=\pi_{\textbf{v}^{\prime}_{n^{\prime}}}\exp(\beta\Phi_{\textbf{v}_{n}}^{*})\rho_{\textbf{v}_{n}}.$
(20)

Because
$\sum_{\textbf{v}^{\prime}\in\mathbb{V}}\sum_{n^{\prime}=-a_{\textbf{v}^{\prime}}}^{a_{\textbf{v}^{\prime}}}\pi_{\textbf{v}^{\prime}_{n^{\prime}}}=1$,
we obtain

$\pi_{\textbf{v}_{n}}=\frac{\exp(\beta\Phi_{\textbf{v}_{n}}^{*})\rho_{\textbf{v}_{n}}}{\sum_{\textbf{v}^{\prime}\in\mathbb{V}}\sum_{n^{\prime}=-a_{\textbf{v}^{\prime}}}^{a_{\textbf{v}^{\prime}}}\exp(\beta\Phi_{\textbf{v}^{\prime}_{n^{\prime}}}^{*})\rho_{\textbf{v}^{\prime}_{n^{\prime}}}}.$
(21)

Letting
$\sigma_{\textbf{v}^{\prime}}=\sum_{n^{\prime}=-a_{\textbf{v}^{\prime}}}^{a_{\textbf{v}^{\prime}}}\rho_{\textbf{v}^{\prime}_{n^{\prime}}}\exp(\beta\frac{n^{\prime}}{a_{\textbf{v}^{\prime}}}\psi_{\textbf{v}^{\prime}})$,
the distribution of the new perturbed CTMC will be

$\overline{\pi}_{\textbf{v}}=\sum_{n=-a_{\textbf{v}}}^{a_{\textbf{v}}}\pi_{\textbf{v}_{n}}=\frac{\sigma_{\textbf{v}}\exp(\beta\Phi^{*}_{\textbf{v}})}{\sum_{\textbf{v}^{\prime}\in\mathbb{V}}\sigma_{\textbf{v}^{\prime}}\exp(\beta\Phi^{*}_{\textbf{v}^{\prime}})}.$
(22)

We use the Total Variation Distance [26, 27] as a metric to quantify the
optimality gap between the stationary distribution of the perturbed CTMC
$\overline{\pi}_{\textbf{v}}$ and $\pi_{\textbf{v}}^{*}$, the optimal solution
of VP-approx, as follows:

$d_{TV}(\pi_{\textbf{v}}^{*},\overline{\pi}_{\textbf{v}})=\frac{1}{2}\sum_{\textbf{v}\in\mathbb{V}}|\pi_{\textbf{v}}^{*}-\overline{\pi}_{\textbf{v}}|.$
(23)

With the stationary distribution of the perturbed CTMC
$\overline{\pi}_{\textbf{v}}$, we use a result in [27], which proved that the
total variation distance is bounded as follows

$d_{TV}(\pi_{\textbf{v}}^{*},\overline{\pi}_{\textbf{v}})\leq
1-\exp(-2\beta\psi_{\text{max}}),$ (24)

where $\psi_{\text{max}}=\text{max}_{\textbf{v}}\psi_{\textbf{v}}$, the
largest perturbation error among states v. The revenue gap is hence bounded as
follows:

$|\pi_{\textbf{v}}^{*}\Phi^{*}_{\textbf{v}}-\overline{\pi}_{\textbf{v}}\overline{\Phi}_{\textbf{v}}|\leq
2\Phi_{\text{max}}(1-\exp(-2\beta\psi_{\text{max}})),$ (25)

where $\Phi_{\text{max}}=\text{max}_{\textbf{v}}\Phi_{\textbf{v}}$.

The upper bound on both the Total Variation Distance between the two
distributions $d_{TV}(\pi_{\textbf{v}}^{*},\overline{\pi}_{\textbf{v}})$ and
the optimality gap
$|\pi_{\textbf{v}}^{*}\Phi^{*}_{\textbf{v}}-\overline{\pi}_{\textbf{v}}\overline{\Phi}_{\textbf{v}}|$
is independent with respect to $\rho_{\textbf{v}_{n}}$, the distribution of
perturbed revenues, and is independent with respect to $|\mathbb{V}|$, the
total number of configurations. This indicates that the optimality gap does
not increase with the network size and number of configurations
$|\mathbb{V}|$. Besides this, using Markov Approximation enables us to perform
a distributed implementation on this large combinatorial problem.

##  VII Simulation Results

In this section, we evaluate the performance of our combined mechanisms cMAP:
MAP (which solves the VM placement problem) along with either OPA or PUFF
(which solve the normalized pricing problem), and provide some insights.

###  VII-A Convergence, and insights on pricing

Firstly, we consider a network in which there are 5 BSs, and 10 VMs being
distributed amongst these 5 BSs. The 5 base stations have $(2,0,2,4,0)$ users
respectively. We set $r_{k,i}$, the number of VMs required by user $i$ at BS
$k$, to be between 1 to 3 VMs. $u_{k,i}$, the willingness to pay of user $i$
at BS $k$, follows uniform distribution $U[0,1]$.

Figure 1: Convergence of the cMAP.

Under this setup, we run cMAP (the combined Markov Approximation VM Placement
Algorithm) along with auction OPA. for different values of $\beta$. We plot
the running average over a window size of $30$ jumps, in comparison with the
optimal value, as seen in Fig 1. The optimal value is obtained by exhaustive
search, evaluating the solution to MPP over all combinations of v. As seen,
for $\beta=50$, we are able to achieve optimality. For $\beta=10$, the
converged stationary distribution over configurations of v is near optimal.
Under $\beta=10$, the top 5 most common states are $\textbf{v}=(2,0,2,5,1)$,
$(2,0,3,5,0)$, $(2,1,2,5,0)$, $(3,0,2,5,0)$, $(2,0,2,6,0)$, which are best
able to meet the total demand of $(2,0,2,4,0)$. Notice that as $\beta$
increases, performance improves: the running average is closer to the optimal
point, and fluctuations decrease. The fluctuations occur because under our
Markov Approximation-inspired algorithm, we converge not to a specific state
of the CTMC, but to a stationary distribution over the states of the CTMC.
Recall that the converged stationary distribution has an optimality gap of
$\frac{1}{\beta}\log|\mathbb{V}|$ from the optimal point of the original
problem VP. This shows that as $\beta\rightarrow\infty$, the performance
converges to the optimal value of VP. A potential tradeoff in having a higher
$\beta$ is: if $\Phi_{\textbf{v}}^{*}>\Phi_{\textbf{v}^{\prime}}^{*}$,
according to (12) there will be a lower rate of switching, and a higher
probability of staying in the current state. As $\beta$ increases, the network
is more likely to stay in the current state. This may lead to a longer time
spent in local minimums, due to the lack of exploration, and hence a longer
convergence time.

Next, with the current setup we compare the performance of our proposed
mechanisms MAP \+ OPA and MAP \+ PUFF to the following baselines:

1) Cooperative BS + Uniform Pricing: Under this scenario, the base stations
are cooperative. They share the VMs with each other, where the VMs are
transferred within the network via our proposed MAP. Unlike our proposed
combined solution, here we use uniform pricing: a common price is set
throughout the network, regardless of the demand pattern. A benefit of uniform
pricing is that it is faster to implement.

2) Non-cooperative BS + Auction: Under this scenario, the base stations are no
longer cooperative - they do not share the VMs with each other. We obtain the
average result under the non-cooperative scenario, by averaging over all the
possible combinations of v. For each configuration v, we use the optimal
auction OPA to obtain $\Phi_{\textbf{v}}^{*}$.

3) Non-cooperative BS + Uniform Pricing: Under this scenario, the base
stations not only do not share the VMs with each other, but also do not
consider the demand pattern, using a common price throughput the network.

Figure 2: The effect of different uniform prices on revenue.

We plot the revenue obtained under the various methods, and show how the
performance varies when different prices are set as the uniform price in Fig.
2. As seen, our proposed algorithms cMAP outperforms the baselines, especially
when OPA is used as the pricing mechanism. While MAP in combination with PUFF
is not near-optimal, we have proved that PUFF has a competitive ratio of $4$.
The baselines involving uniform price perform best when the price is ”neutral”
- neither too low nor too high. If the price is too high, the users (likely
having a lower willingness to pay) would not choose to use the VMs. If the
price is too low, the revenue the network operator obtains will be low. Fig. 2
also shows that resource sharing among base stations increases the revenue.

###  VII-B A larger setup, with insights on willingness to pay and the demand-
supply ratio

Next, we enlarge our setup and compare the performance of our proposed
mechanisms with the different baselines. In this setup, there are 20 VMs
shared amongst the 5 base stations. The number of users at each base station
are randomized, along with $r_{k,i}$, the number of VM units each user
requests. We let the users’ willingness to pay $u_{k,i}$ follow a uniform
distribution $U[a,b]$.

Figure 3: The impact of willingness to pay on revenue.  Figure 4: The impact
of the Demand/Supply ratio on revenue.

In Fig. 3, we show the impact of users’ willingness to pay on the revenue. The
range of $u_{k,i}$ is adjusted, from the uniform distribution $U[0,0.4]$ (low
willingness to pay), to $U[0.2,0.6]$, $U[0.4,0.8]$ and $U[0.6,1]$ (high
willingess to pay). Our propsed solution MAP \+ OPA (with $\beta=10$)
outperforms the baselines, obtaining a near-optimal revenue. Our results show
that on average, having base station cooperation increases the revenue by up
to $53\%$ percent. As seen in Fig. 3, when the users have a higher willingness
to pay, the revenue increases. Notice that uniform pricing ($p=0.5$) does not
perform well, when the users have low willingness to pay.

Fig. 4 illustrates the impact of revenue when the
$\frac{\text{Demand}}{\text{Supply}}$ ratio is varied. Supply is fixed at $20$
VMs, while demand is increased, from $D=7$ (low demand), to $D=21$ (near equal
demand and supply) and high demand $D=38$. Our solution cMAP outperforms the
baselines, especially when demand increases, as the supply of VMs is shifted
around the network to meet demand more effectively, and an optimal auction is
used to extract the highest revenue possible. Our results show that on
average, having base station cooperation increases the revenue by up to
$57\%$. As seen in Fig. 4, as the $\frac{\text{Demand}}{\text{Supply}}$ ratio
increases, revenue increases because more units of demand are being met. Once
the $\frac{\text{Demand}}{\text{Supply}}$ ratio hits 1, revenue no longer
increases much due to the lack of global supply in the system.

##  VIII Conclusions

In this paper, we have addressed the load-unbalanced problem in MEC systems,
by jointly optimizing the VM placement and pricing across base stations.
Specifically, we have formulated a revenue maximization problem from the
network operator’s perspective, which was decomposed to a VM placement master
problem and a normalized pricing slave problem. The objective function of the
master problem is the optimal value of the slave problem. Then, we solved the
master problem by designing a CTMC and solved the slave problem by proposing
auctions considering users’ truthful and untruthful behaviors, respectively.
By combining the algorithms proposed for the master and slave problem, cMAP is
implemented for VM placement and pricing decision making across base stations.
Through theoretical analysis, we give the optimal gap of cMAP, which is nested
with OPA (auction mechanism with users’ truthful behaviors) and PUFF (auction
machanism with users’ untruthful behaviors), respectively. Finally, we
demonstrated the convergence and efficiency of cMAP. For future work we will
analyse the impact of factors like having a heterogeneous cost of VM migration
between base stations.

## References

  * [1] Y. Mao, C. You, J. Zhang, K. Huang, and K. B. Letaief, “A survey on mobile edge computing: The communication perspective,” _IEEE Communications Surveys & Tutorials_, vol. 19, no. 4, pp. 2322–2358, 2017.
  * [2] Y. C. Hu, M. Patel, D. Sabella, N. Sprecher, and V. Young, “Mobile edge computing—a key technology towards 5G.”
  * [3] P. Mach and Z. Becvar, “Mobile edge computing: A survey on architecture and computation offloading,” _IEEE Communications Surveys & Tutorials_, vol. 19, no. 3, pp. 1628–1656, 2017.
  * [4] J. Plachy, Z. Becvar, and E. C. Strinati, “Dynamic resource allocation exploiting mobility prediction in mobile edge computing,” in _2016 IEEE 27th Annual International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC)_. IEEE, 2016, pp. 1–6.
  * [5] A. Ksentini, T. Taleb, and M. Chen, “A markov decision process-based service migration procedure for follow me cloud,” in _2014 IEEE International Conference on Communications (ICC)_. IEEE, 2014, pp. 1350–1354.
  * [6] T. Ouyang, Z. Zhou, and X. Chen, “Follow me at the edge: Mobility-aware dynamic service placement for mobile edge computing,” _IEEE Journal on Selected Areas in Communications_ , vol. 36, no. 10, pp. 2333–2345, 2018.
  * [7] H. Ma, Z. Zhou, and X. Chen, “Leveraging the power of prediction: Predictive service placement for latency-sensitive mobile edge computing,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 10, pp. 6454–6468, 2020\.
  * [8] S. Wang, Y. Guo, N. Zhang, P. Yang, A. Zhou, and X. S. Shen, “Delay-aware microservice coordination in mobile edge computing: A reinforcement learning approach,” _IEEE Transactions on Mobile Computing_ , 2019.
  * [9] Y. Mao, J. Zhang, and K. B. Letaief, “Dynamic computation offloading for mobile-edge computing with energy harvesting devices,” vol. 34, no. 12, pp. 3590–3605, Dec. 2016.
  * [10] X. Chen, L. Jiao, W. Li, and X. Fu, “Efficient multi-user computation offloading for mobile-edge cloud computing,” vol. 24, no. 5, pp. 2795–2808, Oct. 2016.
  * [11] T. Q. Dinh, J. Tang, Q. D. La, and T. Q. Quek, “Offloading in mobile edge computing: Task allocation and computational frequency scaling,” _IEEE Transactions on Communications_ , vol. 65, no. 8, pp. 3571–3584, 2017.
  * [12] Y. Li and S. Wang, “An energy-aware edge server placement algorithm in mobile edge computing,” in _2018 IEEE International Conference on Edge Computing (EDGE)_. IEEE, 2018, pp. 66–73.
  * [13] Q. Wang, S. Guo, J. Liu, C. Pan, and L. Yang, “Profit maximization incentive mechanism for resource providers in mobile edge computing,” _IEEE Transactions on Services Computing_ , pp. 1–1, 2019.
  * [14] Y. Shih, C. Wang, and A. Pang, “Fog computing service provision using bargaining solutions,” _IEEE Transactions on Services Computing_ , pp. 1–1, 2019.
  * [15] A. Kiani and N. Ansari, “Toward hierarchical mobile edge computing: An auction-based profit maximization approach,” _IEEE Internet of Things Journal_ , vol. 4, no. 6, pp. 2082–2091, 2017.
  * [16] Z. Tao, Q. Xia, Z. Hao, C. Li, L. Ma, S. Yi, and Q. Li, “A survey of virtual machine management in edge computing,” _Proceedings of the IEEE_ , vol. 107, no. 8, pp. 1482–1499, 2019.
  * [17] S. Wang, J. Xu, N. Zhang, and Y. Liu, “A survey on service migration in mobile edge computing,” _IEEE Access_ , vol. 6, pp. 23 511–23 528, 2018.
  * [18] J. W. Jiang, T. Lan, S. Ha, M. Chen, and M. Chiang, “Joint VM placement and routing for data center traffic engineering,” in _2012 Proceedings IEEE INFOCOM_. IEEE, 2012, pp. 2876–2880.
  * [19] B. Jennings and R. Stadler, “Resource management in clouds: Survey and research challenges,” _Journal of Network and Systems Management_ , vol. 23, no. 3, pp. 567–619, 2015.
  * [20] X. Sun and N. Ansari, “Primal: Profit maximization avatar placement for mobile edge computing,” in _2016 IEEE International Conference on Communications (ICC)_. IEEE, 2016, pp. 1–6.
  * [21] A. V. Goldberg and J. D. Hartline, “Competitive auctions for multiple digital goods,” in _European Symposium on Algorithms_. Springer, 2001, pp. 416–427.
  * [22] T. Roughgarden, “Algorithmic game theory,” _Communications of the ACM_ , vol. 53, no. 7, pp. 78–86, 2010.
  * [23] D. P. Palomar and M. Chiang, “A tutorial on decomposition methods for network utility maximization,” _IEEE Journal on Selected Areas in Communications_ , vol. 24, no. 8, pp. 1439–1451, Aug. 2006.
  * [24] S. Boyd, S. P. Boyd, and L. Vandenberghe, _Convex optimization_. Cambridge university press, 2004.
  * [25] M. Chen, S. C. Liew, Z. Shao, and C. Kai, “Markov approximation for combinatorial network optimization,” _IEEE transactions on information theory_ , vol. 59, no. 10, pp. 6301–6327, 2013.
  * [26] P. Diaconis and D. Stroock, “Geometric bounds for eigenvalues of markov chains,” _The Annals of Applied Probability_ , pp. 36–61, 1991.
  * [27] S. Zhang, Z. Shao, M. Chen, and L. Jiang, “Optimal distributed P2P streaming under node degree bounds,” _IEEE/ACM Transactions on Networking_ , vol. 22, no. 3, pp. 717–730, 2013.