Cloud and edge computing service providers (SPs) provide heterogeneous computing services to users, which forms the computing market. However, users’ service selections among SPs are unbalanced, resulting in inefficient resource utilization. In this paper, we analyze users’ service selection behaviors and design efficient pricing mechanisms to optimize the social welfare of the computing market. Considering the huge number of users and heterogeneous service providers, users can hardly acquire complete information to make their decisions, and we model users’ interactions as a dynamic service selection evolutionary game. Analyzing the evolutionary stable state (ESS) of the game and designing efficient pricing mechanisms for edge-cloud computing markets are challenging due to the implicit relationship between prices and users’ service selection dynamics, and the heterogeneity of service providers and user populations. We first investigate a single-population scenario where users are homogeneous, for which we prove that the ESS is unique. We design a static pricing mechanism which depends on SPs’ marginal costs and computation capacities, and a dynamic pricing mechanism which also depends on SPs’ real-time congestion tax. We prove that under our pricing mechanisms, the ESS is the socially optimal state and is globally asymptotic stable. We then analyze the general multi-population scenario where users are heterogeneous, for which we prove that the ESS exists but may be not unique. We design a static pricing mechanism (and a dynamic pricing mechanism) which depends on SPs’ marginal costs and the social-optimal average delay costs (and the real-time average delay costs). We prove that under our pricing mechanisms, the socially optimal state is an ESS and is asymptotically stable. Simulation results validate the effectiveness of our designed pricing mechanisms.

As a promising computing paradigm, edge-cloud computing network integrates the ubiquitous computing resources on the cloud and edge servers to provide high-quality services, but is susceptible to complicated distributed denial-of-service (DDoS) attacks. Although some works have studied edge DDoS mitigation, the cooperative defense among cloud and edge servers considering the DDoS attacker’s strategic attack strategy is yet to be explored. In this paper, we model the interactions between the DDoS attacker and defenders as a two-stage dynamic game and propose a distributed cooperative defense scheme. In Stage I, the DDoS attacker strategically launches different amounts of malicious traffic to different edge servers to maximize the total filtering cost. In Stage II, edge servers under attack (i.e., defenders) filter their traffic on the cloud and other edge servers cooperatively to minimize the total filtering cost. The defenders’ problem in Stage II is NP-hard and we solve the problem by modeling defenders’ behaviors as a selfish filtering game. We prove that the selfish filtering game admits a unique Nash equilibrium (NE) with guaranteed social efficiency, and design both a centralized algorithm and a distributed algorithm to calculate the NE. For the attacker’s problem in Stage I, we first analyze a special case where each edge server has the same amount of normal traffic, and design a low-complexity algorithm to calculate the optimal attack strategy. We then analyze the general case where edge servers have different amounts of normal traffic, for which we derive the approximate optimal solution. Simulation results show that the DDoS attacker tends to launch attacks to all edge servers to reduce their cooperative defense capability, and our proposed distributed cooperative defense mechanism can effectively reduce the total filtering cost compared with existing benchmark defense mechanisms.

A user with limited computation resources can address his delay-sensitive and computation-intensive tasks through task offloading to nearby edge servers, by purchasing both network and computation resources from profitseeking providers. We identify a substitutability property of computation and network resources for realizing the delay requirement. That is, to reduce task delay, the user can purchase more network resources to reduce transmission delay or more computation resources to reduce computation delay. This property significantly affects the user's purchase behavior and leads to strategic interactions between the computation service provider (CSP) and the network service provider (NSP), which have not been systematically studied yet. To this end, we formulate a two-stage Stackelberg game. In Stage I, one CSP and one NSP set their prices. In Stage II, each user decides offloading ratio and the amount of resources to purchase. By deriving the closed-form solutions in Stage II, we analytically conclude that the substitutability affects the user's decision through the network price to computation price ratio. We then incorporate the solution in Stage II into Stage I and analyze the service providers' pricing under two market structures. In the cooperative setting, where two service providers are integrated and jointly maximize their total profit, they would flexibly adjust the price ratio based on computation and network costs. In the competitive setting, where they are separate firms and aim to maximize their own profit, we formulate a pricing game and characterize a counter-intuitive equilibrium: the service providers would set high prices instead of low prices. Experimental results show that users benefit from service providers' competitive interactions.

The adoption of deep learning models in V2X scenarios has boosted computing demands in edge computing, while concept drift requires frequent model retraining, further increasing computing resource consumption. However, few works study computing instance allocation considering dynamic model retraining, especially under varying workloads. In this paper, we study the joint online model retraining and instance allocation problem in edge computing networks considering model performance degradation due to concept drift. Solving the online problem is challenging since it is a quadratic binary programming problem and its instance switching cost is time-coupling. We propose an efficient online algorithm, where we first linearize the quadratic term, then regularize the time-linearize the problem and then regularize the timecoupling switching cost to decouple the problem, and finally round the fractional solution by a randomization method. We prove that our proposed algorithm achieves a bounded optimality gap. Simulations demonstrate that our algorithm can achieve a balance between instance costs and model performance.

The increasing reliance on fresh data in real-time applications underscores the significance of commoditized fresh data. However, current research often neglects the crucial data correlation, essential in applications like intelligent transportation. This paper examines the trading of correlated fresh data, where a platform monitors the time-varying numerical status of multiple correlated data sources. Data users arrive stochastically, each seeking to obtain data from the platform to estimate the real-time status of a specific source of interest. To facilitate data trading, we propose a dynamic pricing policy that allows the platform to adjust prices in real time. We demonstrate that dynamic pricing is an NP-hard mixed integer programming problem and propose an approximate algorithm. Our approach begins with threshold-based data allocation and uses linear programming to optimize pricing, achieving a logarithmic approximation ratio. For binary data sources, we derive an optimal closed-form solution, revealing that data correlation can benefit both the platform and users by offsetting data aging with spatially correlated fresher data. Interestingly, despite users placing a higher valuation on fresher data, the presence of correlation results in fresher data being priced lower. This counterintuitive pricing strategy is designed to encourage users to engage in crosssource data purchasing. Numerical results show that the proposed approximate dynamic pricing policy can achieve at least 90 % of the maximum dynamic pricing revenue. Additionally, data correlation can amplify the platform's revenue by up to 100 % compared to scenarios without data correlation.

The immense value of IoT data in real-time applications has led to the rise of fresh IoT data trading. Existing research often neglects strategic users who optimally time their data purchases, significantly affecting market demand and revenue. This paper studies a fresh data market with strategic users arriving stochastically and having heterogeneous data valuations. Strategic users decide purchase timing based on data freshness and price, while the platform optimizes its data pricing policy to maximize profit. We first examine a dynamic pricing policy, offering a price menu to each arriving user. This analysis is technically challenging due to the varied integer programming problems faced by heterogeneous users, making direct price optimization infeasible. To address this, we adopt a mechanism design approach, analytically deriving the optimal dynamic pricing policy. To reduce implementation complexity, we also study two simpler pricing policies: single and two-price pricing. In a two-period refreshing model, we derive the optimal single and two-price pricing policies analytically. Our findings reveal that the optimal two-price policy significantly outperforms the single pricing policy, guaranteeing at least$96\%$of the revenue achieved by the optimal dynamic pricing policy in a two-period refreshing model. Surprisingly, despite having more purchasing options, strategic users may be worse off than if they were myopic due to higher prices. The platform actually benefits from strategic users, generating up to five times more profit with strategic users than with myopic users, even while reducing data refresh frequency.

Edge-cloud computing networks integrate dispersed computing resources of edges and clouds through networks, which improves resource utilization by flexibly scheduling tasks to suitable computing nodes. The performance of edge-cloud computing networks depends significantly on the amount of computing resources and the task scheduling scheme. In this work, we propose a novel computing resource trading and task scheduling framework for edge-cloud computing networks with arbitrary network topology. Specifically, we consider a third-party platform which incentivizes computing nodes to share computing resources by designing proper resource pricing mechanisms, and charges customers execution fees by scheduling tasks optimally in the edge-cloud computing network. The platform’s resource pricing and task scheduling optimization problem captures the unique features of edge-cloud computing networks including the heterogeneities of computing resources and tasks, as well as the multi-hop offloading in arbitrary topology, which is challenging to solve. We solve the problem for the homogeneous workload scenario and the heterogeneous workload scenario, respectively. For the homogeneous workload scenario, we propose a multi-round proposer-voter algorithm (MPV) that achieves the global optimum in polynomial time for the non-competitive case. For the heterogeneous workload scenario, we first propose a Gibbs sampling based iterative algorithm (GSI), which updates task scheduling strategies iteratively using Gibbs sampling and converges to the global optimum with high probability. We further propose a distributed alternating update algorithm (DAU), which converges to the local optimum in a distributed manner with linear complexity. Numerical results demonstrate the effectiveness of our proposed resource trading and task scheduling schemes.

Existing works on data trading often overlook the impact of data freshness on its valuation. This paper explores a fresh data market, where a platform offers data with varying freshness levels, such as real-time traffic data, to users who arrive stochastically. We categorize data updates into two types: lightweight (e.g., noise level) and computation-intensive (e.g., traffic images). Initially focusing on lightweight updates, we introduce three pricing policies: uniform, dual, and dynamic. The challenge lies in jointly optimizing the platform’s data sampling and pricing, a complex non-smooth mixed integer programming problem. Nevertheless, we achieve closed-form optimal solutions for all three policies by analyzing a relaxed version of the problem. Our findings reveal the surprising insight that higher data acquisition costs lead the platform to lower uniform data prices due to staler, less valuable data. Our numerical analysis indicates that the optimal dual pricing policy closely matches the dynamic pricing policy in performance and substantially exceeds the uniform pricing, tripling profits in some cases. Extending our work to computation-intensive updates, which require preprocessing, adds extra complexity. We tackle this by applying fractional programming. Numerical results show that profits from optimal uniform and dual pricing closely approach those from dynamic pricing, as the platform can adjust processing time.

In cross-silo federated learning (FL), clients of common interest cooperatively train a global model without sharing local sensitive data, but they still face potential privacy leakage due to privacy threats from malicious attackers. Although some articles have proposed effective privacy-preserving mechanisms for FL (such as differential privacy (DP)), clients in cross-silo FL are usually different companies or organizations who may behave selfishly to optimize their own benefits. In this article, we study DP-based cross-silo FL where clients selfishly decide their participation levels (i.e., data sizes for model trainings) and privacy leakage tolerance levels to trade off between model accuracy loss and privacy loss, and we model clients’ interactions as a participation-dependent privacy preservation game. It is challenging to analyze the game since the comprehensive impact of participation levels and privacy leakage tolerance levels on model accuracy is unclear and the behaviors of heterogeneous clients are coupled in a highly complex manner. To capture the impact of participation and privacy preservation behaviors, we first characterize the optimality gap of DP-based cross-silo FL for both convex and non-convex models, where the privacy leakage tolerance levels and the participation levels are coupled nonlinearly. We model clients’ costs based on the optimality gap, and prove that clients’ selfish participation-dependent privacy preservation game is a potential game. To analyze the optimal strategies of heterogeneous clients in a stable state, we derive the closed-form expression for the unique Nash equilibrium (NE), where clients may choose full participation or partial participation, and the equilibrium privacy preservation strategy depends on clients’ accuracy-privacy preference ratios. We analyze the social efficiency of the NE by calculating the price of anarchy (PoA) and show that the PoA increases with the number of clients and the heterogeneity of clients’ model accuracy preferences. To improve the social efficiency achieved at equilibrium, we design a socially efficient incentive mechanism that allows clients with large model accuracy preferences to compensate clients with small model accuracy preferences. Extensive experiments verify our theoretical results for both the convex and non-convex models as well as both the i.i.d. data distribution case and the non-i.i.d. data distribution case.

Federated learning is a popular distributed machine learning paradigm that keeps data locally at clients. To further enhance privacy protection, differential privacy techniques are incorporated in the federated learning framework. We can quantify the privacy budget (or privacy protection level) through differential privacy and allocate the budget to different communication rounds according to the composition property of differential privacy. Recent works have shown that suitably allocating budgets to different iterations can improve model performance. How to allocate privacy budgets in different communication rounds for different clients in the federated learning framework is a significant problem to study. The problem is challenging to solve due to the unknown relationship between noise levels and the model accuracy and the coupling property of the clients' decisions. In this paper, we propose a method based on multi-agent reinforcement learning to solve the privacy budget allocation problem, which maximizes the accuracy of the federated learning model given limited privacy budgets for the clients. The experiments show that our proposed method is better than the uniform allocation, arithmetic sequence allocation, and exponential allocation methods.

With the proliferation of edge computing, many business entities deploy their own edge servers to compete for users, which forms multi-server edge computing networks. However, no prior work studies the competition among heterogeneous edge servers and how the competition affects users’ selfish computation offloading behaviors in such a network from an economic perspective. In this paper, we model the interactions between edge servers and users as a two-stage game. In Stage I, edge servers with heterogeneous marginal costs set their service prices to compete for users, and in Stage II, each user selfishly offloads its task to one of the edge servers or the remote cloud. Analyzing the equilibrium of the two-stage game is challenging due to edge servers’ heterogeneity and the congestion effect caused by resource sharing among users. We first investigate the equilibrium when edge servers follow the serve-as-arrive (SAA) model (i.e., serving all offloaded tasks simultaneously), and then extend our analysis to the serve-in-queue (SIQ) model (i.e., serving offloaded tasks one by one following the M/M/1 queue rule). Under the SAA model, we prove that users’ selfish computation offloading game in Stage II is a potential game and admits a unique Nash equilibrium (NE), for which we derive the explicit expressions. Furthermore, for edge servers’ price competition game in Stage I, we characterize the conditions for the uniqueness of the NE and derive its explicit expression. Under the SIQ model, we derive the unique NE of users’ selfish computation offloading game, and show that the NE of edge servers’ price competition game may not always exist. We compare the equilibrium under the two service models and show that at equilibrium, edge servers with low marginal costs can achieve higher profits under the SIQ model when edge servers’ computation capacity is large or the delay incurred on the cloud is moderate; however, edge servers with high marginal costs can obtain higher profits under the SAA model in most cases.

Cross-silo federated learning (FL) is a distributed learning method where clients collaboratively train a global model without exchanging local data. However, recent works reveal that potential privacy leakage occurs when clients upload their local updates. Although some works have studied privacy-preserving mechanisms in FL, the selfish privacy-preserving behaviors of clients (who are usually cost-sensitive companies or organizations) are yet to be explored. In this paper, we formulate clients' privacy-preserving behaviors in cross-silo FL as a multi-stage privacy preservation game, where each stage game corresponds to one training iteration. Specifically, clients selfishly perturb their local updates in each training iteration to trade off between convergence performance and privacy loss. To analyze the game, we first derive a novel theoretical bound to characterize the impact of clients' local perturbations on the convergence of FL through analyzing the corrective effect of gradient descent in model training. With the novel convergence bound, we prove that each stage game is a potential game with a unique Nash equilibrium (NE) and the multi-stage privacy preservation game admits a unique subgame perfect Nash equilibrium (SPNE). We show that at the SPNE, the magnitude of each client's local perturbation decreases geometrically with training iterations. We then characterize the efficiency of the SPNE in terms of social cost by the price of anarchy (PoA), and show that the efficiency decreases with the number of clients in some cases. To tackle this problem, we propose a socially efficient incentive mechanism that allows monetary transfer among clients and guarantees individual rationality, budget balance, and social efficiency. To further elicit the private information from the selfish clients, we propose a truthful mechanism that achieves approximate social efficiency. Simulation results show that our proposed mechanisms are effective even when clients are highly heterogeneous, and can decrease clients' total cost by up to 58.08% compared with that at the SPNE.

The model accuracy achieved by federated learning (FL) depends significantly on devices' data distributions. To improve the model accuracy of FL with heterogeneous data distributions on devices, existing works propose some device sampling methods for the central server, but face the problem that the selected devices may still have unbalanced data. In this paper, we propose a novel coalitional FL framework for FL with heterogeneous data. Specifically, devices can cooperate and form device coalitions to reduce the data unbalancedness, and we formulate devices' interactions as a coalition formation game. Then the server selects an optimal subset of device coalitions to improve the model accuracy. Analyzing the coalition formation and selection framework is challenging since the relationship between model accuracy and data heterogeneity is not clear, and devices' coalition formation decisions and the server's coalition selection strategy are coupled in a highly non-trivial manner. We first derive a novel theoretical characterization of the relationship between model accuracy loss and data heterogeneity which follows an inverse function. With the novel theoretical relationship, we analyze devices' coalition formation game. We characterize the conditions under which the Nash stable partition exists, and propose an accelerated algorithm for devices to reach the Nash stable partition. For the server's device coalition selection problem, we show that the model accuracy loss depends on both data heterogeneity and the number of data samples of device coalitions in a non-monotonous way, and we propose a low-complexity algorithm for the server to select device coalitions efficiently. We conduct extensive simulations and show that our proposed coalition formation and selection framework reduces the data heterogeneity of selected device coalitions by up to$58.6\%$and increases the model accuracy by up to$6.8\%$compared with four existing benchmarks.

As a privacy-preserving distributed learning paradigm, federated learning (FL) enables multiple client devices to train a shared model without uploading their local data. To further enhance the privacy protection performance of FL, differential privacy (DP) has been successfully incorporated into FL systems to defend against privacy attacks from adversaries. In FL with DP, how to stimulate efficient client collaboration is vital for the FL server due to the privacy-preserving nature of DP and the heterogeneity of various costs (e.g., computation cost) of the participating clients. However, this kind of collaboration remains largely unexplored in existing works. To fill in this gap, we propose a novel analytical framework based on Stackelberg game to model the collaboration behaviors among clients and the server with reward allocation as incentive in FL with DP. We first conduct rigorous convergence analysis of FL with DP and reveal how clients’ multidimensional attributes would affect the convergence performance of FL model. Accordingly, we solve the Stackelberg game and derive the collaboration strategies for both clients and the server. We further devise an approximately optimal algorithm for the server to efficiently conduct the joint optimization of the client set selection, the number of global iterations, and the reward payment for the clients. Numerical evaluations using real-world datasets validate our theoretical analysis and corroborate the superior performance of the proposed solution.

Federated learning (FL) is a distributed machine learning scheme in which clients jointly train a model without exposing their private data to a central server. However, two challenges exist: one technical challenge of the non-IID issue and one economic challenge of the incentive issue. Many existing works presented incentive mechanisms to select clients with high-quality data to tackle the non-IID issue. However, the existing works assumed the server's availability of clients' true data quality information. We notice that this assumption is hard to satisfy due to the private nature of the information. In this paper, we try to eliminate this assumption and adopt a local differentially private mechanism in the incentive mechanism. In this regard, we propose a Bayesian-based method for the server to estimate the clients' qualities and an efficient algorithm that incentivizes clients with approximately high-quality data. We prove that our solution has an approximation guarantee and is incentive-compatible, individually rational, and computationally efficient. We also analyze the quality loss due to the integration of the privacy-preserving mechanism. We conduct extensive experiments and show that our proposed solution outperforms the mechanism without considering the non-IID issue and is comparable to the mechanism without privacy protection.

The interests in obtaining fresh data in real-time applications have facilitated fresh data markets. However, existing works on designing fresh data markets have ignored strategic users. Being strategic means that users can optimally time their data purchases, which affects markets' profit. In this paper, we study a fresh data market, where strategic users with heterogeneous data valuations stochastically arrive over time. The strategic users decide the time of data purchase, considering the evolution of data freshness and prices, while the platform decides the data pricing policy over time to maximize its profit. We first consider a dynamic pricing policy, where the platform offers a price menu to each arrival user. The analysis is technically challenging, as heterogeneous users face different integer programming problems in optimizing their data purchase time, making direct optimization of data prices infeasible. To tackle the challenge, we adopt a mechanism design approach. We show that the direct mechanism design problem relax the original problem and obtain the optimal pricing policy analytically. Next, to reduce the implementation complexity, we study a single pricing policy, where the price is fixed over time. We derive the optimal single price analytically in a two-period refreshing model. Perhaps surprisingly, although strategic users have more purchasing options than non-strategic users, users who behave strategically may be worse off. Simulation results show that, although a platform refreshes the data less frequently in the presence of strategic users than facing myopic users, it can earn up to 5 times higher profit.

Federated learning (FL) is a promising distributed framework for collaborative artificial intelligence model training while protecting user privacy. A bootstrapping component that has attracted significant research attention is the design of incentive mechanism to stimulate user collaboration in FL. The majority of works adopt a broker-centric approach to help the central operator to attract participants and further obtain a well-trained model. Few works consider forging participant-centric collaboration among participants to pursue an FL model for their common interests, which induces dramatic differences in incentive mechanism design from the broker-centric FL. To coordinate the selfish and heterogeneous participants, we propose a novel analytic framework for incentivizing effective and efficient collaborations for participant-centric FL. Specifically, we respectively propose two novel game models for contribution-oblivious FL (COFL) and contribution-aware FL (CAFL), where the latter one implements a minimum contribution threshold mechanism. We further analyze the uniqueness and existence for Nash equilibrium of both COFL and CAFL games and design efficient algorithms to achieve equilibrium solutions. Extensive performance evaluations show that there exists free-riding phenomenon in COFL, which can be greatly alleviated through the adoption of CAFL model with the optimized minimum threshold.

Cross-silo federated learning (FL) is a distributed learning approach where clients of the same interest train a global model cooperatively while keeping their local data private. The success of a cross-silo FL process requires active participation of many clients. Different from cross-device FL, clients in cross-silo FL are usually organizations or companies which may execute multiple cross-silo FL processes repeatedly due to their time-varying local data sets, and aim to optimize their long-term benefits by selfishly choosing their participation levels. While there has been some work on incentivizing clients to join FL, the analysis of clients’ long-term selfish participation behaviors in cross-silo FL remains largely unexplored. In this paper, we analyze the selfish participation behaviors of heterogeneous clients in cross-silo FL. Specifically, we model clients’ long-term selfish participation behaviors as an infinitely repeated game, with the stage game being a selfish participation game in one cross-silo FL process (SPFL). For the stage game SPFL, we derive the unique Nash equilibrium (NE), and propose a distributed algorithm for each client to calculate its equilibrium participation strategy. We show that at the NE, clients fall into at most three categories: (i)free riderswho do not perform local model training, (ii) a uniquepartial contributor(if exists) who performs model training with part of its local data, and (iii)contributorswho perform model training with all their local data. The existence of free riders has a detrimental effect on achieving a good global model and sustaining other clients’ long-term participation. For the long-term interactions among clients, we derive a cooperative strategy for clients which minimizes the number of free riders while increasing the amount of local data for model training. We show that enforced by a punishment strategy, such a cooperative strategy is a subgame perfect Nash equilibrium (SPNE) of the infinitely repeated game, under which some clients who are free riders at the NE of the stage game choose to be (partial) contributors. We further propose an algorithm to calculate the optimal SPNE which minimizes the number of free riders while maximizing the amount of local data for model training. Simulation results show that our derived optimal SPNE can effectively reduce the number of free riders by up to$99.3\%$and increase the amount of local data for model training by up to$82.3\%$.

Driven by technologies such as IoT-enabled health care, machine learning applications at the edge, and industrial automation, mobile edge and fog computing paradigms have reinforced a general trend toward decentralized computing, where any network node can route traffic, compute tasks, and store data, possibly at the same time. In many such computing environments, there is a need to cache significant amounts of data, which may include large data sets, machine learning models, or executable code. In this work, we propose a framework for joint computation scheduling, caching, and request forwarding within such decentralized computing environments. We first characterize the stability region of a “genie-aided” computing network where data required by computation are instantly accessible, and develop a throughput optimal control policy for this model. Based on this, we develop a practically implementable distributed and adaptive algorithm, and show that it exhibits superior performance in terms of average task completion time, when compared to several baseline policies.

Sharding is one of the most promising and practical methods to achieve horizontal scalability of blockchain networks. However, the increasing number of cross-shard transactions in blockchain sharding protocols may degrade the system throughput. In this paper, we investigate how to distribute users properly in the shard-based blockchains to boost the system transaction performance. We first build an open Jackson queueing network model to capture users' transaction dynamics on shards. Then we cast users' interactions as a shard-based blockchain game, wherein each user aims to minimize its transaction confirmation time and transaction fee. We investigate the equilibrium of the game, and design a polynomial-time algorithm to find efficient equilibria with good system performance. We further design a novel sharding protocol with dynamic user distribution for the permissionless blockchain, and the protocol can maintain good performance in long-term dynamic environment. Extensive numerical results using realistic blockchain transaction data demonstrate that the proposed algorithm and the designed protocol can achieve superior performance for shard-based blockchains.

As edge computing provides crucial support for delay-sensitive and computation-intensive applications, many business entities deploy their own edge servers to compete for users, which forms multi-server edge computing networks. However, no prior work studies the competition among heterogeneous edge servers and how the competition affects users’ selfish computation offloading behaviors in such a network from an economic perspective. In this paper, we model the interactions between edge servers and users as a two-stage game. In Stage I, edge servers with heterogeneous marginal costs set their service prices to compete for users, and in Stage II, each user selfishly offloads its task to one of the edge servers or the remote cloud. Analyzing the equilibrium of the two-stage game is challenging due to edge servers’ heterogeneity and the congestion effect caused by resource sharing among users. We first prove that in Stage II, users’ selfish computation offloading game is a potential game and admits a unique Nash equilibrium (NE), for which we derive the explicit expression. We then analyze edge servers’ price competition game in Stage I and characterize the conditions for the uniqueness of the NE. We show that at equilibrium, users only choose low-priced edge servers, and hence edge servers with low marginal costs can win the price competition, which reflects the improvement of economic efficiency in competitive markets. Moreover, it is surprising that the equilibrium prices do not monotonically increase with the task execution delay. This is because a long execution delay gives a chance to edge servers with high marginal costs to win the competition, which results in more fierce competition among edge servers.

Data freshness, measured by Age of information (AoI), is becoming an increasingly significant metric for data valuation. However, most existing data trading markets ignore the impact of such a metric. In this paper, we study a fresh data market, where users with heterogeneous valuations for AoI stochastically arrive over time. The platform decides data sampling (which affects the AoI) and pricing policies (to the users), to maximize its profit. We consider three types of pricing policies with increasing flexibility, i.e., a uniform pricing policy, a dual pricing policy, and a dynamic pricing policy. The joint data sampling and pricing optimization is a non-smooth mixed integer programming problem, which is challenging to solve. Despite the difficulty, we derive the closed-form solutions of the optimal data sampling policies and pricing policies for all three cases. Our analysis yields several interesting practical insights. First, the optimal data prices decrease in the unit sampling cost and increase in the users’ arrival rate. Second, for all three pricing policies, the equal-spacing data sampling policy is optimal. Third, numerical results show that the optimal dual pricing policy significantly outperforms the optimal uniform pricing policy. Specifically, the optimal dual pricing policy produces up to 280% of the profit that is achieved by the optimal uniform pricing policy.

The freshness of status information is of great importance for time-critical Internet-of-Things (IoT) applications. A metric measuring status freshness is the Age of Information (AoI), which captures the time elapsed from the status being generated at the source node (e.g., a sensor) to the latest status update. However, in intelligent IoT applications such as video surveillance, the status information is revealed after some computation-intensive and time-consuming data processing operations, which would affect the status freshness. In this article, we propose a novel metric, Age of Processing (AoP), to quantify such status freshness, which captures the time elapsed of the newest received processed status data since it is generated. Compared with AoI, AoP further takes the data processing time into account. Since an IoT device has limited computation and energy resources, the IoT device can choose to offload the data processing to the nearby edge server under constrained status sampling frequency. We aim to minimize theaverageAoP in a long-term process by jointly optimizing the status sampling frequency and processing offloading policy. We first formulate this online problem as an infinite-horizon constrained Markov decision process (CMDP) with an average reward criterion. We then transform the CMDP problem into an unconstrained Markov decision process (MDP) by leveraging a Lagrangian method, and accordingly propose a Lagrangian transformation framework for the original CMDP problem. Furthermore, we integrate the framework with a perturbation-based refinement mechanism for achieving the optimal policy of the CMDP problem. Our investigation shows that to minimize the average AoP: 1) for processing offloading: the policy exploits good channel state to offload processing to the edge server and 2) for status sampling: the waiting time presents a threshold structure. Extensive numerical evaluations show that the proposed algorithm outperforms the benchmarks, with an average AoP reduction up to 30%.

We study the economic interactions among sellers and buyers in online markets. In such markets, buyers have limited information about the product quality, but can observe the sellers' reputations which depend on their past transaction histories and ratings from past buyers. Sellers compete in the same market through pricing, while considering the impact of their heterogeneous reputations. We consider sellers with limited as well as unlimited capacities, which correspond to different practical market scenarios. In the unlimited seller capacity scenario, buyers prefer the seller with the highest reputation-price ratio. If the gap between the highest and second highest seller reputation levels is large enough, then the highest reputation seller dominates the market as a monopoly. If sellers' reputation levels are relatively close to each other, then those sellers with relatively high reputations will survive at the equilibrium, while the remaining relatively low reputation sellers will get zero market share. In the limited seller capacity scenario, we further consider two different cases. If each seller can only serve one buyer, then it is possible for sellers to set their monopoly prices at the equilibrium while all sellers gain positive market shares; if each seller can serve multiple buyers, then it is possible for sellers to set maximum prices at the equilibrium. Simulation results show that the dynamics of reputations and prices in the longer-term interactions will converge to stable states, and the initial buyer ratings of the sellers play the critical role in determining sellers' reputations and prices at the stable state.

Caching networks can reduce the routing costs of accessing contents by caching contents closer to users. However, cache nodes may belong to different entities and behave selfishly to maximize their own benefits, which often lead to performance degradation for the overall network. While there has been extensive literature on allocating contents to caches to maximize the social welfare, the analysis of selfish caching behaviors remains largely unexplored. In this paper, we model the selfish behaviors of cache nodes as selfish caching games on arbitrary directed graphs with heterogeneous content popularity. We study the existence of a pure strategy Nash equilibrium (PSNE) in selfish caching games, and analyze its efficiency in terms of social welfare. We show that a PSNE does not always exist in arbitrary-topology caching networks. However, if the network does not have a mixed request loop, i.e., a directed loop in which each edge is traversed by at least one content request, we show that a PSNE always exists and can be found in polynomial time. Furthermore, we can avoid mixed request loops by properly choosing request forwarding paths. We then show that the efficiency of Nash equilibria, captured by the price of anarchy (PoA), can be arbitrarily poor if we allow arbitrary content request patterns, and adding extra cache nodes can make the PoA worse, i.e., cache paradox happens. However, when cache nodes have homogeneous request patterns, we show that the PoA is bounded even allowing arbitrary topologies. We further analyze the selfish caching games for cache nodes with limited computational capabilities, and show that an approximate PSNE exists with bounded PoA in certain cases of interest. Simulation results show that increasing the cache capacity in the network improves the efficiency of Nash equilibria, while adding extra cache nodes can degrade the efficiency of Nash equilibria.

The emergence of IoT devices and the predicted increase in the number of data-driven and delay-sensitive applications highlight the importance of dispersed computing platforms (e.g. edge computing and fog computing) that can intelligently manage in-network computation and data placement. In this paper, we propose the DECO (Data-cEntric COmputation) framework for joint computation, caching, and request forwarding in data-centric computing networks. DECO utilizes a virtual control plane which operates on the demand rates for computation and data, and an actual plane which handles computation requests, data requests, data objects and computation results in the physical network. We present a throughput optimal policy within the virtual plane, and use it as a basis for adaptive and distributed computation, caching, and request forwarding in the actual plane. We demonstrate the superior performance of the DECO policy in terms of request satisfaction delay as compared with several baseline policies, through extensive numerical simulations over multiple network topologies.

Caching networks can reduce the routing costs of accessing contents by caching contents closer to users. However, cache nodes may belong to different entities and behave selfishly to maximize their own benefits, which often lead to performance degradation for the overall network. In this paper, we model the selfish behaviors of cache nodes as selfish caching games on arbitrary directed graphs with heterogeneous content popularity. We study the existence of a pure strategy Nash equilibrium (PSNE) in selfish caching games, and analyze its efficiency in terms of social welfare. We show that a PSNE does not always exist in arbitrary-topology caching networks. However, if the network does not have a mixed request loop, i.e., a directed loop in which each edge is traversed by at least one content request, we show that a PSNE always exists and can be found in polynomial time. We then show that the efficiency of Nash equilibria, captured by the price of anarchy (PoA), can be arbitrarily poor if we allow arbitrary content request patterns. However, when cache nodes have homogeneous request patterns, we show that the PoA is bounded even allowing arbitrary topologies. We further analyze the selfish caching games for cache nodes with limited computational capabilities, and show that an approximate PSNE exists with bounded PoA in certain cases of interest.

For Internet-based services, users' quality of service (QoS) depends on not only the available resource (capacity) but also the number of users who use the resource simultaneously (e.g., congestion effect). When a new Internet-based service provider first enters the market, there can be uncertainties regarding both the capacity and congestion, and hence the uncertainty of QoS. In this paper, we consider a participation-dependent social learning over the QoS through users' online reviews, where the QoS changes with the number of review participants. We study how such a learning process affects the provider's dynamic pricing strategy. With a simple two-period model, we analyze the strategic interactions between the provider and the users, and characterize the provider's optimal two-period dynamic pricing policy. Our results show that when the capacity is small or the users' prior QoS belief is high, the provider will choose a higher introductory price in the first period (than the price in the second period). This is in sharp contrast with the common practice of setting a lower introductory price to attract users (when congestion is not an issue). Furthermore, the learning process is beneficial to the provider with a large capacity.

Crowdsourced wireless community networks can effectively alleviate the limited coverage issue of Wi-Fi access points (APs), by encouraging individuals (users) to share their private residential Wi-Fi APs with others. In this paper, we provide a comprehensive economic analysis for such a crowdsourced network, with the particular focus on the users' behavior analysis and the community network operator's pricing design. Specifically, we formulate the interactions between the network operator and users as a two-layer Stackelberg model, where the operator determining the pricing scheme in Layer I, and then users determining their Wi-Fi sharing schemes in Layer II. First, we analyze the user behavior in Layer II via a two-stage membership selection and network access game, for both small-scale networks and large-scale networks. Then, we design a partial price differentiation scheme for the operator in Layer I, which generalizes both the complete price differentiation scheme and the single pricing scheme (i.e., no price differentiation). We show that the proposed partial pricing scheme can achieve a good tradeoff between the revenue and the implementation complexity. Numerical results demonstrate that when using the partial pricing scheme with only two prices, we can increase the operator's revenue up to 124.44 percent comparing with the single pricing scheme, and can achieve an average of 80 percent of the maximum operator revenue under the complete price differentiation scheme.

Crowdsourced wireless community networks enable individual users to share their private Wi-Fi access points (APs) with each other, hence can achieve a large Wi-Fi coverage with a low deployment cost. This paper presents the first Wi-Fi sharing mechanism design for the community network operator under incomplete information, where the quality of each user-provided Wi-Fi access is his private information. Specifically, we propose a contract-based incentive mechanism, where the operator offers a set of contract items to users, each consisting of a Wi-Fi access price (that a user can charge others who access his AP) and a subscription fee (that a user needs to pay the operator). Different from prior contract mechanisms for wireless networks, here each user's best contract choice depends not only on his private information, but also on other users' choices. This greatly complicates the contract design, as the operator needs to analyze the equilibrium choices of all users, rather than the best choice of each single user. We derive the feasible contract that guarantees the user participation and truthful information disclosure under the equilibrium. Our analysis shows that a higher type user (who provides a higher quality access) is more likely to choose a higher price and subscription fee. Simulation results further show that when increasing the ratio of higher type users in the system, the operator can gain more profit, while counter-intuitively, offering lower prices and subscription fees for all users.

Mobile users’ correlated mobility and data consumption patterns often lead to severe cellular network congestion in peak hours and hot spots. This paper presents an optimal design of time and location aware mobile data pricing, which incentivizes users to smooth traffic and reduce network congestion. We derive the optimal pricing scheme through analyzing a two-stage decision process, where the operator determines the time and location aware prices by minimizing his total cost in Stage I, and each mobile user schedules his mobile traffic by maximizing his payoff (i.e., utility minus payment) in Stage II. We formulate the two-stage decision problem as a bilevel optimization problem, and propose a derivative-free algorithm to solve the problem for any increasing concave user utility functions. We further develop low complexity algorithms for the commonly used logarithmic and linear utility functions. The optimal pricing scheme ensures a win-win situation for the operator and users. Simulations show that the operator can reduce the cost by up to$97.52$percent in the logarithmic utility case and$98.70$percent in the linear utility case, and users can increase their payoff by up to$79.69$and$106.10$percent for the two types of utilities, respectively, comparing with a time and location independent pricing benchmark. Our study suggests that the operator should provide price discounts at less crowded time slots and locations, and the discounts need to be significant when the operator's cost of provisioning excessive traffic is high or users’ willingness to delay traffic is low.

A crowdsourced wireless community network can effectively alleviate the limited coverage issue of Wi-Fi access points (APs), by encouraging individuals (users) to share their private residential Wi-Fi APs with each other. This paper presents the first study on the users' joint membership selection and network access problem in such a network. Specifically, we formulate the problem as a two-stage dynamic game: Stage I corresponds to a membership selection game, in which each user chooses his membership type; Stage II corresponds to a set of network access games, in each of which each user decides his WiFi connection time on the AP at his current location. We analyze the Subgame Perfect Equilibrium (SPE) of the two-stage game, and analyze whether and how best response dynamics can reach the equilibrium. We further numerically explore how the equilibrium changes with the users' mobility patterns and network access evaluations. We show that a user with a more popular home location, a smaller travel time, or a smaller network access evaluation is more likely to choose the Bill membership type. We further demonstrate how the network operator can optimize its pricing and incentive mechanism based on the equilibrium analysis.

Mobile users' social behaviors often lead to significant temporal and spatial variations of mobile traffic. This could create severe cellular network congestion in peak hours and hot spots. This paper presents an initial study on designing the time and location aware pricing scheme to incentivize users to smooth traffic and reduce network congestion. We derive the optimal pricing scheme through analyzing a two-stage decision process, where the operator announces the time and location aware prices in Stage I, and users schedule their mobile traffic accordingly in Stage II. We can translate such a two-stage decision problem into a bilevel optimization problem, which is NP-hard and challenging to solve. We propose an easily implementable algorithm, which utilizes a penalty method and a block coordinate decent algorithm to solve the problem. The resultant pricing scheme ensures a win-win situation for both the operator and users. Our simulation shows that the operator can reduce the extra cost for provisioning the peak traffic by up to 98.70%, and users can increase their total payoff by up to 106.10%, comparing with a time and location independent pricing benchmark.