††thanks:

# Socially-Optimal Mechanism Design for Incentivized Online Learning

Zhiyuan Wang1, Lin Gao24, and Jianwei Huang34  This work is supported by the
National Key R&D Program (NKRDP) of China under Grant 2019YFB1802803. This
work is supported by the Shenzhen Science and Technology Program
(JCYJ20210324120011032), Shenzhen Institute of Artificial Intelligence and
Robotics for Society, and the Presidential Fund from the Chinese University of
Hong Kong, Shenzhen. This work is also supported by the National Natural
Science Foundation of China (Grant No. 61972113), Shenzhen Science and
Technology Program (Grant No. JCYJ20190806112215116, JCYJ20180306171800589,
and KQTD20190929172545139), and Guangdong Science and Technology Planning
Project under Grant 2018B030322004. (Corresponding author: Jianwei Huang.)
1School of Computer Science and Engineering, Beihang University, Beijing,
China  2School of Electronics and Information Engineering, Harbin Institute of
Technology, Shenzhen, China  3School of Science and Engineering, The Chinese
University of Hong Kong, Shenzhen  4Shenzhen Institute of Artificial
Intelligence and Robotics for Society, Shenzhen, China

###### Abstract

Multi-arm bandit (MAB) is a classic online learning framework that studies the
sequential decision-making in an uncertain environment. The MAB framework,
however, overlooks the scenario where the decision-maker cannot take actions
(e.g., pulling arms) directly. It is a practically important scenario in many
applications such as spectrum sharing, crowdsensing, and edge computing. In
these applications, the decision-maker would incentivize other selfish agents
to carry out desired actions (i.e., pulling arms on the decision-maker’s
behalf). This paper establishes the incentivized online learning (IOL)
framework for this scenario. The key challenge to design the IOL framework
lies in the tight coupling of the unknown environment learning and asymmetric
information revelation. To address this, we construct a special Lagrangian
function based on which we propose a socially-optimal mechanism for the IOL
framework. Our mechanism satisfies various desirable properties such as agent
fairness, incentive compatibility, and voluntary participation. It achieves
the same asymptotic performance as the state-of-art benchmark that requires
extra information. Our analysis also unveils the power of crowd in the IOL
framework: a larger agent crowd enables our mechanism to approach more closely
the theoretical upper bound of social performance. Numerical results
demonstrate the advantages of our mechanism in large-scale edge computing.

##  I Introduction

###  I-A Background and Motivation

Online learning has been widely adopted in many practical optimization
problems, where the decision-maker takes sequential actions in an uncertain
environment [1]. Multi-arm bandit (MAB) is one of the extensively studied
online learning frameworks [2]. As shown in Fig. 1(a), the uncertainty in MAB
corresponds to the unknown rewards that can be obtained from a set of arms.
The decision-maker gains reward by pulling an arm in each time slot, based on
its observations of the realized reward from the arms pulled in previous time
slots. The goal is to maximize the cumulative reward over a time horizon. This
framework has a wide range of networking applications, such as wireless
channel access (e.g., [3, 4, 5]), crowdsourcing worker selection (e.g., [6, 7,
8, 9, 10, 11]), and computation task offloading (e.g., [12, 13, 14, 15]).

Despite the wide adoption, the online learning framework misses an important
scenario where the decision-maker is unable to take actions directly. This is
usually due to the fact that the decision-maker lacks the resource required to
take actions. In this scenario, the decision-maker would act as a principle
and incentivize some selfish agents (who have resource) to take actions on his
behalf. The incentives are necessary, since the agents may incur costs when
taking the actions. In this paper, we will refer to this paradigm as the
incentivized online learning (IOL) as shown in Fig. 1(b). Such a principal-
agent interaction widely exists in many real-world applications, such as
spectrum sharing, mobile crowd sensing, and edge computing. We briefly
introduce two motivating examples shown in Table I, and we will provide
detailed demonstration in Section VI.

(a) Online learning framework

(b) IOL framework

Figure 1: Illustration of two frameworks TABLE I: Motivating examples of IOL framework Principal |  Environment (K Arms) | Agents
---|---|---
IoT Operator | $\normalsize\begin{subarray}{c}\text{Sensors}\\\ \textit{(Unknown sensing data)}\end{subarray}$ | Spectrum owners
MCS Platform | $\normalsize\begin{subarray}{c}\text{Locations}\\\ \textit{(Unknown real-time status)}\end{subarray}$ | Mobile users

  * •

Spectrum Sharing: The IoT operator aims to aggregate sensing data from
multiple sensors, but may not have enough spectrum for the sensors to operate
in [16]. The IoT operator could incentivize other spectrum owners to share
their spectrum with the sensors. The IoT operator’s obtained reward depends on
the sensing data amount and quality, which are unknown ex ante. The spectrum
owners perceive cost or disturbance on their own spectrum utilizations when
sharing the spectrum with sensors, and such costs are spectrum owners’ private
information.

  * •

Mobile Crowd Sensing (MCS): The MCS platform relies on mobile users to acquire
the time-varying status of different locations [17]. The acquired status
exhibits different values for the MCS platform, depending on the status
changing and the importance of locations. Mobile users incur private cost when
sensing the status.

Based on the above discussion, let us move on to the IOL framework
optimization.

###  I-B IOL Framework Optimization

The online learning framework in Fig. 1(a) aims to design an algorithm that
maximizes the reward. The IOL framework, however, is much more complicated due
to the principal-agent interaction in Fig. 1(b). Roughly speaking, the IOL
framework requires us to design a mechanism that properly manipulates the
principal-agent interactions, thereby achieving various desirable prosperities
(beyond reward maximization). Next we introduce the properties in our
mechanism design for the IOL framework (or simply IOL mechanism design).

First, the IOL framework in Fig. 1(b) exhibits a novel learning paradigm that
leverages the selfish agents. The efficiency of this paradigm depends jointly
on the principal’s reward and agents’ costs. This motivates us to consider the
following two properties in our mechanism design for the IOL framework:

######  Definition 1 (Efficiency).

A mechanism is efficient if it maximizes the social welfare in the IOL
framework.

######  Definition 2 (Fairness).

A mechanism is fair if it ensures each agent a predefined maximal utilization
in the IOL framework.

Second, there is an incentive issue in the IOL framework. On the one hand, the
agents will not voluntarily take actions for the principal due to their costs.
On the other hand, the agents’ costs are their private information unknown by
the principle or other agents. Therefore, our mechanism should help the
principal tackle the information asymmetry and induce the agents to carry out
the desired actions. This leads to the following two properties in the IOL
mechanism design.

######  Definition 3 (Incentive Compatibility).

A mechanism satisfies incentive compatibility if it induces the agents to
truthfully reveal their private costs in the IOL framework.

######  Definition 4 (Voluntary Participation).

A mechanism satisfies voluntary participation if it ensures both agents and
principal will not be worse off by participating the IOL framework.

The IOL framework involves coupled unknown environment and information
asymmetry, the coexistence of which renders the corresponding mechanism design
highly challenging. To our knowledge, there is no systematic study yet. In
this paper, we will try to fill in the gap and propose a mechanism satisfying
the properties in Definitions 1$\sim$4. We hope that our study can inspire
further research on the IOL framework.

###  I-C Main Results and Key Contributions

We study the mechanism design problem for the incentivized online learning
(IOL) framework. Specifically, we characterize the principal-agent
interactions in the uncertain environment based on stochastic MAB, and propose
a socially-optimal mechanism satisfying several desired properties. The main
results and key contributions are as follows:

  * •

A Unified IOL Framework: We propose an IOL framework motivated by multiple
real-world applications, where the principal incentivizes selfish agents to
perform the learning actions. This framework enriches the modeling flexibility
of the classic online learning framework, and starts an unexplored learning
paradigm that leverages the selfish agents. To the best of our knowledge, this
is the first systematic study on this paradigm.

  * •

Mechanism Design: The major challenge in the IOL framework optimization is the
coupled unknown environment and information asymmetry. To address it, we
construct a special Lagrangian function based on the environment estimation
and the information revelation. It enables us to properly integrate the
learning and incentive rationale, and develop a mechanism satisfying several
desired properties. Our proposed mechanism is incentive compatible, and
ensures the voluntary participation. It asymptotically performs as well as the
state-of-art baseline (that requires extra information) in terms of the social
welfare and the agent utilization fairness.

  * •

Power of Crowd: We unveil the impact of the agent crowd size in the IOL
framework. Our analysis shows that a larger agent crowd enables our proposed
mechanism to approach more closely the theoretical upper bound of the social
welfare.

  * •

Numerical Results: We demonstrate how to apply our proposed mechanism to the
edge computing system. Results show that a larger edge network makes it less
costly to incentivize the individual.

The rest of this paper is as follows. Section II reviews related literature.
Section III introduces the system model. We propose an IOL mechanism and
present the theoretical performance in Section IV and Section V, respectively.
Section VI provides the numerical results. Section VII concludes this paper.

##  II Related Works

We will review two streams of literatures that are related to this paper in
Section II-A and Section II-B, respectively.

###  II-A Interplay of Exploration, Exploitation, and Incentive

The IOL framework involves three-way interplay of exploration, exploitation,
and incentive. Previous studies on a series of problems known as incentivizing
exploration are also related to this interplay. Next we highlight the key
differences.

####  II-A1 Incentivizing Exploration

The studies on incentivizing exploration are motivated by typical applications
such as recommendation platforms (e.g., Yelp for restaurants) [18]. In these
applications, the agent (e.g., a customer) gains reward by pulling an arm
(e.g., eating in a restaurant), thus they will voluntarily take the
exploitation action (e.g., going to a high-rating restaurant). However, the
principal (e.g., Yelp) is forward-looking, thus it will induce agents to adopt
exploration (e.g., checking a low-rating restaurant) by providing incentive or
compensation. Frazier et al. in [19] and Kremer et al. in [20] initialized the
basic formulation for incentivizing exploration based on the Bayesian MAB
model and strategic information revelation, respectively. Wang and Huang in
[21] considered the non-Bayesian MAB setting and derive the compensation lower
bound. Zhou et al. in [22] took into account the self-reinforcing user
preferences, which capture the random user behaviors in most online
recommender systems. They also proposed two policies achieving $O(\log T)$
expected regret and $O(\log T)$ expected payment.

####  II-A2 IOL Framework

Different from incentivizing exploration, the IOL framework focuses on the
setting where the principal gains reward by persuading the agents to pull the
arms. In this setting, the agents will not voluntarily take the exploration-
exploitation actions for the principal due to their incurred costs. Overall,
the underlying three-way interplay in the IOL framework is substantially
different from that in incentivizing exploration.

###  II-B Generality of IOL Framework

The IOL framework is widely applicable to many real-world applications. Our
proposed mechanism takes into account the coupled unknown environment and
information asymmetry, as well as achieving several desired properties. Our
study generalizes several groups of prior works. For example, Zhang et al. in
[23] proposed an efficient delay-optimal cooperative mobile edge caching
scheme, which ensures a provable optimality and low complexity. The authors in
[24] proposed a novel service-oriented network slicing approach to efficiently
manage the multi-dimensional resource in air-ground integrated vehicular
network. Our mechanism can help tackle the unknown environment and information
asymmetry in these resource sharing studies. Furthermore, some studies on
channel access (e.g., [3, 4, 5]), crowdsensing (e.g., [7, 8, 9, 10]), and edge
computing (e.g., [12, 13, 14, 15]) mainly focused on unknown parameter
learning. For example, Wang et al. in [10] proposed an efficient online
control policy to address the stochastic characteristics and the discontinuous
coverage in crowdsesing. Li et al. in [15] designed a novel learning algorithm
for cooperative edge computing, which ensures the close-to-optimal
performance. Our mechanism tackles the incentive issue from the selfish
spectrum owners, crowdsensing workers, and edge severs, respectively. Some
studies (e.g., [25, 26, 27]) also took into account the budget-constrained
crowdsensing requester. Our mechanism ensures voluntary participation for the
principal, thus captures the same requirement. Overall, we believe that our
study in this paper is a promising attempt for establishing a systematic IOL
framework.

##  III System Model

We study the mechanism design problem for the IOL framework shown in Fig.
1(b). We first present the characterization for this framework in Section
III-A. We then introduce the corresponding mechanism design formulation in
Sections III-B, III-C, and III-D, respectively.

###  III-A IOL Framework Overview

We will characterize the IOL framework from two aspects: the unknown
environment (based on stochastic MAB) and the principal-agent interactions.

####  III-A1 Unknown Environment

The classic stochastic MAB model defines the unknown environment based on the
stochastic reward of a set $\mathcal{K}=\\{1,2,...,K\\}$ of arms [2]. Each arm
$k\in\mathcal{K}$ is associated with an independent and identically
distributed (IID) reward. We let $r_{k}^{t}\in[0,1]$ denote the reward of arm
$k$ in slot $t$, and let $\bar{r}_{k}=\mathbb{E}[r_{k}^{t}]$ denote the
corresponding average reward. The principal will get the reward $r_{k}^{t}$ if
arm $k$ is pulled in slot $t$. We have two-fold elaboration on the principal:

  * •

First, the principal does not know the average reward vector
$\bm{\bar{r}}=(\bar{r}_{k}:\forall k\in\mathcal{K})$, and it cannot observe
the reward $r_{k}^{t}$ unless arm $k$ is pulled in slot $t$.

  * •

Second, in some scenarios (e.g., Table I), the principal cannot play the arms
in person, which naturally leads to the principal-agent interactions in the
IOL framework.

####  III-A2 Principal-Agent Interactions

The IOL framework exhibits the strategic principal-agent interaction, where
the principal will incentivize a set $\mathcal{N}=\\{1,2,...,N\\}$ of selfish
agents to pull the arms for it. The agents are self-interested and may incur
costs from pulling arms for the principal. The cost is the agent’s private
information and possibly time-varying. Mathematically, we model the cost for
each pair of agent $n$ and arm $k$ as the IID random variable
$c_{n,k}^{t}\in[c_{\min},1]$, where $c_{\min}\geq 0$ represents the potential
minimal cost of taking an arm-pulling action. Here we have two-fold
elaboration on the principal-agent interaction:

  * •

First, the agent $n$’s cost realization $\bm{c}_{n}^{t}=(c_{n,k}^{t}:\forall
k\in\mathcal{K})$ and the distribution are his private information, which are
hidden from the principal and other agents.

  * •

Second, agents are selfish, thus will not voluntarily disclose private
information or pull arms for the principal.

####  III-A3 Mechanism Design for IOL Framework

Our goal in the IOL framework is to develop a mechanism that can help the
principal incentivize the selfish agents to take the desired arm-pulling
actions. In each time slot $t$, our mechanism will generate a proposal
$(\bm{x}^{t},\bm{y}^{t})$, which consists of the assignment $\bm{x}^{t}$ and
the payment $\bm{y}^{t}$:

  * •

We let $\bm{x}^{t}=(x_{n,k}^{t}\in\\{0,1\\}:\forall
n\in\mathcal{N},k\in\mathcal{K})$ denote the assignment matrix in slot $t$,
where $x_{n,k}^{t}=1$ represents that agent $n$ is expected to pull arm $k$
for the principal.

  * •

We let $\bm{y}^{t}=(y_{n}^{t}\geq 0:\forall n\in\mathcal{N})$ denote the
payment vector in slot $t$, where $y_{n}^{t}$ is the principal’s monetary
payment to agent $n$. To persuade agents to follow the assignment
$\bm{x}^{t}$, it is critical to appropriately design $\bm{y}^{t}$.

Without loss of generality, we suppose that each agent can only pull one arm
per slot and each arm can be pulled at most once per slot. Mathematically, the
assignment $\bm{x}^{t}$ is chosen from the set $\mathcal{X}$ defined as
follows:

$\displaystyle\mathcal{X}\triangleq\Big{(}\bm{x}\in\\{0,1\\}^{N\times
K}\Big{|}$ $\displaystyle\textstyle\sum_{k=1}^{K}x_{n,k}\leq 1,\ \forall
n\in\mathcal{N},$ (1) $\displaystyle\quad\textstyle\sum_{n=1}^{N}x_{n,k}\leq
1,\ \forall k\in\mathcal{K}\Big{)}.$

Next we introduce four requirements on the mechanism design in Section III-B,
III-C, and III-D, respectively. These requirements guide us to find the
desired proposal $(\bm{x}^{t},\bm{y}^{t})$.

###  III-B Participation Requirement

We start with the participation requirements on the agents and the principal.

####  III-B1 Agent Participation

The agents are selfish and will decide whether to follow the proposal
$(\bm{x}^{t},\bm{y}^{t})$ based on the payment and their incurred costs.
Mathematically, we let $\bm{a}^{t}=(a_{n}^{t}\in\\{0,1\\}:\forall
n\in\mathcal{N})$ denote the decisions of agents in slot $t$, where
$a_{n}^{t}=1$ and $a_{n}^{t}=0$ represent that agent $n$ will follow and
decline the proposal in slot $t$, respectively. Given the proposal
$(\bm{x}^{t},\bm{y}^{t})$, the payoff of agent $n$ in slot $t$ is

$\displaystyle
U_{n}(a_{n}^{t},\bm{x}^{t},\bm{y}^{t})\triangleq\left(y_{n}^{t}-\sum_{k=1}^{K}c_{n,k}^{t}x_{n,k}^{t}\right)a_{n}^{t},$
(2)

where $\sum_{k=1}^{K}c_{n,k}^{t}x_{n,k}^{t}$ represents the cost perceived by
agent $n$ when he follows the assignment $\bm{x}^{t}$ in slot $t$. To
implement the assignment $\bm{x}^{t}$, the IOL mechanism should ensure that
the payment $y_{n}^{t}$ to each agent $n\in\mathcal{N}$ is no less than the
corresponding cost $\sum_{k=1}^{K}c_{n,k}^{t}x_{n,k}^{t}$. In that case, the
agents’ payoff-maximizing decision is $\bm{a}^{t}=\bm{1}_{N}$, where
$\bm{1}_{N}$ is the $N$-dimensional all-one vector. This leads to the first
requirement in our mechanism design for the IOL framework.

######  Requirement 1.

To ensure the voluntary participation of all agents, i.e.,
$\bm{a}^{t}=\bm{1}_{N}$, the mechanism should satisfy

$\textstyle y_{n}^{t}-\sum\limits_{k=1}^{K}c_{n,k}^{t}x_{n,k}^{t}\geq
0,\quad\forall n\in\mathcal{N},t\in\mathcal{T}.$ (3)

####  III-B2 Principal Participation

In the IOL framework, the principal pays the agents in exchange for the reward
of arms played by the agents. Therefore, the principal’s profit in slot $t$ is
the difference between the total reward and the total payment. Given the
assignment $\bm{x}^{t}$ and the agent decision $\bm{a}^{t}$, the principal
gains the following reward in slot $t$:

$\displaystyle
V(\bm{x}^{t},\bm{a}^{t};\bm{r}^{t})\triangleq\sum\limits_{k=1}^{K}\sum\limits_{n=1}^{N}r_{k}^{t}x_{n,k}^{t}a_{n}^{t},$
(4)

where $r_{k}^{t}$ is the reward of playing arm $k$ in slot $t$. Moreover, the
principal’s total payment is $\sum_{n=1}^{N}a_{n}^{t}y_{n}^{t}$.

Intuitively, it is not beneficial for the principal to adopt the IOL framework
if the reward is much smaller than the agents’ costs. However, the principal
does not know whether this is the case until it gradually observes the reward
realizations and elicits the agents’ costs. That is, it is inevitable that the
principal may get an instantaneous deficit, i.e., negative profit in some
slot. Therefore, we will focus on the principal’s long-term profit in the IOL
mechanism design. For presentation convenience, we define the principal’s
cumulative profit as

$\displaystyle\mathtt{Pro}(T)\triangleq\sum\limits_{t=1}^{T}\mathbb{E}\left[V(\bm{x}^{t},\bm{a}^{t};\bm{r}^{t})-\sum\limits_{n=1}^{N}a_{n}^{t}y_{n}^{t}\right],$
(5)

and introduce the second requirement:

######  Requirement 2.

To ensure the voluntary participation of the principal, the mechanism should
satisfy $\mathtt{Pro}(T)\geq 0$.

###  III-C Fairness Requirement

The IOL framework relies on the selfish agents to play the arms for the
principal. In many networking applications (e.g., spectrum sharing), the arm-
pulling actions are resource-consuming for the agents. Besides the agent
participation requirement, we follow the previous studies (e.g., [28, 29, 30])
and take into account the fairness of agent utilization. We formulate the
fairness requirement in two steps:

  * •

First, we let $\phi_{n}\in[0,1]$ denote the maximal long-term utilization
ratio of agent $n$. In practice, $\phi_{n}$ could be negotiated by the
principal and agent $n$, or directly specified by the agent). Hence
$\bm{\phi}=(\phi_{n}:\forall n\in\mathcal{N})$ is the public information in
the IOL framework. The case $\phi_{n}=1$ means no fairness guarantee on agent
$n$.

  * •

Second, given the assignment $\bm{x}^{t}$ and the agents’ decisions
$\bm{a}^{t}$, we define the function $f_{n}(\bm{x}^{t},\bm{a}^{t})$ in (6) to
indicate whether agent $n$ is actually utilized in slot $t$. Note that we have
$f_{n}(\bm{x}^{t},\bm{a}^{t})\in\\{0,1\\}$ for any $\bm{x}^{t}\in\mathcal{X}$.

$f_{n}(\bm{x}^{t},\bm{a}^{t})\triangleq\sum_{k=1}^{K}x_{n,k}^{t}a_{n}^{t},\quad\forall
n\in\mathcal{N}.$ (6)

Based on the above discussions, we define the cumulative fairness violation
among the $N$ agents as follows:

$\displaystyle\mathtt{Vio}(T)\triangleq\sum\limits_{n=1}^{N}\mathbb{E}\left(\sum\limits_{t=1}^{T}\Big{[}f_{n}(\bm{x}^{t},\bm{a}^{t})-\phi_{n}\Big{]}\right)^{+},$
(7)

where $(\cdot)^{+}\triangleq\max(\cdot,0)$. In general, the fairness violation
$\mathtt{Vio}(T)$ is possibly increasing in $T$, while the sub-linear fairness
violation (i.e., $\mathtt{Vio}(T)\sim o(T)$) implies the asymptotic
satisfaction of the fairness requirement. This is the third requirement in our
mechanism design:

######  Requirement 3.

The mechanism should ensure that the fairness violation is sub-linear in $T$,
i.e., $\mathtt{Vio}(T)\sim o(T)$.

###  III-D Efficiency

We evaluate the efficiency of an IOL mechanism based on the aggregated social
welfare, which is the total profit (or payoff) of the principal and the
agents. In this problem, the social welfare is the difference between the
principal’s total reward $V(\bm{x}^{t},\bm{a}^{t};\bm{r}^{t})$ defined in (4)
and the incurred agent cost $C(\bm{x}^{t},\bm{a}^{t};\bm{c}^{t})$ defined as
follows

$C(\bm{x}^{t},\bm{a}^{t};\bm{c}^{t})\triangleq\sum_{n=1}^{N}\sum_{k=1}^{K}c_{n,k}^{t}x_{n,k}^{t}a_{n}^{t}.$
(8)

Accordingly, the social welfare in slot $t$ is given by

$\displaystyle S(\bm{x}^{t},\bm{a}^{t};\bm{r}^{t},\bm{c}^{t})\triangleq
V(\bm{x}^{t},\bm{a}^{t};\bm{r}^{t})-C(\bm{x}^{t},\bm{a}^{t};\bm{c}^{t}).$ (9)

We aim to maximize the cumulative social welfare in the long-term. To
understand the attainable social performance, we introduce two state-of-the-
art benchmarks (i.e., $S^{*}$ and $S^{{\dagger}}$) for the time-average social
welfare in the following.

######  Baseline 1.

Suppose following two conditions hold: C1: The average reward
$\bm{\bar{r}}=(\bar{r}_{k}:\forall k\in\mathcal{K})$ is known. C2: Agents
voluntarily participate (i.e., $\bm{a}^{t}=\bm{1}_{N}$) and disclose their
private information in each slot. In the above idealistic setting, the maximal
achievable social welfare is $\displaystyle
S^{*}\triangleq\max\limits_{\bm{x}(\cdot)}$ $\displaystyle\
\mathbb{E}_{\bm{c}}\left[\sum_{k=1}^{K}\sum_{n=1}^{N}\big{(}\bar{r}_{k}-c_{n,k}\big{)}{x}_{n,k}(\bm{c})\right]$
(10) s.t. $\displaystyle\
\mathbb{E}_{\bm{c}}\left[f_{n}(\bm{{x}}(\bm{c}),\bm{1}_{N})\right]\leq\phi_{n},\
\forall n\in\mathcal{N},$ where the expectation is taken over the disclosed
agent cost $\bm{c}=(c_{n,k}:\forall n\in\mathcal{N},k\in\mathcal{K})$.
Moreover, $\bm{x}(\cdot)$ represents the policy (to be optimized). That is,
the assignment $\bm{x}(\bm{c})\in\mathcal{X}$ will be adopted given the
disclosed agent costs $\bm{c}$.

Baseline 1 shows that achieving the social welfare benchmark $S^{*}$ requires
two ideal conditions. Condition C1 requires the prior knowledge on the
uncertain environment. Similar condition also appears in the benchmark
definition of stochastic MAB [2]. Condition C2 relaxes that fact that the
agents are selfish. This is the new condition for the IOL framework. We
measure the gap between $S^{*}$ and the social performance achieved by our
mechanism based on the cumulative regret:

$\displaystyle\mathtt{Reg}(T)\triangleq\sum\limits_{t=1}^{T}\Big{(}S^{*}-\mathbb{E}\left[S\left(\bm{x}^{t},\bm{a}^{t};\bm{r}^{t},\bm{c}^{t}\right)\right]\Big{)},$
(11)

where $\bm{x}^{t}$ and $\bm{a}^{t}$ denote the assignment and the agent
decisions in slot $t$ under the IOL framework. A sub-linear regret
$\mathtt{Reg}(T)\sim o(T)$ implies that the proposed mechanism performs as
well as the benchmark $S^{*}$ in the long-term.

The regret definition in (11) depends on the agents’ strategic decisions and
private information, thus it is a generalization of that adopted in stochastic
MAB to the IOL framework. It is already more challenging to achieve a sub-
linear regret under the IOL framework. Nevertheless, we will further introduce
an even stronger social welfare benchmark in Baseline 2.

######  Baseline 2.

Suppose that Conditions C1 and C2 in Baseline 1 hold, and the incurred agent
cost is always the potential minimum value $c_{\min}$. In this idealistic
setting, the maximal achievable social welfare is $\displaystyle
S^{{\dagger}}\triangleq\max_{\bm{p}}$
$\displaystyle\quad\sum_{k=1}^{K}\left(\bar{r}_{k}-c_{\min}\right)p_{k}$ (12)
s.t. $\displaystyle\quad\sum_{k=1}^{K}p_{k}\leq\Phi,$ $\displaystyle\quad
p_{k}\in[0,1],\forall k\in\mathcal{K},$ where $\bm{p}=(p_{k}:\forall
k\in\mathcal{K})$ is the arm selection probability (to be optimized), and
$\Phi=\sum_{n=1}^{N}\phi_{n}$ represents the average number of played arms per
slot.

Compared to Baseline 1, Baseline 2 relies on one more condition regarding the
incurred agent cost. Essentially, $S^{{\dagger}}$ is the theoretical upper
bound of the social performance, since it is defined based on the potential
minimal cost $c_{\min}$. We will measure the performance gap between
$S^{{\dagger}}$ and our mechanism based on the following cumulative
degradation:

$\displaystyle\mathtt{Deg}(T)\triangleq\sum\limits_{t=1}^{T}\Big{(}S^{{\dagger}}-\mathbb{E}\left[S\left(\bm{x}^{t},\bm{a}^{t};\bm{r}^{t},\bm{c}^{t}\right)\right]\Big{)}.$
(13)

Note that one cannot change the cost $\bm{c}^{t}\in[c_{\min},1]^{N\times K}$
no matter how we design the learning and incentive scheme. Hence there is an
inevitable gap between the incurred agent cost (e.g., $c_{n,k}^{t}$) and the
potential minimal cost $c_{\min}$. This makes it challenging to achieve a sub-
linear degradation in general. Surprisingly, in Section V-B, we will show that
(under some mild condition) a sub-linear degradation is achievable when the
agent crowd is large (i.e., $N$ is large).

The above discussions lead to the fourth requirement on the mechanism design
problem for the IOL framework.

######  Requirement 4.

The mechanism should achieve a sub-linear regret $\mathtt{Reg}(T)\sim o(T)$
and a sub-linear degradation $\mathtt{Deg}(T)\sim o(T)$.

So far, we have formulated the mechanism design problem for the IOL framework
based on Requirements 1$\sim$4. A proper mechanism should manipulate the
principal-agent interaction by providing incentives to agents and learning the
unknown environment. Next let us introduce the main result.

##  IV Mechanism Design

In this section, we propose a mechanism $\mathfrak{A}$ for the IOL framework.
For notation clarity, we let $(\bm{\hat{x}}^{t},\bm{\hat{y}}^{t})$ and
$\bm{\hat{a}}^{t}$ denote the proposal and agents’ decisions in slot $t$ under
our proposed mechanism $\mathfrak{A}$, respectively. We first overview the
basic idea in Section IV-A. We then introduce two major components of the
mechanism $\mathfrak{A}$ in Section IV-B and Section IV-C, respectively. We
summarize the entire mechanism in Section IV-D.

###  IV-A Overview of Mechanism $\mathfrak{A}$

In mechanism $\mathfrak{A}$, we construct a special Lagrangian function to
facilitate the optimization of the proposal
$(\bm{\hat{x}}^{t},\bm{\hat{y}}^{t})$ in each slot $t$. The Lagrangian
function in slot $t$ is

$\displaystyle\mathcal{L}\big{(}\bm{x},\bm{\lambda}^{t};\bm{\hat{r}}^{t},\bm{\hat{c}}^{t}\big{)}\triangleq$
(14) $\displaystyle\qquad
S(\bm{x},\bm{1}_{N};\bm{\hat{r}}^{t},\bm{\hat{c}}^{t})-\sum_{n=1}^{N}\lambda_{n}^{t}\big{[}f_{n}(\bm{x},\bm{1}_{N})-\phi_{n}\big{]},$

where $\lambda_{n}^{t}\geq 0$ represents the Lagrangian multiplier associated
with the fairness requirement on agent $n$ in slot $t$. To better understand
(14), we further make two-fold elaborations:

  * •

In (14), we presume that the agents are willing to follow the proposal
$(\bm{\hat{x}}^{t},\bm{\hat{y}}^{t})$, thus substitute
$\bm{\hat{a}}^{t}=\bm{1}_{N}$. In Section V-A, we will show that this is
indeed true under our proposed mechanism $\mathfrak{A}$.

  * •

Recall that the reward vector $\bm{r}^{t}$ is prior unknown and the agent cost
matrix $\bm{c}^{t}$ is agents’ private information. Hence we define (14) based
on the estimated reward $\bm{\hat{r}}^{t}$ and the bidding cost
$\bm{\hat{c}}^{t}$. We will elaborate how to generate $\bm{\hat{r}}^{t}$ and
$\bm{\hat{c}}^{t}$ in Section IV-B and Section IV-C, respectively.

Based on the Lagrangian function (14), our proposed mechanism $\mathfrak{A}$
determines the assignment $\bm{\hat{x}}^{t}$ according to

$\bm{\hat{x}}^{t}\triangleq\max\limits_{\bm{x}\in\mathcal{X}}\
\mathcal{L}\left(\bm{x},\bm{\lambda}^{t};\bm{\hat{r}}^{t},\bm{\hat{c}}^{t}\right),$
(15)

and the mechanism updates $\bm{\lambda}^{t+1}$ according to

$\bm{\lambda}^{t+1}=\Pi_{\mathbb{R}_{+}^{N}}\Big{(}\bm{\lambda}^{t}-\eta\nabla_{\bm{\lambda}}\mathcal{L}\big{(}\bm{\hat{x}}^{t},\bm{\lambda}^{t};\bm{\hat{r}}^{t},\bm{\hat{c}}^{t}\big{)}\Big{)},$
(16)

where $\Pi_{\mathbb{R}_{+}^{N}}(\cdot)$ is the projection onto the non-
negative orthant, and $\eta>0$ is the step-size (to be specified in Section
V).

Next we elaborate the rationale of generating $\bm{\hat{r}}^{t}$ and
$\bm{\hat{c}}^{t}$ in Section IV-B and Section IV-C, respectively.

###  IV-B Estimated Reward

Our proposed mechanism $\mathfrak{A}$ will estimate the reward primarily based
on the Upper-Confidence-Bound (UCB) algorithm [31]. Our goal in IOL mechanism
design is not to improve this classic algorithm, but to design an appropriate
incentive scheme that is compatible with this algorithm, so that they can
properly manipulate the principal-agent interactions in the IOL framework
together. Next we introduce the details.

We let $H_{k}^{t}$ denote the number of observations on arm $k$ during the
first $t$ slots, and let $\tilde{r}_{k}^{t}$ denote the empirical average
reward of the $H_{k}^{t}$ observations. At the beginning of slot $t$,
mechanism $\mathfrak{A}$ generates $\bm{\hat{r}}^{t}=(\hat{r}_{k}^{t}:\forall
k\in\mathcal{K})$ according to

$\displaystyle\hat{r}_{k}^{t}=\left\\{\begin{aligned}
&\min\left(\tilde{r}_{k}^{t-1}+\sqrt{\frac{3\ln(t)}{2H_{k}^{t-1}}},\
1\right),&H_{k}^{t-1}>0,\\\ &1,&H_{k}^{t-1}=0.\end{aligned}\right.$ (17)

When $H_{k}^{t-1}>0$, the empirical average reward $\tilde{r}_{k}^{t-1}$
represents the exploitation based on the past observations. The term
$[{\frac{3}{2}}\ln(t)/H_{k}^{t-1}]^{{1}/{2}}$ decreases in $H_{k}^{t-1}$ and
represents the exploration out of the past observations. When $H_{k}^{t-1}=0$,
we set $\hat{r}_{k}^{t}$ as the potential maximal reward to prevent from
overlooking a high-reward arm.

At the end of slot $t$, mechanism $\mathfrak{A}$ will update the counter
$H_{k}^{t}$ and the empirical reward $\tilde{r}_{k}^{t}$. Specifically,
$\sum_{n=1}^{N}\hat{x}_{n,k}^{t}\hat{a}_{n}^{t}\in\\{0,1\\}$ indicates whether
arm $k$ is actually played by an agent in slot $t$. Hence we have

$\displaystyle H_{k}^{t}$
$\displaystyle=H_{k}^{t-1}+\sum_{n=1}^{N}\hat{x}_{n,k}^{t}\hat{a}_{n}^{t},\
\forall k\in\mathcal{K},$ (18a) $\displaystyle\tilde{r}_{k}^{t}$
$\displaystyle=\left(\tilde{r}_{k}^{t-1}H_{k}^{t-1}+r_{k}^{t}\sum_{n=1}^{N}\hat{x}_{n,k}^{t}\hat{a}_{n}^{t}\right)\bigg{/}H_{k}^{t},\
\forall k\in\mathcal{K},$ (18b)

where $r_{k}^{t}$ is the reward of playing arm $k$ in slot $t$.

###  IV-C Bidding Cost

Our proposed mechanism $\mathfrak{A}$ manages to elicit the private agent cost
through an auction scheme based on the Lagrangian function (14). Before
introducing the auction procedure, for notation simplicity, we let
$\mathcal{L}_{-n}(\bm{x},\bm{\lambda}^{t},\bm{\hat{r}}^{t},\bm{\hat{c}}^{t})$
denote the Lagrangian function at the absence of agent $n$, i.e.,

$\displaystyle\mathcal{L}_{-n}(\bm{x},\bm{\lambda}^{t},\bm{\hat{r}}^{t},\bm{\hat{c}}^{t})\triangleq$
$\displaystyle\sum\limits_{k\in\mathcal{K}}\sum\limits_{i\neq
n}\big{(}\hat{r}_{k}^{t}-\hat{c}_{i,k}^{t}\big{)}{x}_{i,k}$ (19)
$\displaystyle-\sum\limits_{i\neq
n}\lambda_{i}^{t}f_{i}(\bm{x},\bm{1}_{N})+\sum\limits_{n\in\mathcal{N}}\lambda_{n}^{t}\phi_{n}.$

Accordingly, we define
$\mathcal{L}_{-n}^{\star}(\bm{\lambda}^{t},\bm{\hat{r}}^{t},\bm{\hat{c}}^{t})$
as the maximal value of
$\mathcal{L}_{-n}(\cdot,\bm{\lambda}^{t},\bm{\hat{r}}^{t},\bm{\hat{c}}^{t})$,
i.e.,

$\mathcal{L}_{-n}^{\star}(\bm{\lambda}^{t},\bm{\hat{r}}^{t},\bm{\hat{c}}^{t})\triangleq\max\limits_{\bm{x}\in\mathcal{X}}\
\mathcal{L}_{-n}(\bm{x},\bm{\lambda}^{t},\bm{\hat{r}}^{t},\bm{\hat{c}}^{t}).$
(20)

Based on the above definitions, our proposed mechanism $\mathfrak{A}$ adopts
the following Cost Revelation Auction:

######  Auction 1 (Cost Revelation Auction).

The auction procedure in mechanism $\mathfrak{A}$ consists of the following
two steps:

  1. 1.

Each agent $n\in\mathcal{N}$ submits the bids indicating his costs

$\displaystyle\bm{\hat{c}}_{n}^{t}=(\hat{c}_{n,k}^{t}:\forall
k\in\mathcal{K}).$ (21)

  2. 2.

The principle computes the payment $\bm{\hat{y}}^{t}=(\hat{y}_{n}^{t}:\forall
n\in\mathcal{N})$ to agents according to

$\displaystyle\hat{y}_{n}^{t}\triangleq$
$\displaystyle\sum_{k=1}^{K}\left(\hat{r}_{k}^{t}-\lambda_{n}^{t}\right)\hat{x}_{n,k}^{t}$
(22a)
$\displaystyle-\Big{[}\mathcal{L}_{-n}^{\star}(\bm{\lambda}^{t},\bm{\hat{r}}^{t},\bm{\hat{c}}^{t})-\mathcal{L}_{-n}(\bm{\hat{x}}^{t},\bm{\lambda}^{t},\bm{\hat{r}}^{t},\bm{\hat{c}}^{t})\Big{]},$
(22b)

where $\hat{\bm{x}}^{t}$ is the adopted assignment in (15).

The payment rule (22) is the core of eliciting the private agent cost in
mechanism $\mathfrak{A}$. Note that the payment $\hat{y}_{n}^{t}$ to agent $n$
is independent of the bid $\bm{\hat{c}}_{n}^{t}$ of agent $n$. Hence there is
no incentive for each agent $n\in\mathcal{N}$ to misrepresent the costs in
this slot. Roughly speaking, the payment rule in (22) has two components with
different roles:

  * •

The component (22a) measures an agent’s contribution to the principal under
the fairness guarantee. According to (22a), if agent $n$ plays arm $k$ (i.e.,
$\hat{x}_{n,k}^{t}=1$), then he will obtain the payment
$\hat{r}_{n,k}^{t}-\lambda_{n}^{t}$. The estimated reward $\hat{r}_{n,k}^{t}$
represents agent $n$’s direct contribution to the principal under the
assignment $\bm{\hat{x}}^{t}$. The Lagrangian multiplier $\lambda_{n}^{t}$ is
an instantaneous monetary loss for ensuring the maximal long-term utilization
ratio $\phi_{n}$. Overall, this component represents the contribution of an
agent’s presence and prevents the agent from being over-utilized.

  * •

The component (22b) is the loss inflicted on the others in the IOL framework
by the presence of agent $n$. It follows from the basic VCG idea (e.g., [32,
33, 34]) and measures the indirect effect of the agent. If an agent is
irreplaceable in terms of being capable of pulling a high-reward arm that
others cannot, then his presence will cause little effect on others, thus the
loss in (22b) is small.

As we will see in Section VI, the above payment rule makes it less costly for
the principal to incentivize the individual when the crowd size $N$ increases.
This is an economic advantage originating from the power of crowd in the IOL
framework.

###  IV-D Mechanism Description

Algorithm 1 summarizes our proposed mechanism $\mathfrak{A}$, which consists
of the following phases in each slot $t$.

  * •

Lines 1$\sim$1: After Auction 1 is initialized, each agent submits the bidding
cost $\bm{\hat{c}}_{n}^{t}$. Moreover, mechanism $\mathfrak{A}$ generates the
current reward estimation $\bm{\hat{r}}^{t}$.

  * •

Lines 1$\sim$1: Mechanism $\mathfrak{A}$ calculates the proposal
$(\bm{\hat{x}}^{t},\bm{\hat{y}}^{t})$, and each agent decides whether to
follow it.

  * •

Lines 1$\sim$1: Mechanism $\mathfrak{A}$ updates the counter $H_{k}^{t}$ and
the empirical reward $\tilde{r}_{k}^{t}$ for each arm based on the new
observation. We update the Lagrangian multiplier $\bm{\lambda}^{t+1}$ based on
the assignment $\bm{\hat{x}}^{t}$ and agents’ decisions $\bm{\hat{a}}^{t}$.

Output : Proposal $(\bm{\hat{x}}^{t},\bm{\hat{y}}^{t})$ in each slot $t$.

1 Initial $\eta>0$, $\bm{\lambda}^{1}=\bm{0}_{N}$ and $H_{k}^{0}=0$ for any
$k\in\mathcal{K}$.

2 for  _$t=1$ to $T$ _ do

3 Initialize Auction 1 and each agent $n\in\mathcal{N}$ bids
$\bm{\hat{c}}_{n}^{t}$.

4 Estimate reward $\bm{\hat{r}}^{t}$ according to (17).

5 Announce $(\bm{\hat{x}}^{t},\bm{\hat{y}}^{t})$ based on (15) and (22).

6 Each agent $n\in\mathcal{N}$ decides $\hat{a}_{n}^{t}$.

7 Update $H_{k}^{t}$ and $\tilde{r}_{k}^{t}$ for each arm $k\in\mathcal{K}$
based on (18).

8 Update $\bm{\lambda}^{t+1}$ based on (16).

Algorithm 1 IOL Mechanism $\mathfrak{A}$

So far, we have introduced mechanism $\mathfrak{A}$. Next let us present its
theoretical performance.

##  V Performance Analysis

We first proceed the general performance analysis for mechanism $\mathfrak{A}$
in Section V-A, and then investigate the impact of the crowd size $N$ in
Section V-B. The proof is given in our technical report [35].

###  V-A Performance of IOL Mechanism $\mathfrak{A}$

####  V-A1 Instantaneous Performance

The IOL framework relies on the selfish agents. We first present how the
selfish agents behave under our proposed mechanism $\mathfrak{A}$ in Theorem
1.

######  Theorem 1.

In Auction 1, it is the dominant strategy for any agent $n\in\mathcal{N}$ to
truthfully bid his cost, i.e., $\bm{\hat{c}}_{n}^{t}=\bm{c}_{n}^{t}$.
Furthermore, we have $\bm{\hat{a}}^{t}=\bm{1}_{N}$ for any slot
$t\in\mathcal{T}$.

Theorem 1 has two-fold implications on the truthfulness and the voluntary
participation of agents:

  * •

First, Theorem 1 shows that truthfully bidding is no worse than any other
bidding strategies for each agent, no matter how the others behave. Such a
truthfulness notion corresponds to the dominant strategy implementation in
each slot.

  * •

Second, Theorem 1 implies that each agent achieves a non-negative payoff by
following the proposal $(\bm{\hat{x}}^{t},\bm{\hat{y}}^{t})$ in mechanism
$\mathfrak{A}$, thus we have $\hat{\bm{a}}^{t}=\bm{1}_{N}$. That is, mechanism
$\mathfrak{A}$ ensures the voluntary participation.

The two aspects above enable our proposed mechanism $\mathfrak{A}$ to
unconsciously enforce the desired assignment and achieve the other desired
properties (to be introduced later).

####  V-A2 Long-term Performance

We will present the long-term performance achieved by mechanism $\mathfrak{A}$
in Theorem 2. For notation simplicity, we first define $\phi_{\min}$ as

$\displaystyle\phi_{\min}\triangleq\min_{n\in\mathcal{N}}\ \phi_{n},$ (23)

where $\phi_{n}$ is the maximal long-term utilization ratio of agent $n$.
Moreover, we define $\Xi(\delta)$ for any $\delta\in(0,\phi_{\min})$ as

$\Xi(\delta)\triangleq\frac{3\sqrt{N}\Theta^{2}}{\phi_{\min}-\delta}\ln\left(\frac{2\Theta}{\phi_{\min}-\delta}\right)+\frac{3\sqrt{N}\Theta}{2\delta},$
(24)

where $\Theta\triangleq\min(K+\Phi,N)$ is a constant, and
$\Phi\triangleq\sum_{n=1}^{N}\phi_{n}$ represents the number of pulled arms
per slot on average. Theorem 2 presents the long-term performance.

######  Theorem 2.

With the step-size $\eta=\frac{4K+2\sqrt{6KT\Phi\ln T}}{T\Theta}$ in (16),
mechanism $\mathfrak{A}$ in Algorithm 1 attains

$\displaystyle\mathtt{Reg}(T)\leq
6K+3\sqrt{6KT\Big{[}\Phi+\frac{\mathtt{Vio}(T)}{T}\Big{]}\ln T},$ (25a)
$\displaystyle\mathtt{Vio}(T)\leq\Xi(\delta)+\frac{\Theta^{2}}{4\delta}\sqrt{\frac{NT}{K\Phi}},$
(25b)
$\displaystyle\mathtt{Pro}(T)+\frac{5K}{2}+2\sqrt{6KT\Big{[}\Phi+\frac{\mathtt{Vio}(T)}{T}\Big{]}\ln
T}\geq 0.$ (25c)

The three inequalities in Theorem 2 correspond to the social performance, the
fairness violation, and the principal’s participation, respectively. We have
two-fold elaborations:

  * •

First, (25a) and (25b) show that our proposed mechanism $\mathfrak{A}$
achieves a sub-linear regret $\mathtt{Reg}(T)\leq O(\sqrt{T})$ and a sub-
linear fairness violation $\mathtt{Vio}(T)\leq O(\sqrt{T})$. That is,
mechanism $\mathfrak{A}$ performs asymptotically as well as the social welfare
benchmark $S^{*}$ in Baseline 1.

  * •

Second, (25c) shows that the principal’s profit satisfies
$\mathtt{Pro}(T)+O(\sqrt{T})\geq 0$. This implies that our proposed mechanism
$\mathfrak{A}$ enables the principal to obtain a non-negative profit in the
long-term (i.e., $\lim_{T\rightarrow\infty}\mathtt{Pro}(T)\geq 0$), which
ensures the principal’s voluntary participation.

Theorem 1 and Theorem 2 indicate that our proposed mechanism $\mathfrak{A}$
satisfies Requirements 1$\sim$4 except the sub-linear degradation. Recall that
the degradation $\mathtt{Deg}(T)$ measures the social performance gap compared
to the benchmark $S^{{\dagger}}$, which is defined based on the potential
minimal cost $c_{\min}$ in Baseline 2. In practice, one cannot control the
agents’ costs, thus there is always an inevitable gap between the incurred
agent cost and the potential minimal cost $c_{\min}$. Therefore, it is
challenging to achieve a sub-linear degradation in the general setting.
Nevertheless, we will show that the sub-linear degradation is achievable in
some specific scenario (when the agent crowd is large). This is the power of
crowd in the IOL framework.

###  V-B Power of Crowd in IOL Framework

The IOL framework has a novel learning paradigm that relies on the crowd of
agents. Hence it is crucial to understand how the crowd size $N$ (i.e., the
number of agents) affects the system performance. To unveil the impact of $N$,
we will narrow down our analysis to a statistically homogeneous IOL system
$\mathcal{H}(\alpha,N)$, which is defined as follows:

######  Definition 5.

The system $\mathcal{H}(\alpha,N)$ consists of $N$ selfish agents with the
same maximal long-term utilization ratio, i.e., $\phi_{n}={\alpha}/{N}$ for
any $n\in\mathcal{N}$. Moreover, the agents’ costs
$\\{\bm{c}_{n}^{t}\in[c_{\min},1]^{K}:\forall
n\in\mathcal{N},t\in\mathcal{T}\\}$ are IID.111The agent cost realization and
distribution are still the private information of the agents, thus are prior
unknown to the principal.

Note that the system $\mathcal{H}(\alpha,N)$ focuses on $N$ agents who are
statistically homogeneous in terms of the fairness requirement and the private
cost distribution. Moreover, there are $\sum_{n=1}^{N}\phi_{n}=\alpha$ arms
played per slot on average in the above system $\mathcal{H}(\alpha,N)$.
Theorem 3 presents the main result of the cumulative degradation
$\mathtt{Deg}(T)$.

######  Theorem 3.

In the system $\mathcal{H}(\alpha,N)$, there exists a finite constant
$\epsilon>0$ such that mechanism $\mathfrak{A}$ attains the following
cumulative degradation

$\displaystyle\mathtt{Deg}(T)\leq\mathtt{Reg}(T)+\frac{\alpha\epsilon
T}{N+1},$ (26)

where $\mathtt{Reg}(T)$ satisfies the inequality (25a) with $\Phi=\alpha$.

Theorem 3 presents a degradation upper bound, which is the sum between the
regret $\mathtt{Reg}(T)$ and an extra term. Specifically, the regret
$\mathtt{Reg}(T)$ is sub-linear in $T$ according to Theorem 2, while
$\frac{\alpha\epsilon T}{N+1}$ increases linearly in $T$. Although the upper
bound in (26) is not sub-linear, we find that $\frac{\alpha\epsilon T}{N+1}$
decreases in the crowd size $N$. This inspires us to investigate whether
mechanism $\mathfrak{A}$ can achieve a sub-linear degradation when the agent
crowd is large. Corollary 1 provides the answer.

######  Corollary 1.

For any parameter $\beta\in(0,\frac{1}{3})$, in the system
$\mathcal{H}(\alpha,N)$ satisfying
$N=\lfloor\alpha^{\frac{1}{3}}T^{\beta}\rfloor$, mechanism $\mathfrak{A}$
attains the following performance

$\displaystyle\mathtt{Deg}(T)\leq
O\left(\alpha^{\frac{2}{3}}T^{1-\beta}\right),$ (27a)
$\displaystyle\mathtt{Reg}(T)\leq O\left(\sqrt{\alpha KT\ln T}\right),$ (27b)
$\displaystyle\mathtt{Vio}(T)\leq
O\left(\frac{K}{\alpha}\sqrt{KT^{1+3\beta}}\right),$ (27c)
$\displaystyle\mathtt{Pro}(T)+O\left(\sqrt{\alpha KT\ln T}\right)\geq 0.$
(27d)

Corollary 1 presents the theoretical performance in the large-scale system.
Let us elaborate this result in three steps:

  * •

First, the aforementioned large-scale system is formally defined by
$N=\lfloor\alpha^{\frac{1}{3}}T^{\beta}\rfloor$. That is, given a total of $T$
operation periods, the crowd size $N$ should be sufficiently large. Such a
large agent crowd enables our proposed mechanism $\mathfrak{A}$ to achieve a
better social performance.

  * •

Second, (27a) shows that mechanism $\mathfrak{A}$ achieves a sub-linear
degradation in the above large-scale system. This is the power of crowd in the
IOL framework: a large crowd makes it possible to attain the theoretical upper
bound $S^{{\dagger}}$ in the long-term. This is the unique feature of the IOL
framework. In Section VI, we will further demonstrate the economic impact of
the crowd size $N$ based on the large-scale networking application.

  * •

Third, (27b)-(27d) present the other desired properties in the large-scale
system. Specifically, the regret upper bound (27b) directly follows from (25a)
when $\Phi=\alpha$. Moreover, (27c) and (27d) validate the requirements on the
agent fairness and principal participation, respectively.

To sum up, the power of crowd enables our proposed mechanism $\mathfrak{A}$ to
satisfy Requirements 1$\sim$4 in the large-scale system.

Figure 2: Electricity prices

(a) Social welfare

(b) Fairness violation

(c) Payoff and profit

Figure 3: Experimental results of the small-scale system

##  VI Numerical Results

As an illustrative example, we will demonstrate how our proposed mechanism
$\mathfrak{A}$ works in the edge computing network. Let us start with
characterizing the edge computing system via the IOL framework in Section
VI-A.

###  VI-A Edge Computing in IOL Framework

Mobile Internet services (e.g., VR/AR) are becoming increasingly computation-
intensive. To improve the quality of experience (QoE), the Content Provider
(CP) would incentivize the nearby edge servers to execute the computation
tasks offloaded by the resource-limited mobile devices (that are using the
CP’s content services). Next we elaborate this scenario based on the IOL
framework.

  * •

Principal: The CP corresponds to the principal in the IOL framework. It aims
to improve the QoE for mobile devices that are using its content services.

  * •

Arms: The mobile devices correspond to the $K$ arms in the IOL framework. They
may have task offloading demands in certain time slot, which are unpredictable
to the principal.

  * •

Agents: The edge servers correspond to the $N$ selfish agents (with computing
resource) in the IOL framework. They perceive a cost (i.e., energy
expenditure) from executing computation tasks for mobile devices. Such a cost
depends on the energy consuming rate and electricity prices, thus is the
private information of edge servers.

Based on the above discussions, we model the reward $r_{k}^{t}\in\\{0,1\\}$ as
the Bernoulli random variable, which indicates the task offloading of the
mobile device $k\in\mathcal{K}$ in slot $t$. That is, the CP perceives QoE
improvement (i.e., reward) if one of the edge servers meets the task
offloading demand of the mobile devices. Furthermore, we model edge servers’
costs as $c_{n,k}^{t}=\pi_{n}^{t}(\eta_{n}^{t}+l_{n,k}^{t})$, where
$\pi_{n}^{t}$ represents the real-time electricity price. Moreover,
$\eta_{n}^{t}$ and $l_{n,k}^{t}$ measure edge server $n$’s energy consumption
due to computation and communication (with mobile device $k$), respectively.

We first demonstrate how mechanism $\mathfrak{A}$ works based on a small-scale
edge computing system in Section VI-B. We then evaluate the performance of the
large-scale edge network in Section VI-C.

###  VI-B Small-Scale Demonstration

We consider a small-scale edge network with $K=5$ mobile devices (i.e., arms)
and $N=2$ edge servers (i.e., agents). We set the maximal utilization ratio of
the two servers as $\phi_{1}=0.7$ and $\phi_{2}=0.3$, respectively. In this
case, server 2 is expected to be less occupied than server 1, and on average
$\phi_{1}+\phi_{2}=1$ server is ready to serve the mobile devices’ task
offloading. As shown in Fig. 3, our experiment follows the real-world
electricity market price in US [36]. We randomly generate the energy
consumption $\eta_{n}^{t}+l_{n,k}^{t}$ according to normal distribution
truncated on the support $[0,0.1]$. We use the average reward vector
$\bm{\bar{r}}=\\{0.1,0.3,0.5,0.7,0.9\\}$ to capture the different offloading
demands of the $K=5$ mobile devices. Fig. 3 plots the per-slot average results
of multiple simulation runs, where the shaded region represents the three-
sigma range.

Fig. 3(a) shows the per-slot average reward, cost, and social welfare achieved
by mechanism $\mathfrak{A}$. Overall, both the social welfare (i.e., the
square curve) and the reward (i.e., the triangle curve) gradually increase.
However, there is still a significant gap between the reward (i.e., the
triangle curve) and $\bar{r}_{5}=0.9$ (i.e., the dash line). Such a gap
implies that incentivizing the selfish agents (i.e., the edge servers)
prevents the principal (i.e., the CP) from choosing the optimal arm (i.e., the
mobile device with the heaviest offloading demand). Nevertheless, Section VI-C
will show that our proposed mechanism $\mathfrak{A}$ can mitigate this
drawback when the system scales.

Fig. 3(b) shows that the fairness violation is decreasing for the two edge
servers. Note that the cumulative violation for server 2 is a little larger
than that for server 1, since server 2 corresponds to a smaller utilization
ratio. Hence the long-term payoff of server 2 is also smaller than server 1 as
show in Fig. 3(c). Furthermore, the triangle curve in Fig. 3(c) shows that the
CP’s average profit is gradually increasing as mechanism $\mathfrak{A}$ learns
about the average offloading demand.

###  VI-C Large-Scale Evaluation

Now we consider the large-scale edge network and investigate the impact of the
crowd size $N$. We set the parameters in Corollary 1 as $\alpha=1$ and
$\beta=0.2$. Fig. 4 plots the long-term average results for different crowd
sizes.

Fig. 4 shows that the total cost (i.e., the square curve) is decreasing in
$N$, and the total reward (i.e., the triangle curve) is increasing in $N$ and
converging to $\bar{r}_{5}=0.9$. This is because that it would be more likely
to match a low-cost edge server to the high-demand mobile device in a larger
edge network. Accordingly, a larger network would also improve the social
performance as shown by the circle curve in Fig. 4.

Fig. 4 shows that the CP profit (i.e., the diamond curve) is increasing in
$N$, while the edge servers’ average payoff (i.e., the star curve) is
decreasing in $N$. This is because that when there are more edge servers, each
individual is becoming increasingly dispensable. In this case, it incurs the
CP less expense to incentivize the low-cost one according to the payment rule
(22) in our proposed mechanism $\mathfrak{A}$.

Figure 4: Impact of the crowd size $N$.

##  VII Conclusions and Future Works

In this paper, we study the mechanism design problem for the incentivized
online learning (IOL) framework. The IOL framework exhibits a novel learning
paradigm that relies on the selfish agents. We characterize the strategic
principal-agent interactions in this framework based on the stochastic MAB
model. We propose a mechanism that is incentive compatible and ensures the
voluntary participation of agents and principal. This mechanism performs
asymptotically as well as the state-of-the-art baseline (that requires extra
information) in terms of the social welfare and the fairness of agent
utilization. Our analysis also unveils the impact of the crowd size. That is,
in the large-scale system, our proposed mechanism can achieve the theoretical
upper bound of the social welfare.

We view our study in this paper as the initial step towards understanding the
IOL framework. There are several valuable aspects for future investigations.
First, this paper focuses on the stationary environment. It would be
interesting to study the IOL mechanism design for the non-stationary case
based on the adversarial MAB model. Second, it is also interesting to study
the revenue-maximizing mechanism design problem under the IOL framework. Such
a design objective would be more attractive to the principal.

## References

  * [1] S. Shalev-Shwartz _et al._ , “Online learning and online convex optimization,” _Foundations and trends in Machine Learning_ , vol. 4, no. 2, pp. 107–194, 2011.
  * [2] S. Bubeck, N. Cesa-Bianchi _et al._ , “Regret analysis of stochastic and nonstochastic multi-armed bandit problems,” _Foundations and Trends® in Machine Learning_ , vol. 5, no. 1, pp. 1–122, 2012\.
  * [3] Y. Gai, B. Krishnamachari, and R. Jain, “Combinatorial network optimization with unknown variables: Multi-armed bandits with linear rewards and individual observations,” _IEEE/ACM Transactions on Networking_ , vol. 20, no. 5, pp. 1466–1478, 2012.
  * [4] P. Yang, B. Li, J. Wang, X.-Y. Li, Z. Du, Y. Yan, and Y. Xiong, “Online sequential channel accessing control: A double exploration vs. exploitation problem,” _IEEE Transactions on Wireless Communications_ , vol. 14, no. 8, pp. 4654–4666, 2015.
  * [5] Y. Liu and M. Liu, “An online approach to dynamic channel access and transmission scheduling,” in _ACM MobiHoc_ , 2015.
  * [6] C. Huang, H. Yu, J. Huang, and R. Berry, “Eliciting information from heterogeneous mobile crowdsourced workers without verification,” _IEEE Transactions on Mobile Computing_ , 2021.
  * [7] K. Han, C. Zhang, and J. Luo, “Taming the uncertainty: Budget limited robust crowdsensing through online learning,” _IEEE/ACM Transactions on Networking_ , vol. 24, no. 3, pp. 1462–1475, 2015.
  * [8] U. ul Hassan and E. Curry, “Efficient task assignment for spatial crowdsourcing: A combinatorial fractional optimization approach with semi-bandit learning,” _Expert Systems with Applications_ , vol. 58, pp. 36–56, 2016.
  * [9] S. K. née Müller, C. Tekin, M. van der Schaar, and A. Klein, “Context-aware hierarchical online learning for performance maximization in mobile crowdsourcing,” _IEEE/ACM Transactions on Networking_ , vol. 26, no. 3, pp. 1334–1347, 2018.
  * [10] X. Wang, R. Jia, X. Tian, and X. Gan, “Dynamic task assignment in crowdsensing with location awareness and location diversity,” in _IEEE INFOCOM_ , 2018\.
  * [11] C. Huang, H. Yu, J. Huang, and R. Berry, “Strategic information revelation mechanism in crowdsourcing applications without verification,” _IEEE Transactions on Mobile Computing_ , 2021.
  * [12] S. Chen, Y. Tao, D. Yu, F. Li, and B. Gong, “Distributed learning dynamics of multi-armed bandits for edge intelligence,” _Journal of Systems Architecture_ , vol. 114, 2021.
  * [13] T. Ouyang, R. Li, X. Chen, Z. Zhou, and X. Tang, “Adaptive user-managed service placement for mobile edge computing: An online learning approach,” in _IEEE INFOCOM_ , 2019.
  * [14] B. Wu, T. Chen, and X. Wang, “An mab approach for mec-centric task-offloading control in multi-rat hetnets,” in _IEEE ICC_ , 2020.
  * [15] Y. Li, X. Wang, X. Gan, H. Jin, L. Fu, and X. Wang, “Learning-aided computation offloading for trusted collaborative mobile edge computing,” _IEEE Transactions on Mobile Computing_ , vol. 19, no. 12, pp. 2833–2849, 2020.
  * [16] L. Zhang, Y.-C. Liang, and M. Xiao, “Spectrum sharing for internet of things: A survey,” _IEEE Wireless Communications_ , vol. 26, no. 3, pp. 132–139, 2018.
  * [17] R. K. Ganti, F. Ye, and H. Lei, “Mobile crowdsensing: current state and future challenges,” _IEEE communications Magazine_ , vol. 49, no. 11, pp. 32–39, 2011.
  * [18] R. D. Kleinberg and A. Slivkins, “Tutorial: incentivizing and coordinating exploration,” in _Proceedings of the 18th ACM conference on economics and computation, Cambridge_ , 2017.
  * [19] P. Frazier, D. Kempe, J. Kleinberg, and R. Kleinberg, “Incentivizing exploration,” in _ACM EC_ , 2014.
  * [20] I. Kremer, Y. Mansour, and M. Perry, “Implementing the “wisdom of the crowd”,” _Journal of Political Economy_ , vol. 122, no. 5, pp. 988–1012, 2014.
  * [21] S. Wang and L. Huang, “Multi-armed bandits with compensation,” in _NeurIPS_ , 2018.
  * [22] T. Zhou, J. Liu, C. Dong, and J. Deng, “Incentivized bandit learning with self-reinforcing user preferences,” in _ICML_ , 2021.
  * [23] S. Zhang, P. He, K. Suto, P. Yang, L. Zhao, and X. Shen, “Cooperative edge caching in user-centric clustered mobile networks,” _IEEE Transactions on Mobile Computing_ , vol. 17, no. 8, pp. 1791–1805, 2018.
  * [24] S. Zhang, W. Quan, J. Li, W. Shi, P. Yang, and X. Shen, “Air-ground integrated vehicular network slicing with content pushing and caching,” _IEEE Journal on Selected Areas in Communications_ , vol. 36, no. 9, pp. 2114–2127, 2018\.
  * [25] S. Yang, F. Wu, S. Tang, T. Luo, X. Gao, L. Kong, and G. Chen, “Selecting most informative contributors with unknown costs for budgeted crowdsensing,” in _IEEE/ACM IWQoS_ , 2016.
  * [26] G. Gao, H. Huang, M. Xiao, J. Wu, Y.-e. Sun, and Y. Du, “Budgeted unknown worker recruitment for heterogeneous crowdsensing using cmab,” _IEEE Transactions on Mobile Computing_ , 2021.
  * [27] M. Xiao, B. An, J. Wang, G. Gao, S. Zhang, and J. Wu, “Cmab-based reverse auction for unknown worker recruitment in mobile crowdsensing,” _IEEE Transactions on Mobile Computing_ , 2021.
  * [28] S. Kannan, M. Kearns, J. Morgenstern, M. Pai, A. Roth, R. Vohra, and Z. S. Wu, “Fairness incentives for myopic agents,” in _Proceedings of the 2017 ACM Conference on Economics and Computation_ , 2017, pp. 369–386.
  * [29] F. Li, J. Liu, and B. Ji, “Combinatorial sleeping bandits with fairness constraints,” _IEEE Transactions on Network Science and Engineering_ , vol. 7, no. 3, pp. 1799–1813, 2019.
  * [30] L. Gao, F. Hou, and J. Huang, “Providing long-term participation incentive in participatory sensing,” in _IEEE INFOCOM_ , 2015.
  * [31] P. Auer, N. Cesa-Bianchi, and P. Fischer, “Finite-time analysis of the multiarmed bandit problem,” _Machine learning_ , vol. 47, no. 2-3, pp. 235–256, 2002.
  * [32] W. Vickrey, “Counterspeculation, auctions, and competitive sealed tenders,” _The Journal of finance_ , vol. 16, no. 1, pp. 8–37, 1961.
  * [33] E. H. Clarke, “Multipart pricing of public goods,” _Public choice_ , vol. 11, no. 1, pp. 17–33, 1971.
  * [34] T. Groves, “Incentives in teams,” _Econometrica: Journal of the Econometric Society_ , pp. 617–631, 1973.
  * [35] _Technical report_ , https://wang-zhi-yuan.github.io/file/INFOCOM22.pdf.
  * [36] _Real-Time Price LMPs_ , https://dataminer2.pjm.com/feed/rt_hrl_lmps/definition.