1
Dynamic Hypergame for Task Assignment in Multi-platform Mobile Crowdsensing Under Incomplete Information Sumedh J. Dongare∗ , Christo Kurisummoottil Thomas¶ , Andrea Ortiz‡ , Walid Saad§ , Anja Klein∗ ∗ Communication Engineering Lab, Technical University of Darmstadt, Germany. ¶ Dept. of Electrical and Computer Engineering, Worcester Polytechnic Institute, Worcester, MA, USA. ‡ Institute of Telecommunications, Vienna University of Technology, Austria.
§ Wireless@VT, Bradley Department of Electrical and Computer Engineering, Virginia Tech, Alexandria, USA.
arXiv:2605.03569v1 [cs.NI] 5 May 2026
Emails: {s.dongare, a.klein}@nt.tu-darmstadt.de, [email protected], [email protected], [email protected]
F
Abstract—Mobile crowdsensing (MCS) is a promising distributed sensing paradigm for future wireless networks, where MCS platforms (MCSPs) recruit mobile units (MUs) through monetary incentives for sensing data collection. While most existing studies assume a single MCSP, practical deployments involve multiple competing MCSPs that simultaneously propose task offers to MUs, and MUs accept offers that maximize their revenue. This interaction gives rise to a two-sided matching game with contracts (MWC), decomposed into two components: (i) task proposal problem of the MCSPs and (ii) task acceptance problem of the MUs. To optimally solve (i), every MCSP requires information about other platforms’ preferences and the qualities of the MUs in advance. Similarly, to solve (ii) optimally, the MUs require information about the task execution efforts of all tasks in advance. Such information is unavailable at the MCSPs and at the MUs. To address the challenge of unknown preferences of the other MCSPs, the MWC is posed as a dynamic hypergame, where every MCSP models the unknown preferences through perceptions and refines them over repeated interactions. To solve the dynamic hypergame under incomplete information, we propose PACMAB, a fully decentralized perception-aware two-sided learning framework where, (i) each MCSP learns an adaptive task proposal strategy under competition, and (ii) each MU learns task acceptance policy by estimating task execution efforts. Computational complexity of PACMAB shows that it scales favorably for the MCSPs as well as the MUs. Extensive simulations show that PACMAB consistently outperforms the benchmarks by completing at least 41% more tasks without assuming complete information. Index Terms—Hypergame theory, Matching with contracts, learningguided matching, Reinforcement learning, Multi-armed bandits.
1
Introduction
1.1
Overview
This work was funded by the BMFTR project Open6GHub+ un- der grant 16KIS2407, by DAAD with funds from the German Fed- eral Ministry of Research, Technology and Space BMFTR under grant 57817830, and by the LOEWE Center emergenCITY under grant LOEWE/1/12/519/03/05.001(0016)/72. The work of Andrea Ortiz was funded by the Vienna Science and Technology Fund WWTF under grant 10.47379/VRG23002. The work of Walid Saad was supported by the U.S. National Science Foundation under grant 2201641.
R
ecently, mobile crowdsensing (MCS) emerged as a promising distributed sensing alternative to traditional wireless sensor networks (WSNs) [1]. Compared to WSNs, MCSs provides lower infrastructure costs, higher mobility, better coverage, and a wide range of applications due to availability of various sensors on mobile units to perform sensing tasks [2]–[4]. With the advancements in the Internet of Things (IoT) and a rapidly growing number of smart devices, MCSs has become a topic of interest in academia and in industrial applications [5], [6] such as traffic [7] and environmental monitoring [8], spectrum sensing [9], [10], and mobile health [11]. An MCS architecture consists of data requesters (DRs), mobile crowdsensing platforms (MCSPs), and mobile units (MUs). When a DR requires some sensing data from the target region, it creates a sensing request and sends it to an MCSP. The DR offers a payment as an incentive to the selected MCSP. The MCSP uses then part of this payment to recruit MUs for the sensing by sending them task offers. If an MU accepts the offer from an MCSP, it performs the task, collects the sensing result, and transmits it back to the respective MCSP. The MU receives the agreed payment according to the original task offer. Every MCSP decides its own task assignment strategy which maximizes its own net revenue. The DRs incentivize the MCSPs to obtain sensing data with better quality by offering the MCSPs payments proportional to the quality of sensing result. For each sensing task, different MUs may produce sensing results of different quality. Equivalently, the quality of the sensing result varies for every MU-task pair. Every MU decides on which task offer to accept from which MCSP depending on the expected net revenue from the offers, i.e., the payment offered minus the task execution efforts. 1.2
Research challenges
The task assignment between the MCSPs and the MUs determines the success of the MCS system. Ideally, the assignment must maximize the revenues of both the MCSPs and the MUs, such that neither of the them have any incentive to deviate from the assignment. To achieve such task assignment, the
2
MCS system has to overcome several challenges: 1) Conflicting interests of the MCSPs and the MUs: The task proposal strategies of the MCSPs and the acceptance strategies of the MUs’ are independent from each other and based only on their own net revenue. For the MCSPs, this means balancing between the revenue they get from the DRs and the payment offered to the MUs. Similarly, the MUs must balance between payments they receive and the efforts required to perform the tasks. Since the interests of the MCSPs and the MUs are not aligned, finding the optimal proposal and acceptance strategies is challenging. 2) Competing MCSPs: Since the number of available MUs is finite, the MCSPs compete with one another to have their proposals accepted. Thus, every MCSPs aims to make its task offers more attractive by selecting a suitable payment. A higher payment increases the likelihood of MUs acceptance, however, it reduces the net revenue of the MCSP. 3) Incomplete information: To make optimal decisions, MCSPs and MUs require complete information about the MCS system. For the MCSPs, this means information about (i) revenues earned from all MU-task combinations, (ii) preferences of the other MCSPs, and (iii) MUs’ preferences over the offered tasks. Similarly, the MUs must know the efforts required to perform the offered tasks. However, in realistic scenarios, such information is unavailable at the MCSPs and MUs. Thus, obtaining a task proposal strategy at the MCSPs and a task acceptance strategy at the MUs under incomplete information is crucial for the success of MCS. 1.3
Related works
Depending on the information available to the decisionmaking entities, existing task assignment approaches in MCS can be broadly classified into optimization- [12]–[15], gametheory- [16]–[18], and learning-based solutions [3], [4], [19], [20]. These approaches differ significantly in scalability, realism, and robustness. Optimization-based solutions formulate task assignment as centralized profit, energy, or social-welfare maximization problems under spatial, temporal, and budget constraints [12]–[15]. Such methods achieve near-optimal performance, but rely on complete non-causal information about the task characteristics and user capabilities. Assuming availability of such information at the MU or at the MCSP is unrealistic. Moreover, these works suffer from high computational complexity, which limits their applicability in large-scale and dynamic MCS systems. To improve scalability, game-theoretic approaches exploit decentralized decision-making by explicitly modeling strategic interactions between MCSPs and MUs, e.g., by modeling the problem as matching with contracts (MWC) [16]–[18]. However, these works assume availability of complete information regarding preferences of the MCSPs and the MUs which usually depends on task execution efforts, and data qualities of the MUs. Moreover, task characteristics and agent preferences are usually assumed to be static, which does not reflect the stochastic and time-varying nature of real-world MCS systems. Learning-based approaches relax these assumptions by allowing MCSPs and MUs to learn task utilities and preferences over time [3], [4], [19], [20]. Despite the improved realism, these works consider a single MCSP handling multiple MUs,
thereby neglecting inter-platform competition and strategic interactions among multiple MCSPs. A more realistic multiplatform MCSs has been recently investigated in [21]–[25]. However, these studies assume either an explicit cooperation among MCSPs or the existence of a trusted and impartial cross-platform task management entity. Such assumptions are difficult to fulfill in competitive real-world deployments, where MCSPs act selfishly. In an MCS system with multiple independent decision making agents, finding an optimal strategy for any agent would require information about the preferences of the other agents. However, the availability of such information is unrealistic to assume in practical applications. In such cases, hypergame theory [26]–[28] provides a framework to model strategic interactions between decision-making agents under incomplete information. Using this framework, agents maintain and update perceptions about the strategies or preferences of the other agents and use them to device a strategy under incomplete information. A hypergame is dynamic when the perceptions change over time [29]. Hypergames have been applied in cyber-security and semantic communications [29]– [32], but their use in MCSs to obtain task proposal and task assignment strategies remains largely unexplored. 1.4 Contributions The main contribution of this paper is a novel fully decentralized task proposal strategy for the MCSPs and task acceptance strategy for the MUs in the considered MCS system. To determine these strategies, every MCSP and MU requires knowledge about the other decision making agents. Under realistic settings, we assume that such information is unavailable to both entities and formulate the problem as a dynamic hypergame. Within the framework of the hypergame, the unknown preferences of the agents are modeled as perceptions and are updated over time. To account for the incomplete information about the MCS system, we utilize reinforcement learning and propose a learning-aided hypergame solution termed as PACMAB. The goal of PACMAB is to find strategies for the MCSPs as well as the MUs which maximize their individual revenues. Towards this goal we make the following key contributions: •
•
•
To solve the dynamic hypergame, we develop a perception-aware matching solution which accounts for the evolving perceptions of the MCSPs to obtain task proposal strategies that maximize their net revenue. In this approach, all MCSPs know their own preferences over MUs and tasks, while the MUs know their task efforts in advance. Under these idealized assumptions, we can determine a performance upper bound which can be used to compare the performance of the proposed PACMAB algorithm. We prove that the perception-aware matching solution converges to a stable hyper Nash equilibrium indicating that every MCSP achieves a stable assignment in its own subjective game under the presence of perceptions. We show that as the perception error reduces, the MCSPs’ net revenue increases. To handle the fully unknown preferences at both MCSPs and MUs, we propose PACMAB, a novel, fully decentralized, perception-aware two-sided learning solution. PACMAB consists of two components:
3
…
MU 1 MU 0
MCSP 0
MCSP 0
MCSP 0
…
…
MU 𝑘
MU 1
MU 2
MU 𝑘 MU 2
MU 0 …
MCSP 𝑖 (a)
MU 1 MU 0
MU 𝑘 MU 2
…
…
MCSP 𝑖 (b)
MCSP 𝑖 (c)
Fig. 1: Overview of the system model: (a) MCSPs send task offers to MUs. (b) MUs respond with either an accept or a reject. (c) Assigned MUs perform the task, transmit the result back to the respective MCSP and receive the payment.
•
•
(a) at every MCSP, we implement an upper confidence bound (UCB) multi-armed bandit algorithm to determine an adaptive task proposal strategy without strict requirement of the knowledge of own and other MCSPs’ preferences, and (b) at every MU, we implement a low complexity multi-armed bandit algorithm to learn the task execution efforts required to find an efficient task acceptance strategy. PACMAB enables each MCSP to maintain and update perceptions about the preferences of other MCSPs to obtain its own task proposal strategy. We analyze the computational complexity of PACMAB from the perspectives of the MCSPs and the MUs separately. Specifically, we show that from the perspective of the MCSPs, the complexity grows only linearly with the number of MUs, tasks, and the payment levels used by the MCSP. From the perspective of the MUs, the complexity grows only linearly with the number of MCSPs. We conduct extensive numerical evaluations to compare PACMAB’s performance against the benchmark algorithms. The results demonstrate superior performance of PACMAB in terms of social welfare, task completion ratio, and sensing quality without the strict requirement of complete information.
The rest of the paper is organized as follows. In Section 2, the considered MCS system model is introduced. Section 3 presents the problem formulation as an MWC and the reformulation as a dynamic hypergame. Section 4.1 provides a solution to this hypergame under information assumptions. Our proposed PACMAB algorithm is described in Section 5. The numerical evaluations are given in Section 6. Finally, conclusions are drawn in Section 7.
2
System model
2.1
Overview
Figure 1 illustrates our MCS system model. We consider a set I = {i}Ii=1 of I MCSPs. Similarly we assume a set K = {k}K k=1 of K MUs. The time is divided into T discrete time steps and each time step is given by t ∈ {0, 1, . . . , T − 1}. Table 1 provides the summary of notations used in this work.
Every MCSP i offers Ni different tasks in every time step t. These tasks are collected in the set Oti and are indexed by n. We consider that different types of tasks are present in Oti , e.g., temperature sensing, noise level monitoring, or taking a picture or a video. Different task types are collected in a set Z = {z}Z z=1 of Z task types. Each available task is given by i On,t and is mapped into a task type z ∈ Z using a mapping i function g : Ait → Z such that g(On,t ) = z . In each time i step, tasks of the same type z are collected in a set Oz,t ⊆ Oti . Each task of type z is characterized by the average data size dz of the raw sensing data which is measured in bits, the task processing complexity cz measured in CPU cycles/bit, and the average size sz of the processed sensing result, measured in bits, and which the MUs transmit back to the MCSP. All i the tasks in Oz,t have identical characteristics. We assume that only one MU is required to successfully complete a task i On,t . If an MCSP requires more sensing results for the same task type z , then it can generate more tasks of the same type and propose them to different MUs. The number ρiz of tasks available in one time step, which belong to the same task type i z , is termed the quota of task type z , with |Oz,t | = ρiz . 2.2
Mobile crowdsensing platforms
At the beginning of each time step t, every MCSP i offers i of type z to MU k along with a payment offer a task On,t i Pk,n,t ∈ Pzi . Pzi is a discrete set containing the possible payments that each MCSP can offer for each task type z . i i i , Pk,n,t ⟩ and aims The offer is denoted by Ôk,n,t = ⟨On,t at maximizing the net revenue of the MCSP. The MCSP transmits this offer to the MU and waits for its acceptance or rejection decision. Once accepted, the MU k completes the i and transmits the sensing result rk,n,t back to the task On,t MCSP i over a wireless channel. Note that an MCSP can offer only one task to an MU in time step t, as the MUs can execute i only one task per time step. If MU k accepts task offer Ôk,n,t i from MCSP i, this assignment is denoted by yk,n,t ∈ {0, 1}. All the assignment decisions for MCSP i are stored in the matrix Yit ∈ {0, 1}K×Ni . MCSP i and the interested DR make a contractual agreement in which the DR pays at least wzi monetary units to the MCSP for every completed task of type z . In addition to the basic payment wzi , the DR is willing to pay more proportional to the quality of the sensing task result. When MU k completes a task, it sends the sensing result rk,n,t back to the MCSP. MCSP i calculates the quality factor i qk,n,t ∈ [0, 1] of the sensing result rk,n,t using a quality function Qiz (·) given by i qk,n,t = Qiz (rk,n,t ).
(1)
i For a fixed MU k and task On,t of type z , the quality i qk,n,t is an unknown random variable which can be observed only after completing the task. Each MCSP evaluates the quality independently and based on the specific aspect of the sensing result it wants to focus on. Some examples of the quality functions are the Peak Signal-to-Noise Ratio (PSNR) of an image, or the accuracy and resolution of a temperature measurement. As Qiz (·) is different for each MCSP, the same sensing result rk,n,t can have different quality factors depending on to which MCSP it is submitted. The calculation
4
TABLE 1: Table of notations Description
Notation
Description
Notation
Set of MCSPs, total available MCSPs, MCSP index Set of MUs, total available MUs, MU index Time horizon, time step index Set of task types, total available task types, task type index Set of payments offered by MCSP i per task type z , payment index, offered payment to MU k Set of tasks from MCSP i at time step t Available task of MCSP i Sensing data size, complexity, task size of type z Minimum earning of MCSP i from completion of a i task On,t of type z Actual earning of MCSP i from completion of a task i On,t of type z by MU k Offered payment from MCSP i to MU k Preferences of MCSP i over MU k and task type z
I, I, i K, K , k T, t Z, Z, z
i Quality of MU k for task On,t i Utility of MCSP i if MU k completes task On,t i Utility of MU k after performing task On,t i Task completion time of MU k for task On,t
i qk,n,t MCSP,i Uk,n,t MU Uk,n,t τk,n,t
i Pzi , p, Pk,n,t
Task quotas of MCSP i for task type z
ρiz
Oti i On,t sz , c z , d z wzi
i Task completion energy of MU k for task On,t i Sensing time/energy of MU k for task On,t i Computing time/energy of MU k for task On,t i Communication time/energy of MU k for task On,t
Ek,n,t sense sense τk,n,t , Ek,n,t comp comp τk,n,t , Ek,n,t comm comm τk,n,t , Ek,n,t
i wk,z
i MCSP i’s offer to MU k for task On,t
i i i Ôk,n,t = ⟨On,t , Pk,n,t ⟩
i Pk,n,t i Sk,z
Task assignments of MCSP i Preferences of the other MCSPs over MU k and task type z
yti −i Sk,z
i of wk,z given by i i wk,z = (1 + qk,n,t )wzi .
(2)
We emphasize that the proposed system model is flexible and allows alternative functions to be easily integrated for i i evaluating wk,z . As the quality qk,n,t of MU k is unknown, MCSP,i i MCSP i does not know wk,z in advance. The utility Uk,n,t i of the MCSP when the task On,t of type z is successfully performed by MU k is given by MCSP,i i i Uk,n,t = wk,z − Pk,n,t .
(3)
Thus, the MCSP has to balance the quality of the MUs with the payments they will receive. The total utility achieved by MCSP i in time step t is given by
UtMCSP,i =
Ni K ∑ ∑
MCSP,i i yk,n,t Uk,n,t .
k=1 n=1
of type z assigned to MU k is given by
MCSP,i
The total estimated utility Ūt
ŪtMCSP,i =
Ni K ∑ ∑
(5)
in t is given by
MCSP,i Ūk,n,t .
comp τk,n,t =
c z dz , fklocal
(7)
where fklocal is the CPU frequency of MU k , measured in Hz. After processing, the sensing result rk,n,t has size sz < dz . This sensing result is then transmitted to MCSP i. The comm,i transmission time τk,n,t required for this is drawn from a comm,i stationary random distribution with PDF fτzcomm,i (τk,n,t ). k,n,t
(4)
i Since wk,z is not known, the MCSP estimates its utility while MCSP,i assigning the tasks. The estimated utility Ūk,n,t for a task MCSP,i MCSP,i i i Ūk,n,t = E{Uk,n,t } = E{wk,z } − Pk,n,t .
sense distribution function (PDF) fτzsense (τk,n,t ) with expected k,n,t sense sense value τ̄k,z = E{τk,n,t }. This expected value depends on the task type z and the capabilities of MU k . After generating the raw sensing data dz , MUs k has to process it such that the result can be transmitted to the MCSP over a wireless comp channel [20], [33]. The computing time τk,n,t for processing the sensing data dz is given by
(6)
k=1 n=1
2.3 Mobile Units In every time step t, the MUs receive task offers from the MCSPs. Without loss of generality, we assume that all the available MUs are capable of performing tasks of all types. However, the quality of the sensing result may vary depending on which MU performs the task. Every MU k may receive multiple task offers from different MCSPs. However, in one time step t, MU k can perform only one task and thus, it has to decide which task offer to accept and which to reject. MU k makes this decision depending on the efforts required to complete the offered task. To successfully complete a task i On,t , the MU has to spend time and energy. Specifically, an sense MU k requires time τk,n,t , measured in seconds, to sense sense and generate sensing data dz , measured in bits. τk,n,t is drawn from a stationary random distribution with probability
comm,i
The expected value of this distribution is denoted by τ̄k,z and depends on sz and the quality of the communication channel between MU k and MCSP i. We assume that the transmission happens via orthogonal frequency division multiple access (OFDMA), meaning, each MU is assigned a communication bandwidth which is orthogonal to that of the other MUs. The total time required for successfully comp comm,i sense completing the task will be τk,n,t = τk,n,t + τk,n,t + τk,n,t . Similar to time efforts, the MUs also spend energy. The i total energy effort invested by MU k to perform task On,t is denoted by Ek,n,t and is given by comp sense comm Ek,n,t =Ek,n,t + Ek,n,t + Ek,n,t comp comp comm,i comm sense sense =τk,n,t pk,n + τk,n,t pk + τk,n,t pk .
(8) (9)
comp comm Here psense , pk represent the sensing, computing, k,n , pk
and communication power required by MU k . Considering the time and energy efforts, we define the MU-specific cost effort function Ck,n,t [20], [33] as effort Ck,n,t = αk τk,n,t + βk Ek,n,t .
(10)
Note that the cost of performing any task of type z is identical for a given MU k irrespective of the MCSP i offering it. This is because the cost depends only on the MU capabilities and the task type. The cost function balances completion time and consumed energy using the MU-specific time-cost parameter αk measured in monetary units per second and energy-
5
cost parameter βk measured in monetary units per joules. effort Each MU uses Ck,n,t as the minimum payment required to compensate its efforts. In reality, the MUs prefer payments effort higher than Ck,n,t in order to make profit. The MU profit is calculated as MU i i effort Uk,n,t = yk,n,t (Pk,n,t − Ck,n,t ).
(11)
effort Since the true task efforts Ck,n,t are not known to MU k in advance, it estimates its utility as MU MU i i Ūk,n,t = E{Uk,n,t |On,t ∈ Oz,t } i effort }. = Pk,n,t − E{Ck,n,t
(12)
The MUs accept the task offers that maximize their expected MU . They make this decision indepenestimated utility Ūk,n,t dently and selfishly. We assume that the MUs provide a feedback to the MCSPs when a task is rejected. The feedback involves which task they have accepted and at what payment. The MUs share this information as an incentive to receive better and more attractive offers in the future. Additionally, it helps the MCSP to estimate the preferences of MUs as well as the strategy of the other MCSPs.
the received task offers from different platforms according to their expected utility, i.e., j i MU MU MU Ôk,n,t ⪰MU Ôk,n Ūk,n ′ ,t . ′ ,t ⇐⇒ Ūk,n,t ⪰k k
(14)
The MU will always choose the offer that maximizes its i expected utility ŪkMU . The binary variable yk,n,t = 1 if MU k i i accepts task offer Ôk,n,t , and yk,n,t = 0 otherwise. We define a stable task assignment as follows: Definition 1. A task assignment Yt is unstable if there are i two MUs, MU k and MU l, and two task offers, Ôk,n,t and j Ôl,n′ ,t , from MCSPs i and j such that: i i a) yk,n,t = 1, i.e., MU k has accepted the task offer Ôk,n,t . j j b) yl,n′ ,t = 1, i.e., MU l has accepted the task offer Ôk,n′ ,t . j MU i i i MCSP Ôk,n,t , ⟨k, z, Pk,n,t ⟩ and Ôk,n c) ⟨l, z ′ , Pl,n ′ ,t ⟩ ⪰i ′ ,t ⪰k ′ i i.e., MCSP i would prefer contract ⟨l, z , Pl,n′ ,t ⟩ instead of the i ⟩ and MU k would also prefer assigned contract ⟨k, z, Pk,n,t j i task offer Ôk,n′ ,t over the assigned offer Ôk,n,t . Consequently, a stable task assignment solution maximizes the achieved utilities of the MCSPs and the MUs, where neither of them can unilaterally change their task assignment strategy to improve their utility.
3 Problem formulation 3.1 Problem formulation as a matching game with contracts To capture the fact that both the MCSPs and the MUs make independent and selfish decisions based on their own preferences, we formulate the task proposal and task acceptance problem using MWC [34]. All the MCSPs and the MUs are considered to be rational and selfish decision makers which aim to maximize their own utilities. The main goal of MWC is to identify a stable matching solution, i.e., task assignments which neither the MCSPs nor the MUs can improve by changing the assignments. The MWC is a model designed for two-sided matching markets such as our MCS system where the MCSPs have certain sensing demands from a target area and the MUs offer their sensing resources in exchange for payments. The sensing demands are defined as sensing tasks which the MCSPs offer to the MUs along with a certain payment as an incentive. The matching game G in time step t MCSP } is formally defined by the tuple G = {I, K, Oti , ⪰MU k , ⪰i where ⪰MU represents the preference ordering of MU k , and, k similarly, ⪰MCSP represents the preference ordering of MCSP i i i i. We also define a contract xik,z,p = {i, k, On,t , Pk,n,t } for i the MWC [34]. Each contract xk,z,p is bilateral, i.e., it is associated to one MCSP and one MU. The finite set X contains all possible contracts. The MCSPs’ preference ordering ⪰MCSP ranks the coni tracts in X in decreasing order of the expected utility, i.e., i i ⟨k, z, Pk,n,t ⟩ ⪰MCSP ⟨l, z ′ , Pl,n ′ ,t ⟩ i MCSP,i MCSP,i . ⪰MCSP Ūl,n ⇐⇒ Ūk,n,t ′ ,t i
(13)
i In other words, MCSP i prefers to offer task On,t of type z to i MU k for the payment Pk,n,t more than it prefers to offer task i Oni ′ ,t of type z ′ to MU l at the payment Pl,n ′ ,t . This is because the former offer yields higher expected utility. Note that tasks of same type will also yield different expected utilities depending on which MU performs the task and the payment offered. Similarly, the MUs’ preference ordering ⪰MU ranks k
3.2
Problem reformulation as a dynamic hypergame
To solve game G , every MCSP requires its own preference ordering over all the possible contracts and the task assignment strategy of all other MCSPs. In reality, the MCSPs do not know about the strategies of the other MCSPs. Therefore, in order to obtain a task assignment strategy, every MCSP maintains its own perception about the other MCSPs’ preferences. As a result, the utility achieved by the MCSP from task assignment strategy depends on the accuracy of its perceptions. The lack of knowledge about the other MCSPs motivates us to reformulate the MWC into a dynamic levelone hypergame in which misperceptions about the preferences of other MCSPs exist. The MCSPs observe the outcomes of the repeated matching game to improve their perceptions. Formally, a dynamic level-one hypergame Ht [26]–[28], [35] is defined as follows. Definition 2. A hypergame Ht is given by (I, (G i )i∈I ), where I is a set of I MCSPs and Gti = (I, S i , UtMCSP,i ) is a subjective game of the ith MCSP, where: a) I is a set of MCSPs perceived by MCSP i. b) S i = ×j∈I Sji is a set of strategies perceived by MCSP i, where Sji is the set of the strategies of MCSP j perceived by MCSP i. MCSP,i is the utility function of MCSP i. c) Ut Note that the set I contains all the MCSPs in the MCS system including the MCSP i itself. Due to the existence of the MCSP-specific perceptions, every MCSP virtually plays its subjective game Gti in which it uses its own perceptions and own preferences to device a task proposal strategy. In hypergame Ht , the strategy S i of MCSP i depends on its perception about the other MCSPs, denoted by −i. If the strategy Sji that MCSP i perceives about MCSP j , with j ̸= i, differs from MCSP j ’s actual strategy, then MCSP i misperceives MCSP j . Misperceptions degrade the achieved utilities of the MCSPs and the achieved utilities of the MUs as
6
Algorithm 1 MCSP i’s perception-aware matching algorithm
MCSP i Own preferences
Perception of MCSP j
MCSP i’s strategy
update Matching surprise for MCSP i
MCSP i’s task offers Available MUs
MCSP j’s strategy
Own preferences
Perception of MCSP i
MUs’ decisions
MCSP j’s task offers
Matching outcome
Matching surprise for MCSP j
update
MCSP j
Fig. 2: Illustration of interaction between 2 MCSPs in a perception-aware matching solution they result in suboptimal task assignments. The definition of rationality in a hypergame remains subjective to the perceived game Gti of MCSP i. If MCSP i misperceives other MCSPs, the obtained task assignment strategy of MCSP i may not be rational to other players in their perceived game Gt−i and also in the base game G . However, the obtained strategy can be rational for MCSP i in its own perceived game Gti if it is the best response to its perceptions. The repeated nature of the MWC allows the MCSPs to update their perceptions using the outcomes of the game as feedback. The selected strategy of MCSP i may result in unexpected outcomes or surprises due to the existence of misperceptions. As a result, the MCSPs have an intrinsic motivation to use this feedback to update their perceptions and adjust their task proposal strategy. Over time, the misperceptions decrease as the estimate of the other MCSPs’ strategy becomes more accurate. When the perception error between the perceived preferences of other MCSPs and their respective true preferences reaches a constant value, the solution becomes a stable hypergame solution [36]. After this point, MCSP i has no intrinsic motivation to update its perceptions because there are no matching surprises in the outcome. The hypergame Ht is then said to have achieved stability. In our MCS system, since the base game is an MWC, stability means that the decision making entities have found an assignment from which they cannot deviate unilaterally without reducing their individual achieved utilities. In this context, a stable hypergame outcome indicates that the decision making agents have obtained an assignment under their own perceptions from which they will not deviate.
4 Perception-aware Matching Solution 4.1 Overview To optimally solve the hypergame Ht under the presence of MCSP-specific perceptions, the MCSPs must know their own preferences over all MU-task combinations. Similarly, the MUs must know their own preferences over the task types. The MCSPs maintain their own perceptions about the preferences of the other MCSPs and update them over repeated interactions. Using this information, every MCSP obtains a task proposal strategy that maximizes its own utility while accounting for the competition. Similarly, the MUs accept the offers that maximize their own utilities. The success of the task proposal and task acceptance strategies
Require: θii . 1: Initialization: i,min i 2: Initialize θ−i,k,z = 0, Pk,n,t = 0. 3: for t = 1, 2, . . . , T do 4: Initialize Oti 5: Draw a random variable v from U [0, 1]. 6: if ϵt > v then 7: for k = 1, 2, . . . , K do i 8: Choose On,t ← z from a uniform random distribution of i . available task type z ∈ Oz,t ▷ Exploration 9: Draw random variable va from U [0, 1]. 10: if va < 0.5 then i,min i 11: Pk,n,t ← Pk,n,t 12: else i i 13: Pk,n,t ← θi,k,z 14: end if i i ,Pi 15: Send sensing offer Ôk,n,t = ⟨On,t k,n,t ⟩ 16: end for 17: else i 18: Get k, On,t ∀k, n. ▷ Exploitation i i . 19: Calculate shadow price P̄k,z by removing z from θ−i i,min i i 20: Set Pk,n,t = max(Pk,n,t , P̄k,z ). i i ,Pi 21: Send sensing offer Ôk,n,t = ⟨On,t k,n,t ⟩. 22: end if 23: Get MU’s response to the task offer. i 24: for each offer Ok,n,t do i i 25: if Ok,n,t is accepted, i.e., yk,n,t = 1 then MCSP,i 26: MU k performs the task, MCSP i observes Uk,n,t , i qk,n,t . 27: else 28: if Rejection due to Negative Utility then i,min i,min +1 ← Pk,n,t 29: Update Pk,n,t 30: else 31: MU k accepts MCSP j ’s task offer j i i } 32: Update θj,k,z = max{θj,k,z , Pk,n,t 33: end if 34: end if 35: end for 36: Update ϵt = ϵt−1 ∗ ϵd 37: end for
resulting from the solution of Ht highly depends on the accuracy of the perceptions. In this section, we present a perception-aware matching algorithm to optimally solve the dynamic hypergame Ht formulated in Section 3. Using this algorithm, every MCSP obtains a task proposal strategy which maximizes its own utility. For this algorithm, we assume that every MCSP i i i knows its own expected revenue θi,k,z ≜ E{wk,z } for each MU-task type pair (k, z). The assumption implies that every MCSP knows the qualities of every MU for every task type z . On the MU-side, we assume that every MU knows the task execution efforts for all task types in advance. Note that the availability of such information to any of the entities in advance is unrealistic, and makes it impossible to implement the perception-aware matching solution in real-world MCS applications. However, we present this algorithm as a theoretical upper bound solution for the dynamic hypergame. We also provide the equilibrium analysis of this solution to illustrate that it is a stable hyper Nash equilibrium solution. The known expected revenues and the possible payments induce preference orderings of MCSP i over all MU-task combinations. Note that MCSP i does not know the expected revenues of other MCSPs and maintains its perceptions i }∀j∈I,j̸=i which are updated from observed outcomes {θj,k,z i or surprises. To simplify the notation, we use θ−i to denote
7
the perception MCSP i has about all other MCSPs for all MUs and task types. The core idea of the algorithm is that every MCSP uses its preferences over MUs and tasks and its perceptions to devise a task proposal strategy. This is illustrated in Fig. 2. At first, the perceptions are inaccurate, and thus the resulting task proposal strategy is also suboptimal. Over repeated interactions, the MCSPs observe the outcomes of the game and use these outcomes to update their perceptions about the other MCSPs. As the perception error, i.e., the difference between the true expected revenues of the other MCSPs and the perceived values, reduces, the task proposal strategy improves. To learn their perceptions, the MCSPs employ an ϵ-greedy algorithm which balances between exploring new MU-task combinations at different payments and exploiting their current perceptions to obtain offers which maximize the expected utility using the ϵ parameter. 4.2
Solution description
i As shown in Alg. 1, every MCSP i initializes θ−i and the i,min minimum payment matrix Pk,z per MU k and task type z with zeros (Line 2). In every time step t, the MCSP i obtains the set Oti of tasks it has to assign to the available MUs (Line 4). With probability ϵt , the MCSP explores or else, exploits (Line 5,6). In the exploration phase, the MCSP probes the i,min environment by offering a random payment between Pk,z i and its own expected revenue θi,k,z with a probability ϵa (Line i i i 10-14). The MCSP creates a task offer Ôk,n,t = ⟨On,t , Pk,n,t ⟩ for every MU (Line 15). In the exploitation phase, the MCSP i utilizes its percepi tions θ−i about the other MCSPs about the willingness of the other MCSPs to offer tasks to the MUs. MCSP i then uses the well-known Hungarian algorithm [37], [38] to obtain a task proposal strategy from the expected revenue θii of itself i and its perception θ−i about the other MCSPs (Line 18). The Hungarian algorithm essentially identifies task proposals that will maximize the expected utility of the MCSP. Additionally, the Hungarian algorithm also estimates proposals of the other MCSPs from the perceptions of MCSP i. The next step is to identify suitable payments for the MU-task combinations found using the Hungarian algorithm. MCSP i estimates how valuable a task type z is to its competitor by calculating the decrease in the overall expected utility of the competitor if it had one less task of that type. From this value, MCSP i evaluates how much it needs to offer to outbid the competitor for some MU (Line 20). After sending the sensing offer to the MUs, every MCSP waits for their responses (Line 21). If the i i offer Ôk,n,t is accepted, i.e., yk,n,t = 1, MU k performs task i On,t (Line 25). With this assignment, the MCSP i achieves MCSP,i i Uk,n,t and pays Pk,n,t to the MU k (Line 26). If the offer is i rejected, i.e. yk,n,t = 0, the MU conveys this decision to the MCSP i along with a reason. In case of a rejection due to a i,min negative utility, the MCSP i updates Pk,z by increasing the payment index p by one (Line 28-29). Otherwise, the rejection is because the MU k chose the offer of some other MCSP j with j ̸= i. This is a matching surprise for the MCSP i which j i then triggers the perception update as θj,k,z = Pk,n,t for the accepted MCSP j (Line 32). Finally, ϵt is updated for the next time step (Line 36).
4.3
Equilibrium analysis
We will now analyze the strategies of the competing MCSPs obtained from the perception-aware matching algorithm to solve the hypergame Ht . We show that the algorithm reaches a Hyper Nash Equilibrium (HNE) [35], [36] under the existence of MCSP-specific perceptions. We collect all the matching decisions made in time step t in matrix Yt . The MCSP-specific perceptions induce MCSP-specific MCSP,i (Yti ; θi ), where θi = perceived expected utility Ut i i [θi θ−i ]. Every MCSP i aims to obtain a task proposal strategy i which is its best response to the perceptions θ−i about the other MCSPs’ that maximizes its perceived expected utility. As discussed in the previous section, due to the existence of perceptions, every MCSP plays a game Gti which is its own subjective game due to its own perceptions. We define a hyper Nash equilibrium subject to the MCSP-specific perceptions of all MCSPs. Definition 3. For a fixed perception profile θ = (θi )i∈I , a joint task assignment Y∗ = (Yit )i∈I is a Hyper Nash Equilibrium (HNE) solution for every MCSP i ∈ I MCSP,i if, Y∗ ∈ arg maxYit ∈Yt Ut (Yit ; θi ). Equivalently, for i
MCSP,i
all unilateral deviations, Ỹt ∈ Yt , Ut i UtMCSP,i (Ỹt ; θi ).
(Yit ; θi ) ≥
This means that each MCSP i’s offers must be its best response to its perceptions about the other MCSPs in its perceived game Gti . Due to the misperceptions, even with the best response strategy, MCSPs can experience matching surprises in the MCS system. The matching surprises occur when an MU was expected to accept a task offer but rejected or when an MU accepted a task offer at a lower payment than before. The perceptions are updated when a matching surprise is encountered. The mean absolute error between the true expected revenue of the MCSP j , i.e., θjj , and the perception of this parameter θji maintained by MCSP i is∑called perception error of MCSP i given by, j i ∆θi (t) = j E{|θj − θj |}∀j ∈ I where j ̸= i. In our i MCS system, ∆θ (t) is a monotonically decreasing function i since the perceptions θ−i are monotonically increasing and j the true revenue θj ∀j ∈ I is fixed. In the context of a perception error, an HNE solution is a stable HNE (SHNE) if the profile of the strategies is a NE in the subjective games of the MCSPs, i.e., SHNE(Ht ) = ∩i∈I N (Gti ) [35], [36]. In a repeated matching game with contracts, this means that the perceptions have stabilized to a constant value and no player has an intrinsic motivation to update its perception to imMCSP,i (Yti ; θi ) [35], [36]. When the prove its expected utility Ut i perceptions converge, i.e., ∆θ (t) = 0, each MCSP i achieves an optimal best response strategy. This is an SHNE solution that the MCSPs have achieved as SHNE(Ht ) = ×i∈I N (Gti ). When the misperceptions disappear from every MCSP, all of the MCSPs are practically playing the base game G with complete information which helps them achieve their highest ∗MCSP,i possible utility Ut . At this point, for every MCSP i, the strategies that other MCSPs have chosen are consistent with the MCSP i’s anticipation and there is no incentive to update their perceptions further, i.e., a stable solution is achieved [35], [36]. In the following, we summarize the assumptions made for the perception-aware matching algorithm.
8
Assumption 1. All MCSPs maximize their expected utility:
Yti ∈ arg max UtMCSP,i (Y i ; θi ) Y i ∈Yi
i Assumption 2. When MU k rejects offer Ôk,n,t from MCSP i j because it accepted offer Ôk,n′ ,t from MCSP j ̸= i, the MU j truthfully reveals the tuple (j, Pk,n′ ,t , z) to MCSP i. i Assumption 3. There exists M < ∞ such that θi,k,z ≤M for all i ∈ I , k ∈ K, z ∈ Z . −1 Assumption 4. The exploration rate {ϵt }Tt=0 satisfies ∞ ∑
ϵt = ∞ and
t=0
∞ ∑
ϵ2t < ∞.
t=0
Theorem 1. Under Assumptions 1-4, the perception-aware matching algorithm satisfies the following properties: 1)
2)
3)
4)
Monotone Perception The perception ∑ Convergence: ∑ j i error ∆θi (t) = E [|θ j̸=i k,z j,k,z − θj,k,z (t)|] is monotonically non-increasing in t. Almost Sure Convergence: limt→∞ ∆θi (t) = i i ∆θ∞ almost surely where ∆θ∞ ≥ 0 is the residual perception error. Exponential Convergence Rate: There exist constants λ > 0 and ϵnoise ≥ 0 such that E[∆θi (t)] ≤ ∆θi (0) · e−λt + ϵnoise λ MCSP,i Utility Convergence: Let USHNE denote the utility at the stable hyper Nash equilibrium. Then MCSP,i i lim inf E[UtMCSP,i ] ≥ USHNE − L · ∆θ∞
t→∞
where L is the Lipschitz constant of the utility function. Proof: See Appendix.
5
Proposed Algorithm
5.1
Overview
The perception-aware matching algorithm presented in the previous section solves the dynamic hypergame Ht under the assumption that MCSPs and MUs know their own individual preferences. In realistic scenarios, the MCSPs and the MUs do not know their own preferences in advance. Additionally, the MCSPs do not know the strategies of other MCSPs which, however they need to obtain an optimal best response strategy. To help the MCSPs and the MUs to learn their own preferences based on their expected utilities, we propose a fully decentralized perception-aware combinatorial multi-armed bandit (PACMAB) solution. This algorithm has two components: (i) MCSPs’ perception-aware online learning algorithm for task assignment strategy, and (ii) MUs’ multi-armed bandit based online learning for task offer acceptance strategy. Given these two components, PACMAB is essentially a multi-agent multi-armed bandit algorithm in which different players have different goals and selfishly and independently decide on their strategy. For the MCSP’s task assignment problem, we employ an upper confidence bound (UCB)-based algorithm. Since the action space of each MCSP is prohibitively large, an algorithm capable of systematically addressing the explorationexploitation trade-off through uncertainty reduction is essential. To this end, we incorporate perception-based action
Algorithm 2 MCSP i’s learning-based perception-aware matching algorithm 1: Initialization: win,i lost,i 2: UCB values for {⟨k, z, p⟩ : 0}∀k, z, p, γk,z = 0, γk,z =0 3: for t = 1, 2, . . . , T do a,i 4: ζta , ρz = ϕ. 5: Check available tasks Ait . i , γ win,i , and γ lost,i . 6: Compute feasible set Õtfeas,i based on θ−i k,z k,z 7: for k = 1, . . . , K do 8: for z = 1, . . . , Z do i and (k, z) ∈ Õ feas,i then 9: if z ∈ Oz,t t 10: for p = 1, . . . , P do 11: Get UCB values in a set {⟨k, z, p⟩ : UCBik,z,p }. 12: end for 13: end if 14: end for 15: end for 16: Sort the set {⟨k, z, p⟩ : UCBik,z,p } in decreasing order. 17: for each candidate in {⟨k, z, p⟩ : UCB score} do 18: if k ∈ ζta then 19: continue 20: end if i 21: if ρa,i z ≥ ρz then 22: continue 23: end if i i ,Pi 24: Create offer Ok,n,t = ⟨On,t k,n,t ⟩. 25: Update ζta ← k. a,i 26: Update ρa,i z = ρz + 1 . 27: end for 28: Get MU’s response to the task offer. ▷ Algorithm 3 i 29: for each offer Ok,n,t : do i 30: if Ok,n,t is accepted, i.e., yk,n,t = 1 then win,i win,i 31: Increase acceptance counter γk,z = γk,z +1 MCSP,i 32: MU k performs the task, MCSP i observes Uk,n,t , i qk,n,t . i
MCSP . 33: Update estimates Ûk,n,t 34: else lost,i lost,i 35: Increase the rejection counter γk,z = γk,z +1 MCSP,i MCSP,i 36: Ûk,n,t ← Ûk,n,t−1 . ▷ Eq. (16) 37: end if 38: end for 39: end for
pruning, which restricts each MCSP’s candidate arm set to those expected to yield superior performance, rather than exhaustively evaluating all the possible arms. This pruning mechanism significantly accelerates the convergence of the proposed PACMAB algorithm. 5.2 Perception-aware combinatorial multi-armed bandit (PACMAB) solution The algorithm is presented in Alg.2. Every MCSP initializes the UCB values with zeros. Additionally every MCSP win,i i maintains an acceptance counter γk,z and a rejection lost,i counter γk,z per MU and task type combination (Line 2). These counters keep track of how many times offers involving the (k, z) combination were accepted and rejected, respectively. In every time step t, a set ζta and a vector ρa,i z are initialized with ϕ and zeros, respectively (Line 4). The set ζta monitors assigned MUs in the current time step t such that one MU will receive only one task from MCSP i. The vector ρa,i z monitors assigned tasks per task type z such that the task quotas ρiz are respected. The MCSP i then checks the available tasks Oti to be performed (Line 5). Out of all possible task offers, MCSP i evaluates a feasible set a,i feas,i based on acceptance counter γk,z and of task offers Ot win,i its perception θi−i about other MCSPs. Considering γk,z ,
9
an acceptance ratio of every (k, z) is evaluated. From this, the MCSP i evaluates expected utility given the acceptance win,i
MCSP,i
ratio as Ûk,n,t = Ûk,n,t
win,i γk,z
win,i lost,i (γk,z +γk,z )
. The MCSP i prunes
different ⟨k, z, p⟩ combinations for which the expected utility win,i Ûk,n,t ≤ 0. Additionally, the MCSP i prunes the payment indices based on θi−i . To do so, it estimates the chances of i winning, i.e, attract the MU k to perform the task On,t , −i based on the∑ payment index p and own perceptions θi as p −i −i Prwin,i (p) = p′ =0 πk,z (p′ ) where πk,z is a probability mass function of other MCSP for the given MU k and task type z . All payment levels with a probability of winning below a threshold are removed. Then, for every MU, task type, and the payment index in the feasible task offer set Ofeas,i , we compute the UCB value given by √ log(UCBt ) MCSP,i i UCBk,z,p = Ūk,n,t + UCBc , (15) Lk,z,p where UCBc and UCBt denote the UCB exploration constant and UCB time step index, respectively. Lk,z,p monitors how often the contract xik,z,p has been selected (Line 7-15). Initially, the algorithm explores different contracts to gather more information about them and as the time progresses, the algorithm exploits the gathered information. The feasible task offer set Ofeas,i is then sorted according to the decreasing order of UCB values (Line 16). Out of this set, task offers are chosen respecting task quotas and ensuring that each MU receives only one offer per MCSP. Therefore, if MU k is already assigned, i.e. k ∈ ζta , then we skip all contracts involving MU k (Line 18-19). Similarly, if the task quotas i are already exhausted, i.e., ρa,i z = ρz , then we skip all the contracts which involve the task type z (Line 20-21). When i a task offer Ok,n,t is created from the feasible set, the values a a,i of ζt and ρz are updated (Line 24-26). The MCSP i then sends all the task offers to the respective MUs and waits for their responses (Line 28). For every task offer, the MU responds with either an accept or a reject decision. If the i task offer is accepted, i.e. yk,n,t = 1, the acceptance counter win,i γk,z is increased by one (Line 31). MU k performs task ain,t and sends the task result back to MCSP i. From the i result, MCSP i evaluates the true quality qk,n,t and observes MCSP,i MCSP,i Uk,n,t (Line 32). From the observed utility Uk,n,t , the estimated expected utility is updated (Line 33) as MCSP,i MCSP,i Uk,n,t − Ûk,n,t MCSP,i MCSP,i Ûk,n,t = Ûk,n,t−1 + . Lk,z,p
(16)
i = 0, then the rejection If the offer is rejected, i.e. yk,n,t lost,i counter γk,z is increased by one and the expected utility from the previous time step is used again.
The MUs do not know the efforts required to perform different tasks in advance, and have to learn them over time. To learn these task efforts, every MU k runs a multi-armed bandit in which it learns about the task efforts for each task type z . MU k ’s learning-aided task acceptance algorithm is given in Algorithm 3. Every MU k initializes its expected MU utility Ûk,z for every task type z with zeros (Line 1). In every time step t, every MU k draws a random variable ϵMU k between [0, 1]. If ϵMU < ϵa , the MU explores, else exploits k (Line 3). In the exploration phase, the MU randomly selects
Algorithm 3 MU k ’s learning-based task offer acceptance algorithm MU ∀z ∈ Z . 1: Initialize: Ûk,z 2: for t=1,…, T do 3: Draw ϵMU from U [0, 1]. k a then 4: if ϵMU < ϵ k i 5: Select random task offer Ôk,n,t from the received offers ∀i ∈ I. i 6: Convey the acceptance decision yk,n,t = 1 to the respective MCSP i. 7: else MU i which maximizes the Ûk,n,t 8: Select a task offer Ôk,n,t i 9: Convey the acceptance decision yk,n,t = 1 to the respective MCSP i. 10: end if −i 11: Convey the rejection decision yk,n,t = 0 to the other MCSPs along with rejection reason. i 12: Perform the task On,t and transmit the result rk,n,t to the MCSP i. i MU , τ 13: Receive the payment Pk,n,t and observe the Uk,n,t k,n,t , and Ek,n,t . MU . 14: Update the estimates Ûk,z ▷ Eq. (17) 15: end for
a task offer from one of the offering MCSPs (Line 4). In the i exploitation phase, the MU k selects the task offer Ôk,n,t MU that maximizes its expected utility Ûk,n,t (Line 7). After a decision has been made, MU k informs the respective MCSP i i with an acceptance decision, i.e. yk,n,t = 1 (Line 8). MU k conveys its rejection decision along with the reason to all the other MCSPs (Line 9). If the task is accepted, MU k performs i and transmits the result rk,n,t back to MCSP i. task On,t i MU Afterwards, it receives payment Pk,n,t and observes Uk,n,t . The expected utility estimate is updated as MU MU (Uk,n,t − Ûk,z ) , (17) Mz where Mz represents the number of times MU k has performed tasks of type z . 5.3 Stability and convergence of PACMAB In this section, we discuss the stability and convergence properties of the proposed PACMAB algorithm. As is common in multi-agent reinforcement learning (MARL) frameworks, deriving formal theoretical guarantees for stability and convergence is challenging. This difficulty is compounded in the case of PACMAB, which operates within a MARL framework wherein heterogeneous learning agents (MABs) interact in a competitive setting [39], [40]. In such environments, even simple example instances can give rise to considerable analytical complexity, rendering closed-form convergence proofs intractable [40]. Nevertheless, through extensive numerical evaluation, we empirically demonstrate that the PACMAB algorithm converges to the solution obtained by the PRISM algorithm, which has been formally shown to attain the stable hyper-Nash equilibrium (SHNE), i.e., stable assignments under MCSP-specific perceptions. 5.4 Computational complexity analysis Since PACMAB is fully decentralized, we analyze the complexity from the perspective of the entity that runs the algorithm. As MCSP i runs a combinatorial UCB algorithm (Algorithm 2) in every time step t, we first take a look at the worst case complexity. In lines 4-15 we can see that the algorithm computes a UCB value for each arm with complexity O(1). For K MUs, Z task types, and P payment MU MU Ûk,z = Ûk,z +
10
$ Y H U D J H 0 & 6 3 8 W L O L W \
6 R F L D O : H O I D U H
7 L P H 6 W H S
(d) Average completed tasks
& 0 $ % > @
7 L P H 6 W H S
7 L P H 6 W H S
7 L P H 6 W H S
(c) Achieved average MU utility
5 D Q G R P 0 & 6 3
(b) Achieved average MCSP utility
& X P X O D W L Y H & R O O L V L R Q V
7 D V N & R P S O H W L R Q 5 D W L R
(a) Achieved average social welfare
3 $ & 0 $ %
7 L P H 6 W H S
3 5 , 6 0
$ Y H U D J H 0 8 8 W L O L W \
0 R G L I L H G * D O H 6 K D S O H \ > @
( Q H U J \ & R Q V X P S W L R Q
& H Q W U D O L ] H G 2 3 7
H
(e) Average cumulative collisions
7 L P H 6 W H S
(f) Average energy consumption
Fig. 3: Performance comparison for K = 50, N = [10, 50], Z = 5. levels, the worst case complexity of computing the UCB value is O(KZP ). Afterwards, in line 16, these UCB values are sorted, which has complexity of O(KZP log(KZP )) [41]. The rest of the algorithm has complexity of O(N ) since it involves updating the UCB values of the N selected arms. Thus, the total computational complexity of the algorithms is given as O(KZP ) + O(KZP log(KZP )) + O(N ) = O(KZP log(KZP )) because the dominant term is O(KZP log(KZP )) as ZP ≫ log N in our case. Thus, over the time horizon T , the complexity becomes O(T KZP ). This complexity is reasonable for the MCSP since it has linear dependence on the time horizon, number of participating MUs, number of available task types, and the payment levels. MCSPs are equipped with sufficient computational capacity to implement an algorithm such as PACMAB. At the MU-side, Algorithm 3 is used to learn about Z different task types by selecting one task at a time. The algorithm computes the expected utility of each task type z by performing a task and updating the estimate using the sampled efforts. Such operation has complexity of O(1) (Line 4-13). Since each MU has to decide whether to accept the task or not, out of maximum I offers, the algorithm in time step t has computing complexity of O(I) [19]. Over the entire time horizon T , the resulting complexity is O(T I). This complexity is reasonable since the MUs are typically simple devices with limited computational capacity. Our proposed PACMAB algorithm respects this constraint and enables the MUs to make decisions which maximize their achieved utilities at a low computational cost. Note that for both, the MCSPs and the MUs, the communication overhead required for matching is low. The MCSP sends task offers to each MU which contains only the task type z and the payment information. The task acceptance as well as the task rejection with reason is a short message which the MUs transmit back to the respective MCSPs. The MUs then perform the accepted task and transmit the result back to the respective MCSPs.
6
Simulation Results and Analysis
6.1
Evaluation metrics
Since the MCSPs and the MUs have conflicting interests, we consider different metrics to evaluate the performance of our proposed PACMAB algorithm. Specifically, we consider metrics evaluating the complete MCS system as well as metrics from the perspective of the MCSPs and MUs. a) Social welfare: Social welfare is often used to evaluate the collective performance of the MCS system [33]. Mathematically, the social welfare UtSW (Yt ) is given by
UtSW (Yt ) =
Ni I ∑ K ∑ ∑
MCSP,i MU yk,n,t (Uk,n,t + Uk,n,t ).
(18)
i=1 k=1 n=1
b) Achieved average MCSP and MU utility: To study the effectiveness of the algorithms from the individual entity’s perspective, we consider individual achieved utilities of MCSPs and MUs. This is the net revenue earned by the MCSPs and the MUs individually. c) Task completion ratio: This is the ratio of the total tasks available to the total number of tasks completed in a time step. d) Cumulative collisions: A collision is the event when different MCSPs send a task offer to the same MU. Since the MU can only accept one offer, the rejected offers remain unfinished. Thus, collisions degrade the performance of the MCS system since the rejected offers affect the task completion of the respective MCSPs. 6.2 Baseline algorithms We use the following benchmark algorithms to compare the performance of our proposed algorithm. •
Centralized OPT (COPT): This is an offline optimization-based solution which requires complete information about the entire MCS system, i.e., the qualities and efforts of the MUs for every task type. The algorithm aims to find a task assignment that maximizes the social welfare given in (18). Note that
11
•
•
•
•
6.3
Value 10000 time steps K = [50, 200] Z = [5, 25] tasks |Pzi | = 20 levels |Ozi | = [1, 5] tasks comm τ̄k,z = [40, 80]Mbit/s fklocal = [1, 2]GHz sense τ̄k,z = [60, 180]ms pcomm = 200mW k 1W cz = [200, 300] CPU cycles/bit dz = [50, 100]Mbit sz = [10, 20]Mbit units αk = 0.01 Monetary s Monetary units βk = 0.004 J UCBc = 2 ϵa = 1 ϵt = 0.999
the algorithm ignores the individual preferences of the MCSPs and the MUs. Perception-aware matching solution (PRISM): This is the offline game-theory-based solution presented in Section 4.1. The algorithm requires complete information about the individual preferences of each player and iteratively finds a solution to the dynamic hypergame. Using this algorithm, every player tries to maximize its own utility selfishly. Modified Gale-Shapley (MGS) [19]: This is an offline game-theory-based solution which uses the well-known deferred acceptance (DA) algorithm to iteratively find stable task assignments. Due to the restriction in our MCS system, one MCSP cannot offer multiple tasks to the same MU. Thus, we modify the implementation of DA in [19] to an MCSP proposing scenario and enforce the one task offer per MU constraint. The algorithm requires complete information about the preferences of both, the MCSPs and the MUs. CMAB [20]: This two-sided learning approach uses a combinatorial upper confidence bound algorithm at each MCSP without considering the perceptions of the other MCSPs. At the MU-side, a multi-armed bandit is implemented which learns the efforts of different task types. Random MCSP: This is a benchmark algorithm which requires no information about the MCS system. The MCSPs randomly offer tasks to the MUs with random payments. The MUs strategically choose the better offers which maximize their own utility.
Simulation setup
For the numerical evaluation, we consider 100 independent Monte Carlo iterations. Each iteration runs for T = 10000 time steps. The number of MCSPs is set to I = 2, i.e., MCSP 0 and MCSP 1. The number of available MUs is set to K = 50, and the number of available tasks per MCSPs varies between 10 ≤ Ni ≤ 50 tasks in each time step for each MCSP. We consider Z = 10 types of tasks [19]. Rest of the simulation parameters are summarized in Table 2.
3 H U F H S W L R Q ( U U R U
Parameter Total number of time steps T Number of available MUs K Number of available task types [19] Number of payment levels Number of tasks per type Mean communication rate [19] CPU frequency [19] Mean sensing time [42] Transmission power [19] Computing power [19] Computational complexity [12] Sensing data size [19] Sensing result size [19] MU’s time cost parameter [19], [20] MU’s energy cost parameter [19], [20] UCB exploration constant MU exploration constant MU exploration rate
0 & 6 3 0 & 6 3
, W H U D W L R Q
6 R F L D O : H O I D U H
TABLE 2: Simulation parameters
, W H U D W L R Q
Fig. 4: PRISM: Perception er- Fig. 5: Achieved social welfare of PRISM over iterations ror over iterations 6.4
Results and discussion
In Fig. 3a, we compare the social welfare achieved by different benchmarks over time. The COPT algorithm achieves the maximum social welfare by exploiting complete system information. PRISM converges to COPT as misperceptions diminish through repeated iterations. Both, COPT and PRISM, find the optimal assignments, however, in COPT, the MUs do not receive any payments, therefore, the achieved utilities of the MCSPs and the MUs are different, but the sum, i.e., the social welfare, converges. The evolution of the perception error is illustrated in Fig. 4. As the perceptions improve, PRISM is able to improve its social welfare as shown in Fig. 5. In Fig.3a, our PACMAB algorithm attains 99.1% of the COPT performance, demonstrating that perception-aware learning effectively maximizes social welfare. MGS achieves about 99.4% of the COPT social welfare. However, its strategy to completely outbid the other MCSP leads to suboptimal but unchangeable assignments. In contrast, CMAB achieves only 52.9% due to slow learning in a large combinatorial action space and convergence to local optima. Random MCSP performs worst, reaching 42.3%, as it ignores both MCSP preferences and competition. Figure 3b shows the achieved MCSP-side utility. COPT attains the highest MCSP utility as it exploits the complete information without considering the individual preferences of the MCSPs and the MUs. PRISM and MGS achieve 87.9% and 86.8% of the COPT utility, respectively. Note that the PRISM and MGS both exploit the complete information about the MCS system and, they also consider the individual preferences of the MCSPs and the MUs. MGS performs worse than PRISM because its contest-based mechanism overpays the MUs such that they will accept the offer, which results in lower MCSP utility. PACMAB achieves 86.4% of the COPT utility without requiring complete information by leveraging perceptions to prune contracts which lead to low achieved utility and focus on the ones which the MCSPs as well as the MUs prefer. In contrast, CMAB reaches only 45.9% due to the lack of perception-aware learning. Random MCSP results in negative utility as it does not use any information. In Fig. 3c, we see that the achieved MU utility in case of the COPT is negative. This is because COPT forces the MUs to perform the tasks without any payments. Our proposed PACMAB algorithm achieves higher MU utility and converges to PRISM and MGS solution such that the MUs are also satisfied from the assignments. On the contrary, the Random MCSP overpays the MUs and thus achieves high MU utility. However this is unrealistic since the achieved MU utility is at the cost of MCSP utility. The CMAB achieves MU utility of only 55.91% as compared to our proposed PACMAB because CMAB performs less tasks and therefore, in CMAB, the MUs earn less on average.
12
& H Q W U D O L ] H G 2 3 7 0 R G L I L H G * D O H 6 K D S O H \ > @
3 5 , 6 0 3 $ & 0 $ % $ Y H U D J H 0 & 6 3 8 W L O L W \
6 R F L D O : H O I D U H
.
.
.
.
& 0 $ % > @ 5 D Q G R P 0 & 6 3
.
.
.
.
Fig. 6: Achieved social welfare Fig. 7: Achieved MCSP utility vs. number of MUs vs. number of MUs $ Y H U D J H 0 & 6 3 8 W L O L W \
6 R F L D O : H O I D U H
In Fig. 3d, we analyze task completion ratios of the benchmark solutions in comparison with our proposed PACMAB. COPT and MGS algorithms exploit complete information and are able to complete all the available tasks. When the misperceptions vanish, the PRISM algorithm also achieves a task completion ratio of 1. Our proposed PACMAB achieves 99.8% task completion without the requirement of complete information about the MCS system. This means, the PACMAB algorithm not only prioritizes high welfare, but also aims to maximize the task completion. CMAB completes only 59% of tasks since it fails to learn about the dynamic competition between the MCSPs which results in poor performance. The Random MCSP algorithm performs the worst by completing only 55.5% of tasks since it does not utilize any information about the MCS system. The collision ratio, i.e., the ratio of rejected task offers over total offered tasks, directly affects the task completion ratio. In Fig. 3e, we compare the average cumulative collisions over time. These are task offer rejections in the scenario which degrade the task completion performance and consequently the achieved utilities of the MUs and the MCSPs along with the achieved social welfare. The COPT and the MGS do not have any collisions since they exploit the complete information about the scenario. PRISM minimizes the collisions by offering better task offer proposals over time and converges to COPT and MGS. PACMAB learns MCSP’s own preferences as well as reduces collisions over time. Therefore, it exhibits sublinear cumulative collisions. For the CMAB and the Random MCSP, the perceptions about the preferences of other MCSPs are not considered which results in frequent rejections of task offers. In Fig. 3f, we compare the energy consumption of the benchmark algorithms in comparison with the proposed PACMAB algorithm. We exclude the Random MCSP algorithm from the comparison for the clarity of the presentation. The Random MCSP consumes high energy with a larger variance which obscures the performances of other schemes. The CMAB algorithm consumes lower energy however, the algorithm also performs less tasks on average. This result illustrates that our PACMAB algorithm achieves energy consumption which is comparable to that of the COPT and the PRISM without the requirement of the complete information. The result highlights that the PACMAB algorithm achieves a superior performance while being energy efficient. To analyze the effect of increasing number of MUs on the social welfare and the achieved MCSP utility, we consider K = {50, 100, 150, 200} MUs and set N = K . The results are illustrated in Fig. 6 and Fig. 7, respectively. As the number of MUs increase, the achieved social welfare also increases. For the case of K = 200 MUs, PRISM converges to the COPT algorithm while the MGS algorithm achieves 98.9% social welfare. In larger scenarios, the possible number of matching assignments grow exponentially with the number of MUs. Consequently, it is difficult to learn which matching combinations are better suitable and which are not. Still, PACMAB achieves at least 93.0% social welfare as compared to the COPT, indicating that PACMAB is well-suited for larger networks with more MUs and tasks. To analyze the effect of heterogeneity of tasks on the social welfare and the achieved MCSP utility, we consider the following scenario. The number of task types are varied
=
=
=
=
=
=
=
=
Fig. 8: Achieved social welfare Fig. 9: Achieved MCSP utility vs. number of task types vs. number of task types between Z = {5, 10, 20, 25}. We consider K = N = 100 for this case. The result of this analysis is shown in Fig. 8 and in Fig. 9, respectively. PACMAB achieves at least 95.0% social welfare as compared to the COPT and PRISM algorithm. As the number of tasks increase, the possible actions that each MCSP can take also increase. For example, for K = 100 MUs, N = 100 tasks of Z = 25 task types, and 20 payment levels, the possible number of actions for each MCSP are approximately 2297 . Even for such a high number, PACMAB learns efficient task proposal and task acceptance strategies. In comparison, CMAB performs worse with at the most 46.3% of social welfare and 46.8% achieved MCSP utility as compared to our PACMAB algorithm. This demonstrates that the PACMAB algorithm is well-suited for MCS systems with high number of heterogeneous tasks, too.
7 Conclusion In this paper, we have investigated competitive multiplatform mobile crowdsensing under incomplete information by modeling task offers and acceptances as a two-sided matching market with contracts. To address uncertainty about competitors’ preferences, we have introduced a level-one dynamic hypergame formulation in which MCSPs update perceptions through repeated interactions and derived a perception-aware benchmark solution under partial-information assumptions. To operate under fully unknown MU qualities and task execution efforts, we have proposed PACMAB, a fully decentralized perception-aware two-sided bandit-learning framework that learns task-proposal and task-acceptance strategies online. PACMAB has linear computational complexity in terms of number of MUs, available tasks, and the discrete payment levels at the MCSP. At the MU side, PACMAB exhibits linear complexity in terms of number of task offers received. Simulation results demonstrate that PACMAB achieves at least 93% of the optimal social welfare and over 99% task completion, even as the number of MUs and task types scale significantly, and without assuming complete system information. These findings confirm that perception-aware learning is a promising paradigm for decentralized MCS systems, effectively bridging the gap between fully informed centralized solutions and practical deployments under incomplete information.
13
References [1]
R. K. Ganti, F. Ye, and H. Lei, “Mobile crowdsensing: current state and future challenges,” IEEE Commun. Mag., vol. 49, no. 11, pp. 32–39, 2011. [2] W. Gong, B. Zhang, and C. Li, “Task assignment in mobile crowdsensing: Present and future directions,” IEEE Network, vol. 32, no. 4, pp. 100–107, 2018. [3] S. Dongare, A. Ortiz, and A. Klein, “Deep reinforcement learning for task allocation in energy harvesting mobile crowdsensing,” in IEEE Global Commun. Conf., 2022, pp. 269–274. [4] ——, “Federated deep reinforcement learning for task participation in mobile crowdsensing,” in IEEE Global Commun. Conf., 2023, pp. 4436–4441. [5] C. Dai, X. Wang, K. Liu, D. Qi, W. Lin, and P. Zhou, “Stable task assignment for mobile crowdsensing with budget constraint,” IEEE Trans. on Mobile Comput., vol. 20, no. 12, pp. 3439–3452, 2021. [6] J. An, X. Gui, J. Yang, S. Yu, and X. He, “Mobile crowd sensing for internet of things: A credible crowdsourcing model in mobilesense service,” in IEEE Int. Conf. on Multimedia Big Data, 2015, pp. 92–99. [7] Z. Jiang, H. Zhu, B. Zhou, C. Lu, M. Sun, X. Ma, X. Fan, C. Wang, and L. Chen, “Crowdpatrol: A mobile crowdsensing framework for traffic violation hotspot patrolling,” IEEE Transactions on Mobile Computing, vol. 22, no. 3, pp. 1401–1416, 2023. [8] T. A. N. Dinh, A. D. Nguyen, T. T. Nguyen, T. H. Nguyen, and P. L. Nguyen, “Spatial-temporal coverage maximization in vehicle-based mobile crowdsensing for air quality monitoring,” in IEEE Wireless Commun. and Networking Conf. (WCNC), 2022, pp. 1449–1454. [9] X. Li and Q. Zhu, “Social incentive mechanism based multi-user sensing time optimization in co-operative spectrum sensing with mobile crowd sensing,” Sensors, vol. 18, no. 1, 2018. [10] X. Dong, Z. You, T. H. Luan, Q. Yao, Y. Shen, and J. Ma, “Optimal mobile crowdsensing incentive under sensing inaccuracy,” IEEE IoT Journal, vol. 8, no. 10, pp. 8032–8043, 2021. [11] R. Pryss, J. Schobel, and M. Reichert, “Requirements for a flexible and generic API enabling mobile crowdsensing mhealth applications,” in Int. Workshop on Requirements Engineering for Self-Adaptive, Collaborative, and Cyber Physical Systems (RESACS), 2018, pp. 24–31. [12] Y. Huang, H. Chen, G. Ma, K. Lin, Z. Ni, N. Yan, and Z. Wang, “OPAT: Optimized allocation of time-dependent tasks for mobile crowdsensing,” IEEE Trans. on Industrial Informatics, vol. 18, no. 4, pp. 2476–2485, 2022. [13] S. Chang, S. Deng, Y. Wu, W. Ma, and H. Zhou, “Online energy balancing strategy based on lyapunov optimization in mobile crowdsensing,” IEEE Transactions on Industrial Informatics, vol. 19, no. 9, pp. 9266–9279, 2023. [14] B. Zhao, W. Guo, B. Tian, C. Qiao, Q. Pei, and X. Liu, “RATE: Privacy-preserving task assignment with bi-objective optimization for mobile crowdsensing,” IEEE Transactions on Mobile Computing, vol. 23, no. 12, pp. 13 851–13 865, 2024. [15] X. Xie, T. Bai, W. Guo, Z. Wang, and A. Nallanathan, “Cooperative computing for mobile crowdsensing: Design and optimization,” IEEE Transactions on Mobile Computing, vol. 23, no. 5, pp. 6437–6454, 2024. [16] Y. Wang, Z. Cai, Z.-H. Zhan, Y.-J. Gong, and X. Tong, “An optimization and auction-based incentive mechanism to maximize social welfare for mobile crowdsourcing,” IEEE Transactions on Computational Social Systems, vol. 6, no. 3, pp. 414–429, 2019. [17] F. Yucel and E. Bulut, “Online stable task assignment in opportunistic mobile crowdsensing with uncertain trajectories,” IEEE Internet of Things Journal, vol. 9, no. 11, pp. 9086–9101, 2022. [18] B. Simon, S. Dongare, T. Mahn, A. Ortiz, and A. Klein, “Delay- and Incentive-Aware Crowdsensing: A Stable Matching Approach for Coverage Maximization,” in Proc. of the IEEE Int. Conf. on Commun. (ICC), 2022, pp. 2984–2989. [19] B. Simon, A. Ortiz, W. Saad, and A. Klein, “Decentralized online learning in task assignment games for mobile crowdsensing,” IEEE Trans. on Commun., vol. 72, no. 8, pp. 4945–4960, 2024. [20] S. Dongare, B. Simon, A. Ortiz, and A. Klein, “Two-sided learning: A techno-economic view of mobile crowdsensing under incomplete information,” in IEEE Int. Conf. on Commun., 2024. [21] Y. Li, F. Li, S. Yang, Y. Wu, H. Chen, K. Sharif, and Y. Wang, “MP-coopetition: Competitive and cooperative mechanism for multiple platforms in mobile crowd sensing,” IEEE Transactions on Services Computing, vol. 14, no. 6, pp. 1864–1876, 2021. [22] S. Peng, G. Zhang, B. Zhang, Z. Yao, C. Liu, and C. Li, “A stable task assignment mechanism for multi-platform mobile crowdsensing,” IEEE Transactions on Vehicular Technology, vol. 74, no. 5, pp. 8079–8094, 2025. [23] K. Liu, G. Ji, B. Zhang, Z. Yao, and C. Li, “Cooperativerationality-based multiplatform task assignment mechanisms for mobile crowdsensing,” IEEE Internet of Things Journal, vol. 12, no. 8, pp. 10 920–10 931, 2025.
[24] G. Yang, J. Li, X. He, F. Sun, and Y. Liu, “Hybrid coopetitive mechanism for multiplatform mobile crowdsensing: A two-stage approach to pricing and matching,” IEEE Internet of Things Journal, vol. 12, no. 24, pp. 54 652–54 663, 2025. [25] N. Zhao, Y. Sun, Y. Pei, and D. Niyato, “Joint sensing and computation incentive mechanism for mobile crowdsensing networks: A multiagent reinforcement learning approach,” IEEE Internet of Things Journal, vol. 12, no. 9, pp. 13 033–13 046, 2025. [26] P. G. Bennett, “Toward a theory of hypergames,” Omega, vol. 5, no. 6, pp. 749–751, 1977. [27] ——, “Hypergames: Developing a model of conflict,” Futures, vol. 12, no. 6, pp. 489–507, 1980. [28] ——, “Bidders and dispenser: manipulative hypergames in a multinational context,” European Journal of Operational Research, vol. 4, no. 5, pp. 293–306, 1980. [29] L. Li, H. Ma, A. N. Kulkarni, and J. Fu, “Dynamic hypergames for synthesis of deceptive strategies with temporal logic objectives,” IEEE Transactions on Automation Science and Engineering, vol. 20, no. 1, pp. 334–345, 2023. [30] Y. M. Aljefri, M. A. Bashar, L. Fang, and K. W. Hipel, “Firstlevel hypergame for investigating misperception in conflicts,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 48, no. 12, pp. 2158–2175, 2018. [31] Z. Wan, J.-H. Cho, M. Zhu, A. H. Anwar, C. A. Kamhoua, and M. P. Singh, “Foureye: Defensive deception against advanced persistent threats via hypergame theory,” IEEE Transactions on Network and Service Management, vol. 19, no. 1, pp. 112–129, 2022. [32] C. K. Thomas and W. Saad, “Hypergame theory for decentralized resource allocation in multi-user semantic communications,” in 2024 IEEE 63rd Conference on Decision and Control (CDC), 2024, pp. 6036–6043. [33] B. Simon, A. Ortiz, W. Saad, and A. Klein, “Decentralized online learning in task assignment games for mobile crowdsensing,” 2023. [34] J. W. Hatfield and P. R. Milgrom, “Matching with contracts,” The American Economic Review, vol. 95, no. 4, pp. 913–935, 2005. [35] N. Kovach, A. Gibson, and G. Lamont, “Hypergame theory: A model for conflict, misperception, and deception,” Game Theory, vol. 2015, pp. 1–20, 08 2015. [36] Y. Sasaki, “Preservation of misperceptions – stability analysis of hypergames,” Proceedings of the 52nd Annual Meeting of the ISSS - 2008, Madison, Wisconsin, vol. 3, no. 1, July 2008. [Online]. Available: https://journals.isss.org/index.php/ proceedings52nd/article/view/1007 [37] H. W. Kuhn, “The hungarian method for the assignment problem,” Naval Research Logistics Quarterly, vol. 2, no. 1-2, pp. 83–97, 1955. [Online]. Available: https: //onlinelibrary.wiley.com/doi/abs/10.1002/nav.3800020109 [38] J. Munkres, “Algorithms for the assignment and transportation problems,” Journal of the society for industrial and applied mathematics, vol. 5, no. 1, pp. 32–38, 1957. [39] L. T. Liu, F. Ruan, H. Mania, and M. I. Jordan, “Bandit learning in decentralized matching markets,” Journal of Machine Learning Research, vol. 22, no. 211, pp. 1–34, 2021. [40] K. Zhang, Z. Yang, and T. Başar, “Multi-agent reinforcement learning: A selective overview of theories and algorithms,” 2021. [Online]. Available: https://arxiv.org/abs/1911.10635 [41] H. Zhang, N. Ti, D. Wang, X. Du, Q. Wang, and W. Xia, “Quality-aware incentive mechanism for efficient federated learning in mobile crowdsensing,” IEEE Transactions on Vehicular Technology, vol. 73, no. 12, pp. 19 696–19 707, 2024. [42] T. Mahn and A. Klein, “A Global Orchestration Matching Framework for Energy-Efficient Multi-Access Edge Computing,” in Proc. of the IEEE Int. Conf. on Cloud Networking (CloudNet), Cookeville, USA, Nov. 2021, pp. 11–18. [43] H. Robbins and S. Monro, “A stochastic approximation method,” The Annals of Mathematical Statistics, vol. 22, no. 3, pp. 400–407, 1951. [44] R. A. Horn and C. R. Johnson, Matrix Analysis, 2nd ed. Cambridge University Press, 2012.
Appendix A Proof of Theorem 1 For property 1), consider the perception update rule from j i i }. Algorithm 1 (Line 31) : θj,k,z (t + 1) = max{θj,k,z (t), Pk,n,t We further define the perception gap for each (j, k, z), j i i δj,k,z (t) = θj,k,z − θj,k,z (t). ≥ 0
14
We can make three key observations here. First, percepi tions are monotonically non-decreasing, θj,k,z (t + 1) ≥ i θj,k,z (t) ∀t. By Assumption 1, MCSP j will not pay more than its valuation (except during exploration). Therefore: j j Pk,n,t ≤ θj,k,z + ϵt · M . When MCSP i observes MU k j accepting an offer from MCSP j at payment Pk,n,t , we have j i two cases. If Pk,n,t > θj,k,z (t) (a misprediction/surprise): j i i δj,k,z − θj,k,z (t + 1) = θj,k,z (t + 1) j j i = θj,k,z − max{θj,k,z (t), Pk,n,t } j j − Pk,n,t = θj,k,z j i i ≤ θj,k,z − θj,k,z (t) = δj,k,z (t).
The gap decreases and hence perception improves over time. j i (t), i.e., no surprise, then Otherwise, if Pk,n,t ≤ θj,k,z i i i i θj,k,z (t + 1) = θj,k,z (t) =⇒ δj,k,z (t + 1) = δj,k,z (t). i i In both cases, δj,k,z (t + 1) ≤ δj,k,z (t). Therefore: ∑ ∑ i i ∆θi (t+1) = E[δj,k,z (t+1)] ≤ E[δj,k,z (t)] = ∆θi (t). j,k,z
MCSP i observes this event in a given time step. Then: j
j
i i E[θj,k,z (t+1)−θj,k,z ] = (1−γj,k,z )·(θj,k,z (t)−θj,k,z )+νj,k,z (t)
where νj,k,z (t) is exploration noise. Vectorizing, let ⃗δi (t) ∈ RKZ contain all perception errors:
⃗δi (t + 1) = (I − Γ)⃗δi (t) + ⃗ν (t) where Γ = diag(γj,k,z ) is a diagonal matrix with entries in (0, 1). The eigenvalues of (I − Γ) lie in [0, 1). Let λmax = max{eigenvalues of (I − Γ)} < 1. Then: E[∥⃗δi (t)∥] ≤ λtmax ∥⃗δi (0)∥ +
t−1 ∑
t−s λmax E[∥⃗ ν (s)∥].
(19)
s=0
(19) follows from [44] by solving the linear difference equation ⃗δ i (t+1) = (I −Γ)⃗δ i (t)+⃗ν (t) by recursive substitution, which ∑t−1 ν (s). Taking gives ⃗δ i (t) = (I − Γ)t⃗δ i (0) + s=0 (I − Γ)t−s−1 ⃗ norms and using the bound ∥(I − Γ)t ∥ ≤ λtmax , where λmax is the spectral radius of I − Γ, yields the desired inequality. Under∑ Assumption 4, E[∥⃗ ν (s)∥] ≤ Cϵs for some constant C . ∞ Since s=0 ϵ2s < ∞: ∞ ∑
j,k,z
λ−s ν (s)∥] ≤ C max E[∥⃗
s=0
∞ ∑
ϵs λ−s max < ∞
s=0
For the property 2), we apply stochastic approximation theory by defining the Lyapunov function: ∑∑ j i (θj,k,z − θj,k,z V i (t) = (t))2 .
Define λ = − log(λmax ) > 0. Then λmax = e−λ , and: ϵnoise E[∆θi (t)] ≤ C1 ∥⃗δi (0)∥ · e−λt + λ j̸=i k,z where ϵnoise = C2 supt ϵt for appropriate constants C1 , C2 . When an update occurs at time t for triple (j, k, z) (i.e., when For property 4), from the ϵ-robust HNE analysis, the utility function satisfies a Lipschitz condition with respect to perMCSP j competes for MU k on task type z ), we have: ception errors. Specifically, for any assignment Y i based on j i i i 2 i E[V (t + 1)|Ft ] = V (t) − (θj,k,z − θj,k,z (t)) perception θ−i and the optimal assignment Y i∗ based on true −i j j i + E[(θj,k,z − max{θj,k,z (t), Pk,z (t)})2 |Ft ], values θ−i , where the expectation is taken over the random payment j Pk,n,t that MCSP j will offer at time t (not yet observed) and Ft denotes the filtration (history/information set) containing all observations available to MCSP i up to and including i time t, including past perceptions {θj,k,z (s)}s≤t , actions, and feedback from MUs. Under rational play (Assumption 1) with exploration, j
j,∗
−i −i −i i |U MCSP,i (Y i ; θ−i ) − U MCSP,i (Y i∗ ; θ−i )| ≤ L · ∥θ−i − θ−i ∥∞ ,
where L = K · maxz maxP ∈Pzi P is the maximum total i payment difference across all MUs. As t → ∞, ∥θ−i (t) − −i i . At SHNE, each MCSP plays optimally with θ−i ∥∞ → ∆θ∞ respect to its (converged) perceptions. The utility achieved is: MCSP,i MCSP,i MCSP,i i USHNE = Uopt − L · ∆θ∞ , where Uopt is the utility at Nash equilibrium with perfect information. Therefore:
j
E[Pk,z (t)] = (1 − ϵt ) · Pk,z + ϵt · P̄k,z , j,∗
MCSP,i lim inf E[UtMCSP,i ] ≥ USHNE ,
t→∞
j
where Pk,z is the optimal payment and P̄k,z is the exploration distribution mean. The optimal payments satisfy j,∗ j j j Pk,z ≤ θj,k,z by rationality, as ϵt → 0, E[Pk,z (t)] → θj,k,z . This shows that the updates are in the direction of the true values. By the∑ Robbins-Monro∑theorem [43], since Assumption 4 ensures t ϵt = ∞ and t ϵ2t < ∞, we have, j i i θj,k,z (t) → θj,k,z − δj,k,z,∞ , i ≥ 0 is the residual error which is potentially where δj,k,z,∞ zero. Therefore, ∑ i i ∆θi (t) → ∆θ∞ = δj,k,z,∞ . j,k,z
For the property 3), we consider the exploitation phase when ϵt ≈ 0. The perception update can be approximated as a linear dynamical system. For each triple (j, k, z), let γj,k,z denote the probability that MCSP j competes for (k, z) and
which can also be written as: MCSP,i MCSP,i i − L · ∆θ∞ = USHNE lim inf E[UtMCSP,i ] ≥ Uopt
t→∞