Dynamic games for resource allocation in metaverse services and architectures

• Main Author: Han, Yue
• Other Authors: Dusit Niyato
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2023
• Subjects: Engineering::Computer science and engineering
• Online Access: https://hdl.handle.net/10356/164497
• Institution: Nanyang Technological University

The Metaverse is an interoperable platform, hosting various virtual sub-worlds, each of which is operated by a virtual service provider (VSP) to provide various types of virtual services, such as virtual sightseeing, virtual driver training, etc. There are many latency-sensitive and computation-intensive (LSCI) tasks in the Metaverse, such as scene rendering, 3D reconstruction, multi-user interactions, and data analytics based on Artificial Intelligence (AI). One specific LSCI task is the synchronization of VSPs' digital replicas, i.e., the digital entities which mirror their real-world counterparts. To collect and process the counterparts' state data for the synchronization, flexible Internet-of-Things (IoT) devices and advanced computation methods with reduced latency at the network edge are necessary. In particular, the advanced computation method can be considered a service provided by edge infrastructure providers (EIPs) that offer edge computing services to IoT devices so as to avoid a long transmission delay in the backhaul. Since different VSPs may have different synchronization preferences for their digital replicas based on their service types, an effective synchronization solution should consider various agents, i.e., IoT devices, EIPs, and VSPs. In this thesis, I aim to study their strategic interactions using game-theoretical approaches, in the context of (1) VSPs' synchronization assisted by ubiquitous IoT devices in chapter3 and (2) advanced computation services offered by EIPs to facilitate LSCI tasks in chapter4. In chapter3, I model the interactions among IoT devices and VSPs as a hierarchical game. In the lower level, after choosing a VSP to work for, IoT devices selecting the same VSP collectively sense its physical counterparts. In the upper level, VSPs determine synchronization intensities to maximize their payoffs in response to the amount of sensing data provided by IoT devices and the values of the digital replicas, characterized by digital replicas' usefulness to the virtual service. The digital replica values are subject to natural decay, as counterpart information can become more unreliable over time without any synchronization. I model the lower-level VSP selection as an evolutionary game and the upper-level synchronization intensity control as a simultaneous differential game. The model incorporates the digital replicas' value decay dynamics, to reflect the realistic assumption that the value of digital replicas decrease with time and increase with synchronization intensity. I further extend the upper-level model as a Stackelberg differential game in which there is sequential decision making among VSPs. I adopt open-loop solutions based on the control theory for both formulations. The proposed framework provides a first attempt at studying digital replicas' value dynamics and a flexible, agile, and practical synchronization solution for the Metaverse. In chapter4, I consider EIPs to be service providers, which provide coded distributed computing (CDC), an augmented computing paradigm, to improve the performance for the LSCI tasks, e.g., rendering. CDC is known for its robustness against the straggler effects in parallel computing by injecting redundant sub-tasks via coding techniques. Many LSCI tasks involve matrix computation and gradient computing, which can be processed in a parallel way. However, CDC's requirement of additional computation resources may challenge a resource-limited EIP to deliver CDC as a service independently. Thus, I propose a framework, Coded Edge Federation (CEF), which enables a group of EIPs to jointly provide edge resources for CDC tasks. I adopt an evolutionary game to model the EIPs' strategy adaptation processes and incorporate memory features based on Caputo fractional derivatives. The memory features can reflect EIPs' economic-aware nature, i.e., leveraging past decision information in future decision-making. The proposed CEF framework enables CDC services to be provided at the network edge without increasing the EIPs' infrastructure expenditure. In addition, the inclusion of memory features in the evolutionary game allow us to model a broader range of EIP dynamic behaviours, such as EIP sensitivity and aggressiveness in strategy adaptation, which classical evolutionary game, with traditional replicator dynamics, cannot capture. This makes the CEF framework more applicable in real life. In summary, this thesis investigates major resource allocation problems in emerging edge networks, with evolutionary game as a primary tool. The tool is further extended by incorporating value dynamics and controls in chapter3 and memory features based on fractional calculus in chapter4. In each work, I provide theoretical analyses for the game equilibrium and extensive numerical experiments and sensitivity analysis to illustrate insightful properties of the equilibrium. The advantages of the proposed methods are demonstrated through comparisons with baselines. Finally, I describe some promising research directions for future work.