What if machines could discover human behavioral patterns better than experts? Traditional behavioral modeling in economics depends on costly manual refinement by domain experts, severely limiting scalability and discovery potential. We introduce AutoBM, an automated behavioral modeling framework leveraging large language models (LLMs) to systematically generate, evaluate, and refine interpretable behavioral models directly from human behavior data. AutoBM represents candidate models as structured natural language specifications, explicitly defining symbolic terms along with their tunable parameters, interpretations, and design rationales. AutoBM leverages LLMs to automatically translate each language specification into executable code, optimize tunable parameters, and evaluate model performance. Utilizing LLM-guided search strategies, AutoBM iteratively recombines and improves models at the term level, closely mirroring human expert practices. Experiments conducted across three distinct strategic environments (the ultimatum game, repeated rock-paper-scissors, and continuous double auctions) demonstrate that AutoBM-generated models consistently outperform leading manually crafted models, achieving significant improvements in prediction accuracy while maintaining clear interpretability. Our results demonstrate that automated frameworks can not only match but systematically exceed human expertise in behavioral modeling, fundamentally changing how we understand strategic human behavior.

Federated Learning (FL) enables collaborative model training without data sharing, yet participants face a fundamental challenge, e.g., simultaneously ensuring fairness across demographic groups while protecting sensitive client data. We introduce a differentially private fair FL algorithm (FedPF) that transforms this multi-objective optimization into a zero-sum game where fairness and privacy constraints compete against model utility. Our theoretical analysis reveals an inverse relationship: privacy mechanisms that protect sensitive attributes can reduce the statistical power available for detecting and correcting demographic biases under finite samples in federated settings. We further show that our theoretical bounds are consistent with a non-monotonic fairness-utility relationship, which is empirically validated by experiments where moderate fairness constraints improve generalization before excessive enforcement degrades performance. Compared with mainstream algorithms, even under strict privacy constraints, FedPF still maintains the lowest discrimination level among all tested algorithms while retaining high utility. Experimental validation demonstrates up to 42.9 % discrimination reduction across three datasets while maintaining competitive accuracy, but more importantly, reveals that achieving strong privacy and fairness simultaneously requires carefully balanced tradeoffs rather than optimizing either objective in isolation. Furthermore, hardware-level simulations demonstrate that FedPF maintains a low computational footprint, making it suitable for resource-constrained edge devices. The source code for our proposed algorithm is publicly accessible at https://github.com/szpsunkk/FedPF.

Vector data trading is essential for cross-domain learning with vector databases, yet it remains largely unexplored. We study this problem under online learning, where sellers face uncertain retrieval costs and buyers provide stochastic feedback to posted prices. Three main challenges arise: (1) heterogeneous and partial feedback in configuration learning, (2) variable and complex feedback in pricing learning, and (3) inherent coupling between configuration and pricing decisions. We propose a hierarchical bandit framework that jointly optimizes retrieval configurations and pricing. Stage I employs contextual clustering with confidence-based exploration to learn effective configurations with logarithmic regret. Stage II adopts interval-based price selection with local Taylor approximation to estimate buyer responses and achieve sublinear regret. We establish theoretical guarantees with polynomial time complexity and validate the framework on four real-world datasets, demonstrating consistent improvements in cumulative reward and regret reduction compared with existing methods.

Proximity graphs are the state-of-the-art solution for approximate nearest neighbor (ANN) search, supporting applications such as Web search and retrieval-augmented generation (RAG). Sustaining long-term performance requires adaptive pruning as data and query workloads evolve. However, existing approaches are largely static and uniform. Adaptive pruning faces three key challenges: temporal drift in data and query distributions, spatial heterogeneity across graph regions, and costly feedback due to graph-level evaluations. We present BANCO, a bandit-based framework for adaptive proximity graph pruning. BANCO unifies diverse pruning strategies within a common decision space and optimizes them via a drift-aware batched bandit algorithm. It addresses temporal drift through drift-aware updates, captures spatial heterogeneity using contextual features for region-specific pruning, and reduces evaluation costs through batched feedback aggregation. We establish a dynamic regret bound with sublinear loss and polynomial computational complexity. Extensive experiments on four real-world datasets demonstrate that BANCO helps maintain long-term ANN search efficiency and accuracy under evolving data and workloads.

In the bigdata era, data trading significantly enhances data-driven decision-making by facilitating data sharing. Streaming data from sources such as mobile devices and social media platforms creates new opportunities and challenges for data trading. Traditional data trading methods, designed for one time queries over static data base snapshots, neglect the growing need for trading continuous queries over streaming data. If applied directly to continuous queries, existing methods often result in repeated and imprecise charges that reduce the seller's profit, as they do not consider computation sharing during continuous query execution. To address these challenges, we propose CQ Trade, the first mechanism for continuous query based data trading, which incorporates computation sharing in query execution and integrates seamlessly with existing trading mechanisms. Our contributions are threefold: (1) we provide a theoretical analysis of prevalent computation-sharing techniques, including costmodeling and closed-form computation-sharing strategy derivation; (2) we formulate a general optimization problem to maximize the seller's profit, adaptable to various computation-sharing techniques; (3) we identify that our op timization problem merges vector bin packing and multidimensional knapsack challenges, and we tackle this complexity with a tailored branch-and-price algorithm that decomposes the problem in to a master problem and multiple sub-problems, achieving a globally optimal solution. Evaluation shows CQ Trade improve strading success rate by 12.8% and increases seller profit by 28.7% compared to traditional methods.

Blockchain-based energy trading (BBET) systems depend on prosumers to allocate energy betweentradingactivities andblockchain miningoperations. However, inadequate incentive structures lead prosumers to under-contribute to mining, creating throughput bottlenecks and system performance degradation. This paper introduces the Fee and Two-Piece Compensation (FTPC) mechanism to optimize energy allocation and enhance system throughput. We formulate the interaction between the system designer and prosumers as a three-stage Stackelberg game where the system designer establishes the incentive framework in Stage I, while prosumers determine energy allocation in Stage II and set transaction fees in Stage III. Our analysis demonstrates that prosumers' failure to internalize mining's positive externality results in suboptimal throughput investment. Counterintuitively, we show that impatient prosumers may exploit others' mining contributions as free riders. The FTPC mechanism resolves these issues by jointly optimizing transaction fees and compensation structures to align individual incentives with social welfare. We prove that FTPC achieves socially optimal outcomes through fully decentralized decision-making. Numerical evaluation shows FTPC improves social welfare and prosumer payoffs by 88.1% and 87.8%, respectively. Ethereum testbed implementation validates equilibrium convergence through iterative best-response dynamics.

Information Elicitation Without Verification (IEWV) refers to eliciting high-accuracy solutions from crowd members when the ground truth is unverifiable. While prior research on IEWV has focused on central entities providing incentives to motivate effort exertion, this work explores the less-studied decentralized setting, which is increasingly relevant in machine learning, crowd decision-making, and autonomous organization applications. We model members’ strategic interactions as a two-stage game, where each member decides her incentive contribution strategy in Stage I and her effort exertion strategy in Stage II. We examine two types of incentive allocation mechanisms: Equal Allocation (EA), where each member receives an equal proportion of the total incentives, and Output Agreement (OA), where a member receives incentives if her solution matches a reference solution generated by other members. This paper first analyzes the two-member case and provides closed-form equilibrium results. For more than two members, we use a binomial approximation to simplify the combinatorial computation of the majority voting problem and characterize the symmetric Nash equilibrium under EA. For OA, we derive equilibrium results for effort exertion and propose an algorithm for the incentive contribution game due to discontinuous payoffs. Our results show that OA outperforms EA in the aggregated team solution accuracy at equilibrium. Furthermore, we reveal that higher member ability beyond a certain threshold may lead to reduced effort exertion under EA, and that smaller teams achieve better accuracy when the effort cost is high due to less free-riding behavior. Numerical and empirical simulations validate our theory.

Unmanned Aerial Vehicles (UAVs) have emerged as powerful tools for real-time data collection across Points of Interest (PoIs) in critical domains such as environmental monitoring, disaster response, and intelligent transportation systems. In this paper, we tackle the challenging problem of UAV trajectory planning to minimize Age of Information (AoI)—a key metric that captures data freshness—within networks modeled as graphs. By establishing fundamental lower bounds on achievable AoI under any routing policy, we reveal that these bounds become tight specifically when the graph contains a Hamiltonian cycle, while proving the general AoI minimization problem is NP-hard. To overcome this complexity barrier, we introduce two innovative approximation algorithms: HPA, which achieves a 4 3 -approximation ratio for Hamiltonian paths, and TSA, which guarantees a 2-approximation ratio for general connected graphs. For disconnected graphs, we propose algorithms to construct the connected graphs by adding additional nodes, and then apply HPA and TSA on the connected graphs. Numerical studies further show that these algorithms outperform both conventional heuristic and deep reinforcement learning approaches and maintain robust performance across diverse graph granularities, confirming their real-world applicability and effectiveness.

Generative Artificial Intelligence (GenAI) enables digital representatives to make decisions on behalf of team members in collaborative tasks, but faces challenges in accurately representing preferences. While supplying GenAI with detailed personal information improves representation fidelity, feasibility constraints make complete information access impractical. We bridge this gap by developing a game-theoretic framework that models strategic information revelation to GenAI in collective decision-making. The technical challenges lie in characterizing members’ equilibrium behaviors under interdependent strategies and quantifying the imperfect preference learning outcomes by digital representatives. Our contribution includes closed-form equilibrium characterizations that reveal how members strategically balance team decision preference against communication costs. Our analysis yields an interesting finding: Conflicting preferences between team members drive competitive information revelation, with members revealing more information than those with aligned preferences. While digital representatives produce aggregate preference losses no smaller than direct participation, individual members may paradoxically achieve decisions more closely aligned with their preferences when using digital representatives, particularly when manual participation costs are high or when GenAI systems are sufficiently advanced.

In crowdfunding, a project creator maximizes revenue by jointly optimizing information disclosure and pricing strategies for contributors who arrive stochastically. Such a joint optimization problem is challenging to solve due to its online nature and intertwined strategies. Nevertheless, we propose an online algorithm (with low computational complexity$\mathcal{O}\left(N_{\textit{max}}^{2}\right)$) to address the problem in two steps. First, we show that it is optimal for the creator to charge the same price between two consecutive information disclosure instances. Second, we prove that a creator only needs to consider whether to disclose information immediately after a contributor arrives. We show that the creator increases the price as the campaign processes, which is consistent with the common observation. Our mechanism numerically outperforms the popular information disclosure policy used by leading platforms like Kickstarter and Indiegogo, yielding an average revenue gain of 150%.

Energy efficiency (EE) is vital for 5G networks to manage the increased traffic demand while minimizing operational costs and reducing environmental impact. Optimizing energy usage also supports scalability and helps meet regulatory sustainability goals as network infrastructure expands. In a practical commercial 5G network, a widely-used method to reduce energy consumption is to dynamically shut down underutilization cells and reduce the overlapping cell coverage based on real-time traffic patterns. However, the inherent uncertainty of traffic demands, coupled with the unknown distribution function, significantly complicates the optimization of cell shutdown strategies, rendering both conventional deterministic and stochastic optimization methods ineffective. To tackle these challenges, we propose a distributionally robust optimization framework for EE optimization that does not rely on distributional knowledge. First, we construct a data-driven uncertainty set to model traffic distribution and apply Lagrangian duality to transform the infinite-dimensional optimization problem into a more tractable finite-dimensional one. Then, we employ a Bayesian optimization algorithm to efficiently solve this reformulated problem, which involves a mixed space of high-dimensional combinatorial cell shutdown and continuous Lagrangian multipliers, even with constrained black-box evaluations. Simulations on real-world field data show that our proposed solution outperforms existing benchmarks, achieving energy efficiency improvements ranging from 0.7 % to 11.05 %.

Data streams collected from multiple sources are rarely independent. Values evolve over time and influence one another across sequences. These correlations improve prediction in healthcare, finance, and smart-city control yet violate the record-independence assumption built into most Differential Privacy (DP) mechanisms. To restore rigorous privacy guarantees without sacrificing utility, we introduce Correlated-Sequence Differential Privacy (CSDP), a framework specifically designed for preserving privacy in correlated sequential data. CSDP addresses two linked challenges: quantifying the extra information an attacker gains from joint temporal and cross-sequence links, and adding just enough noise to hide that information while keeping the data useful. We model multivariate streams as a Coupling Markov Chain, yielding the derived loose leakage bound expressed with a few spectral terms and revealing a counterintuitive result: stronger coupling can actually decrease worst-case leakage by dispersing perturbations across sequences. Guided by these bounds, we build the Freshness-Regulated Adaptive Noise (FRAN) mechanism—combining data aging, correlation-aware sensitivity scaling, and Laplace noise—that runs in linear time. Tests on two-sequence datasets show that CSDP improves the privacy-utility trade-off by approximately 50% over existing correlated-DP methods and by two orders of magnitude compared to the standard DP approach.

Data trading significantly enhances data utility by enabling data sharing across diverse applications. Despite being crucial for real-time analytics and online machine learning, trading continuous queries with streaming data output remains largely unexplored. The inherent characteristics of trading continuous queries pose distinctive technical challenges in scheduling query execution. First, the streaming nature demands online scheduling under information uncertainty, where data utilities and execution costs vary unpredictably during query execution. Second, the intrinsic NP-hardness of the optimization problem, coupled with repeated invocation requirements, necessitates efficient algorithmic solutions to address computational complexity. We present OSTOR, the first online scheduling framework for trading continuous queries. OSTOR aims to maximize social welfare, defined as the difference between buyers' obtained utilities and sellers' execution costs, while achieving both theoretical guarantees and practical efficiency. To handle the information uncertainty, we present a primary-dual decomposition method that transforms the online scheduling problem into multiple one-round integer programming problems, enabling adaptive decision-making that only needs current system information. To address the computational complexity, we design an adaptive dual descent (ADD) algorithm that iteratively optimizes dual variables, achieving a bounded constant approximation ratio in polynomial time. We further enhance OSTOR through structureaware greedy optimization strategies with provable performance guarantees. Extensive experiments demonstrate that OSTOR substantially improves social welfare and reduces query execution costs on both real-world and synthetic datasets, compared to existing data trading methods.

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 rapid growth of AI-generated content (AIGC) services has created an urgent need for effective prompt pricing strategies, yet current approaches overlook users' strategic two-step decision-making process in selecting and utilizing generative AI models. This oversight creates two key technical challenges: quantifying the relationship between user prompt capabilities and generation outcomes, and optimizing platform payoff while accounting for heterogeneous user behaviors. We address these challenges by introducing prompt ambiguity, a theoretical framework that captures users' varying abilities in prompt engineering, and developing an Optimal Prompt Pricing (OPP) algorithm. Our analysis reveals a counterintuitive insight: users with higher prompt ambiguity (i.e., lower capability) exhibit non-monotonic prompt usage patterns, first increasing then decreasing with ambiguity levels, reflecting complex changes in marginal utility. Experimental evaluation using a character-level GPT-like model demonstrates that our OPP algorithm achieves up to 31.72 % improvement in platform payoff compared to existing pricing mechanisms, validating the importance of user-centric prompt pricing in AIGC services.

Large-scale wireless networks pose significant challenges in resource scheduling, where the solution space grows exponentially with network size. While network decomposition offers a promising solution by breaking networks into manageable subnetworks, existing approaches, including spectral clustering, fail to effectively capture the complex service relationships between base stations (BSs) and users, particularly in networks with massive user populations. This paper presents BSCCD (Bidirectional Spectral Co-Clustering Based Decomposition), a new decomposition scheme that addresses these challenges through two key innovations: (i) a two-round spectral co-clustering framework that captures bidirectional BS-user relationships, and (ii) a user node merging strategy that handles massive user populations. Extensive experiments on real-world datasets from multiple Chinese cities demonstrate that BSCCD reduces computation latency by up to 61.91 % compared to global optimization, while achieving more than 10 % improvement in solution quality over traditional clustering approaches. The advantage is particularly pronounced in medium-scale networks, where BSCCD outperforms traditional methods by$\mathbf{2 8. 7 6 \%}$. Our results demonstrate BSCCD's practical viability for resource scheduling in contemporary wireless networks, especially in scenarios with complex BS-user interactions and large user populations.

Federated learning (FL) has been extensively applied in industrial cyber-physical systems (ICPSs) to develop powerful models for complex industrial tasks (e.g., fault diagnosis), while safeguarding industrial data confidentiality. Asynchronous federated learning (AFL) effectively mitigates the straggler issue in the synchronous paradigm by aggregating client models in a first-come-first-served manner. Proper client selection is crucial for achieving efficient model training in AFL. A widely adopted model for implementing client selection in AFL is multi-armed bandit (MAB), which models client selection as arm pulling. Existing MAB-based client selection schemes overlook practical scenarios where direct client-server communications are unfavorable or unavailable (for example, in ICPSs such as mines, where communication infrastructure is underdeveloped, direct client-server communication is often unreliable or even unfeasible). In such cases, the server needs to incentivize self-interested relays to perform arm-pulling actions, including selecting the right client and relaying the communication from the selected client to the server. This paper proposes the first framework of incentivized online client selection for AFL. The design and optimization of such a framework involve significant challenges due to the tight coupling between unknown client behavior and private relay cost. To circumvent this challenge, we adopt the dual-based method and construct a special Lagrangian function that incorporates client behavior learning and relay cost revelation, and utilize it to design a socially-optimal mechanism for the framework. Our mechanism satisfies several desirable properties, including voluntary participation, incentive compatibility, relay utilization fairness, and client participation fairness. The proposed mechanism achieves the same asymptotic performance as the state-of-the-art benchmark that requires additional information. Furthermore, our analysis reveals that more available relays bring our mechanism closer to the theoretical upper bound of social performance. Numerical results demonstrate that our proposed mechanism achieves up to 85% and 99% of the social welfare obtained by the benchmarks.

Federated learning protects users’ data privacy by sharing users’ local model parameters (instead of raw data) with a server. However, when massive users train a large machine learning model through federated learning, the dynamically varying and often heavy communication overhead can put significant pressure on the network operator. The operator may choose to dynamically change the network prices in response, which will eventually affect the payoffs of the server and users. This paper considers the under-explored yet important issue of the joint design of participation incentives (for encouraging users’ contribution to federated learning) and network pricing (for managing network resources). Due to heterogeneous users’ private information and multi-dimensional decisions, the optimization problems in Stage I of multi-stage games are non-convex. Nevertheless, we are able to analytically derive the corresponding optimal contract and pricing mechanism through proper transformations of constraints, variables, and functions, under three interaction structures of the participants. We show that the coordinated structure is better than the two uncoordinated structures, as it avoids the selfish behaviors of the network operator and the server; the vertically uncoordinated structure is better than the horizontally uncoordinated structure, as it avoids the interests misalignment between the server and the network operator. We also propose multi-period network pricing to reduce the implementation complexity of dynamic pricing. Numerical results based on real-world datasets show that our proposed mechanisms decrease the server's cost by up to 24.87% and increase the network operator's profit by up to 1245.25%, compared with the state-of-the-art benchmarks.

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.

The high-definition (HD) map is a cornerstone of autonomous driving. The crowdsourcing paradigm is a cost-effective way to keep an HD map up-to-date. Current HD map crowdsourcing mechanisms aim to enhance HD map freshness within recruitment budgets. However, many overlook unique and critical traits of crowdsourcing vehicles, such as random arrival and heterogeneity, leading to either compromised map freshness or excessive recruitment costs. Furthermore, these characteristics complicate the characterization of the feasible space of the optimal recruitment policy, necessitating a method to compute it efficiently in dynamic transportation scenarios. To overcome these challenges, we propose an efficient and cost-effective vehicle recruitment (ENTER) mechanism. Specifically, the ENTER mechanism has a threshold structure and balances freshness with recruitment costs while accounting for the vehicles’ random arrival and heterogeneity. It also integrates the bound-based relative value iteration (RVI) algorithm, which utilizes the threshold-type structure and upper bounds of thresholds to reduce the feasible space and expedite convergence. Numerical results show that the proposed ENTER mechanism increases the HD map company's payoff by 23.40$\%$and 43.91$\%$compared to state-of-the-art mechanisms that do not account for vehicle heterogeneity and random arrivals, respectively. Furthermore, the bound-based RVI algorithm in the ENTER mechanism reduces computation time by an average of 18.91% compared to the leading RVI-based algorithm.

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.

Machine learning (ML) model trading, known for its role in protecting data privacy, faces a major challenge: information asymmetry. This issue can lead to model deception, a problem that current literature has not fully solved, where the seller misrepresents model performance to earn more. We propose a game-theoretic approach, adding a verification step in the ML model market that lets buyers check model quality before buying. However, this method can be expensive and offers imperfect information, making it harder for buyers to decide. Our analysis reveals that a seller might probabilistically conduct model deception considering the chance of model verification. This deception probability decreases with the verification accuracy and increases with the verification cost. To maximize seller payoff, we further design optimal pricing schemes accounting for heterogeneous buyers’ strategic behaviors. Interestingly, we find that reducing information asymmetry benefits both the seller and buyer. Meanwhile, protecting buyer order information doesn’t improve the payoff for the buyer or the seller. These findings highlight the importance of reducing information asymmetry in ML model trading and open new directions for future research.

Trilevel learning, also called trilevel optimization (TLO), has been recognized as a powerful modelling tool for hierarchical decision process and widely applied in many machine learning applications, such as robust neural architecture search, hyperparameter optimization, and domain adaptation. Tackling TLO problems has presented a great challenge due to their nested decision-making structure. In addition, existing works on TLO face the following key challenges: 1) they all focus on the non-distributed setting, which may lead to privacy breach; 2) they do not offer any non-asymptotic convergence analysis which characterizes how fast an algorithm converges. To address the aforementioned challenges, this paper proposes an asynchronous federated trilevel optimization method to solve TLO problems. The proposed method utilizes u-cuts to construct a hyper-polyhedral approximation for the TLO problem and solve it in an asynchronous manner. We demonstrate that the proposed u-cuts are applicable to not only convex functions but also a wide range of non-convex functions that meet the u-weakly convex assumption. Furthermore, we theoretically analyze the non-asymptotic convergence rate for the proposed method by showing its iteration complexity to obtain ϵ-stationary point is upper bounded by O(1/ϵ²). Extensive experiments on real-world datasets have been conducted to elucidate the superiority of the proposed method, e.g., it has a faster convergence rate with a maximum acceleration of approximately 80%.

In the era of big data, data trading significantly enhances data-driven technologies by facilitating data sharing. Despite the clear advantages often experienced by data users when incorporating multiple sources, the topic of multi-source data trading remains largely unexplored. This paper designs a novel data trading framework, which enables multi-source data trading through multi-source cooperation. The proposed framework aims to improve data usage efficiency and increase seller revenue. In particular, we model data sellers’ cooperative decisions through the Nash bargaining framework and systematically outline the interactions between sellers and buyers as a two-stage Stackelberg game. A key contribution of this work is the consideration of coupling among diverse data products, which is essential but often overlooked in prior studies. We properly classify data’s utility into endogenous and relational categories to disentangle the coupling. Despite the inherent non-convex nature of the optimization problem, we methodically derive the closed-form optimal solutions by decomposing the problem into several subproblems. Interestingly, we reveal that, under our proposed framework, sellers’ revenue initially remains steady with the increase of product coupling level, but begins to rise once the level exceeds a certain threshold due to the substitute effect. Finally, experimental results show that our proposed framework can improve the seller’s profit by up to 46.32% compared to traditional data trading methods in the current data market.

In SplitFed learning (SFL), a global model is split into two segments, where distributed clients train the first segment in a federated manner and a main server trains the other. Existing studies focus on algorithm development but ignore the important issue of incentives, without which self-interested clients may be unwilling to participate. We fill this gap by presenting a first incentive study in SFL. One challenge is that the design requires an understanding of how clients' participation affects the model performance. To this end, we provide a first convergence analysis for SFL considering partial client participation to guide the mechanism design. Another challenge is that monetary payment may not be viable for large distributed systems. To this end, we propose a model-versioning mechanism where the main server assigns different versions of models (of different qualities) to clients as incentives. The design is further complicated by clients' multi-dimensional private information. To this end, we design the model-versioning mechanism so that it decouples clients' decisions and admits a weakly dominant strategy at equilibrium. We prove that our mechanism is feasible, effective, and incentive compatible. Experimental results show that our mechanism greatly improves client participation and model accuracy compared to a benchmark.

While providing machine learning model as a service to process users’ inference requests, online applications can periodically upgrade the model utilizing newly collected data. Federated learning (FL) is beneficial for enabling the training of models across distributed clients while keeping the data locally. However, existing work has overlooked the coexistence of model training and inference under clients’ limited resources. This paper focuses on the joint optimization of model training and inference to maximize inference performance at clients. Such an optimization faces several challenges. The first challenge is to characterize the clients’ inference performance when clients may partially participate in FL. To resolve this challenge, we introduce a new notion of age of model (AoM) to quantify client-side model freshness, based on which we use FL’s global model convergence error as an approximate measure of inference performance. The second challenge is the tight coupling among clients’ decisions, including participation probability in FL, model download probability, and service rates. Toward the challenges, we propose an online problem approximation to reduce the problem complexity and optimize the resources to balance the needs of model training and inference. Experimental results demonstrate that the proposed algorithm improves the average inference accuracy by up to 12%.

A proper mechanism design can help federated learning (FL) to achieve good social welfare by coordinating self-interested clients through the learning process. However, existing mechanisms neglect the network effects of client participation, leading to suboptimal incentives and social welfare. This paper addresses this gap by exploring network effects in FL incentive mechanism design. We establish a theoretical model to analyze FL model performance and quantify the impact of network effects on heterogeneous client participation. Our analysis reveals the non-monotonic nature of FL network effects. To leverage such effects, we propose a model trading and sharing (MTS) framework that allows clients to obtain FL models through participation or purchase. To tackle heterogeneous clients' strategic behaviors, we further design a socially efficient model trading and sharing (SEMTS) mechanism. Our mechanism achieves social welfare maximization solely through customer payments, without additional incentive costs. Experimental results on an FL hardware prototype demonstrate up to 148.86% improvement in social welfare compared to existing mechanisms.

In this paper, we consider a blockchain-based energy trading (BBET) system with the proof-of-stake (PoS) protocol. The system designer aims to minimize system cost by considering the prosumers' strategic token allocation between blockchain staking and energy purchase for their applications. This is challenging as the system designer does not know prosumers' private information of impatience levels towards different applications. To this end, we propose an online learning mechanism (OLM), which includes incentive mechanisms to guide both prosumers' private information reporting and staking decisions in two phases. In the exploration phase, we design a randomized staking reward to encourage prosumers' truthful reporting of their private information for the learning of impatience level distributions. Based on the threshold structure of the prosumers' equilibrium staking strategies, in the exploitation phase, we propose a learning-error-based reward to minimize the system cost considering the finite-sample bias. By characterizing the optimal exploration duration, we prove that OLM achieves an asymptotic zero-regret against the complete information benchmark, with the regret bounded by [EQUATION] when operating for T time slots. We implement the corresponding smart contract in Ethereum to demonstrate the feasibility of our approach. Experiment results show that our mechanism reduces regret by an average of 74% compared to the state-of-art mechanism.

Knowledge distillation (KD) can enable collaborative learning among distributed clients that have different model architectures and do not share their local data and model parameters with others. Each client updates its local model using the average model output/feature of all client models as the target, known as federated KD. However, existing federated KD methods often do not perform well when clients’ local models are trained with heterogeneous local datasets. In this paper, we propose Federated knowledge distillation enabled by Adversarial Learning (FedAL) to address the data heterogeneity among clients. First, to alleviate the local model output divergence across clients caused by data heterogeneity, the server acts as a discriminator to guide clients’ local model training to achieve consensus model outputs among clients through a min-max game between clients and the discriminator. Moreover, catastrophic forgetting may happen during the clients’ local training and global knowledge transfer due to clients’ heterogeneous local data. Towards this challenge, we design the less-forgetting regularization for both local training and global knowledge transfer to guarantee clients’ ability to transfer/learn knowledge to/from others. Experimental results show thatFedALand its variants achieve higher accuracy than other federated KD baselines.

The proliferation of real-time applications has motivated extensive research on analyzing and optimizing data freshness in the context of age of information. However, classical frameworks of privacy (e.g., differential privacy (DP)) have overlooked the impact of data freshness on privacy guarantees, which may provide a new tool for time-varying databases. In this work, we introduce age-dependent DP, taking into account the underlying stochastic nature of a time-varying database. In this new framework, we assume knowledge of the data process’s statistical information and establish a connection between classical DP and age-dependent DP. We use this connection to characterize the impact of data staleness and temporal correlation on privacy guarantees. Our characterization reveals that the total variation distance is the sole essential statistical information. Moreover, we demonstrate that aging, which involves utilizing stale data inputs and/or delaying the release of outputs, can serve as a novel strategy for safeguarding data privacy, in addition to the traditional approach of injecting noise in the DP framework. Furthermore, to generalize our results to a multi-query scenario, we present a sequential composition result for age-dependent DP under any publishing and aging policies. We then characterize the optimal tradeoffs between privacy risk and utility and show how this can be achieved. Finally, case studies show that to achieve an arbitrarily small privacy risk in a single-query case, combing aging and noise injection only leads to a bounded accuracy loss, whereas using noise injection only (as in the benchmark case of DP) will lead to an unbounded accuracy loss.

As the sociological theory of homophily suggests, people tend to interact with those of similar preferences. Motivated by this well-established phenomenon, today's online sellers, such as Amazon, seek to learn a new buyer's private preference from his friends’ purchase records. Although such learning allows the seller to enable personalized pricing and boost revenue, buyers are also increasingly aware of these practices and may alter their social behaviors accordingly. This paper presents the first study regarding how buyers strategically manipulate their social interaction signals considering their preference correlations, and how a seller can take buyers’ strategic social behaviors into consideration when designing the pricing scheme. Starting with the basic two-buyer network, we propose and analyze a parsimonious model that uniquely captures the double-layered information asymmetry between the seller and buyers, integrating both individual buyer information and inter-buyer correlation information. Our analysis reveals that only high-preference buyers tend to manipulate their social interactions to evade the seller's personalized pricing, but surprisingly, their payoffs may actually worsen as a result. Additionally, we demonstrate that the seller can considerably benefit from the learning practice, regardless of whether the buyers are aware of this fact or not. Indeed, our analysis reveals that buyers’ learning-aware strategic manipulation has only a slight impact on the seller's revenue. In light of the tightening regulatory policies concerning data access, it is advisable for sellers to maintain transparency with buyers regarding their access to buyers’ social interaction data for learning purposes. This finding aligns well with current informed-consent industry practices for data sharing. Finally, we explore the seller's dynamic learning process across multiple interconnected buyers, and show that learning previous buyers’ preferences may not necessarily help infer other buyers’ preferences in the seller's subsequent learning phase.

Federated learning (FL) algorithms usually sample a fraction of clients in each round (partial participation) when the number of participants is large and the server's communication bandwidth is limited. Recent works on the convergence analysis of FL have focused on unbiased client sampling, e.g., sampling uniformly at random, which suffers from slow wall-clock time for convergence due to high degrees of system heterogeneity (e.g., diverse computation and communication capacities) and statistical heterogeneity (e.g., unbalanced and non-i.i.d. data). This paper aims to design an adaptive client sampling algorithm for FL over wireless networks that tackles both system and statistical heterogeneity to minimize the wall-clock convergence time. We obtain a new tractable convergence bound for FL algorithms with arbitrary client sampling probability. Based on the bound, we analytically establish the relationship between the total learning time and sampling probability with an adaptive bandwidth allocation scheme, which results in a non-convex optimization problem. We design an efficient algorithm for learning the unknown parameters in the convergence bound and develop a low-complexity algorithm to approximately solve the non-convex problem. Our solution reveals the impact of system and statistical heterogeneity parameters on the optimal client sampling design. Moreover, our solution shows that as the number of sampled clients increases, the total convergence time first decreases and then increases because a larger sampling number reduces the number of rounds for convergence but results in a longer expected time per-round due to limited wireless bandwidth. Experimental results from both hardware prototype and simulation demonstrate that our proposed sampling scheme significantly reduces the convergence time compared to several baseline sampling schemes. Notably, for EMNIST dataset, our scheme in hardware prototype spends 71% less time than the baseline uniform sampling for reaching the same target loss.

Traditional user profiling techniques rely on browsing history or purchase records to identify users’ willingness to pay. This enables sellers to offer personalized prices to profiled users while charging only a uniform price to non-profiled users. However, the emergence of privacy-enhancing technologies has caused users to actively avoid on-site data tracking. Today, major online sellers have turned to public platforms such as online social networks to better track users’ profiles from their product-related discussions. This paper presents the first analytical study on how users should best manage their social activities against potential personalized pricing, and how a seller should strategically adjust her pricing scheme to facilitate user profiling in social networks. We formulate a dynamic Bayesian game played between the seller and users under asymmetric information. The key challenge of analyzing this game comes from the double couplings between the seller and the users as well as among the users. Furthermore, the equilibrium analysis needs to ensure consistency between users’ revealed information and the seller’s belief under random user profiling. We address these challenges by alternately applying backward and forward induction, and successfully characterize the unique perfect Bayesian equilibrium (PBE) in closed form. Our analysis reveals that as the accuracy of profiling technology improves, the seller tends to raise the equilibrium uniform price to motivate users’ increased social activities and facilitate user profiling. However, this results in most users being worse off after the informed consent policy is imposed to ensure users’ awareness of data access and profiling practices by potential sellers. This finding suggests that recent regulatory evolution towards enhancing users’ privacy awareness may have unintended consequences of reducing users’ payoffs. Finally, we examine prevalent pricing practices where the seller breaks a pricing promise to personalize final offerings, and show that it only slightly improves the seller’s average revenue while introducing higher variance.

In a crowdfunding campaign, the project creator determines various campaign decisions, such as the pricing and information revelation strategy, to maximize the funding. Each contributor has a high or low valuation for the project. In this paper, we present a study on how the contributors’ random arrival and pledging process affect the creator’s campaign decisions. Specifically, a creator first determines and announces the pricing and information disclosure strategy before the campaign starts. Then contributors randomly arrive and choose their pledging decisions. Contributors make their decisions based on not only the disclosed status so far but also the estimation of the later contributors’ random arrival and pledging decisions. This randomness and complicated decision coupling among contributors render the analysis challenging. Nonetheless, we prove that contributors’ equilibrium decisions follow a threshold structure. Based on this, we propose an algorithm to solve the creator’s optimal campaign decisions. Our analysis on the creator’s strategic information disclosure shows that the contributors’ prior belief on the fraction of high-valuation contributors is critical. Specifically, when the prior belief is high, the creator withholds the pledging status information from the contributors until the campaign ends. When the prior belief is low, the creator should disclose the information update immediately once the first contributor arrives. Such an early disclosure increases the confidence of later contributors and motivates their pledging decisions. Our numerical results show that with strategic information disclosure, the creator can increase the funding by 100% on average, compared with the immediate-disclosure policy widely adopted by crowdfunding platforms.

Federated learning (FL) enables multiple data owners to collaboratively train machine learning (ML) models for different model requesters while keeping data localized. Thus, FL can mitigate privacy leakage in conventional data marketplaces for ML applications requiring raw data trading for centralized model training. Nevertheless, data owners involved in FL may still suffer potential privacy leakage from gradient exposure to the model requesters. In this work, we advocate a novel data marketplace with differentially private federated learning (DPFL) to reduce such threats and maximize the social welfare. Designing such a marketplace involves several challenges. First, it is difficult to determine the privacy budget that a data owner should choose for a model requester, since they have conflicting objectives and private utility/cost information. Second, each data owner sustains privacy costs from his friends’ participation in DPFL due to data correlations, which introduces a negative externality to the market. We design a social-aware iterative double auction (SARDA) mechanism to resolve these challenges and achieve socially optimal market operation. SARDA employs a broker to coordinate the interactions between data owners and model requesters and induces them to truthfully report by iteratively updating the allocation and pricing rules. Moreover, SARDA accounts for the negative externality by incorporating others’ bids to reimburse each data owner. We show that SARDA achieves the optimal social performance and creates up to$60\%$higher social welfare than the social-agnostic benchmark.

Distributed ensemble learning (DEL) involves training multiple models at distributed learners, and then combining their predictions to improve performance. Existing related studies focus on algorithm development but ignore the important issue of incentives, without which self-interested learners may be unwilling to participate. We aim to fill this gap by presenting a first study on the incentive mechanism design in DEL. The mechanism specifies both the training data and the reward for learners with heterogeneous computation and communication costs. One challenge is that it is unclear how learners' diversity (in terms of training data) contributes to the ensemble accuracy. To this end, we decompose the ensemble accuracy into a diversity-precision tradeoff to guide the mechanism design. Another challenge is that the mechanism design is a mixed-integer program with a large search space. To this end, we propose an alternating algorithm that iteratively updates each learner's training data size and reward. We prove that the algorithm converges and is polynomial in the number of learners. Numerical results using MNIST dataset are consistent with our analysis. Interestingly, we show that the mechanism may prefer a lower level of learner diversity to achieve a higher ensemble accuracy. Our code is made publicly available.

Machine learning (ML) model trading prevents data breaches in privacy-sensitive data-driven applications. Departing from commonly assumed complete information scenarios, we consider the more practical trading scenario where model deception may emerge under information asymmetry. More specifically, the model seller may provide false information on model quality to maximize her payoff. This paper takes the first step in tackling information asymmetry through the lens of model verification. We propose an ML model market that allows buyers to verify model quality before purchasing. Such verification can be costly and often imperfect, which makes the buyer's decision highly nontrivial. We first formulate the ML model trading process as a three-stage sequential game with imperfect information, where the seller determines the model delivery strategy after observing the buyer's order decision. Our analysis reveals that at the equilibrium, the seller will probabilistically conduct model deception, considering the possibility of model verification. The equilibrium deception probability increases with the buyer's verification cost and decreases with verification accuracy. Interestingly, we also show that reducing information asymmetry through verification benefits both the buyer and seller. We further consider a second market model with buyer order information protection, where the buyer's order information is unobservable before the seller makes the delivery strategy. Our analysis shows a surprising result under this market model: protecting buyer's order information will not increase the payoff of either the buyer or seller.

Incentive mechanism is crucial for federated learning (FL) when rational clients do not have the same interests in the global model as the server. However, due to system heterogeneity and limited budget, it is generally impractical for the server to incentivize all clients to participate in all training rounds (known as full participation). The existing FL incentive mechanisms are typically designed by stimulating a fixed subset of clients based on their data quantity or system resources. Hence, FL is performed only using this subset of clients throughout the entire training process, leading to a biased model because of data heterogeneity. This paper proposes a game-theoretic incentive mechanism for FL with randomized client participation, where the server adopts a customized pricing strategy that motivates different clients to join with different participation levels (probabilities) for obtaining an unbiased and high-performance model. Each client responds to the server's monetary incentive by choosing its best participation level, to maximize its profit based on not only the incurred local cost but also its intrinsic value for the global model. To effectively evaluate clients' contribution to the model performance, we derive a new convergence bound which analytically predicts how clients' arbitrary participation levels and their heterogeneous data affect the model performance. By solving a non-convex optimization problem, our analysis reveals that the intrinsic value leads to the interesting possibility of bi-directional payment between the server and clients. Experimental results using real datasets on a hardware prototype demonstrate the superiority of our mechanism in achieving higher model performance for the server as well as higher profits for the clients.

In this paper, we propose FedRos, a Federated Reinforcement Learning based multi-robot system, which enables networked robots collaboratively to train a shared model without sharing their private sensing data. Firstly, we present the FedRos pipeline that embeds the Webots robotics simulator. We then highlight features of FedRos, including its compatibility with the state-of-the-art Federated Learning and Reinforcement Learning algorithms and its sim-to-real viability. Lastly, we present benchmark experiments to show the effectiveness of FedRos.11Jianwei Huang and Bing Luo are co-corresponding authors of this paper. This work is supported by the National Natural Science Foundation of China (Project 62271434), Shenzhen Science and Technology Program (Project JCY120210324120011032), Guangdong Basic and Applied Basic Research Foundation (Project 2021B1515120008), Shenzhen Key Lab of Crowd Intelligence Empowered Low-Carbon Energy Network (No. ZDSYS20220606100601002), and the Shenzhen Institute of Artificial Intelligence and Robotics for Society. Video of FedRos demo: https://youtube/oDVpB6eo6qs

Federated learning protects users’ data privacy though sharing users’ local model parameters (instead of raw data) with a server. However, when massive users train a large machine learning model through federated learning, the dynamically varying and often heavy communication overhead can put significant pressure on the network operator. The operator may choose to dynamically change the network prices in response, which will eventually affect the payoffs of the server and users. This paper considers the under-explored yet important issue of the joint design of participation incentives (for encouraging users’ contribution to federated learning) and network pricing (for managing network resources). Due to heterogeneous users’ private information and multi-dimensional decisions, the optimization problems in Stage I of multi-stage games are non-convex. Nevertheless, we are able to analytically derive the corresponding optimal contract and pricing mechanism through proper transformations of constraints, variables, and functions, under both vertical and horizontal interaction structures of the participants. We show that the vertical structure is better than the horizontal one, as it avoids the interests misalignment between the server and the network operator. Numerical results based on real-world datasets show that our proposed mechanisms decrease server’s cost by up to 24.87% comparing with the state-of-the-art benchmarks.

Multi-modal sensing systems are increasingly prevalent in real-world applications such as health monitoring and autonomous driving. Most multi-modal learning approaches need to access users' raw data, which poses significant concerns to users' privacy. Federated learning (FL) provides a privacy-aware distributed learning framework. However, current FL approaches have not addressed the unique challenges of heterogeneous multi-modal FL systems, such as modality heterogeneity and significantly longer training delay. In this paper, we propose Harmony, a new system for heterogeneous multi-modal federated learning. Harmony disentangles the multi-modal network training in a novel two-stage framework, namely modality-wise federated learning and federated fusion learning. By integrating a novel balance-aware resource allocation mechanism in modality-wise FL and exploiting modality biases in federated fusion learning, Harmony improves the model accuracy under non-i.i.d. data distributions and speeds up system convergence. We implemented Harmony on a real-world multi-modal sensor testbed deployed in the homes of 16 elderly subjects for Alzheimer's Disease monitoring. Our evaluation on the testbed and three large-scale public datasets of different applications show that, Harmony outperforms by up to 46.35% accuracy over state-of-the-art baselines and saves up to 30% training delay.

Information Elicitation Without Verification (IEWV) refers to the problem of eliciting high-accuracy solutions from crowd members when the ground truth is unverifiable. A high-accuracy team solution (aggregated from members' solutions) requires members‘ effort exertion, which should be incentivized properly. Previous research on IEWV mainly focused on scenarios where a central entity (e.g., the crowdsourcing platform) provides incentives to motivate crowd members. Still, the proposed designs do not apply to practical situations where no central entity exists. This paper studies the overlooked decentralized IEWV scenario, where crowd members act as both incentive contributors and task solvers. We model the interactions among members with heterogeneous team solution accuracy valuations as a two-stage game, where each member decides her incentive contribution strategy in Stage 1 and her effort exertion strategy in Stage 2. We analyze members‘ equilibrium behaviors under three incentive allocation mechanisms: Equal Allocation (EA), Output Agreement (OA), and Shapley Value (SV). We show that at an equilibrium under any allocation mechanism, a low-valuation member exerts no more effort than a high-valuation member. Counter-intuitively, a low-valuation member provides incentives to the collaboration while a high-valuation member does not at an equilibrium under SV. This is because a high-valuation member who values the aggregated team solution more needs fewer incentives to exert effort. In addition, when members‘ valuations are sufficiently heterogeneous, SV leads to team solution accuracy and social welfare no smaller than EA and OA.

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.

Differentially private federated learning enables clients with privacy concerns to collaboratively train a model while preserving their privacy. Clients' locally available data and maximum tolerable privacy budgets will affect their contributions to the training performance. To date, existing studies focus on homogeneous privacy budgets and thus there lack systematic studies regarding the impact of clients' diverse privacy budgets (privacy heterogeneity). This paper represents the first step toward filling this gap. Through rigorous convergence analysis, we illustrate that the influence of privacy protection on training loss is affected by client selection probabilities. In addition, client selection and privacy protection together induce a non-vanishing training error in federated learning. Our analysis then shows that the non-vanishing training error is a convex function of client selection probabilities and thus allows us to formulate privacy-aware client selection as a convex optimization problem. Numerical results demonstrate that the privacy-aware client selection strategy can significantly improve learning performance. For example, compared with unbiased selection, the privacy-aware client selection strategy decreases the test loss by up to 63% on MNIST convolutional neural network classifier.

The high-definition map is a cornerstone of autonomous driving. Unlike constructing a costly fleet of mapping vehicles, the crowdsourcing paradigm is a cost-effective way to keep an HD map up to date. Achieving practical success for crowdsourcing-based HD maps is contingent on addressing two critical issues: freshness and recruitment costs. Given that crowdsource vehicles are often heterogeneous in terms of operational costs and sensing capabilities, it is practical to recruit heterogeneous crowdsource vehicles to achieve the tradeoff between freshness and recruitment costs. However, existing works neglect this aspect. To solve it, we formulate this problem as a Markov decision process. We demonstrate that the optimal policy is threshold-type age-dependent. Additionally, our findings reveal some counter-intuitive insights. In some cases, the company should initiate vehicle recruitment earlier when vehicles arrive more frequently, or have higher operational costs or sensing capabilities. Besides, we propose an efficient algorithm, called the bound-based relative value iteration (BRVI) algorithm, to overcome the technical challenge that finding an optimal policy is time-consuming. Numerical simulations show that (i) the optimal policy reduces the average cost by 19.04℅ compared to the state-of-the-art mechanism, and (ii) the proposed algorithm can reduce the convergence time by 13.66℅ on average compared to the existing algorithm.

We study the design of incentive mechanisms for the problem of information elicitation without verification (IEWV). In IEWV, a data requester seeks to design proper incentives to optimize the tradeoff between the quality of information (collected from distributed crowd workers) and the total cost of incentives (provided to crowd workers) without verifiable ground truth. While prior work often relies on sufficient knowledge of worker information, we study a scenario where the data requester cannot access workers’ heterogeneous information quality and costs ex-ante. We propose a continuum-armed bandit-based incentive mechanism that dynamically learns the optimal reward level from workers’ reported information. A key challenge is that the data requester cannot evaluate the workers’ information quality without verification, which motivates the design of an inference algorithm. The inference problem is non-convex, yet we reformulate it as a bi-convex problem and derive an approximate solution with a performance guarantee, which ensures the effectiveness of our online reward design. We further enhance the inference algorithm using part of the workers’ historical reports. We also propose a novel rule for the data requester to aggregate workers’ solutions more effectively. We show that our mechanism achieves a sub-linear regret$\tilde {O}(T^{1/2})$and outperforms several celebrated benchmarks.

In this article, we focus on performing few-shot learning (FSL) under multi-agent scenarios in which participating agents only have scarce labeled data and need to collaborate to predict labels of query observations. We aim at designing a coordination and learning framework in which multiple agents, such as drones and robots, can collectively perceive the environment accurately and efficiently under limited communication and computation conditions. We propose a metric-based multi-agent FSL framework which has three main components: an efficient communication mechanism that propagates compact and fine-grained query feature maps from query agents to support agents; an asymmetric attention mechanism that computes region-level attention weights between query and support feature maps; and a metric-learning module which calculates the image-level relevance between query and support data fast and accurately. Furthermore, we propose a specially designed ranking-based feature learning module, which can fully utilize the order information of training data by maximizing the inter-class distance, while minimizing the intra-class distance explicitly. We perform extensive numerical studies and demonstrate that our approach can achieve significantly improved accuracy in visual and acoustic perception tasks such as face identification, semantic segmentation, and sound genre recognition, consistently outperforming the state-of-the-art baselines by 5%-20%.

An Internet of Things (IoT) system can include several different types of service providers, who sell IoT service, network service, and computation service to customers, either jointly or separately. A deep understanding of complicated coupling among these providers in terms of pricing and service decisions is critical to the success of IoT networks. This paper studies the impact of the provider interaction structures on the overall IoT system with heterogeneous customers. Specifically, we first study a generic IoT scenario with three interaction structures: coordinated, vertically-uncoordinated, and horizontally-uncoordinated structures. Despite the challenging non-convex optimization problems involved in modeling and analyzing these structures, we successfully obtain the closed-form optimal pricing strategies of providers in each interaction structure. We further extend the analysis to a specific IoT scenario with local computation capability (e.g., Internet of Vehicles (IoV)). We prove that the coordinated structure is better than two uncoordinated structures for both providers and customers, as it avoids selfish price markup behaviors in uncoordinated structures. Between the two uncoordinated structures, when customers' demand variance is large and utility-cost ratio is medium, vertically-uncoordinated structure is better than horizontal one for both providers and customers, due to the complementary providers' competition in horizontally-uncoordinated structure. Counter-intuitively, we identify that providers' optimal prices do not change with their costs at the critical point of customers' full participation in the vertically-uncoordinated structure.

We study a crowdsourcing problem, where a platform aims to incentivize distributed workers to provide high-quality and truthful solutions that are not verifiable. We focus on a largely overlooked yet pratically important asymmetric information scenario, where the platform knows more information regarding workers’ average solution accuracy and can strategically reveal such information to workers. Workers will utilize the announced information to determine the likelihood of obtaining a reward. We first study the case where the platform and workers share the same prior regarding the average worker accuracy (but only the platform observes the realized value). We consider two types of workers: (1)naiveworkers who fully trust the platform's announcement, and (2)strategicworkers who update prior belief based on the announcement. For naive workers, we show that the platform should always announce a high average accuracy to maximize its payoff. However, this is not always optimal when facing strategic workers, and the platform may benefit from announcing an average accuracy lower than the actual value. We further study the more challenging non-common prior case, and show the counter-intuitive result that when the platform is uninformed of the workers’ prior, both the platform payoff and the social welfare may decrease as the high accuracy workers’ solutions become more accurate.

When it is difficult to verify contributed solutions in mobile crowdsourcing, the majority voting mechanism is widely utilized to incentivize distributed workers to provide high-quality and truthful solutions. In the majority voting mechanism, a worker is rewarded based on whether his solution is consistent with the majority. However, most prior related work relies on a strong assumption that workers solution accuracy levels are public knowledge, which may not hold in many practical scenarios. We relax such an assumption and propose an online mechanism, which allows the platform to learn the distribution of the workers solution accuracy levels via asking workers to report their private accuracy levels (which do not need to be the true values), in addition to deciding their effort levels and solution reporting strategies. The mechanism design is challenging, as neither the workers task solutions nor their accuracy reports can be verified. We devise a randomized reward mechanism that computes the workers rewards based on their reported accuracy levels, under which the workers obtain rewards if their reported solutions match the majority. Our mechanism induces workers to truthfully report their solution accuracy levels in the long run, and the empirical accuracy distribution converges to the actual accuracy distribution.

Data reporters have privacy concerns when they are requested to contribute personal data to a data collector. Such privacy concerns are strengthened by data correlation and social relationship, as the data correlation could inevitably cause privacy issues to their socially-connected individuals who even do not report the data. However, both factors are hard to quantify precisely in practice due to their private nature. Such an incomplete information situation poses great challenges for the data reporters to determine their coupled privacy-preserving strategies and for the data collector to choose a proper privacy-preserving mechanism. This motivates us to propose a novel Bayesian game-theoretic framework to analyze the data reporters’ behaviors. We show that the game has a symmetric Bayesian Nash Equilibrium (BNE) with a threshold structure, which builds a connection between the data reporter’s action and privacy concern under incomplete information. The complicated relationship between the BNE and the data collector’s strategy makes it difficult to solve the data collector’s optimization problem. However, by exploiting the unimodal feature of the problem, we present a low-complexity algorithm to compute the optimal privacy-preserving mechanism. Through analytical and numerical studies, we find that the lack of complete information could cause the data reporters to adopt more conservative strategies but make the data collector adopt a less conservative mechanism, resulting in an overall privacy protection degradation. The simulations further demonstrate that the degradation could be alleviated by stronger data correlation and social relationship, and a higher probability of serious privacy concerns.

To achieve the desirable funding target in a crowdfunding campaign, the project creator needs to accurately anticipate the pledging behaviors of contributors with practical cognitive limitations. In this paper, we present a study on how the contributors’ cognitive bounded rationality affects the creator’s campaign decisions. Specifically, we consider a two-stage crowdfunding model, where a creator first announces the project decisions (i.e., price and the minimum number of required contributors), and then the contributors choose their pledging behaviors (whether and how to contribute) as they arrive stochastically. We consider the cognitive hierarchy model, where contributors are classified into different levels according to their capability of anticipating other contributors’ behaviors. Surprisingly, we show that the cognitive limitation may improve the chance of project success, especially when the crowdfunding target is high. We prove that with a high average contributor cognitive level, a low funding target, and a low difficulty of motivating the lowest cognitive level contributors, the creator can achieve a close-to-optimal revenue by simply assuming that contributors are fully rational. Otherwise, ignoring the contributors’ cognitive limitations can lead to a significant revenue loss.

Federated Learning (FL) has recently received significant interest, thanks to its capability of protecting data privacy. However, existing FL paradigms yield unsatisfactory performance for a wide class of human activity recognition (HAR) applications, since they are oblivious to the intrinsic relationship between data of different users. We propose ClusterFL, a clustering-based federated learning system that can provide high model accuracy and low communication overhead for HAR applications. ClusterFL features a novel clustered multi-task federated learning framework that minimizes the empirical training loss of multiple learned models while automatically capturing the intrinsic clustering relationship among the nodes. We theoretically prove the convergence of proposed FL framework for non-convex and strongly convex models and provide the guidance on selection of hyper-parameters for achieving such convergence. Based on the learned cluster relationship, ClusterFL can efficiently drop the nodes that converge slower or have little correlations with others in each cluster, significantly speeding up the convergence while maintaining the accuracy performance. We evaluate the performance of ClusterFL on an NVIDIA edge testbed using four new HAR datasets collected from 145 users. The results show that ClusterFL outperforms several state-of-the-art FL paradigms in terms of overall accuracy and can save more than 50% communication overhead.

We study a federated learning (FL) framework to effectively train models from scarce and skewly distributed labeled data. We consider a challenging yet practical scenario: a few data sources own a small amount of labeled data, while the rest mass sources own purely unlabeled data. Classical FL requires each client to have enough labeled data for local training, thus is not applicable in this scenario. In this work, we design an effective federated semi-supervised learning framework (FedSSL) to fully leverage both labeled and unlabeled data sources. We establish a unified data space across all participating agents, so that each agent can generate mixed data samples to boost semi-supervised learning (SSL), while keeping data locality. We further show that FedSSL can integrate differential privacy protection techniques to prevent labeled data leakage at the cost of minimum performance degradation. On SSL tasks with as small as 0.17% and 1% of MNIST and CIFAR-10 datasets as labeled data, respectively, our approach can achieve 5-20% performance boost over the state-of-the-art methods.

An Internet of Things (IoT) system can include several different types of service providers, who sell IoT service, network service, and computation service to customers, either jointly or separately. The complicated coupling among these providers in terms of pricing and service decisions is an under-explored research area, the understanding of which is critical to the success of IoT networks. This paper studies the impact of the provider interaction structures on the overall IoT system with massive heterogeneous customers. Specifically, we consider three interaction structures: coordinated, vertically-uncoordinated, and horizontally-uncoordinated structures. Despite the challenging non-convex optimization problems involved in modeling and analyzing these structures, we successfully obtain the closed-form optimal pricing strategies of providers in each interaction structure. We prove that the coordinated structure is better than two uncoordinated structures for both providers and customers, as it avoids selfish price markup behaviors in uncoordinated structures. When customers’ demand variance is large and utility-cost ratio is medium, vertically-uncoordinated structure is better than horizontal one for both providers and customers, due to the complementary providers’ competition in horizontally-uncoordinated structure. Counter-intuitively, we identify that providers’ optimal prices do not change with their costs at the critical point of customers’ full participation in the vertically-uncoordinated structure.

Federated learning (FL) algorithms usually sample a fraction of clients in each round (partial participation) when the number of participants is large and the server’s communication bandwidth is limited. Recent works on the convergence analysis of FL have focused on unbiased client sampling, e.g., sampling uniformly at random, which suffers from slow wall-clock time for convergence due to high degrees of system heterogeneity and statistical heterogeneity. This paper aims to design an adaptive client sampling algorithm that tackles both system and statistical heterogeneity to minimize the wall-clock convergence time. We obtain a new tractable convergence bound for FL algorithms with arbitrary client sampling probabilities. Based on the bound, we analytically establish the relationship between the total learning time and sampling probabilities, which results in a non-convex optimization problem for training time minimization. We design an efficient algorithm for learning the unknown parameters in the convergence bound and develop a low-complexity algorithm to approximately solve the non-convex problem. Experimental results from both hardware prototype and simulation demonstrate that our proposed sampling scheme significantly reduces the convergence time compared to several baseline sampling schemes. Notably, our scheme in hardware prototype spends 73% less time than the uniform sampling baseline for reaching the same target loss.

Existing machine learning (ML) model marketplaces generally require data owners to share their raw data, leading to serious privacy concerns. Federated learning (FL) can partially alleviate this issue by enabling model training without raw data exchange. However, data owners are still susceptible to privacy leakage from gradient exposure in FL, which discourages their participation. In this work, we advocate a novel differentially private FL (DPFL)-based ML model marketplace. We focus on the broker-centric design. Specifically, the broker first incentivizes data owners to participate in model training via DPFL by offering privacy protection as per their privacy budgets and explicitly accounting for their privacy costs. Then, it conducts optimal model versioning and pricing to sell the obtained model versions to model buyers. In particular, we focus on the broker’s profit maximization, which is challenging due to the significant difficulties in the revenue characterization of model trading and the cost estimation of DPFL model training. We propose a two-layer optimization framework to address it, i.e., revenue maximization and cost minimization under model quality constraints. The latter is still challenging due to its non-convexity and integer constraints. We hence propose efficient algorithms, and their performances are both theoretically guaranteed and empirically validated.

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

Human activity recognition (HAR) is a key enabling technology for a wide range of emerging applications. Although multimodal sensing systems are essential for capturing complex and dynamic human activities in real-world settings, they bring several new challenges including limited labeled multimodal data. In this paper, we propose Cosmo, a new system for contrastive fusion learning with small data in multimodal HAR applications. Cosmo features a novel two-stage training strategy that leverages both unlabeled data on the cloud and limited labeled data on the edge. By integrating novel fusion-based contrastive learning and quality-guided attention mechanisms, Cosmo can effectively extract both consistent and complementary information across different modalities for efficient fusion. Our evaluation on a cloud-edge testbed using two public datasets and a new multimodal HAR dataset shows that Cosmo delivers significant improvement over state-of-the-art baselines in both recognition accuracy and convergence delay.

We investigate an unmanned aerial vehicle (UAV) trajectory planning problem for minimizing the Age of Information (AoI) over a sensor network defined on a square grid graph. Despite that the AoI-minimal trajectory planning problem is NP-hard, we derive the fundamental limit of minimum network AoI achieved among all feasible UAV trajectories. We show that such a lower bound is only achievable for graphs with a Hamiltonian Cycle (HC). Based on this finding, we develop an HPA algorithm for graphs with at least one Hamiltonian Path (HP). It achieves a time-average network AoI no more than of that of the optimal trajectory. For more general graphs, we propose a tree-searching algorithm (TSA) which achieves a time-average network AoI at most twice that of the optimal trajectory with a polynomial-time complexity. Numerical results show that the average performance of TSA could be much better than the theoretical bound, and both two algorithms significantly outperform the baseline scheme.

As the sociological theory of homophily suggests, people tend to interact with those of similar preferences. This motivates product sellers to learn buyers’ product preferences from the buyers’ friends’ purchase records. Although such learning allows sellers to enable personalized pricing to improve profits, buyers are also increasingly aware of such practices and may alter their behaviors accordingly. This paper presents the first study regarding how buyers may strategically manipulate their social interaction signals considering their preference correlations, and how an informed seller can take buyers’ strategic social behaviors into consideration when designing the pricing schemes. Our analytical results show that only high-preference buyers tend to manipulate their social interactions to hurdle the seller’s personalized pricing. Surprisingly, these high-preference buyers’ payoff may become worse after their strategic manipulation. Furthermore, we show that the seller can greatly benefit from the learning practice, no matter whether the buyers are aware of such learning or not. In fact, buyers’ learning-aware strategic manipulation only slightly reduces the seller’s revenue. Considering the increasingly stricter policies on data access by authorities, it is thus advisable for sellers to make buyers aware of their access and learning based on social interaction data. This justifies well with current regulatory policies and industry practices regarding informed consent for data sharing.

In current blockchain systems, the transaction fee is often not enough to cover the storage cost, jeopardizing blockchain sustainability in the long run. Such a storage sustainability issue is partially due to miners’ heterogeneous storage costs and users’ low-intensity fee competition. Motivated by these two observations, we propose a Fee and Transaction Expiration Time (FTET) mechanism to alleviate this issue. Specifically, we model the blockchain operation as a three-stage game. In Stage I, the system designer proposes the storage sustainability mechanism. In Stage II, each user decides whether to propose transactions and the corresponding transaction fees. In Stage III, each miner decides which transactions to include in the block. Although the analysis of the heterogeneous miner interaction is technically challenging, we fully solve it in closed-form motivated by how miners select transactions in practice. The equilibrium analysis reveals that high-storage-cost miners admit transactions with fees above a time-increasing threshold. Under the optimal FTET mechanism, the blockchain system can achieve the storage sustainability without any social welfare loss, comparing with the maximum achievable social welfare without the storage sustainability constraint. Moreover, the optimal FTET mechanism achieves a higher social welfare than the fee mechanism in current practice by selectively rejecting some transactions suffering high delays. Finally, we implement a blockchain prototype to compare the performance of the optimal FTET mechanism with the mining round time adjustment (MRTA) mechanism. The optimal FTET mechanism achieves higher social welfare (94.5% on average) and better storage sustainability. We find that more pending transactions may lead to lower transaction fees.

When using location-based services (LBSs), a user obtains points-of-interest (PoI) information by providing the LBS platform with his current geo-location. Such a search leads to potential privacy leakage if an adversary has access to his geo-data. Traditionalk-anonymity mechanisms instruct a user to bear the overhead to report his current location together withk- 1 dummy locations to confuse the adversary, which only work well given a large numberk. Aware of the common practices that a user is actually flexible in service requirement (e.g., as long as the searched PoIs are within his walking distance), we propose a novel approach to help the user gain location privacy from service flexibility for the challenging case of a small numberk. By analyzing the strategic interaction between the user and the adversary in a dynamic Bayesian game, we prove that the user’s equilibrium strategy depends on the adversary’s capability of accessing geo-data. Takek= 2 for example, we find that if the adversary is not likely to access both geo-data, the user should report the two dummy locations at two different directions of his real location, and otherwise at the same direction. Perhaps surprisingly, the user may benefit from the adversary’s access to more geo-data. Furthermore, we extend the game-theoretic approach for multi-query and arbitrary user location distributions. Numerical results show that our approach obviously outperformsk-anonymity mechanisms especially under a small numberk.

Mobile crowdsourcing platforms often want to incentivize workers to finish tasks with high quality and truthfully report their solutions by providing proper rewards. Most existing incentive mechanisms reward workers based on the comparison among workers’ reported solutions. However, these mechanisms are vulnerable to worker collusion, i.e., workers coordinate to misreport their solutions. We address such an issue by proposing a novel rewarding mechanism based on a${truth detection}$technology, which relies on the independent verification of the correctness of each worker’s response to some question with animperfectaccuracy. We model the interactions between the platform and workers as a two-stage Stackelberg game. In Stage I, the platform optimizes the reward mechanism parameters associated withtruth detectionto maximize its payoff. In Stage II, the workers decide their effort levels and reporting strategies to maximize their payoffs (which depend on the output of the truth detector). We analyze the game’s equilibrium and show that our proposed mechanism can effectively mitigate worker collusion. We also propose a novel rule, namedfiltered majority, for the platform to more effectively aggregate the workers’ solutions. Our proposed aggregation rule utilizes truth detection and outperforms the conventional simple majority rule. We further characterize the impact of the truth detection accuracy on the platform’s decisions. Surprisingly, under the simple majority rule, we show that as the truth detection accuracy improves, the platform should always incentivize more workers to exert effort and truthfully report. However, under our proposed filtered majority rule, we show that as the truth detection accuracy improves, in some cases, the platform should incentivize fewer workers and save costs. We further examine the impact of the workers’ imperfect estimation of the truth detection accuracy on the platform’s decisions.

In mobile crowdsourcing, platforms seek to incentivize heterogeneous workers to complete tasks (e.g., road traffic sensing) and truthfully report their solutions. When platforms cannot verify the quality of the workers’ solutions, the crowdsourcing problem is known asinformation elicitation without verification(IEWV). In an IEWV problem, a platform needs to provide incentives to motivate high-quality solutions and truthful reporting of the solutions from the workers. A common approach to solve the IEWV problem is majority voting, where each worker is rewarded according to whether his solution matches the majority’s solution. However, previous work has not considered workers with heterogeneous solution accuracy. This is unrealistic in many domains, where one would expect workers to differ in judgment, expertise, and reliability. Moreover, prior work has not considered how this heterogeneity affects a platform’s tradeoff between the quality of the workers’ solutions and the platform’s cost of achieving this. We address these gaps by studying the interactions between the mobile crowdsourcing platform and workers as a two-stage Stackelberg game. In Stage I, the platform chooses the reward level for majority voting. In Stage II, the workers decide their effort levels and reporting strategies. We show that as a worker’s solution accuracy increases, he is more likely, in equilibrium, to exert effort and truthfully report his solution. However, given a fixed total worker population, surprisingly, the platform’s payoff may decrease in the number of high-accuracy workers. We further characterize the value of knowing the workers’ solution accuracy in terms of improving the platform’s optimal reward design and maximizing its payoff. Knowing such information enables a more effective aggregation of the workers’ solutions. We further design a discriminatory reward policy to incentivize heterogeneous workers. Surprisingly, such a discriminatory policy can improve both the platform’s and the workers’ payoffs, and hence improve the social welfare.

Mobile network operators (MNOs) provide wireless data services based on a tariff data plan with a month data cap. Traditionally, the data cap is only valid for domestic data consumption and users have to pay extra roaming fees for overseas data consumption. A recently emerged location-flexible service allows users to access the domestic data cap in overseas locations (by configuring location-flexibility with a daily fee). This paper studies the economic impact of the location-flexibility on the overseas market. The overseas market tracks the travelers on a monthly basis, hence it is month-variant. Each user in overseas market decides his joint flexibility configuration and data consumption (J-FCDC) every day, which corresponds to an on-line payoff maximization problem. We first analyze the off-line version of J-FCDC problem (which is NP-hard), and then we design an on-line strategy with a provable performance guarantee. Moreover, we propose a pricing policy for the location-flexible service without the need of knowing the market statistic information. We find that the location-flexibility induces users to consume more data in low-valuation days, and the MNO benefits from stimulating users’ data consumption through an appropriate pricing. Numerical results show that the location-flexibility improves the MNO’s revenue and the users’ payoffs.

To exploit users’ heterogeneous data demands, several mobile network operators worldwide have launched the mobile data trading markets, where users can trade mobile data quota with each other. In this paper, we aim to understand the importance of data trading market (DTM) by studying the users’ operator selection and trading decisions, and analyzing the operator’s profit maximizing strategy. We model the interactions between the mobile operator and the users as a three-stage Stackelberg game. In Stage I, the operator chooses the operation fee imposed on sellers to maximize its profit. In Stage II, each user chooses his operator. In Stage III, each DTM user chooses his trading decisions. We derive the closed-form expression of the unique Nash equilibrium (NE) in Stages II and III, where every user proposes the same price such that the total demand matches with the total supply. We further show that the Stage I’s problem is convex and compute the optimal operation fee. Our analysis and numerical results show that an operator with a small initial market share can increase its profit by proposing a DTM, which is in line with the real-world situation in Hong Kong.

In an online social network, users exhibit personal information to enjoy social interaction. The social network provider (SNP) exploits users’ information for revenue generation through targeted advertisement, in which the SNP presents advertisements to proper users effectively. Therefore, an advertiser is more willing to pay for targeted advertisement to promote his product. However, the over-exploitation of users’ information would invade users’ privacy, which would negatively impact users’ social activeness. Motivated by this, we study the privacy policy (policies) of the SNP(s) with targeted advertisement, in both monopoly and duopoly markets. We characterize the privacy policy in terms of the fraction of users’ information that the provider should exploit, and formulate the interactions among users, advertiser, and SNP(s) as a three-stage Stackelberg game. By leveraging the model’s supermodularity property, we prove the threshold structure of users’ equilibrium information levels. We discover the overall information that can be exploited by an SNP is non-monotonic in the exploitation fraction. Monopoly (one SNP) study shows our proposed optimal privacy policy helps the SNP earn even more advertisement revenue than full exploitation policy does. The situation of the duopoly market is much more complicated. In that case, if the service quality gap between the two SNPs is large, the stronger SNP will choose a conservative privacy protection policy that drives the other SNP out of the market. However, if the service quality gap is small and the advertisement revenue is promising, the stronger SNP would choose an aggressive policy to exploit the advertisement revenue and both SNPs will have positive market shares.

Miners in a blockchain system are suffering from ever-increasing storage costs, which in general have not been properly compensated by the users’ transaction fees. This reduces the incentives for the miners’ participation and may jeopardize the blockchain security. To mitigate this blockchain insufficient fee issue, we propose a Fee and Waiting Tax (FWT) mechanism, which explicitly considers the two types of negative externalities in the system. Specifically, we model the interactions between the protocol designer, users, and miners as a three-stage Stackelberg game. By characterizing the equilibrium of the game, we find that miners neglecting the negative externality in transaction selection cause they are willing to accept insufficient-fee transactions. This leads to the insufficient storage fee issue in the existing protocol (i.e., deployed in Bitcoin and Ethereum). Moreover, our proposed optimal FWT mechanism can motivate users to pay sufficient transaction fees to cover the storage costs and achieve the unconstrained social optimum. Numerical results show that the optimal FWT mechanism guarantees sufficient transaction fees and achieves an average social welfare improvement of 51.43% or more over the existing protocol. Furthermore, the optimal FWT mechanism reduces the average waiting time of low-fee transactions and all transactions by 68.49% and 61.56%, respectively.

Due to its mobility and agility, unmanned aerial vehicle (UAV) has emerged as a promising technology for various tasks, such as sensing, inspection and delivery. However, a typical UAV has limited energy storage and cannot fly a long distance without being recharged. This motivates several existing proposals to use trucks and other ground vehicles to offer riding to help UAVs save energy and expand the operation radius. We present the first theoretical study regarding how UAVs should optimally hitch on ground vehicles, considering vehicles' different travelling patterns and supporting capabilities. For a single UAV, we derive closed-form optimal vehicle selection and hitching strategy. When vehicles only support hitching, a UAV would prefer the vehicle that can carry it closest to its final destination. When vehicles can offer hitching plus charging, the UAV may hitch on a vehicle that carries it farther away from its destination and hitch a longer distance. The UAV may also prefer to hitch on a slower vehicle for the benefit of battery recharging. For multiple UAVs in need of hitching, we develop the max-saving algorithm (MSA) to optimally match UAV-vehicle collaboration. We prove that the MSA globally optimizes the total hitching benefits for the UAVs.

A distributed machine learning platform needs to recruit many heterogeneous worker nodes to finish computation simultaneously. As a result, the overall performance may be degraded due to straggling workers. By introducing redundancy into computation, coded machine learning can effectively improve the runtime performance by recovering the final computation result through the first k (out of the total n) workers who finish computation. While existing studies focus on designing efficient coding schemes, the issue of designing proper incentives to encourage worker participation is still under-explored. This paper studies the platform's optimal incentive mechanism for motivating proper workers' participation in coded machine learning, despite the incomplete information about heterogeneous workers' computation performances and costs. A key contribution of this work is to summarize workers' multi-dimensional heterogeneity as a one-dimensional metric, which guides the platform's efficient selection of workers under incomplete information with a linear computation complexity. Moreover, we prove that the optimal recovery threshold k is linearly proportional to the participator number n if we use the widely adopted MDS codes for data encoding. We also show that the platform's increased cost due to incomplete information disappears when worker number is sufficiently large, but it does not monotonically decrease in worker number.

We study a crowdsourcing problem where the platform aims to incentivize distributed workers to provide high-quality and truthful solutions without the ability to verify the solutions. While most prior work assumes that the platform and workers have symmetric information, we study an asymmetric information scenario where the platform has informational advantages. Specifically, the platform knows more information regarding workers' average solution accuracy, and can strategically reveal such information to workers. Workers will utilize the announced information to determine the likelihood that they obtain a reward if exerting effort on the task. We study two types of workers: (1) naive workers who fully trust the announcement, and (2) strategic workers who update prior belief based on the announcement. For naive workers, we show that the platform should always announce a high average accuracy to maximize its payoff. However, this is not always optimal for strategic workers, as it may reduce the credibility of the platform's announcement and hence reduce the platform's payoff. Interestingly, the platform may have an incentive to even announce an average accuracy lower than the actual value when facing strategic workers. Another counter-intuitive result is that the platform's payoff may decrease in the number of high-accuracy workers.

Federated learning (FL) is a distributed learning paradigm that enables a large number of devices to collaboratively learn a model without sharing their raw data. Despite its practical efficiency and effectiveness, the iterative on-device learning process incurs a considerable cost in terms of learning time and energy consumption, which depends crucially on the number of selected clients and the number of local iterations in each training round. In this paper, we analyze how to design adaptive FL that optimally chooses these essential control variables to minimize the total cost while ensuring convergence. Theoretically, we analytically establish the relationship between the total cost and the control variables with the convergence upper bound. To efficiently solve the cost minimization problem, we develop a low-cost sampling-based algorithm to learn the convergence related unknown parameters. We derive important solution properties that effectively identify the design principles for different metric preferences. Practically, we evaluate our theoretical results both in a simulated environment and on a hardware prototype. Experimental evidence verifies our derived properties and demonstrates that our proposed solution achieves near-optimal performance for various datasets, different machine learning models, and heterogeneous system settings.

Many online platforms are providing valuable real-time contents (e.g., traffic) by continuously acquiring the status of different Points of Interest (PoIs). In status acquisition, it is challenging to determine how frequently a PoI should upload its status to a platform, since they are self-interested with private and possibly time-varying preferences. This paper considers a general multi-period status acquisition system, aiming to maximize the aggregate social welfare and ensure the platform freshness. The freshness is measured by a metric termed age of information. For this goal, we devise a long-term decomposition (LtD) mechanism to resolve the time-varying information asymmetry. The key idea is to construct a virtual social welfare that only depends on the current private information, and then decompose the per-period operation into multiple distributed bidding problems for the PoIs and platforms. The LtD mechanism enables the platforms to achieve a tunable trade-off between payoff maximization and freshness conditions. Moreover, the LtD mechanism retains the same social performance compared to the benchmark with symmetric information and asymptotically ensures the platform freshness conditions. Numerical results based on real-world data show that when the platforms pay more attention to payoff maximization, each PoI still obtains a non-negative payoff in the long-term.

We study few-shot learning (FSL) under multi-agent scenarios, in which participating agents only have local scarce labeled data and need to collaborate to predict query data labels. Though each of the agents, such as drones and robots, has minimal communication and computation capability, we aim at designing coordination schemes such that they can collectively perceive the environment accurately and efficiently. We propose a novel metric-based multi-agent FSL framework which has three main components: an efficient communication mechanism that propagates compact and fine-grained query feature maps from query agents to support agents; an asymmetric attention mechanism that computes region-level attention weights between query and support feature maps; and a metric-learning module which calculates the image-level relevance between query and support data fast and accurately. Through analysis and extensive numerical studies, we demonstrate that our approach can save communication and computation costs and significantly improve performance in both visual and acoustic perception tasks such as face identification, semantic segmentation, and sound genre recognition.

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.

The crowdfunding industry is expected to reach a volume of $90 billion per year. In crowdfunding, a creator needs to decide not only the pricing but also when and how frequent to disclose the campaign progress to the contributors, in order to maximize the project revenue. In this paper, we present a first analytical study on how the creator's pricing and information disclosure strategies affect the potential contributors' belief update process, hence the project success and creator's expected revenue. Specifically, we consider a multi-stage crowdfunding model, where a stage corresponds to the period between the creator's two information disclosures. At the beginning of the campaign, a creator announces her pricing decision and information disclosure strategy for revenue maximization. Then contributors coming in each following stage will choose whether to contribute, based on not only the disclosed pledging status so far but also the estimation of the impact of their decisions on later contributors. Such a model is challenging to optimize because of the coupling across multiple stages, especially with contributors' anticipations of future stages. Nevertheless, we are able to characterize the contributors' threshold-based equilibrium pledging decisions, and we incorporate such a structural result into the creator's mixed-integer revenue maximization problem. Through both analytical and numerical studies, we show that the contributors' prior belief of high-valuation contributor percentage plays a critical role in the creator's optimal strategic information disclosure decisions. When the contributors have a high prior belief, a creator should not announce the pledging history until all the contributors have made their pledging decisions. When the prior belief is low, the creator should disclose more often.

Federated Learning (FL) has recently received significant interests thanks to its capability of protecting data privacy. However, existing FL paradigms yield unsatisfactory performance for a wide class of human activity recognition (HAR) applications since they are oblivious to the intrinsic relationship between data of different users. We propose ClusterFL, a similarity-aware federated learning system that can provide high model accuracy and low communication overhead for HAR applications. ClusterFL features a novel clustered multi-task federated learning framework that maximizes the training accuracy of multiple learned models while automatically capturing the intrinsic clustering relationship among the data of different nodes. Based on the learned cluster relationship, ClusterFL can efficiently drop out the nodes that converge slower or have little correlation with other nodes in each cluster, significantly speeding up the convergence while maintaining the accuracy performance. We evaluate the performance of ClusterFL on an NVIDIA edge testbed using four new HAR datasets collected from total 145 users. The results show that, ClusterFL outperforms several state-of-the-art FL paradigms in terms of overall accuracy, and save more than 50% communication overhead at the expense of negligible accuracy degradation.

When using location-based services (LBSs), a user obtains points-of-interest $(\text{P}\text{o}\text{I})$ information by providing the LBS platform with his current geo-location. Such a search also leads to potential privacy leakage if an adversary has access to his geo-data. Traditional k-anonymity mechanisms instruct a user to bear the overhead to report his current location together with k-1 dummy locations to confuse the adversary, which only work well given a large number k. Aware of the common practices that a user is actually flexible in service requirement (e.g., as long as the searched PoIs are within his walking distance), we propose a novel approach to help the user gain location privacy from service flexibility for the case of a small number k. By analyzing the strategic interaction between the user and the adversary in a Bayesian game, we prove that the user with service flexibility should never report his real location for searching PoIs nearby. Instead, he should jointly use all k dummy locations to confuse the adversary’s inference of his real location. Take $k=2$ for example, we manage to show that if the adversary is not likely to access both dummy geo-data, the user should report the two dummy locations at two opposite directions of his real location, and otherwise at the same direction. Perhaps surprisingly, our approach may enable the user to benefit from the adversary’s access to more geo-data. Finally, extensive simulations using some real data show that our mechanism obviously outperforms k anonymity mechanism especially under a small number k.

While users claim to be concerned about privacy, often they do little to protect their privacy in their online actions. One prominent explanation for this "privacy paradox'' is that when an individual shares her data, it is not just her privacy that is compromised; the privacy of other individuals with correlated data is also compromised. This information leakage encourages oversharing of data and significantly impacts the incentives of individuals in online platforms. In this paper, we study the design of mechanisms for data acquisition in settings with information leakage and verifiable data. We design an incentive compatible mechanism that optimizes the worst-case trade-off between bias and variance of the estimation subject to a budget constraint, where the worst-case is over the unknown correlation between costs and data. Additionally, we characterize the structure of the optimal mechanism in closed form and study monotonicity and non-monotonicity properties of the marketplace.

We are interested in developing a unified machine learning framework for effectively training machine learning models from many small data sources such as mobile devices. This is a commonly encountered situation in mobile computing scenarios, where data is scarce and distributed while the tasks are distinct. In this paper, we propose a federated few-shot learning (FedFSL) framework to learn a few-shot classification model that can classify unseen data classes with only a few labeled samples. With the federated learning strategy, FedFSL can utilize many data sources while keeping data privacy and communication efficiency. To tackle the issue of obtaining misaligned decision boundaries produced by client models, we propose to regularize local updates by minimizing the divergence of client models. We also formulate the training in an adversarial fashion and optimize the client models to produce a discriminative feature space that can better represent unseen data samples. We demonstrate the intuitions and conduct experiments to show our approaches outperform baselines by more than 10% in learning benchmark vision tasks and 5% in language tasks.

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.

User profiling allows product sellers to identify users’ willingness to pay and enable personalized pricing. However, users’ information exploited in profiling is usually private and hard to obtain accurately due to users’ privacy concerns. With the increasing popularity of social networks, where users reveal their private information through social interactions, more sellers today profile users through their social data. This paper is the first to study how a seller optimizes personalized pricing through user profiling on social networks, where users proactively react by controlling their social activities and information leakage. We formulate and analyze a dynamic Bayesian game played between users and the seller. First, users decide their social activities by trading off the social network benefit against the potential risk of revealing private information. Then, the seller exploits users’ profiles to determine the personalized prices for the profiled users and a uniform price for the non-profiled users. It is challenging to analyze the Perfect Bayesian Equilibrium (PBE) of this game due to i) the randomness in user profiling, and ii) the coupling among users’ activity levels and that between the seller’s pricing decisions and users’ social activities. Despite the difficulty, we propose to alternate backward induction and forward induction to successfully solve the PBE. We show the surprising result that users’ activity levels do not monotonically decrease as the profiling technology improves. Instead, when user profiling is of high accuracy, the seller strategically chooses a high uniform price to stimulate their increased social activities to profile more users.

A distributed machine learning platform needs to recruit many heterogeneous worker nodes to finish computation simultaneously. As a result, the overall performance may be degraded due to straggling workers. By introducing redundancy into computation, coded machine learning can effectively improve the runtime performance by recovering the final computation result through the first k (out of the total n) workers who finish computation. While existing studies focus on designing efficient coding schemes, the issue of designing proper incentives to encourage worker participation is still under-explored. This paper studies the platform's optimal incentive mechanism for motivating proper workers' participation in coded machine learning, despite the multi-dimensional incomplete information about heterogeneous workers' computation performances and costs. A key contribution of this work is to summarize workers' multi-dimensional heterogeneity as a one-dimensional metric, which guides the platform's efficient selection of workers under incomplete information with a linear computation complexity. Although the exact overall runtime is intractable, we characterize the platform's (asymptotically) optimal load assignment to heterogeneous workers in coded machine learning. When the platform has incomplete information about workers' costs, it is optimal to assign loads only based on workers' computation performances; when the platform further lacks workers' computation performance information, it is optimal to design the loads to be cost-dependent and performance-dependent.

As an emerging machine learning technique, federated learning has received significant attention recently due to its promising performance in mitigating privacy risks and costs. While most of the existing work of federated learning focused on designing learning algorithm to improve training performance, the incentive issue for encouraging users' participation is still under-explored. This paper presents an analytical study on the server's optimal incentive mechanism design, in the presence of users' multi-dimensional private information (e.g., training cost and communication delay). Specifically, we consider a multi-dimensional contract-theoretic approach, with a key contribution of summarizing users' multi-dimensional private information into a one-dimensional criterion that allows a complete order of users. We further perform the analysis in three information scenarios to reveal the impact of information asymmetry levels on server's optimal strategy and minimum cost. We show that weakly incomplete information does not increase the server's cost (comparing with the complete information scenario) when training data is IID, but it in general does when data is non-IID. Furthermore, the optimal mechanism design under strongly incomplete information is much more challenging, and it is not always optimal for the server to incentivize the group of users with the lowest training cost and delay to participate.

Federated learning (FL) is a distributed learning paradigm that enables a large number of mobile devices to collaboratively learn a model under the coordination of a central server without sharing their raw data. Despite its practical efficiency and effectiveness, the iterative on-device learning process (e.g., local computations and global communications with the server) incurs a considerable cost in terms of learning time and energy consumption, which depends crucially on the number of selected clients and the number of local iterations in each training round. In this paper, we analyze how to design adaptive FL in mobile edge networks that optimally chooses these essential control variables to minimize the total cost while ensuring convergence. We establish the analytical relationship between the total cost and the control variables with the convergence upper bound. To efficiently solve the cost minimization problem, we develop a low-cost sampling-based algorithm to learn the convergence related unknown parameters. We derive important solution properties that effectively identify the design principles for different optimization metrics. Practically, we evaluate our theoretical results both in a simulated environment and on a hardware prototype. Experimental evidence verifies our derived properties and demonstrates that our proposed solution achieves near-optimal performance for different optimization metrics for various datasets and heterogeneous system and statistical settings.

We introduce the concept of fresh data trading, in which a destination user requests, and pays for, fresh data updates from a source provider, and data freshness is captured by the age of information (AoI) metric. Keeping data fresh relies on costly frequent data updates by the source, which motivates the source to price fresh data. In this work, the destination incurs an age-related cost, modeled as a general increasing function of the AoI. The source designs a pricing mechanism to maximize its profit, while the destination chooses a data update schedule to trade off its payments to the source and its age-related cost. Depending on different real-time applications and scenarios, we study both a finite-horizon model and an infinite-horizon model with time discounting. The key challenge of designing the optimal pricing scheme lies in the destination's time-interdependent valuations, due to the nature of AoI, and the infinite-dimensional dynamic optimization. To this end, we exploit three different dimensions in designing pricing by studying three pricing schemes: a time-dependent pricing scheme, in which the price for each update depends on when it is requested; a quantity-based pricing scheme, in which the price of each update depends on how many updates have been previously requested; and a simple subscription-based pricing scheme, in which the price per update is constant but the source charges an additional subscription fee. Our analysis reveals that (1) the optimal subscription-based pricing maximizes the source's profit among all possible pricing schemes under both finite-horizon and infinite-horizon models; (2) the optimal quantity-based pricing scheme is only optimal with a finite horizon; and (3) the time-dependent pricing scheme, under the infinite-horizon model with significant time discounting, is asymptotically optimal. Numerical results show that the profit-maximizing pricing schemes can also lead to significant reductions in AoI and social costs, and that a moderate degree of time discounting is enough to achieve a close-to-optimal time-dependent pricing scheme.

With the rich set of embedded sensors installed in smartphones, we are witnessing the emergence of many innovative commercial mobile crowdsensing applications, which combine the power of mobile technology with crowdsourcing to effectively collect time-sensitive and location-dependent information. Motivated by these real-world applications, we consider the distributed task selection problem for heterogeneous users with different initial locations, destinations, costs, speeds, and reputation levels. We design a Bayesian asynchronous task selection (BATS) algorithm to help the users plan their task selections based on the incomplete information of the task popularity statistics. We prove its convergence and characterize the computation time for the users' updates. As a performance benchmark, we consider the ideal case that the service provider centrally allocates the tasks to the users for social surplus maximization. We show that it is an NP-hard problem and propose a greedy centralized algorithm with a lower complexity as the benchmark performance. Simulation results suggest that the BATS scheme achieves the highest Jain's fairness index and coverage, while yielding a user payoff similar to that with the greedy centralized benchmark. Finally, we evaluate the schemes based on some real-world movement time and distance data from Google Maps.

Wireless power transfer (WPT) technology enables a cost-effective and sustainable energy supply in wireless networks. However, the broadcast nature of wireless signals makes them non-excludable public goods, which leads to potential free-riders among energy receivers. In this study, we formulate the wireless power provision problem as a public goods provision problem, aiming to maximize the social welfare of a system of an energy transmitter (ET) and all the energy users (EUs), while considering their heterogeneous valuations, private information, and self-interested behaviors. We propose a two-phase all-or-none scheme involving a low-complexity Power And Taxation (PAT) mechanism, which ensures voluntary participation, truthfulness, budget balance, and social optimality at every Nash equilibrium (NE). We propose a distributed PAT (D-PAT) algorithm to reach an NE, and prove its convergence by connecting the structure of NEs and that of the optimal solution to a related optimization problem. We further extend the analysis to a multi-channel system, which brings a further challenge of non-strictly concave agents' payoffs. We propose a Multi-Channel PAT (M-PAT) mechanism and a distributed M-PAT (D-MPAT) algorithm to address the challenge. Simulation results show that, our design is most beneficial when there are more EUs and more homogeneous channel gains.

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.

Donation-based markets have been implemented by many online platforms, such as live streaming platforms. In these markets, producers provide services without mandatory charges, and customers enjoy the services and voluntarily donate money to the producers. The donation is split between the producers and platform with a pre-agreed fraction. To gain insights into the market operation, we use a two-stage game to capture the sequential decision process between the platform and producers. In Stage I, the platform decides a donation-split-fraction (DSF), i.e., the fraction of donation kept by the producers. In Stage II, producers decide whether to participate in the platform and (if yes) how to choose their service attributes considering the DSF as well as the producers' and customers' preferences. We prove that the Stage II game is a potential game with a counter-intuitive equilibrium result: although a larger DSF leads to more producer participation and a better match between the producers' choices and the customers' preferences, it does not necessarily lead to more total donation. The Stage I problem, nevertheless, is challenging to solve analytically due to its non-convexity. To gain insights regarding the optimal DSF that maximizes the platform's payoff, we characterize both its upper-bound and lower-bound. We show numerically that the platform's optimal payoff always decreases with the mismatch between the producers' and customers' preferences. Finally, we conduct a case study with the dataset from Twitch and demonstrate the approach of computing the platform's optimal DSF without the producers' inherent preferences.

Sharing platforms have facilitated the redistribution of underused resources by providing convenient online marketplaces for individual sellers and buyers. However, the sellers on these platforms may not fully disclose the information of their shared commodities, due to strategic behaviors or privacy concerns. Sellers' strategic information disclosure significantly affects buyers' user experiences and platforms' reputation. This paper presents one of the first analytical studies on information disclosure and pricing strategies of competing sellers on a sharing platform. In particular, we propose a three-stage game framework to capture sellers' strategic behaviors and buyers' decisions. Although the corresponding optimization problem is non-convex, we are able to completely characterize the complex market equilibria. We demonstrate that full disclosure by all sellers or non-disclosure by all sellers will both lead to intense price competition. We prove that the former all-disclosure case is never an equilibrium even when all sellers have good commodity qualities and low privacy costs, while the latter non-disclosure case can be an equilibrium under which all sellers get zero profit. Interestingly, we also reveal that buyers' estimation biases encourage information disclosure as they mitigate the competition among sellers.

A crowdfunding platform enables project creators to raise funding from a crowd of contributors to develop their projects. An accurate modeling and predication of contributors' behaviors is critical for a creator to achieve the project success. In this paper, we present a first study on a creator's optimal crowdfunding campaign parameter choices, considering the contributors' realistic cognitive limitations. Specfically, we consider a two-stage crowdfunding model: in Stage I a creator determines the project decisions (i.e., price and minimum number of contributors); in Stage II the contributors choose their pledging behaviors (whether to contribute and with what probabilities). We apply the cognitive hierarchy theory to model the cognitive limitations of the contributors, i.e., contributors are grouped based on their cognitive levels which reflect their capabilities of reasoning other contributors' decisions. Although the project decisions are highly coupled between contributors' pledging and creator's revenue maximization, we exploit the monotonic structure of the revenue maximization problem to compute creator's optimal solutions. We show that contributors with the same valuation exhibit the same pledging behaviors, independent of their cognitive levels (except those at the lowest cognitive levels). This explains the real-world phenomenon that projects either attract few contributors (often under 40% pledging rate) or are oversubscribed.

Miners in a blockchain system are suffering from the ever-increasing storage costs, which in general have not been properly compensated by the users' transaction fees. In the long run, this may lead to less participation of miners and jeopardize the blockchain security. In this paper, we study the economics of blockchain storage and identify the incentive issues related to this storage cost problem. More specifically, we model the interactions among users (who generate transactions) and miners in two stages, where the users set the transaction fees in Stage 1, and the miners select which transactions to include in Stage 2. Through characterizing the Nash equilibrium of the two-stage game, we find that the transaction fees indeed cannot cover the storage costs under the current practice in general, due to the negative externality and the unfair delay-based pricing. We also identify that a longer block interval can alleviate the concern by raising the transactions fees at the expense of larger delay.

A widely adopted approach to guarantee high-quality services on on-demand service platforms is to introduce a reputation system, where good reputation workers will receive a bonus for providing high-quality services. In this paper, we propose a general reputation framework motivated by various practical examples. Our model captures the evolution of a reputation system, jointly considering worker's strategic behaviors and imperfect customer reviews that are usually studied separately before. We characterize the stationary equilibrium of the market, in particular, the existence and uniqueness of a non-trivial equilibrium that ensures high-quality services. Furthermore, we propose an efficient subsidization mechanism that helps induce high-quality services on the platform, and show the market convergence to the high service quality equilibrium under such a mechanism.

In an online social network, users exhibit personal information to enjoy social interaction. The social network provider (SNP) exploits users' information for revenue generation through targeted advertising. The SNP can present ads to proper users efficiently. Therefore, an advertiser is more willing to pay for targeted advertising. However, the over-exploitation of users' information would invade users' privacy, which would negatively impact users' social activeness. Motivated by this, we study the optimal privacy policy of the SNP with targeted advertising business. We characterize the privacy policy in terms of the fraction of users' information that the provider should exploit, and formulate the interactions among users, advertiser, and SNP as a three-stage Stackelberg game. By carefully leveraging supermodularity property, we reveal from the equilibrium analysis that higher information exploitation will discourage users from exhibiting information, lowering the overall amount of exploited information and harming advertising revenue. We further characterize the optimal privacy policy based on the connection between users' information levels and privacy policy. Numerical results reveal some useful insights that the optimal policy can well balance the users' trade-off between social benefit and privacy loss.

Mobile Network Operators (MNOs) provide wireless data services based on a tariff data plan with a month data cap. Traditionally, the data cap is only valid for domestic data consumption and users have to pay extra roaming fees for overseas data consumption. A recent location-flexible service allows the user to access the domestic data cap in overseas locations (by configuring location-flexibility with a daily fee). This paper studies the economic effect of the location-flexibility on the overseas market. The overseas market comprises users who travel overseas within the month, thus is monthly variant. Each user decides his joint flexibility configuration and data consumption (J-FCDC) every day. The user's J-FCDC problem is an on-line payoff maximization. We analyze its off-line problem (which is NP-hard) and design an on-line strategy with provable performance. Moreover, we propose a pricing policy for the location-flexible service without relying on the market statistic information. We find that the location-flexibility induces users to consume more data in low-valuation days, and the MNO benefits from stimulating users' data consumption through an appropriate pricing. Numerical results based on empirical data show that the location-flexibility improves the MNO's revenue by 18% and the users' payoffs by 12% on average.

Mobile crowd sensing (MCS) has been used to enable a wide range of resource-discovery applications by exploiting the "wisdom" of many mobile users. However, in many applications, a user's valuation depends on other users' sensory data, which introduces the problem of interdependent valuations. This feature can encourage sensory data misreport, hence makes economic mechanisms challenging. While some work has been done to address this problem, the issues of private utility information and communication overheads remain unsolved. In this study, we formulate the first interdependent-valuation model for the resource-discovery MCS systems, aiming to elicit truthful sensory reports and utility information and to maximize expected social welfare. We design a Truthful Sense-And-Bid (T-SAB) Mechanism based on surrogate functions, which can reveal marginal utility information by only requiring each user to submit one-dimensional signaling per resource. We show that the surrogate function and a reward function can limit users' willingness to misreport, when users have small informational sizes, a reasonable condition in large-scale MCS systems. Consequently, our T-SAB Mechanism yields a Perfect Bayesian Equilibrium (PBE) with the efficient allocation outcome, approximate truthfulness, individual rationality, and approximate budget balance. To illustrate the effectiveness of the T-SAB Mechanism, we perform a case study of a cognitive radio network. We demonstrate that the social welfare gain of the T-SAB Mechanism can achieve up to 20% social welfare gain comparing with a benchmark.

The growing demand for mobile data and the evolution of next-generation networks, particularly fifth-generation (5G) wireless networks, has called for new approaches to pricing and managing the limited capacity of existing network resources and infrastructures. In particular, emerging mobile applications like autonomous vehicles, augmented/virtual reality, and more broadly the Internet-of-Things will have heterogeneous demand patterns and service requirements, raising questions on how they should pay for their data usage and how next-generation networks can meet their demands with limited resources. Several recent policy changes and regulatory initiatives have been proposed to address the shift in demands due to next-generation networks and technologies. These include the FCC’s “5G Fast Plan,” which outlines strategies for modifying spectrum policies, infrastructure policies, and existing regulations, in light of emerging 5G technologies. This plan has included the rollback of net neutrality rules in June 2018, allowing broadband providers to offer a wider variety of service options.

Renewable energy generations and energy storage are playing increasingly important roles in serving consumers in power systems. This paper studies the market competition between renewable energy suppliers with or without energy storage in a local energy market. The storage investment brings the benefits of stabilizing renewable energy suppliers' outputs, but it also leads to substantial investment costs as well as some surprising changes in the market outcome. To study the equilibrium decisions of storage investment in the renewable energy suppliers' competition, we model the interactions between suppliers and consumers using a three-stage game-theoretic model. In Stage I, at the beginning of the investment horizon (containing many days), suppliers decide whether to invest in storage. Once such decisions have been made (once), in the day-ahead market of each day, suppliers decide on their bidding prices and quantities in Stage II, based on which consumers decide the electricity quantity purchased from each supplier in Stage III. In the real-time market, a supplier is penalized if his actual generation falls short of his commitment. We characterize a price-quantity competition equilibrium of Stage II in the local energy market, and we further characterize a storage-investment equilibrium in Stage I incorporating electricity-selling revenue and storage cost. Counter-intuitively, we show that the uncertainty of renewable energy without storage investment can lead to higher supplier profits compared with the stable generations with storage investment due to the reduced market competition under random energy generation. Simulations further illustrate results due to the market competition. For example, a higher penalty for not meeting the commitment, a higher storage cost, or a lower consumer demand can sometimes increase a supplier's profit. We also show that although storage investment can increase a supplier 's profit, the first-mover supplier who invests in storage may benefit less than the free-rider competitor who chooses not to invest in storage.

The growing competition drives the mobile network operators (MNOs) to explore adding time flexibility to the traditional data plan, which consists of a monthly subscription fee, a data cap, and a per-unit fee for exceeding the data cap. The rollover data plan, which allows the unused data of the previous month to be used in the current month, provides the subscribers with the time flexibility. In this paper, we formulate two MNOs' market competition as a three-stage game, where the MNOs decide their data mechanisms (traditional or rollover) in Stage I and the pricing strategies in Stage II, and then users make their subscription decisions in Stage III. Different from the monopoly market where an MNO always prefers the rollover mechanism over the traditional plan in terms of profit, MNOs may adopt different data mechanisms at an equilibrium. Specifically, the high-QoS MNO would gradually abandon the rollover mechanism as its QoS advantage diminishes. Meanwhile, the low-QoS MNO would progressively upgrade to the rollover mechanism. The numerical results show that the market competition significantly limits MNOs' profits, but both MNOs obtain higher profits with the possible choice of the rollover data plan.

An effective way for a Mobile network operator (MNO) to improve its revenue is price discrimination, i.e., providing different combinations of data caps and subscription fees. Rollover data plan (allowing the unused data in the current month to be used in the next month) is an innovative data mechanism with time flexibility. In this paper, we study the MNO's optimal multi-cap data plans with time flexibility in a realistic asymmetric information scenario. Specifically, users are associated with multi-dimensional private information, and the MNO designs a contract (with different data caps and subscription fees) to induce users to truthfully reveal their private information. This problem is quite challenging due to the multi-dimensional private information. We address the challenge in two aspects. First, we find that a feasible contract (satisfying incentive compatibility and individual rationality) should allocate the data caps according to users' willingness-to-pay (captured by the slopes of users' indifference curves). Second, for the non-convex data cap allocation problem, we propose a Dynamic Quota Allocation Algorithm, which has a low complexity and guarantees the global optimality. Numerical results show that the time-flexible data mechanisms increase both the MNO's profit (25 percent on average) and users' payoffs (8.2 percent on average) under price discrimination.

An increasing number of mobile applications (abbrev. apps), like Pokemon Go and Snapchat, reward the users who physically visit some locations tagged as POIs (places-of-interest) by the apps. We study the novel POI-based collaboration between apps and venues (e.g., restaurants). On the one hand, an app charges a venue and tags the venue as a POI. The POI tag motivates users to visit the venue, which potentially increases the venue's sales. On the other hand, the venue can invest in the app-related infrastructure, which enables more users to use the app and further benefits the app's business. The apps' existing POI tariffs cannot fully incentivize the venue's infrastructure investment, and hence cannot lead to the most effective app-venue collaboration. We design an optimal two-part tariff, which charges the venue for becoming a POI, and subsidizes the venue every time a user interacts with the POI. The subsidy design efficiently incentivizes the venue's infrastructure investment, and we prove that our tariff achieves the highest app's revenue among a general class of tariffs. Furthermore, we derive some counter-intuitive guidelines for the POI-based collaboration. For example, a bandwidth-consuming app should collaborate with a low-quality venue (users have low utilities when consuming the venue's products).

We study a problem of privacy-preserving mechanism design. A data collector wants to obtain data from individuals to perform some computations. To relieve the privacy threat to the contributors, the data collector adopts a privacy-preserving mechanism by adding random noise to the computation result, at the cost of reduced accuracy. Individuals decide whether to contribute data when faced with the privacy issue. Due to the intrinsic uncertainty in privacy protection, we model individuals' privacy-related decision using Prospect Theory. Such a theory more accurately models individuals' behavior under uncertainty than the traditional expected utility theory, whose prediction always deviates from practical human behavior. We show that the data collector's utility maximization problem involves a polynomial of high and fractional order, the root of which is difficult to compute analytically. We get around this issue by considering a large population approximation, and obtain a closed-form solution that well approximates the precise solution. We discover that the data collector who considers the more realistic Prospect Theory based individual decision modeling would adopt a more conservative privacy-preserving mechanism, compared with the case based on the expected utility theory modeling. We also study the impact of Prospect Theory parameters, and concludes that more loss-averse or risk-seeking individuals will trigger a more conservative mechanism. When individuals have different Prospect Theory parameters, simulations demonstrate that the privacy protection first becomes stronger and then becomes weaker as the heterogeneity increases from a low value to a high one.

We study a privacy-preserving data collection problem by considering individuals' data correlation and social relationship. A data collector gathers data from some data reporters to perform certain analysis with a privacy-preserving mechanism. Due to the data correlation, the analysis will cause privacy leakage not only to the data reporters but also to those individuals who do not report data. Owing to the social relationship among them, the data reporters would consider the possibility of adding some random noise to the reported data to reduce the privacy leakage. The privacy loss of the individuals (both data reporters and non-reporters) depend on all the data reporters' strategies, which naturally leads to a game theoretical analysis. A key result shows that the data reporters can be ordered based on their levels of joint considerations of social relationship and data correlation, and at the Nash Equilibrium of the game at most one data reporter with the most significant consideration may add noise to the reported data. We design an efficient algorithm for the data collector to construct the data reporter set, and derive the optimal privacy-preserving mechanism to ensure all the data reporters' truthful reporting. We conduct extensive simulations with the Facebook social data to demonstrate some insights: It is optimal for the data collector to adopt a more conservative mechanism when the data correlation or the social relationship is stronger. Compared with the data correlation information, the social network information plays a more critical role in the data collector's utility maximization problem.

Many online social networking platforms are leveraging crowdsourcing to enhance the user experience. These platforms seek to incentivize heterogeneous workers to exert efforts to complete tasks (e.g., moderation of posts and articles) and truthfully report their solutions. Output agreement mechanism (e.g., majority voting) is a common approach to this end. In an output agreement mechanism, a worker is rewarded according to whether his solution matches those of his peers. However, prior related work has not studied the workers' heterogeneous solution accuracy and how this heterogeneity affects the platform's payoff. We fill this void by modeling and analyzing the interactions between the platform and workers as a two-stage Stackelberg game. In Stage I, the platform chooses the reward level for the majority voting to maximize its payoff. In Stage II, the workers decide their effort levels and reporting strategies to maximize their payoffs. We show that as a worker's solution accuracy increases, he is more likely to exert effort and truthfully report his solution under the equilibrium reward mechanism. However, given a fixed total worker population, it is surprising that the platform's overall payoff does not monotonically increase in the number of high-accuracy workers. This is because a larger number of high-accuracy workers brings marginally decreasing benefit to the platform, but the rewards required to incentivize them may significantly grow. Moreover, we show that as the solutions of the high-accuracy workers become more accurate, the platform needs a smaller number of such workers to achieve the maximum payoff.

Renewable energy resources are playing an increasingly important role in serving consumers at the distribution level of power systems. This paper studies a duopoly two-settlement local renewable energy market, in which one energy supplier has controllable generations (with the help of energy storage) while the other supplier has random generations. In the day-ahead energy market, suppliers determine the bidding prices and quantities, and then consumers decide the energy quantity to purchase from each supplier. In the real-time energy market, a supplier gets penalized if he cannot deliver the amount of energy as committed in the day-ahead market. We formulate the interactions between suppliers and consumers in the day-ahead market as a two-stage problem. The two-dimensional bidding strategies (price and quantity) in the day-ahead market together with the penalty in the real-time market increase the complexity of the equilibrium analysis. To address such a challenge, we first derive weakly dominant bidding quantity strategies for both suppliers, and then characterize the corresponding pure and mixed price equilibrium. We demonstrate that the supplier with controllable generations can earn a much higher payoff than the supplier with random generations. In some cases, however, we show the perhaps counterintuitive result that a higher penalty or a higher variance of random generations may increase both suppliers' payoffs.

Donation-based markets are becoming increasingly popular in our daily life. One example is the online streaming platform Twitch, which attracts millions of users on a daily basis. On such platforms, firms provide services to customers without mandatory charge, and customers voluntarily donate money to the firms. The donations are split between the firms and the platform with a fixed pre-agreed fraction. To gain insights into the operation and optimization of such platforms, we formulate a two-stage game to study the platform's and firms' behaviors. In Stage I, the platform decides a donation-split-fraction (DSF), which corresponds to the fraction of donations kept by the firms. In Stage II, firms decide whether to participate in the platform and how to choose their service attributes considering the DSF as well as the preferences of firms and customers. Analyzing such a two-stage game directly is challenging, as the Stage II problem corresponds to the multi-firm extension of the Hotelling model and is still an open problem. To resolve this issue, we approximate the large number of firms as non-atomic decision makers, where a single firm's strategy choice does not affect the payoffs of the firm population. Under such an approximation, we prove that the Stage II problem is a potential game. We further show that at the equilibrium, a larger DSF leads to more firm participations and a better match to the customers' preferences. The stage I problem, nevertheless, is a non-convex optimization problem that does not render a closed-form solution. To gain insights, we derive the upper-bound and lower-bound of the optimal DSF solution. The bounds suggest that the platform should increase its DSF if the customers' donation sensitivity to the number of firms increases or if the firms' opportunity cost for participation increases. Finally, we collect data from Twitch and demonstrate the results of the two-stage model with a case study. Our simulation results suggest that under our data and model settings, there exists a significant potential for Twitch to improve its payoff, by setting the DSF to 0.38, instead of 0.71 as in Twitch's current practice.

Mobile Network Operators (MNOs) are providing more flexible wireless data services to attract subscribers and increase revenues. For example, the data trading market enables user-flexibility by allowing users to sell leftover data to or buy extra data from each other. The rollover mechanism enables time-flexibility by allowing a user to utilize his own leftover data from the previous month in the current month. In this paper, we investigate the economic viability of offering the data trading market together with the rollover mechanism, to gain a deeper understanding of the interrelationship between the user-flexibility and the time-flexibility. We formulate the interactions between the MNO and mobile users as a multi-slot dynamic game. Specifically, in each time slot (e.g., every day), the MNO first determines the selling and buying prices with the goal of revenue maximization, then each user decides his trading action (by solving a dynamic programming problem) to maximize his long-term payoff. Due to the availability of monthly data rollover, a user's daily trading decision corresponds to a dynamic programming problem with two time scales (i.e., day-to-day and month-to-month). Our analysis reveals an optimal trading policy with a target interval structure, specified by a buy-up-to threshold and a sell-down-to threshold in each time slot. Moreover, we show that the rollover mechanism makes users sell less and buy more data given the same trading prices, hence it increases the total demand while decreasing the total supply in the data trading market. Finally, numerical results based on real-world data unveil that the time-flexible rollover mechanism plays a positive role in the user-flexible data trading market, increasing the MNO's revenue by 25% and all users' payoff by 17% on average.

Network utility maximization (NUM) is a general framework for optimally allocating constrained resources in many networked applications. When agents have asymmetric and private information, a fundamental economic challenge is how to solve the NUM Problem considering the self-interests of strategic agents. Many previous related works have proposed economic mechanisms that can cope with agents' private utilities. However, the related literature largely neglected the issue of information asymmetries regarding constraints, and limited closely related studies provided solutions only applicable to specific application scenarios. To tackle this issue, we propose the DeNUM Mechanism, the first mechanism for solving a general class of decomposable NUM Problems considering both private utility and constraint information. The key idea is to decentralize the decision process to agents, who will make resource allocation decisions without the need of revealing private information to others. We further show that the DeNUM mechanism yields the network-utility maximizing solution at an equilibrium, and achieves other desirable economic properties (such as individual rationality and budget balance). However, the corresponding equilibrium solution concept, the generalized Nash equilibrium (GNE), makes it difficult to achieve through a distributed algorithm. To address this issue, we further establish the connection between the structure of GNE and that of the primal-dual solution to a reformulated NUM problem, based on which we present the convergent DeNUM Algorithm that is provably convergent. Finally, as a case study, we apply the DeNUM Mechanism to solving the NUM problem for a user-provided network, and show that the DeNUM algorithm improves the network utility by 17% compared to a non-cooperation benchmark.

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.

We introduce the concept of a fresh data market, in which a destination user requests, and pays for, fresh data updates from a source provider. Data freshness is captured by the age of information (AoI) metric, defined as the time elapsed since the latest update has reached the destination. The source incurs an operational cost, modeled as an increasing convex function of the number of updates. The destination incurs an age-related cost, modeled as an increasing convex function of the AoI. The source charges the destination for each update and designs a pricing mechanism to maximize its profit; the destination on the other hand chooses a data update schedule to minimize the summation of its payments to the source and its age-related cost. The interaction among the source and destination is hence game-theoretic. Motivated by the existing pricing literature, we first study a time-dependent pricing scheme, in which the price for each update depends on when it is requested. We show in this case that the game equilibrium leads to only one data update, which does not yield the maximum profit to the source. This motivates us to consider a quantity-based pricing scheme, in which the price of each update depends on how many updates have been previously requested. We show that among all pricing schemes in which the price of an update may vary according to both time and quantity, the quantity-based pricing scheme performs best: it maximizes the source's profit and minimizes the social cost of the system, defined as the aggregate source's operational cost and the destination's age-related cost. Numerical results show that the optimal quantity-based pricing can be 27% more profitable for the source and incurs 54% less social cost, compared with the optimal time-dependent pricing.

Data quality, or sometimes referred to as data credibility, is a critical issue in mobile crowd sensing (MCS) and more generally Internet of Things (IoT). While candidate solutions, such as incentive mechanisms and data mining have been well explored in the literature, the power of crowds has been largely overlooked or under-exploited. In this paper, we propose a cross validation approach which seeks a validating crowd to ratify the contributing crowd in terms of the sensor data contributed by the latter, and uses the validation result to reshape data into a more credible posterior belief of the ground truth. This approach consists of a framework and a mechanism, where the framework outlines a four-step procedure and the mechanism implements it with specific technical components, including a weighted random oversampling (WRoS) technique and a privacy-aware trust-oriented probabilistic push (PATOP2) algorithm. Unlike most prior work, our proposed approach augments rather than redesigning existing MCS systems, and requires minimal effort from the crowd, making it conducive to practical adoption. We evaluate our proposed mechanism using a real-world MCS IoT dataset and demonstrate remarkable (up to 475%) improvement of data quality. In particular, it offers a unified solution to reconciling two disparate needs: reinforcing obscure (weakly recognizable) ground truths and discovering hidden (unrecognized) ground truths.

In multimedia crowdsourcing, the requester's quality requirements and reward decisions will affect the workers' task selection strategies and the quality of their multimedia contributions. In this paper, we present a first study on how the workers' bounded cognitive rationality interacts with and affects the decisions and performance of a multimedia crowdsourcing system. Specifically, we consider a two-stage model, where a requester first determines the reward and the quality requirement for each task, and the workers select the tasks to accomplish accordingly. First, we consider the benchmark case where users are fully rational, and derive the requester's optimal rewards and quality requirements for the tasks. Furthermore, we focus on the more practical bounded rational case by modeling the workers' task selection behaviors using the cognitive hierarchy theory. Comparing with the fully rational benchmark, we show that the requester can increase her profit by taking advantage of the workers' bounded cognitive rationality, especially when the workers' population is large or the workers' average cognitive level is low. When the workers' average cognitive level is very high, however, the equilibrium under the practical bounded rational model converges to that under the benchmark fully rational model. It is because the workers at different levels make decisions sequentially and high cognitive level workers can accurately predict other users' strategies. Under both the fully and bounded rational models, we show that if workers are heterogeneous but one type of workers (either the high or the low quality) dominates the platform, the requester cannot make a higher profit by setting different quality requirements for different tasks.

Network sharing has become a key feature of various enablers of the next-generation network, such as network function virtualization and fog computing architectures. Network utility maximization (NUM) is a general framework for achieving fair, efficient, and cost-effective sharing of constrained network resources. When agents have asymmetric and private information, however, a fundamental economic challenge is how to solve the NUM problem considering the self-interests of strategic agents. Many previous related works have proposed economic mechanisms that can cope with agents' private utilities. However, the network sharing paradigm introduces the issue of information asymmetries regarding constraints. The related literature largely neglected such an issue; limited closely related studies provided solutions only applicable to specific application scenarios. To tackle these issues, we propose the Decomposable NUM (DeNUM) mechanism and the Dynamic DeNUM (DyDeNUM) mechanism, the first mechanisms in the literature for solving NUM problems considering private utility and constraint information. The key idea of both mechanisms is to decentralize the decision process to agents, who will make resource allocation decisions without the need of revealing private information to others. Under a monitorable influence assumption, the DeNUM mechanism yields the network-utility maximizing solution at an equilibrium and achieves other desirable economic properties (such as individual rationality and budget balance). We further establish the connection between the equilibrium structure and the primal-dual solution to a related optimization problem, based on which we prove the convergence of the DeNUM algorithm to an equilibrium. When the agents' influences are not monitorable, we propose the DyDeNUM mechanism that yields the network-utility maximizing solution at the cost of the balanced budget. Finally, as a case study, we apply the proposed mechanisms to solving the NUM problem for a fog-based user-provided network and show that both mechanisms improve the network utility by 34% compared to a non-cooperation benchmark.

Adaptive bitrate streaming enables video users toadapttheir playing bitrates to the real-time network conditions, hence achieving the desirable quality-of-experience (QoE). In a multi-user wireless scenario, however, existing single-user based bitrate adaptation methods may fail to provide the desirable QoE, due to lack of consideration of multi-user interactions (such as the multi-user interferences and network congestion). In this work, we propose a novel user cooperation framework based onuser-provided networkingfor multi-user mobile video streaming over wireless cellular networks. The framework enables nearby mobile video users to crowdsource their cellular links and resources for cooperative video streaming. We first analyze the social welfare performance bound of the proposed cooperative streaming system by introducing a virtual time-slotted system. Then, we design a low complexity Lyapunov-based online algorithm, which can be implemented in an online and distributed manner without the complete future and global network information. Numerical results show that the proposed online algorithm achieves an average 97 percent of the theoretical maximum social welfare. We further conduct experiments with real data traces, to compare our proposed online algorithm with the existing online algorithms in the literature. Experiment results show that our algorithm outperforms the existing algorithms in terms of both the achievable bitrate (with an average gain of 20$\sim$30 percent) and social welfare (with an average gain of 10$\sim$50 percent).

Recently, the mobile network operators (MNOs) are exploring more time flexibility with the rollover data plan, which allows the unused data from the previous month to be used in the current month. Motivated by this industry trend, we propose a general framework for designing and optimizing the mobile data plan with time flexibility. Such a framework includes the traditional data plan, two existing rollover data plans, and a new credit data plan as special cases. Under this framework, we formulate a monopoly MNO's optimal data plan design as a three-stage Stackelberg game: In Stage I, the MNO decides the data mechanism. In Stage II, the MNO further decides the corresponding data cap, subscription fee, and the per-unit fee. Finally, in Stage III, users make subscription decisions based on their own characteristics. Through backward induction, we analytically characterize the MNO's profit-maximizing data plan and the corresponding users' subscriptions. Furthermore, we conduct a market survey to estimate the distribution of users' two-dimensional characteristics, and evaluate the performance of different data mechanisms using the real data. We find that a more time-flexible data mechanism increases MNO's profit and users' payoffs, hence improves the social welfare.

Mobile collaborative Internet access (MCA) enables mobile users to share their Internet through flexible tethering arrangements. This can potentially make better use of network resources. However, from a mobile network operator's (MNO's) viewpoint, it can either reduce revenue or increase congestion, and thus has been blocked by some MNOs in practice. We propose a hybrid pricing framework for MNOs who charge users separately for access and tethering. This scheme serves to coordinate the tethering decisions of mobile users with MNO network management objectives. We analyze the MNOs' equilibrium pricing strategies in both cooperative and competitive scenarios. In the cooperative scenario, at the equilibrium, each user's cost is independent of any chosen tethering links. We then characterize the optimal hybrid pricing strategies of MNOs in this scenario. For the competitive scenario, we formulate the MNOs' competitive interactions as a pricing game, and we show that MNO competition leads to equalized prices for users if an equilibrium exists but does not guarantee its existence. Both insights motivate a quantity competition game, which is shown to guarantee equilibrium. Simulation results show that in scenarios of interest the proposed hybrid pricing schemes can double both MNOs' profit and users' payoff and such improvements increase with the degree of network heterogeneity.

Previous studies in crowdsourcing systems usually regard workers as fully rational players, who have infinite cognitive capabilities when reasoning about other players' decisions. However, recent psychological studies have revealed that humans are often bounded rational with cognitive reasoning limits. In this paper, we present a first study regarding the impact of such worker bounded rationality in a crowdsourcing system, and characterize how the result obtained from this more practical assumption deviates from the fully rational benchmark. Specifically, we consider a simple two-stage crowdsourcing model, where a requester first determines the rewards for workers completing the tasks, and then workers make their task choices accordingly. First, we show that such a model is non-trivial to analyze even in the fully rational case, due to the integer constraints on workers' choices. Nevertheless, we are able to characterize the closed-form solution of the optimal rewards and Nash equilibrium with full rationality by exploiting the special structure of the problem formulation. Next, we focus on the more practical bounded rational model, and apply the cognitive hierarchy theory from behavioral economics in the modeling of workers' decisions. Comparing with the fully rational benchmark, we show that in practice the requester can receive a higher profit when considering the workers' bounded rationality, especially when the number of workers is large or the workers' average cognitive level is low. When the workers' average cognitive level is high enough, however, the practical bounded rational model converges to the benchmark fully rational model.

Many mobile applications (abbrev. apps) reward the users who physically visit some locations tagged as POIs (places-of-interest) by the apps. In this paper, we study the POI-based collaboration between apps and venues (e.g., restaurants and cafes). On the one hand, an app charges a venue and tags the venue as a POI, which attracts users to visit the venue and potentially increases the venue's sales. On the other hand, the venue can invest in the app-related infrastructure (e.g., Wi-Fi networks and smartphone chargers), which enhances the users' experience of using the app. However, the existing POI pricing schemes of the apps (e.g., Pokemon Go and Snapchat) cannot incentivize the venue's infrastructure investment, and hence cannot achieve the most effective app-venue collaboration. We model the interactions among an app, a venue, and users by a three-stage Stackelberg game, and design an optimal two-part pricing scheme for the app. This scheme has a charge-with-subsidy structure: the app first charges the venue for becoming a POI, and then subsidizes the venue every time a user interacts with the POI. Compared with the existing pricing schemes, our two-part pricing better incentivizes the venue's investment, attracts more users to interact with the POI, and achieves a much larger app revenue. We analyze the impacts of the app's and venue's characteristics on the app's optimal revenrevenueue, and show that the apps with small and large congestion effects should collaborate with opposite types of venues.

We study a privacy-preserving data collection problem, by jointly considering data reporters' data correlation and social relationship. A data collector gathers data from individuals to perform a certain analysis with a privacy-preserving mechanism. Due to data correlation, the data analysis based on the reported data can cause privacy leakage to other individuals (even if they do not report data). The data reporters will take such a privacy threat into account, owing to the social relationship among individuals. This motivates us to formulate a two-stage Stackelberg game: In Stage I, the data collector selects some individuals as data reporters and designs a privacy-preserving mechanism for a sum query analysis. In Stage II, the selected data reporters contribute their data with possible perturbations (through adding noise). By analyzing the data reporters' equilibrium decisions in Stage II, we show that given any fixed reporter set, only one data reporter with the most significant joint consideration of the social relationship and data correlation may add noise to his reported data. The rest of the data reporters will truthfully report their data. In Stage I, we derive the data collector's optimal privacy-preserving mechanism and propose an efficient algorithm to select the data reporters. We conclude that the data collector should jointly capture the impact of data correlation and social relation to ensure all data reporters truthfully reporting their data. We conduct extensive simulations based on random network and real-world social data to investigate the impact of data correlation and social network on the system. We find that the availability of social network information is more critical to the data collector compared with data correlation information.

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.

Mobile network operators (MNOs) have been offering mobile data plans with different data caps and subscription fees as an effective way of achieving price discrimination and improving revenue. Recently, some MNOs are investigating innovative data plans with time flexibility based on the multi-cap scheme. The rollover data plan and the credit data plan are such innovative data plans with time flexibility. In this paper, we study how the MNO optimizes its multi-cap data plan with time flexibility in the realistic asymmetric information scenario, where each user is associated with multidimensional private information, i.e., the data valuation and the network substitutability. Specifically, we consider a multi-dimensional contract-theoretic approach, and analyze the optimal data caps and the subscription fees design systematically. We find that each user's willingness-to-pay for a particular data cap can be captured by the slope of his indifference curve on the contract plane, and the feasible contract (satisfying the incentive compatibility and individual rationality conditions) will allocate larger data caps for users with higher willingness-to-pay. Furthermore, we conduct a market survey to estimate the statistical distribution of users' private information, and examine the performance of our proposed multi-dimensional contract design using the empirical data. Numerical results further reveal that the optimal contract may provide price discounts (i.e., negative subscription fees) to attract low valuation users to select a small-cap (possibly zero-cap) contract item. A data mechanism with better time flexibility brings users higher payoffs and the MNO more profit, hence increases the social welfare.

Today, many mobile network operators (MNOs) provide data services through a three-part tariff data plan, which involves a fixed subscription fee, a data cap, and a per-unit fee for the data over-usage exceeding the data cap. To increase their market competitiveness, MNOs have been trying to provide more time flexibility in the data plans. One of such innovations is the rollover data plan, which allows a subscriber to use the unused data of the previous month in the current month. Depending on the consumption priority of the rollover data, different rollover data plans can have different levels of time flexibility. The interactions among multiple MNOs offering rollover data plans, however, are quite complicated and sometimes counter-intuitive. To examine this issue, in this paper we build a simple market model of two MNOs competing to serve the same pool of heterogeneous users. We formulate the market competition as a two-stage game: in Stage I, the MNOs simultaneously decide their pricing strategies of their chosen data mechanisms; In Stage II, users make their subscription decisions among the two MNOs. We characterize the sub-game perfect equilibrium (SPE) of the two-stage game through backward induction. Comparing with a monopoly market where a better time flexibility always improves the MNO's profit, our analysis reveals a rather complicated story in the duopoly market: (i) with a mild competition, the stronger MNO will increase both MNOs' profits by adopting a data plan with a better time flexibility, while the weaker MNO will decrease both MNOs' profits by adopting a data plan with a better time flexibility; (ii) with a fierce competition, any MNO will increase its profit and decrease the competitor's profit by adopting a data plan with a better time flexibility.

Wireless power transfer (WPT) technology enables a cost-effective and sustainable energy supply in wireless networks, where energy users (EUs) can remotely harvest energy from the wireless signal transmitted by energy transmitters (ETs). However, the broadcast nature of wireless signal makes wireless power a non-excludable public good, which renders the traditional market mechanisms inefficient due to the possibility of the free-riders. In this study, we formulate the transmit power provision problem in a single-channel WPT network as a public good provision problem, aiming to maximize the social welfare of all the ET and EUs considering their private information and selfish behaviors. The considered problem also brings both economic and technical challenges in ensuring voluntary participation and distributed algorithm design. To this end, we propose a two- phase all-or-none procedure involving a low-complexity Power And Taxation (PAT) Nash mechanism, which ensures voluntary participation, incentive compatibility, and budget balance, and yields the socially optimal transmit power at all Nash equilibria. We further propose a distributed D-PAT Algorithm and prove its convergence by exploiting the connection between the structure of Nash equilibria and that of the optimal solutions to a related optimization problem. Finally, our simulation results validate the PAT Mechanism and the practical algorithm. We show that our design can significantly improve the social welfare compared to the benchmark market mechanism, especially when there are many and relatively comparable EUs.

Tactile Internet often requires: 1) the ultra-reliable and ultra-responsive network connection and 2) the proactive and intelligent actuation at edge devices. A promising approach to address these requirements is to enable mobile edge devices to share their communication, computation, and caching (3C) resources via device-to-device connections. In this paper, we propose a general 3C resource sharing framework, which includes many existing 1C/2C sharing models in the literature as special cases. Comparing with the 1C/2C models, the proposed 3C framework can further improve the resource utilization efficiency by offering more flexibilities in terms of the device cooperation and resource scheduling. As a typical example, we focus on the energy utilization under the proposed 3C framework. Specifically, we formulate an energy consumption minimization problem, which is an integer non-convex optimization problem. To solve the problem, we first transform it into an equivalent integer linear programming problem that is much easier to solve. Then, we propose a heuristic algorithm based on linear programming, which can further reduce the computation time and produce an empirically close-to-optimal solution. Moreover, we evaluate the energy reduction due to the 3C sharing both analytically and numerically. Numerical results show that, comparing with the existing 1C/2C approaches, the proposed 3C sharing framework can reduce the total energy consumption by 83.8% when the D2D energy is negligible. The energy reduction is still 27.5% when the D2D transmission energy per unit time is twice as large as the cellular transmission energy per unit time.

In a delay-sensitive mobile crowdsensing (MCS) platform, a service provider offers monetary incentives to mobile users for participating in the data collection and reporting their obtained data by a deadline. One aspect missing from most prior literature in the incentive mechanism design is the consideration of the detailed data reporting process through cellular or Wi-Fi networks. In this paper, we consider the interactions between the service provider and the users in two stages. First, the service provider chooses a reward to maximize its expected profit under the incomplete information of the users' responses. Next, given the reward, each user makes his participation and reporting decisions, which are complicated due to his mobility and network heterogeneity. We propose an algorithm to compute the optimal user's decisions under the general setting using dynamic programming, and derive closed-form decision criteria for the special yet practical case of a non-discounted reward. We compute the optimal reward by characterizing the solution set and the discontinuity in the profit function. Simulation results show that our proposed algorithm achieves a significant gain in the user payoff over three benchmark heuristic schemes. In addition, a service provider's profit is sensitive to the estimation of the users' Wi-Fi availabilities.

Mobile crowdsensing (MCS) is a novel and appealing sensing paradigm that leverages the diverse embedded sensors of massive mobile devices to collect different kinds of data. One of the key challenges in MCS is to efficiently schedule mobile device users to perform different sensing tasks. Prior effort to this problem mainly focused on the interaction between the task-layer and the user-layer, without considering the similar data requirements of tasks and the heterogeneous sensing capabilities of users. In this work, we introduce a new data-layer between tasks and users, and propose a three-layer data-centric MCS framework, which enables different tasks to reveal their common data requirements and hence reuse the common data items. We focus on studying the joint task selection and user scheduling problem under this new framework, aiming at maximizing the social welfare. Specifically, we first analyze theoretical performance gain due to data reuse in the ideal scenario with complete information. We then consider the practical scenario with private information of both tasks and users, and propose a two-sided randomized auction mechanism, which is computationally efficient, individually rational, incentive compatible (truthful) in expectation, and close-to-optimal. We further show that the proposed randomized auction may not be budget balanced, and hence introduce a reserve price into the auction to achieve the desired budget balance at the cost of certain welfare loss. Simulation results show that with data reuse, the social welfare achieved in the proposed randomized auction can be increased from 270 up to 4,500 percent, comparing with those without data reuse.

Mobile crowdsensing (MCS) is a new paradigm of sensing by taking advantage of the rich embedded sensors of mobile user devices. However, the traditional server-client MCS architecture often suffers from the high operational cost on the centralized server (e.g., for storing and processing massive data), hence the poor scalability. Peer-to-peer (P2P) data sharing can effectively reduce the server's cost by leveraging the user devices' computation and storage resources. In this work, we propose a novel P2P-based MCS architecture, where the sensing data is saved and processed in user devices locally and shared among users in a P2P manner. To provide necessary incentives for users in such a system, we propose a quality-aware data sharing market, where the users who sense data can sell data to others who request data but not want to sense the data by themselves. We analyze the user behavior dynamics from the game-theoretic perspective, and characterize the existence and uniqueness of the game equilibrium. We further propose best response iterative algorithms to reach the equilibrium with provable convergence. Our simulations show that the P2P data sharing can greatly improve the social welfare, especially in the model with a high transmission cost and a low trading price.

The rapid growth of mobile traffic has heavily overloaded the cellular networks, making it increasingly desirable to offload mobile users' (MUs') traffic to small-cell networks. In this paper, we study the MUs' optimal uplink traffic offloading scheme based on the new paradigm of small-cell dual-connectivity (DC). Through DC, an MU can flexibly schedule its traffic between a macro-cell base station (BS) and a small-cell access point (AP) via two different radio interfaces. To optimize the overall network radio resource usage, we jointly optimize the BS' bandwidth allocation as well as the MUs' traffic scheduling and power allocation. Specifically, for reducing the bandwidth usage, the BS prefers to allocate the MUs small amount of bandwidth to encourage the MUs to utilize the small-cell networks. However, excessive traffic offloading can lead to severe interferences among MUs, which increase the MUs' power consumption. Hence, our joint optimization strikes a proper balance between these two aspects. Despite the non-convexity of the proposed joint optimization problem, we propose an efficient algorithm to compute the optimal offloading solution. The key idea is to exploit the layered-structure of the joint optimization problem, and decompose it into the BS' bandwidth allocation problem (on the top-level) and the MUs' traffic scheduling and power allocation problem (as a subproblem). Such a decomposition enables us to exploit the hidden convexity of the MUs' problem and the monotonic structure of the BS' problem for an effective algorithm design. Numerical results show that our proposed algorithm can achieve the global optimum solution with significantly reduced computational time. Moreover, the proposed traffic offloading scheme can significantly reduce the overall system cost, in comparison with using the fixed bandwidth allocation or traffic scheduling schemes.

It is well known that a game equilibrium can be far from efficient or fair, due to the misalignment between individual and social objectives. The focus of this paper is to design a new mechanism framework that induces an efficient and fair equilibrium in a general class of games. To achieve this goal, we propose a taxation framework, which first imposes a tax on each player based on the perceived payoff (income), and then redistributes the collected tax to other players properly. By turning the tax rate, this framework spans the continuum space between strategic interactions (of selfish players) and altruistic interactions (of unselfish players), hence provides rich modelling possibilities. The key challenge in the design of this framework is the proper taxing rule (i.e., the tax exemption and tax rate) that induces the desired equilibrium in a wide range of games. First, we propose a flat tax rate (i.e., a single tax rate for all players), which is necessary and sufficient for achieving an efficient equilibrium in any static strategic game with common knowledge. Then, we provide several tax exemption rules that achieve some typical fairness criterions (such as the Max-min fairness) at the equilibrium. We further illustrate the implementation of the proposed taxation framework in the game of Prisoners' Dilemma.

We study a mechanism design problem of privacy- preserving data collection with privacy protection uncertainty. A data collector wants to collect enough data to perform a certain computation that benefits the individuals who contribute the data, with the possibility of individual privacy leakage. The data collector adopts a privacy-preserving mechanism by adding some random noise to the computation result, which reduces the accuracy of the computation. Individuals decide whether to contribute data based on the potential benefit and the possible privacy cost induced by the mechanism. Due to the intrinsic uncertainty involved in privacy protection, we model individuals' privacy-aware participation using the prospect theory, which more accurately models individuals' behavior under uncertainty than the traditional expected utility theory. We show that the data collector's utility maximization problem involves a polynomial of high and fractional order, which is difficult to solve analytically. We get around this issue by proposing an approximation method, which allows us to obtain a closed form unique solution of the data collector's decision problem. We numerically show that the approximation error is small when the number of individuals is large. By comparing with the results under the expected utility theory, we conclude that a data collector who considers the more realistic prospect theory modeling should adopt a stricter privacy-preserving mechanism to boost her utility.

Today's mobile devices are capable of tackling various complicated tasks that may require a large amount of communication, computation, and caching (3C) resources. Due to users' heterogeneous resources and service requirements, it is challenging for each user to always accomplish his task satisfactorily. To alleviate this issue, mobile users can exploit the heterogeneity and crowdsource their resources to enhance the task execution performance. In this paper, we propose a general 3C framework that enables mobile users to share all three types of resources through device- to-device connections. Such a framework generalizes many existing 1C/2C resource sharing models (that only shares one or two types of resources among users). To quantify the benefit of the proposed framework, we focus on an energy minimization problem, and show that the 3C framework always achieves a smaller total energy consumption, comparing with other 1C/2C models. Furthermore, we show that the energy reduction is maximized, when user connection probability and content caching ratio are neither too large nor too small. Our numerical results show that, when ignoring device-to-device transmission energy, the general 3C framework can reduce the total energy consumption by 82.98%, comparing with the 1C/2C models.

This paper develops a novel business model to enable virtual storage sharing among a group of users. Specifically, an aggregator owns a central physical storage unit and virtualizes the physical storage into separable virtual storage capacities that can be sold to users. Each user purchases the virtual storage capacity, and schedules the charge and discharge of the virtual storage to reduce his peak power consumption. We formulate the interaction between the aggregator and users in each operation horizon as a two-stage problem. At the beginning of the operation horizon, the aggregator first determines the unit price of virtual storage capacity to maximize her profit in Stage 1, and users decide the capacities to purchase and the storage scheduling during the operation horizon in Stage 2. Since the closed-form solution is not available and the decisions are coupled across the two stages, we characterize the solutions of the two-stage problem based on parametric linear programming. Simulation results show that compared to the case where each user acquires his own physical storage, storage virtualization reduces the overall physical capacity needed for all users by 34.9%, and the overall physical power rating by 45.1%.

In a mobile crowdsensing (MCS) application, user diversity and social effect are two important phenomena that determine its profitability, where the former improves the sensing quality, while the latter incentives the users' participation. In this paper, we consider a reward mechanism design for the service provider to achieve diversity in the collected data by exploiting the users' social relationship. Specifically, we formulate a two-stage decision problem, where the service provider first optimizes its rewards for profit maximization. The users then decide their effort levels through social network interactions as a participation game. The analysis is particularly challenging due to the users' interplay in both the diversity and social graphs, which leads to a non-convex bilevel optimization problem. Surprisingly, we find that the service provider can focus on one superimposed graph that incorporates the diversity and social relationship and compute the optimal reward as the Katz centrality in closed-form. Simulation results, based on the random graph and a real Facebook trace, show that the availability of network information improves both the service provider's profit and the users' social surplus over the incomplete information cases.

Crowdsourced mobile video streaming enables nearby mobile video users to aggregate their network resources to improve the video streaming performance. However, users are often selfish and may not be willing to cooperate without proper incentives. Designing an incentive mechanism for such a scenario is challenging due to the users' asynchronous downloading behaviors as well as their private valuations for multi-bitrate encoded videos. In this work, we propose a multi-object multi-dimensional auction-based incentive framework, through which users can download multiple video segments with different bitrates for multiple nearby users (and themselves). Based on this incentive framework, we propose a Vickrey-score auction, which is the first multi-object multi-dimensional auction that achieves both truthfulness and efficiency. Simulations with real traces show that crowdsourced mobile streaming outperforms noncooperative streaming by 48.6% (on average) in terms of social welfare. We further implement our proposed auction mechanism in a demostration system, and show that the crowdsourced framework together with the auction mechanism can substantially increase mobile user's welfare and video service stability.

Mobile Crowdsourced Access (MCA) enables mobile users (MUs) to share their Internet connections by serving as tethers to other MUs, hence can improve the quality of service of MUs as well as the overall utilization of network resources. However, MCA can also reduce the revenue-generating mobile traffic and increase the network congestion for mobile network operators (MNOs), and thus has been blocked by some MNOs in practice. In this work, we reconcile the conflicting objectives of MNOs and MUs by introducing a pricing framework for MCA, where the direct traffic and tethering traffic are charged independently according to a data price and a tethering price, respectively. We derive the optimal data and tethering prices systematically for MUs with the α-fair utility in two scenarios with cooperative and competitive MNOs, respectively. We show that the optimal tethering prices are zero and the optimal usage-based data prices are identical for all MUs, in both the cooperative and competitive scenarios. Such optimal pricing schemes will lead to mutually beneficial results for MNOs and MUs. Our simulation results show that the proposed pricing scheme approximately triples both the MNOs' profit and the MUs' payoff when the MNOs cooperate, comparing to the case where MCA is blocked. Moreover, competition among MNOs will decrease MNOs' profit and further increase the MUs' payoff.

Rollover data plans are attractive to mobile users by allowing them to keep their unused data for future use, and hence has been widely implemented by Mobile Network Operators (MNOs) around the world. In this work, we formulate a three-stage Stackelberg game to analyze the interactions between an MNO and its subscribed users under both traditional and rollover data plans. Specifically, in Stage I, the MNO decides which data plan(s) to implement; In Stage II, the MNO decides the price(s) of the data plan(s) to maximize its expected revenue; In Stage III, users make their individual subscription decisions to maximize their expected payoffs. Our analysis shows that in general, high evaluation users are more likely to choose the rollover data plan than medium evaluation users. More precisely, as the network substitutability increases, high evaluation users tend to choose the rollover data plan, while medium evaluation users tend to choose the traditional data plan. We further prove that the MNO can achieve the maximum revenue by only providing the rollover data plan (without bundling with the traditional data plan). Numerical results show that the rollover data plan can increase not only the MNO's revenue but also the users' payoffs (and hence the social welfare) comparing with the traditional data plan. We also compare two rollover data plans that differ in whether the rollover data is consumed prior to monthly data cap, and show that allowing the rollover data to be consumed before the monthly data cap is more beneficial to both users and the MNO.

To exploit users' heterogeneous data demands, several mobile network operators worldwide have launched the mobile data trading markets, where users can trade mobile data quota with each other. In this work, we aim to understand the users' optimal trading decisions and the operator's revenue maximizing strategy. We model the interactions between the mobile operator and the users as a two-stage Stackelberg game. In Stage I, the operator chooses the operation fee imposed on sellers to maximize its revenue. In Stage II, each user decides whether to be a seller or a buyer and optimizes the corresponding trading price and quantity. We derive the closed-form expression of the unique Nash equilibrium (NE) in Stage II in closed-form, and prove that the users' decisions can converge to the NE through distributed best response updates. We show that at the NE, different types of sellers and buyers should propose the same price such that the total demand matches the total supply. We further show that the Stage I operation fee optimization problem is convex, and derive the optimal operation fee in closed-form. Our analysis and numerical results show that the users who have less uncertainty of their data usages can benefit more from data trading. We also show that an operation fee that is too high hurts both the users' payoffs and the operator's revenue.

Intelligent network selection plays an important role in achieving an effective data offloading in the integrated cellular and Wi-Fi networks. However, previously proposed network selection schemes mainly focused on offloading as much data traffic to Wi-Fi as possible, without systematically considering the Wi-Fi network congestion and the ping-pong effect, both of which may lead to a poor overall user quality of experience. Thus, in this paper, we study a more practical network selection problem by considering both the impacts of the network congestion and switching penalties. More specifically, we formulate the users' interactions as a Bayesian network selection game (NSG) under the incomplete information of the users' mobilities. We prove that it is a Bayesian potential game and show the existence of a pure Bayesian-Nash equilibrium that can be easily reached. We then propose a distributed network selection (DNS) algorithm based on the network congestion statistics obtained from the operator. Furthermore, we show that computing the optimal centralized network allocation is an NP-hard problem, which further justifies our distributed approach. Simulation results show that the DNS algorithm achieves the highest user utility and a good fairness among users, as compared with the on-the-spot offloading and cellular-only benchmark schemes.

Next-generation networks will be characterized by three key features:heterogeneity, in terms of technologies and services,dynamics, in terms of rapidly varying environments and uncertainty, andsize, in terms of the numbers of users, nodes, and services. The emergence of such large-scale and decentralized heterogeneous networks operating under dynamic and uncertain environments imposes new challenges in the design, analysis, and optimization of networks. The past decade has witnessed a confluence among the disciplines of networks, games, and economics, which has necessitated novel mathematical tools and designs that can truly remove the boundaries between these disciplines. In this context, advancing game-theoretic models and tailoring them towards the optimization and operation of future networked systems become pressing needs for our research community. The main goal of this IEEE JSAC Special Issue on “Game Theory for Networks” is to collect cutting-edge contributions that address and show the latest developments in game-theoretic models for emerging networking applications. The response of the community to the call has been overwhelming. We received a total of 120 submissions. We want to thank all the authors who submitted their works to this Special Issue. After a strict and selective review process, we accepted 40 papers and decided to publish two issues. Papers were selected based on their appropriateness for and relevance to the Special Issue as well as their technical merits. Unfortunately, a number of interesting papers did not make the cut because of the criteria set forth above and also due to the constraints on the total page count in a JSAC Special Issue. We hope that such interesting papers will find other venues for publication.

This is the second part of the IEEE JSAC Special Issue on “Game Theory for Networks.” The response of the community to the call has been overwhelming. We received a total of 120 submissions. We want to thank all the authors who submitted their works to this Special Issue. After a strict and selective review process, we accepted 40 papers and decided to publish two issues, each of 20 papers. The first one was published in February 2017. The papers of this second issue cover a wide selection of topics as follows.

Motivated by the recently launched mobile data trading markets (e.g., China Mobile Hong Kong's 2nd exChange Market), in this paper, the mobile data trading problem is studied under future data demand uncertainty. A brokerage-based market is introduced, in which sellers and buyers propose their selling and buying quantities, respectively, to the trading platform that matches the market supply and demand. To understand the users' realistic trading behaviors, a prospect theory (PT) model from behavioral economics is proposed, which includes the widely adopted expected utility theory (EUT) as a special case. Although the PT modeling leads to a challenging non-convex optimization problem, the optimal solution can be characterized by exploiting the unimodal structure of the objective function. Building upon this analysis, an algorithm is designed to help estimate the users' risk preference and provide trading recommendations dynamically, considering the latest market and usage information. It is shown via simulations that the risk preferences have a significant impact on a user's decision and outcome: a risk-averse dominant user can guarantee a higher minimum profit in the trading, while a risk-seeking dominant user can achieve a higher maximum profit. By comparing with the EUT benchmark, it is shown that a PT user with a low reference point is more willing to buy mobile data. Moreover, compared with an EUT user, a PT user is more willing to buy mobile data when the probability of large data demand is low.

Motivated by the recent efforts in extending long term evolution (LTE) to the unlicensed spectrum, we propose a novel spectrum sharing framework for the coopetition (i.e., cooperation and competition) between LTE and Wi-Fi in the unlicensed band. Basically, the LTE network can choose to work in one of the two modes: in the competition mode, it randomly accesses an unlicensed channel, and interferes with the Wi-Fi access point using the same channel; in the cooperation mode, it onloads the Wi-Fi users' traffic in exchange for the exclusive access of the corresponding channel. We design a second-price reverse auction mechanism, which enables the LTE provider and the Wi-Fi access point owners (APOs) to effectively negotiate the operation mode. Specifically, the LTE provider is the auctioneer (buyer), and the APOs are the bidders (sellers) who compete to sell the rights of onloading the APOs' traffic to the LTE provider. In Stage I of the auction, the LTE provider announces a reserve rate, which is the maximum data rate that it is willing to allocate to the APOs in the cooperation mode. In Stage II of the auction, the APOs submit their bids, which indicate the data rates that they would like the LTE provider to offer in the cooperation mode. We show that the auction involves allocative externalities, i.e., the cooperation between the LTE provider and one APO benefits other APOs who are not directly involved in this cooperation. We characterize the APOs' unique equilibrium bidding strategies in Stage II, and analyze the LTE provider's optimal reserve rate in Stage I. Numerical results show that our framework improves the payoffs of both the LTE provider and the APOs comparing with a benchmark scheme. In particular, our framework increases the LTE provider's payoff by 70% on average, when the LTE provider has a large throughput and a small data rate discounting factor. Moreover, our framework leads to a close-to-optimal social welfare under a large LTE throughput.

Dynamic spectrum access (DSA) can effectively improve the spectrum efficiency and alleviate the spectrum scarcity, by allowing unlicensed secondary users (SUs) to access the licensed spectrum of primary users (PUs) opportunistically. Cooperative spectrum sharing is a new promising paradigm to provide necessary incentives for both PUs and SUs in dynamic spectrum access. The key idea is that SUs relay the traffic of PUs in exchange for the access time on the PUs' licensed spectrum. In this paper, we formulate the cooperative spectrum sharing between multiple PUs and multiple SUs as a two-sided market, and study the market equilibrium under both complete and incomplete information. First, we characterize the sufficient and necessary conditions for the market equilibrium. We analytically show that there may exist multiple market equilibria, among which there is always a unique Pareto-optimal equilibrium for PUs (called PU-Optimal-EQ), in which everyPU achieves a utility no worse than in any other equilibrium. Then, we show that under complete information, the unique Pareto-optimal equilibrium PU-Optimal-EQ can always be achieved despite the competition among PUs; whereas, under incomplete information, the PU-Optimal-EQ may not be achieved due to the mis-representations of SUs (in reporting their private information). Regarding this, we further study the worse-case equilibrium for PUs, and characterize a Robustequilibrium for PUs (called PU-Robust-EQ), which provides every PU a guaranteed utility under all possible mis-representation behaviors of SUs. Numerical results show that in a typical network where the number of PUs and SUs are different, the performance gap between PU-Optimal-EQ and PU-Robust-EQ is quite small (e.g., less than 10 percent in the simulations).

Wireless interference management through continuous power control has been extensively studied in the literature. However, practical systems often adopt discrete power control with a limited number of power levels and MCSs (Modulation Coding Schemes). In general, discrete power control is NP-hard due to its combinatorial nature. To tackle this challenge, we propose an innovative approach of interference management: ARM (Anonymous Rating Mechanism). Inspired by the successes of the simple anonymous rating mechanism in E-commerce, we develop ARM as distributed near-optimal algorithm for solving the discrete power control problem (i.e., the joint scheduling, power allocation, and modulation coding adaption problem) under the physical interference model. We show that ARM achieves a close-to-optimal network throughput with a low control overhead. We also characterize the performance gap of ARM with the theoretical optimal solution due to the loss of rating information, and study the trade-off between such gap and the convergence time of ARM. We present numerical results with practical parameter choices to validate the theoretical findings, and highlight the impacts of approximation factor, the number of power levels, and the incomplete rating information.

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.

Mobile data offloading can help the mobile network operator (MNO) cope with the explosive growth of cellular traffic, by delivering mobile traffic through third-party access points. However, the access point owners (APOs) would need proper incentives to participate in data offloading. In this paper, we consider a data offloading market that includes both price-taking and price-setting APOs. We formulate the interactions among the MNO and these two types of APOs as a three-stage Stackelberg game, and study the MNO's profit maximization problem. Due to a non-convex strategy space, it is in general a non-convex game. Nevertheless, we transform the strategy space into a convex set and prove that a unique subgame perfect equilibrium exists. We further propose iterative algorithms for the MNO and price-setting APOs to obtain the equilibrium. Employing the proposed algorithms, the APOs do not need to obtain full information about the MNO and other APOs. Through numerical studies, we show that the MNO's profit can increase up to three times comparing with the no-offloading case. Furthermore, our proposed incentive mechanism outperforms an existing algorithm by 18 percent in terms of the MNO's profit. Results further show that price competition among price-setting APOs drives the equilibrium market prices down.

In this paper, we investigate the cooperative traffic offloading among mobiles devices (MDs) which are interested in receiving a common content from a cellular base station (BS). For offloading traffic, the BS first sends the content to some selected MDs which then broadcast the received data to the other MDs, such that each MD can receive the entire content simultaneously. Due to each MD's limited transmit-power and energy budget, the transmission rate of the content should be properly designed, since it strongly influences whether and how long each MD can perform relaying. Therefore, different from most existing MDs cooperative schemes, we focus on a novel joint optimization of the content transmission rate and each MD's relay-duration, with the objective of minimizing the system cost accounting for the energy consumption and the cellular-link usage. To tackle with the technical challenge due to the coupling effect between the content transmission rate and each MD's relay-duration, we exploit the decomposable property of the joint optimization problem, based on which we characterize different possible cases for achieving the optimal solution. We then derive the optimal solution for each case analytically, and further propose an efficient algorithm for finding the globally optimal solution of the original joint optimization problem. Numerical results are provided to validate the proposed algorithm (including its accuracy and computational efficiency) and demonstrate that the optimal MDs' cooperative offloading can significantly reduce the system cost compared to some heuristic schemes. Several interesting insights about the cooperative offloading are also obtained.

We study the cooperation of the mobile network operator (MNO) and the venue owners (VOs) on the public Wi-Fi deployment. We consider aone-to-many bargainingframework, where the MNO bargains with VOs sequentially to determine where to deploy Wi-Fi and how much to pay. Taking into account the negative externalities among different steps of bargaining, we analyze the following two cases: for theexogenous bargaining sequencecase, we compute the optimal bargaining solution on the cooperation decisions and payments under a predetermined bargaining sequence; for theendogenous bargaining sequencecase, the MNO decides the bargaining sequence to maximize its payoff. Through exploring the structural property of the optimal bargaining sequence, we design a low-complexityOptimal VO Bargaining Sequencing(OVBS) algorithm to search the optimal sequence. More specifically, we categorize the VOs into three types based on the impact of the Wi-Fi deployment at their venues, and show that it is optimal for the MNO to bargain with these three types of VOs sequentially. Numerical results show that compared with the random and worst bargaining sequences, the optimal bargaining sequence improves the MNO's payoff by up to 14.8 and 45.3 percent, respectively.

The surging global mobile data traffic challenges the economic viability of cellular networks and calls for innovative solutions to reduce the network congestion and improve user experience. In this context, user-provided networks (UPNs), where mobile users share their Internet access by exploiting their diverse network resources and needs, turn out to be very promising. Heterogeneous users with advanced handheld devices can form connections in a distributed fashion and unleash dormant network resources at the network edge. However, the success of such services heavily depends on users' willingness to contribute their resources, such as network access and device battery energy. In this paper, we introduce a general framework for UPN services and design a bargaining-based distributed incentive mechanism to ensure users' participation. The proposed mechanism determines the resources that each user should contribute in order to maximize the aggregate data rate in UPN, and fairly allocate the benefit among the users. The numerical results verify that the service can always improve users' performance, and such improvement increases with the diversity of the users' resources. Quantitatively, it can reach an average 30% increase of the total served traffic for a typical scenario even with only six mobile users.

The proliferation of public Wi-Fi hotspots has brought new business potentials for Wi-Fi networks, which carry a significant amount of global mobile data traffic today. In this paper, we propose a novelWi-Fi monetizationmodel for venue owners (VOs) deploying public Wi-Fi hotspots, where the VOs can generate revenue by providing two different Wi-Fi access schemes for mobile users (MUs): 1) thepremium access, in which MUs directly pay VOs for their Wi-Fi usage, and 2) theadvertising sponsored access, in which MUs watch advertisements in exchange of the free usage of Wi-Fi. VOs sell their ad spaces to advertisers (ADs) via an ad platform, and share the ADs’ payments with the ad platform. We formulate the economic interactions among the ad platform, VOs, MUs, and ADs as a three-stage Stackelberg game. In Stage I, the ad platform announces its advertising revenue sharing policy. In Stage II, VOs determine the Wi-Fi prices (for MUs) and advertising prices (for ADs). In Stage III, MUs make access choices and ADs purchase advertising spaces. We analyze the sub-game perfect equilibrium (SPE) of the proposed game systematically, and our analysis shows the following useful observations. First, the ad platform’s advertising revenue sharing policy in Stage I will affect only the VOs’ Wi-Fi prices but not the VOs’ advertising prices in Stage II. Second, both the VOs’ Wi-Fi prices and advertising prices are non-decreasing in the advertising concentration level and non-increasing in the MU visiting frequency. Numerical results further show that the VOs are capable of generating large revenues through mainly providing one type of Wi-Fi access (the premium access or advertising sponsored access), depending on their advertising concentration levels and MU visiting frequencies.

Mobile crowdsensing emerges as a promising sensing paradigm through leveraging the diverse embedded sensors in massive mobile devices. A key objective in mobile crowdsensing is to efficiently schedule mobile device users to perform multiple sensing tasks. Prior work mainly focused on the interactions between the task layer and the user layer, without considering the similarity of tasks' data requirements and the heterogeneity of users'sensing capabilities. In this work, we propose a three-layer data-centric crowdsensing model by introducing a new data layer between tasks and users, which allows us to effectively leverage both the task similarity and the user heterogeneity. We formulate a joint task selection and user scheduling problem on top of the data layer, aiming at maximizing the social welfare. This problem is difficult to solve due to the combinatorial nature as well as the two-sided private information of tasks and users. To address both issues, we propose a two- sided randomized auction mechanism, which is computationally efficient, individually rational, and incentive compatible in expectation. Simulations show that (i) the proposed randomized auction can achieve 90% of the maximum social welfare (benchmark), and (ii) the social welfare gain due to data reuse increases with the task similarity and reaches up to 1300% in our simulations.

Accurate mobility prediction is becoming increasingly important in human behavior research, mainly due to many location-based applications such as mobile social networks and mobile advertisements. In this work, we propose a new crowd-sourced human mobility prediction model for public regions. We first analyze human trajectories collected through a cluster of densely deployed Wi-Fi access points (AP) in a shopping mall, and then characterize the close relationship between the human mobility patterns and the spatio-temporal contexts. Based on the distinct features of human trajectories in different types of public regions, we further propose a Markov-based crowdsourced mobility prediction method utilizing spatio-temporal contexts. We evaluate the performance of the proposed method using real traces, and show that our method is 28% more accurate in predicting human location transitions and incurs 14% smaller error in stay time prediction than the baseline methods.

There has been a proliferation of public Wi-Fi hotspots that serve a significant amount of global mobile traffic today. In this paper, we propose a general Wi-Fi monetization model for public Wi-Fi hotspots deployed by venue owners (VOs), where VOs generate revenue from providing both the premium Wi-Fi access and the advertising sponsored Wi-Fi access to mobile users (MUs). With the premium access, MUs directly pay VOs for their Wi-Fi usage; while with the advertising sponsored access, MUs watch advertisements for the free usage of Wi-Fi. VOs sell their ad spaces to advertisers (ADs) via an ad platform, and share a proportion of the revenue with the ad platform. We formulate the economic interactions among the ad platform, VOs, MUs, and ADs as a three-stage Stackelberg game. By analyzing the equilibrium, we show that the ad platform's advertising revenue sharing policy affects a VO's Wi-Fi price but not the VO's advertising price. Moreover, we prove that a single term called equilibrium indicator determines whether a VO will fully rely on the premium access, or fully rely on the advertising sponsored access, or obtain revenue from both types of access. Numerical results show that the VO obtains a large revenue under a large advertising concentration level and a medium MU visiting frequency.

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.

Adaptive bitrate video streaming is a widely-used technology for mobile video streaming over HTTP. In this work, we study a crowdsourced video streaming framework, which enables nearby mobile users to crowdsource their radio resources for cooperatively adaptive bitrate video streaming. We propose a multi-dimensional auction based incentive mechanism to promote the user cooperation, supporting the asynchronous downloading and the bitrate adapting of video users. In this mechanism, each user initiates an auction whenever he is ready to download a new data segment in an asynchronous fashion, and all nearby users compete for the downloading opportunity by submitting a multidimensional bid consisting of the intended segment bitrate and the associated value. Design of such a multi-dimensional auction is very challenging, as we need to guarantee the user's truthful reporting on the information on multiple dependent dimensions. We first propose a truthful second-score (multi-dimensional) auction framework, within which we further derive the efficient mechanism that maximizes the social welfare (of each segment downloading) and the sub-optimal mechanism that approximately maximizes the auctioneer payoff. Experiment results show that our proposed crowdsourced streaming can achieve 60% ˜ 76% of the maximum social welfare even when 80 percentage of users lose their direct network connections.

Motivated by the recent efforts in extending LTE to the unlicensed spectrum, we propose a novel spectrum sharing framework for the coopetition (i.e., cooperation and competition) between LTE and Wi-Fi in the unlicensed band. Basically, the LTE network chooses to work in one of the two modes: in the competition mode, it randomly accesses an unlicensed channel, and interferes with a Wi-Fi access point; in the cooperation mode, it onloads a Wi-Fi access point's traffic in exchange for the full access of the corresponding channel. Because the LTE network works in an interference-free manner in the cooperation mode, it can achieve a much larger total data rate (comparing to the competition mode) to serve both its own users and the Wi-Fi users under proper channel conditions. To achieve the maximum potential of this novel coopetition framework, we design a reverse auction mechanism, where the LTE provider is the auctioneer (buyer), and the Wi-Fi access point owners (APOs) are the bidders who compete to sell their channels to the LTE provider. An APO's bid indicates the data rate that it would like the LTE provider to offer in the cooperation mode. We show that the auction involves the allocative externalities, i.e., the cooperation between the LTE provider and an APO benefits other APOs who are not directly involved in this cooperation. As a result, a particular APO's bidding strategy is affected by its belief about other APOs' bidding strategies. This makes our analysis much more challenging than that of the standard second-price auction, where bidding truthfully is a weakly dominant strategy. We characterize the APOs' unique equilibrium bidding strategies, and analyze the LTE provider's optimal reserve rate that maximizes its payoff for a general APO type distribution. Our analysis shows that only when the LTE throughput exceeds a threshold, the LTE provider will choose a reasonably large reserve rate to cooperate with the APOs; otherwise, it will restrict the reserve rate to a small value and work in the competition mode.

A database-assisted TV white space network can achieve the goal of green cognitive communication by effectively reducing the energy consumption in cognitive communications. The success of such a novel network relies on a proper business model that provides substantial incentives for all parties involved. In this paper, we propose an integrated spectrum and information market for a database-assisted TV white space network, where a geolocation database acts as an online platform providing services to both a spectrum market and an information market. We model the interactions among the database operator, the spectrum licensee, and the unlicensed users as a three-stage sequential decision process. Specifically, Stage I characterizes the negotiation between the database and the spectrum licensee, in terms of the commission for the licensee to use the spectrum market platform, Stage II models the pricing decisions of the database and the spectrum licensee, and Stage III characterizes the subscription behaviors of the unlicensed users. Analyzing such a three-stage model is very challenging due to the co-existence of positive and negative network externalities in the information market. We explicitly characterize the impact of network externalities on the equilibrium behaviors of all parties involved. We also analytically show that the spectrum licensee can never get a market share larger than half in the integrated market. Our numerical results further show that the proposed integrated market can outperform the pure information market in terms of network profit up to 87%.

Offloading cellular mobile users' (MUs') data traffic to small-cell networks is a cost-effective approach to relieve congestion in macrocell cellular networks. However, as many small-cell networks operate in the unlicensed bands, the data offloading might suffer from a security issue, i.e., some eavesdropper could overhear the offloaded data over unlicensed spectrums. This motivates us to investigate a secrecy-based energy-efficient uplink data offloading scheme. Specifically, we consider the recent paradigm of traffic offloading via dual connectivity, which enables an MU to simultaneously deliver traffic to a macro base station (mBS) over the licensed channel and a small-cell access point (sAP) over the unlicensed channel. We formulate an MU's joint optimization of traffic scheduling and power allocation problem, with the objective of minimizing the total power consumption while meeting both the MU's traffic demand and secrecy requirement. Despite the non-convex nature of the joint optimization problem, we propose an efficient algorithm to compute the optimal offloading solution. By evaluating the impact of the MU's secrecy requirement and the eavesdropper's channel condition, we quantify the conditions under which the optimal offloading solution corresponds to the full-offloading and zero-offloading, respectively. Numerical results validate the optimal performance of our proposed algorithm, and show that the optimal offloading can significantly reduce the total power consumption compared with some fixed offloading schemes. Based on the optimal offloading solution for each MU, we further analyze the scenario of multiple MUs and sAPs, and investigate how to optimally exploit the sAPs' total offloading capacity to serve the MUs while accounting for the MUs' corresponding power consumptions for offloading data. To this end, we formulate a total network-benefit maximization problem that accounts for the reward for serving the MUs successfully, the mBS's bandwidth usage, and the MUs' power consumptions. Numerical results show that the optimal solution can improve the total network benefit compared with some heuristic sAP-selection scheme.

In this paper, we study a virtual wireless operator's spectrum investment problem under spectrum supply uncertainty. To obtain enough spectrum resources to meet its customer demands, the virtual operator can either sense for the temporarily unused spectrum in a licensed band or lease spectrum from a spectrum owner. Sensing is usually cheaper than leasing, but the amount of available spectrum obtained by sensing is uncertain due to the primary users' activities in the licensed band. Previous studies on spectrum investment problems mainly considered the expected profit maximization problem of a risk-neutral operator based on the expected utility theory (EUT). In reality, however, an operator's decision is influenced by not only the consideration of expected profit maximization, but also the level of its risk preference. To capture this tradeoff between these two considerations, we analyze the operator's optimal decision problem using the prospect theory from behavioral economics, which includes EUT as a special case. The sensing and leasing optimal problem under prospect theory is non-convex and challenging to solve. Nevertheless, by exploiting the unimodal structure of the problem, we are able to compute the unique global optimal solution. We show that, compared with an EUT operator, both the risk-averse and risk-seeking operator achieve a smaller expected profit. On the other hand, a risk-averse operator can guarantee a larger minimum possible profit, while a risk-seeking operator can achieve a larger maximum possible profit. Furthermore, the tradeoff between the expected profit and the minimum possible profit for a risk-averse operator is better when the sensing cost increases, while the tradeoff between the expected profit and the maximum possible profit for a risk-seeking operator is better when the sensing cost decreases.

The explosive growth of global mobile traffic has led to rapid growth in the energy consumption in communication networks. In this paper, we focus on the energy-aware design of the network selection, subchannel, and power allocation in cellular and Wi-Fi networks, while taking into account the traffic delay of mobile users. Based on the two-timescale Lyapunov optimization technique, we first design an online Energy-Aware Network Selection and Resource Allocation (ENSRA) algorithm, which yields a power consumption within$O\left({\frac{1}{V}} \right)$bound of the optimal value, and guarantees an$O\left(V \right)$traffic delay for any positive control parameter$V$. Motivated by the recent advancement in the accurate estimation and prediction of user mobility, channel conditions, and traffic demands, we further develop a novel predictive Lyapunov optimization technique to utilize the predictive information, and propose a Predictive Energy-Aware Network Selection and Resource Allocation (P-ENSRA) algorithm. We characterize the performance bounds of P-ENSRA in terms of the power-delay tradeoff theoretically. To reduce the computational complexity, we finally propose a Greedy Predictive Energy-Aware Network Selection and Resource Allocation (GP-ENSRA) algorithm, where the operator solves the problem in P-ENSRA approximately and iteratively. Numerical results show that GP-ENSRA significantly improves the power-delay performance over ENSRA in the large delay regime. For a wide range of system parameters, GP-ENSRA reduces the traffic delay over ENSRA by 20–30% under the same power consumption.

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.

This paper studies how to maximize a spectrum database operator's expected revenue in sharing spectrum to secondary users, through joint pricing and admission control of spectrum resources. A unique feature of our model is the consideration of the stochastic and heterogeneous nature of secondary users' demands. We formulate the problem as a stochastic dynamic programming problem, and present the optimal solutions under both static and dynamic pricing schemes. In the case of static pricing, the prices do not change with time, although the admission control policy can still be time-dependent. In this case, we show that a stationary (time-independent) admission policy is in fact optimal under a wide range of system parameters. In the case of dynamic pricing, we allow both prices and admission control policies to be time-dependent. We show that the optimal dynamic pricing can improve the operator's revenue by more than 30% over the optimal static pricing, when secondary users' demands for spectrum opportunities are highly elastic.

Mobile crowdsensing is a new sensing paradigm relying on computation and storage capabilities of mobile devices. However, traditional server-client mobile crowdsensing models suffer from a high operational cost on the server, and hence a poor scalability. Peer-to- peer (P2P) mobile crowdsensing models can effectively reduce the server's operational cost, by leveraging the mobile devices' under-utilized computation and storage resources. In a P2P mobile crowdsensing model, the sensing data is saved and processed in mobile users' devices in a distributed fashion, and is shared among mobile users directly in a P2P manner. In this work, we focus on the incentive issue in such a P2P mobile crowdsensing model. Specifically, we propose a data market and a generic pricing scheme for the data sharing among data sensors and requesters. We analyze the user interactions in such a data market from a game theoretic perspective, and prove the existence and uniqueness of the market equilibrium. We further propose a generalized best response dynamics to reach the market equilibrium. Our theoretic analysis and numerical results indicate that the equilibrium social welfare decreases with the data transfer cost and data prices, while the ratio of the equilibrium social welfare to the maximum social welfare benchmark increases with the data transfer cost and data prices.

A properly designed incentive mechanism is important for cooperative relay networks, as it will encourage relays assisting sources' data transmissions. However, previous related studies didn't give enough consideration to the topology effect, i.e., how the network topology can substantially influence the relay selection and profit distribution in cooperations. In this paper, we quantify the topology effect in multi-source-multi-relay networks analytically, by using a multi-node Nash bargaining framework based on the network exchange theory. The proposed multinode Nash bargaining outcome guarantees not only the individual satisfaction for each node, but also the social optimality for the entire network (of all nodes). Then, we propose a distributed incentive mechanism, named as natural algorithm, which enables each node to take advantage of the network topology to reach a multi-node Nash bargaining outcome through proper source/relay selection and payment bargaining. Simulation results illustrate the profit distribution among relays and sources under different network topologies.

This paper studies the energy trading among multiple connected microgrids, and analyzes the impacts of such trading on the microgrids' costs. In our model, microgrids with excessive power generations can trade with other microgrids in deficit of power supplies for mutual benefits. We design a bargaining-based energy trading market, where all the interconnected microgrids cooperatively decide the amount of energy trade and the associated payments. We propose a decentralized algorithm to solve the bargaining problem, with minimum information exchange overhead. Numerical studies based on realistic data demonstrate the effectiveness of the bargaining-based energy trading market design, and show that the reduction of total cost of the interconnected-microgrids system can be up to 22% comparing with the case of no trading.

Providing an adequate long-term user participation incentive is important for a participatory sensing system to maintain enough number of active users (sensors), so as to collect a sufficient number of data samples and support a desired level of service quality. In this work, we consider the sensor selection problem in a general time-dependent and location-aware participatory sensing system, taking the long-term user participation incentive into explicit consideration. We study the problem systematically under different information scenarios, regarding both future information and current information (realization). In particular, we propose a Lyapunov-based VCG auction policy for the on-line sensor selection, which converges asymptotically to the optimal off-line benchmark performance, even with no future information and under asymmetry of current information. Extensive numerical results show that our proposed policy outperforms the state-of-art policies in the literature, in terms of both user participation (e.g., reducing the user dropping probability by 25% ~ 90%) and social performance (e.g., increasing the social welfare by 15% ~ 80%).

We propose a hybrid spectrum and information market for database-assisted TV white space networks, where a geo-location white space database serves as the platform for both the spectrum market and the information market. We study the interactions among the database operator, the spectrum licensee, and unlicensed users systematically, using a three-layer hierarchical model. In Layer I, the licensee negotiates with the database regarding the commission fee of using the spectrum market platform. In Layer II, the database and the licensee compete for selling information or channels to unlicensed users. In Layer III, unlicensed users determine whether to buy the exclusive usage right of licensed channels from the licensee, or to buy the information regarding unlicensed channels from the database. Analyzing such a three-layer model is challenging, due to the coexistence of both positive and negative network externalities in the information market. We characterize the market equilibrium systematically, and analyze how the network externalities affect the equilibrium behaviours of all parties involved. Our numerical results show that the proposed hybrid market can improve the network profit more than 80%, compared with a pure information market. Meanwhile, the achieved network profit is very close to the coordinated benchmark (e.g., the gap is less than 4%).

With the rich set of embedded sensors installed in smartphones and the large number of mobile users, we witness the emergence of many innovative commercial mobile crowdsensing applications that combine the power of mobile technology with crowdsourcing to deliver time-sensitive and location-dependent information to their customers. Motivated by these real-world applications, we consider the task selection problem for heterogeneous users with different initial locations, movement costs, movement speeds, and reputation levels. Computing the social surplus maximization task allocation turns out to be an NP-hard problem. Hence we focus on the distributed case, and propose an asynchronous and distributed task selection (ADTS) algorithm to help the users plan their task selections on their own. We prove the convergence of the algorithm, and further characterize the computation time for users' updates in the algorithm. Simulation results suggest that the ADTS scheme achieves the highest Jain's fairness index and coverage comparing with several benchmark algorithms, while yielding similar user payoff to a greedy centralized benchmark. Finally, we illustrate how mobile users coordinate under the ADTS scheme based on some practical movement time data derived from Google Maps.

Wireless interference management through continuous power control has been extensively studied in the literature. However, practical systems often adopt discrete power control with a limited number of power levels and MCSs (Modulation Coding Schemes). In general, discrete power control is NP-hard due to its combinatorial nature. To tackle this challenge, we propose an innovative approach of interference management: ARM (Anonymous Rating Mechanism). Inspired by the successes of the simple Anonymous Rating Mechanism in Internet and E-commerce, we develop ARM as distributed near-optimal algorithm for solving the discrete power control problem (i.e., the joint scheduling, power allocation, and modulation coding adaption problem) under the physical interference model. We show that ARM achieves a close-to-optimal network throughput with a very low control overhead. We also characterize the performance gap of ARM due to the loss of rating information, and study the trade-off between such gap and the convergence time of ARM. Through comprehensive simulations under various network scenarios, we find that the optimality gap of ARM is small and such a small gap can be achievable with only a small number of power levels. Furthermore, the performance degradation is marginal if only limited local network information is available.

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.

In this paper, we study the cooperative Wi-Fi deployment problem, where the mobile network operator (MNO) cooperates with some venue owners (VOs) to deploy public Wi-Fi networks. The MNO negotiates with the VOs to determine where to deploy Wi-Fi and how much to pay. The MNO's objective is to maximize its payoff, which depends on the payments to VOs, the benefits due to data offloading and mobile advertising, and the costs due to deploying and operating Wi-Fi. We analyze the interactions among the MNO and VOs under the one-to-many bargaining framework, where the MNO bargains with VOs sequentially, taking into account the externalities among different steps of bargaining. We apply the Nash bargaining theory to analyze the cases with exogenous and endogenous bargaining sequences. For the former case, the bargaining sequence is predetermined, and we apply backward induction to compute the optimal bargaining solution related to the cooperation decisions and payments. For the latter case, the MNO can decide the bargaining sequence to maximize its payoff. We explore the structural property of the one-to-many bargaining, and design an Optimal VO Bargaining Sequencing (OVBS) algorithm that computes the optimal bargaining sequence. More precisely, we categorize VOs into three types based on the impact of the Wi-Fi deployment at their venues, and show that it is optimal for the MNO to bargain with these three types of VOs sequentially. Numerical results show that the optimal bargaining sequence improves the MNO's payoff over the random and worst bargaining sequences by up to 14.7% and 45.8%, respectively.

Motivated by the recently launched 2CM data trading platform of China Mobile Hong Kong, we study the optimal user mobile data trading problem under the future demand uncertainty. We consider a brokerage-based market, where sellers and buyers propose their selling and buying prices and quantities to the trading platform, respectively. The platform acts as a broker, which facilitates the trade by matching the supply and demand. To understand users' realistic trading behaviors, we use prospect theory (PT) from behavioral economics in the modeling, which leads to a challenging non-convex optimization problem. Nevertheless, we are able to determine the unique optimal solution in closed-form, by utilizing the unimodal structure of the objective function. When comparing with the benchmark expected utility theory (EUT), we show that a PT user with a low reference point is more willing to buy mobile data. Moreover, when the probability of high demand is low, comparing with an EUT user, a PT user is more willing to buy mobile data due to the probability distortion.

To accommodate the explosive growth in mobile data traffic, both mobile cellular operators and mobile users are increasingly interested in offloading the traffic from cellular networks to Wi-Fi networks. However, previously proposed offloading schemes mainly focus on reducing the cellular data usage, without paying too much attention on the quality of service (QoS) requirements of the applications. In this paper, we study the Wi-Fi offloading problem with delay-tolerant applications under usage-based pricing. We aim to achieve a good tradeoff between the user's payment and its QoS characterized by the file transfer deadline. We first propose a general Delay- Aware Wi-Fi Offloading and Network Selection (DAWN) algorithm for a general single-user decision scenario. We then analytically establish the sufficient conditions, under which the optimal policy exhibits a threshold structure in terms of both the time and file size. As a result, we propose a monotone DAWN algorithm that approximately solves the general offloading problem, and has a much lower computational complexity comparing to the optimal algorithm. Simulation results show that both the general and monotone DAWN schemes achieve a high probability of completing file transfer under a stringent deadline, and require the lowest payment under a non-stringent deadline as compared with three heuristic schemes.

In this paper, we investigate an oligopoly-competitive TV white space (TVWS) market, where multiple secondary network operators compete to serve a common pool of secondary end users by using TVWS purchased from a white space database. We first study the competitive interactions among secondary operators. Specifically, we formulate the interactions as a noncooperative price-inventory competition game, where operators determine the spectrum inventory (purchased from the database) and the service price (charged to end users) simultaneously. We prove the existence and uniqueness of the Nash equilibrium using the supermodular game theory. Then, we study the impact of the database manager's wholesale pricing strategy on the market equilibrium. Specifically, we analytically show how the wholesale prices affect the operators' equilibrium inventory and pricing decisions. Based on this analysis, we further propose two different spectrum wholesale pricing strategies that maximize the database manager's profit and the total network profit, respectively. Our simulations evaluate the performance difference between these two wholesale pricing strategies.

Geo-location database-assisted TV white space network reduces the need for energy-intensive processes (such as spectrum sensing), and hence can achieve green cognitive communication effectively. The success of such a network relies on a proper business model that provides incentives for all parties involved. In this paper, we propose a Model of INformation markEt for GeO-Location Database (MINE GOLD), which enables databases to sell spectrum information to unlicensed white space devices (WSDs) for profit. Specifically, we focus on an oligopoly information market with multiple databases, and study the interactions among databases and WSDs using a two-stage hierarchical model. In Stage I, databases compete to sell information to WSDs by optimizing their information prices. In Stage II, each WSD decides whether and from which database to purchase the information, to maximize his benefit of using the TV white space. We first characterize how the WSDs' purchasing behaviors dynamically evolve, and what is the equilibrium point under fixed information prices from the databases. We then analyze how the system parameters and the databases' pricing decisions affect the market equilibrium, and what is the equilibrium of the database price competition. Our numerical results show that, perhaps counter-intuitively, the databases' aggregate revenue is not monotonic with the number of databases. Moreover, numerical results show that a large degree of positive network externality would improve the databases' revenues and the system performance.

To match wireless users' soaring traffic demand, spectrum regulators are considering allocating additional spectrum to the wireless market. There are two major directions for the spectrum allocation: licensed (e.g., 4G cellular service) and unlicensed services (e.g., Super Wi-Fi service). The 4G service provides a ubiquitous coverage, has a higher spectrum efficiency, and often charges users a high service price. The Super Wi-Fi service has a limited coverage, a lower spectrum efficiency, but often charges users a low service price. The spectrum regulator now simply allocates the spectrum to maximize its income, but such an income-centric allocation does not ensure the best spectrum utilization by the users. This motivates us to design a new spectrum allocation scheme which jointly considers the spectrum regulator's income and the users' aggregate utility by investigating three market tiers: the spectrum regulator, 4G and Super Wi-Fi operator coalitions, and all the wireless users. We formulate it as a three-stage game and derive the unique subgame perfect equilibrium. Compared with the traditional income-centric allocation, we prove that the proposed scheme significantly improves users' aggregate utility with a limited spectrum regulator's income loss.

A key feature of wireless communications is the spatial reuse. However, the spatial aspect is not yet well understood for the purpose of designing efficient spectrum sharing mechanisms. In this paper, we propose a framework of spatial spectrum access games on directed interference graphs, which can model quite general interference relationship with spatial reuse in wireless networks. We show that a pure Nash equilibrium exists for the two classes of games: (1) any spatial spectrum access games on directed acyclic graphs, and (2) any games satisfying the congestion property on directed trees and directed forests. Under mild technical conditions, the spatial spectrum access games with random backoff and Aloha channel contention mechanisms on undirected graphs also have a pure Nash equilibrium. We also quantify the price of anarchy of the spatial spectrum access game. We then propose a distributed learning algorithm, which only utilizes users' local observations to adaptively adjust the spectrum access strategies. We show that the distributed learning algorithm can converge to an approximate mixed-strategy Nash equilibrium for any spatial spectrum access games. Numerical results demonstrate that the distributed learning algorithm achieves up to 100 percent performance improvement over a random access algorithm.

Dynamic spectrum sharing is a promising technology for improving the spectrum utilization. In this paper, we study how secondary users can share the spectrum in a distributed fashion based on social imitations. The imitation-based mechanism leverages the social intelligence of the secondary user crowd and only requires a low computational power for each individual user. We introduce the information sharing graph to model the social information sharing relationship among the secondary users. We propose an imitative spectrum access mechanism on a general information sharing graph such that each secondary user first estimates its expected throughput based on local observations, and then imitates the channel selection of another neighboring user who achieves a higher throughput. We show that the imitative spectrum access mechanism converges to an imitation equilibrium, where no beneficial imitation can be further carried out on the time average. Numerical results show that the imitative spectrum access mechanism can achieve efficient spectrum utilization and meanwhile provide good fairness across secondary users.

This paper analyzes two pricing schemes commonly used in Wi-Fi markets: the flat-rate and the usage-based pricing. The flat-rate pricing encourages the maximum usage, while the usage-based pricing can flexibly attract more users especially those with low valuations in mobile Internet access. First, we use theoretical analysis to compare the two schemes and show that for a single provider in a market, as long as the Wi-Fi capacity is abundant, the flat-rate pricing leads to more revenue. Second, we study how a global provider (e.g., Skype) collaborates with this monopolist in each local market to provide a global Wi-Fi service. We formulate the interactions between the global and local providers as a dynamic game. In Stage I, the global provider bargains with the local provider in each market to determine the global Wi-Fi service price and revenue sharing agreement. In Stage II, local users and travelers choose local or global Wi-Fi services. We analytically show that the global provider prefers to use the usage-based pricing to avoid a severe competition with the local provider. At the equilibrium, the global provider always shares the majority of his revenue with the local provider to incentivize the cooperation. Finally, we analytically study how the interaction changes if the local market has more than one local provider. In this case, the global provider can integrate the coverages of multiple local providers and provide a better service. Compared to the local monopoly case, local market competition enables the global provider to share less revenue with each of the local providers. However, we numerically show that the global provider's revenue could decrease, as he shares his revenue with more providers and can only charge a lower price.

As the successor to the 3G standard, the 4G cellular standard provides much higher data rates to address cellular users' ever-increasing demands for high-speed multimedia communications. This paper analyzes the cellular operators' timing of network upgrades, by considering user subscription dynamics induced by switching from 3G to 4G technologies. Being the first to upgrade 3G to 4G service, an operator increases its market share but takes more risk or upgrade cost as 4G technology matures overtime. This paper first studies a 4G monopoly market with one dominant operator and some small operators, where the monopolist decides its upgrade time by trading off increased market share and upgrade cost. The paper also considers a 4G competitive market and develops a game theoretic model for studying operators' interactions. The analysis shows that operators select different upgrade times to avoid severe competition. One operator takes the lead to upgrade, using the benefit of a larger market share to compensate for the larger cost of an early upgrade. This result matches well with many industry observations of asymmetric4G upgrades. The paper further shows that the availability of 4G upgrade may decrease both operators' profits due to increased competition. Perhaps surprisingly, the profits can increase with the upgrade cost.

The unprecedented growth of mobile data traffic challenges the performance and economic viability of today's cellular networks and calls for novel network architectures and communication solutions. Mobile data offloading through third-party Wi-Fi or femtocell access points (APs) can significantly alleviate the cellular congestion and enhance user quality of service (QoS), without requiring costly and time-consuming infrastructure investments. This solution has substantial benefits both for the mobile network operators (MNOs) and the mobile users, but comes with unique technical and economic challenges that must be jointly addressed. In this paper, we consider a market where MNOs lease APs that are already deployed by residential users for the offloading purpose. We assume that each MNO can employ multiple APs, and each AP can concurrently serve traffic from multiple MNOs. We design an iterative double-auction mechanism that ensures the efficient operation of the market by maximizing the differences between the MNOs' offloading benefits and APs' offloading costs. The proposed scheme takes into account the particular characteristics of the wireless network, such as the coupling of MNOs' offloading decisions and APs' capacity constraints. Additionally, it does not require full information about the MNOs and APs and creates nonnegative revenue for the market broker.

Femtocell networks have the potential to satisfy the increasing demand of mobile data usage. The recently proposed concept of cognitive femtocell network provides an effective way to further improve the spectrum spatial and frequency reuse. In this paper, we study the subchannel allocation problem for orthogonal frequency division multiple access (OFDMA)-based hybrid overlay/underlay cognitive femtocell networks. While most of the previous related studies did not fully exploit the potential of spatial and frequency reuse of the network, we propose a hybrid overlay and underlay spectrum access mechanism to further improve the performance of cognitive femtocell networks. We formulate the subchannel allocation problem as a coalition formation game among femtocell users under the hybrid access scheme, and analyze the stability of the coalition structure. We propose an efficient algorithm based on the solution concept of recursive core, and achieve a stable and efficient allocation. Simulation results show that the proposed algorithm achieves an improvement in aggregate network throughput up to 72% comparing to the overlay only scheme, 35% comparing to the underlay only scheme, and 18% comparing to a recently proposed coalition formation algorithm in the literature.

To address the increasingly severe congestion problem in cellular networks, mobile operators are actively considering offloading the cellular traffic to other complementary networks. In this paper, we study the online network selection problem in operator-initiated data offloading with multiple mobile users, taking into account the operation cost, queueing delay, and traffic load in different access networks (e.g., cellular macrocell, femtocell, and Wi-Fi networks). We first design a Delay-Aware Network Selection (DNS) algorithm based on the Lyapunov optimization technique. The DNS algorithm yields an operation cost within O (1/V) bound of the optimal value, and guarantees an O (V) traffic delay for any control parameter V > 0. Next, we incorporate the prediction of users' mobilities and traffic arrivals into the network selection. Specifically, we assume that the users' locations and traffic arrivals in the next few time slots can be estimated accurately, and propose a Predictive Delay-Aware Network Selection (P-DNS) algorithm to utilize this information based on a novel frame-based design. We characterize the performance bounds of P-DNS in terms of cost-delay tradeoff theoretically. To further reduce the computational complexity, we propose a Greedy Predictive Delay-Aware Network Selection (GP-DNS) algorithm, where the operator solves the network selection problem approximately and iteratively. Numerical results show that GP-DNS improves the cost-delay performance over DNS, and reduces the queueing delay by roughly 40% with the same operation cost.

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.

We study a secondary wireless operator's spectrum investment problem under spectrum supply uncertainty using prospect theory. In order to meet the demands of its users, the secondary operator can either sense for the unused spectrum in a licensed band, or lease spectrum from a spectrum owner. Sensing is usually cheaper than leasing, but the amount of spectrum obtained by sensing is uncertain. We formulate such a hybrid spectrum investment problem as a two-stage optimization problem, and compute the optimal sensing and leasing decisions using backward induction. To model the realistic investment behaviors under uncertainty, we apply prospect theory to overcome the limitations of the widely adopted expected utility theory. We show that the investment decision model based on prospect theory leads to a non-convex optimization problem, which is challenging to solve in closed-form. However, we characterize the uniqueness of the optimal solution analytically, and compute it through a simple line search. Comparing with the expected utility theory benchmark, the analysis based on prospect theory shows that the operator will be more conservative in sensing, in order to reduce the investment risk and to avoid a large possible loss. In other words, the operator is both risk averse and loss averse.

User-provided connectivity (UPC) is a promising paradigm to achieve a low-cost ubiquitous connectivity. In this paper, we study a network-assisted UPC service model, where a mobile virtual network operator (MVNO) enables its subscribers to operate as mobile WiFi hotspots (hosts) and provide Internet connectivity for others. A unique aspect of this service model is that the MVNO offers some free data quota to hosts as reimbursements (incentives) for connectivity sharing. This reimbursing scheme, together with a usage-based pricing, constitute a revolutionary hybrid data pricing-reimbursing scheme, which has not been considered before. We analyze the different impacts of data price and reimbursement on the host's connectivity sharing decision systematically. Based on this analysis, we further derive the optimal hybrid pricing-reimbursing policy that maximizes the MVNO's revenue. Our numerical result indicates that by using the proposed hybrid pricing policy, the MVNO can increase its revenue by 20% to 135% under an elastic client demand, and by 20% to 550% under an inelastic client demand, comparing to those achieved under a pricing-only policy.

Crowd-sourced mobile Internet access services enable mobile users to connect with each other and share their Internet connections. This is a promising solution for addressing users' increasing needs for ubiquitous connectivity and alleviating network congestion. The success of such services heavily depends on users' willingness to contribute their resources. In this paper, we consider a general model for such services, and design a distributed incentive mechanism for encouraging users' participation. This bargaining based scheme ensures that the contribution of user resources, in terms of Internet access bandwidths and battery energy, and the allocation of service capacity, measured in the delivered mobile data, are Pareto efficient and proportionally fair. The numerical results verify that the service always improves users' performance and that these benefits depend on the diversity of the users' resources.

In participatory sensing (PS), users use smartphones to collect information related to a certain phenomenon of interest, and report their sensed data to the service provider through cellular or Wi-Fi networks. Previous studies on the incentive mechanism design for user participation often neglect the details of data reporting, which is non-trivial given the user mobility, location-dependent network availability, and transmission cost. In this paper, we study the decisions of the service provider and the users in PS applications that involve photo or video transmissions, where the reporting cost through the cellular network is non-negligible. The service provider uses a deadline reward scheme to motivate users to participate, and optimizes its reward to maximize its expected surplus. Users make their participation and reporting decisions based on the reward announced by the service provider. We jointly consider the user mobility and multiple access methods with different transmission costs and location heterogeneity in the problem formulation and analysis. For the general case with a time-discounted reward, we formulate a user's reporting decision problem as a sequential decision problem, and propose an optimal participation and reporting decisions (OPRD) algorithm using dynamic programming. For the special case with a fixed reward, we derive the closed-form participation and reporting decisions. Simulation results show that the OPRD algorithm improves the user payoff over the patient and impatient schemes by 9.8% and 13.2%, respectively.

This paper solves the problem of long-term revenue maximization of a spectrum database operator, through joint pricing of spectrum resources and admission control of secondary users. A unique feature that we consider is the stochastic and heterogeneous nature of secondary users' demands. We formulate the problem as a stochastic dynamic programming problem, and consider the optimal solutions under both static and dynamic prices. In the case of static pricing, we constrain the prices to be time-independent while allowing the admission control policies to be time dependent. We show that in most cases a stationary (time independent) admission policy is in fact optimal in this case. We further look at the general case of dynamic pricing, where both the prices and admission control policies can be time dependent. We show that the flexibility of dynamic pricing can significantly improve the operator's revenue (by more than 30%) when secondary users have high demand elasticities.

In this paper, we propose a novel information market for TV white space networks, where the spectrum database operator sells the information regarding TV white space to secondary users. Different from the traditional spectrum market, the information market processes the unique property of positive externality, as more users purchasing the information service will increase the value of the service to each buyer. We systematically characterize the market equilibrium and the database operator's optimal information pricing strategy. Specifically, we first study how the market share dynamically evolves over time and eventually converge to a market equilibrium. We show that the market equilibrium increases with the initial market share, and there exist several tipping points of the initial market share, around which a slight change will lead to a significant change on the emerging market equilibrium. Based on the market equilibrium analysis, we further study the impact of the database operator's information pricing strategy on the market equilibrium, and derive the optimal information price that maximizes the database operator's revenue. Theoretical analysis and numerical result indicate that this is a promising business model for creating incentives for the database operator in TV white space networks.

The unprecedented growth of mobile data traffic challenges the performance and economic viability of today's cellular networks and calls for novel network architectures and communication solutions. Data offloading through third-party WiFi or femtocell access points (APs) can effectively alleviate the cellular network congestion in low operational and capital expenditure. This solution requires the cooperation and agreement of mobile cellular network operators (MNOs) and AP owners (APOs). In this paper, we model and analyze the interaction among one MNO and multiple APOs (for the amount of MNO's offloading data and the respective APOs' compensations) by using thew Nash bargaining theory. Specifically, we introduce a one-to-many bargaining game among the MNO and APOs and analyze the bargaining solution (game equilibrium) systematically under two different bargaining protocols: 1) sequential bargaining, where the MNO bargains with APOs sequentially, with one APO at a time, in a given order; and 2) concurrent bargaining, where the MNO bargains with all APOs concurrently. We quantify the benefits for APOs when bargaining sequentially and earlier with the MNO, and the losses for APOs when bargaining concurrently with the MNO. We further study the group bargaining scenario where multiple APOs form a group bargaining with the MNO jointly and quantify the benefits for APOs when forming such a group. Interestingly, our analysis indicates that grouping of APOs not only benefits the APOs in the group but may also benefit some APOs not in the group. Our results shed light on the economic aspects and the possible outcomes of the MNO/APOs interactions and can be used as a roadmap for designing policies for this promising data offloading solution.

Today's wireless networks are increasingly crowded with an explosion of wireless users, who have greater and more diverse quality of service (QoS) demands than ever before. However, the amount of spectrum that can be used to satisfy these demands remains finite. This leads to a great challenge for wireless users to effectively share the spectrum to achieve their QoS requirements. This paper presents a game theoretic model for spectrum sharing, where users seek to satisfy their QoS demands in a distributed fashion. Our spectrum sharing model is quite general, because we allow different wireless channels to provide different QoS, depending upon their channel conditions and how many users are trying to access them. Also, users can be highly heterogeneous, with different QoS demands, depending upon their activities, hardware capabilities, and technology choices. Under such a general setting, we show that it is NP hard to find a spectrum allocation which satisfies the maximum number of users' QoS requirements in a centralized fashion. We also show that allowing users to self-organize through distributed channel selections is a viable alternative to the centralized optimization, because better response updating is guaranteed to reach a pure Nash equilibria in polynomial time. By bounding the price of anarchy, we demonstrate that the worst case pure Nash equilibrium can be close to optimal, when users and channels are not very heterogenous. We also extend our model by considering the frequency spatial reuse, and consider the user interactions as a game upon a graph where players only contend with their neighbors. We prove that better response updating is still guaranteed to reach a pure Nash equilibrium in this more general spatial QoS satisfaction game.

We propose a revenue sharing based resource allocation scheme for dynamic spectrum access (DSA) networks. In our scheme, based on a mutually agreed revenue sharing scheme, a primary network operator (PNO) actively shares its radio resource with a secondary network operator (SNO), which provides access service to secondary users (SUs) for its revenue maximization. To investigate the coupling effect between the revenue sharing and resource allocation, we formulate the interaction between PNO and SNO as a two-layered game, which includes a top layer game to model their revenue sharing and a bottom layer game to model their joint resource allocations. Specifically, in the top layer, based on their joint resource allocation decisions, the PNO and SNO form a Nash bargaining game to determine the revenue sharing scheme such that both of them can benefit from cooperation satisfactorily. Then, in the bottom layer, under the given revenue sharing scheme, the PNO and SNO form a Stackelberg game to determine their joint resource allocation decisions, which also influence their respective revenues. The two games work iteratively such that the PNO and SNO reach a final equilibrium state at which neither PNO nor SNO will change its decisions unilaterally in both layers. We propose efficient algorithms to solve both the top layer and bottom layer games and compute the final equilibrium of the two-layered game. Specifically, despite the non-convexity of joint resource allocation optimization problem in the bottom layer, we identify its hidden monotonic structure and propose an efficient algorithm, which is based on the polyblock approximation, to achieve the optimal solutions. Moreover, in the top layer, to tackle with the difficulty due to the lack of an analytical objective function for the revenue sharing problem, we explore its hidden unimodal property and propose a Brent's method based algorithm to achieve the optimal solution. Numerical results are presented to verify the performance of our algorithms and show that our revenue sharing based resource allocation scheme yields a win-win situation for the PNO and SNO.

The emergence of cloud computing provides a cost-effective approach to deliver video streams to a large number of end users with the desired user quality of experience (QoE). Under such a paradigm, a video service provider (VSP) can launch its own video streaming services virtually by renting the distribution infrastructure from one or more cloud service providers (CSPs). However, CSPs such as Amazon EC2 normally offer multiple pricing options for virtual machine (VM) instances that they can provide, such as on-demand instances, reserved instances, and spot instances. Such diverse pricing models make it challenging for a VSP to determine how to optimally procure the required number of VM instances in different types to satisfy dynamic user demands. Given the limited budget, a VSP needs to carefully balance the procurement cost and the achieved QoE for end users. In this paper, we investigate the tradeoff between the cost incurred by VM instance procurement and the achieved QoE of end users under Amazon EC2's pricing models, and formulate the VM instance provisioning and procurement problem into a constrained stochastic optimization problem. By applying the Lyapunov optimization framework, we design an online procurement algorithm, which approaches the optimal solution with explicitly provable upper bounds. We also conduct extensive trace-driven simulations and our results show that our proposed algorithm (OPT-ORS) achieves a good balance between the procurement cost and the user QoE for cloud-based VSPs. In the achieved near-optimal situation, our algorithm guarantees that reserved VM instances are fully utilized to satisfy the baseline user demand, on-demand VM instances are only rented to handle flash crowds, while more spot VM instances are rented than on-demand VM instances to serve user demand over the baseline due to their low prices.

Providing economic incentives to all parties involved is essential for the success of dynamic spectrum access. Cooperative spectrum sharing is one effective way to achieve this, where secondary users (SUs) relay traffics for primary users (PUs) in exchange for dedicated spectrum access time for SUs' own communications. In this paper, we study the cooperative spectrum sharing under incomplete information, where SUs' wireless characteristics are private information and not known by a PU. We model the PU-SU interaction as a labor market using contract theory. In contract theory, the employer generally does not completely know employees' private information before the employment and needs to offers employees a contract under incomplete information. In our problem, the PU and SUs are, respectively, the employer and employees, and the contract consists of a set of items representing combinations of spectrum accessing time (i.e., reward) and relaying power (i.e., contribution). We study the optimal contract design for both weakly and strongly incomplete information scenarios. In the weakly incomplete information scenario, we show that the PU will optimally hire the most efficient SUs and the PU achieves the same maximum utility as in the complete information benchmark. In the strongly incomplete information scenario, however, the PU may conservatively hire less efficient SUs as well. We further propose a decompose-and-compare (DC) approximate algorithm that achieves a close-to-optimal contract. We further show that the PU's average utility loss due to the suboptimal DC algorithm and the strongly incomplete information are relatively small (less than 2 and 1.3 percent, respectively, in our numerical results with two SU types).

This paper analyzes and compares different incentive mechanisms for a master to motivate the collaboration of smartphone users on both data acquisition and distributed computing applications. To collect massive sensitive data from users, we propose a reward-based collaboration mechanism, where the master announces a total reward to be shared among collaborators, and the collaboration is successful if there are enough users wanting to collaborate. We show that if the master knows the users' collaboration costs, then he can choose to involve only users with the lowest costs. However, without knowing users' private information, then he needs to offer a larger total reward to attract enough collaborators. Users will benefit from knowing their costs before the data acquisition. Perhaps surprisingly, the master may benefit as the variance of users' cost distribution increases. To utilize smartphones' computation resources to solve complex computing problems, we study how the master can design an optimal contract by specifying different task-reward combinations for different user types. Under complete information, we show that the master involves a user type as long as the master's preference characteristic outweighs that type's unit cost. All collaborators achieve a zero payoff in this case. If the master does not know users' private cost information, however, he will conservatively target at a smaller group of users with small costs, and has to give most benefits to the collaborators.

We study the profit maximization problem of a cognitive virtual network operator in a dynamic network environment. We consider a downlink OFDM communication system with various network dynamics, including dynamic user demands, uncertain sensing spectrum resources, dynamic spectrum prices, and time-varying channel conditions. In addition, heterogeneous users and imperfect sensing technology are incorporated to make the network model more realistic. By exploring the special structural of the problem, we develop a low-complexity online control policies that determine pricing and resource scheduling without knowing the statistics of dynamic network parameters. We show that the proposed algorithms can achieve arbitrarily close to the optimal profit with a proper tradeoff with the queuing delay.

We study a problem where wireless service providers compete for heterogenous wireless users. The users differ in their utility functions as well as in the perceived quality of service of individual providers. We model the interaction of an arbitrary number of providers and users as a two-stage multi-leader-follower game. We prove existence and uniqueness of the subgame perfect Nash equilibrium for a generic channel model and a wide class of users' utility functions. We show that the competition of resource providers leads to a globally optimal outcome under mild technical conditions. Most users will purchase the resource from only one provider at the unique subgame perfect equilibrium. The number of users who connect to multiple providers at the equilibrium is always smaller than the number of providers. We also present a decentralized algorithm that globally converges to the unique system equilibrium with only local information under mild conditions on the update rates.

We study the optimal usage-based pricing problem in a resource-constrained network with one profit-maximizing service provider and multiple groups of surplus-maximizing users. With the assumption that the service provider knows the utility function of each user (thus complete information), we find that the complete price differentiation scheme can achieve a large revenue gain (e.g., 50%) compared to no price differentiation, when the total network resource is comparably limited and the high-willingness-to-pay users are minorities. However, the complete price differentiation scheme may lead to a high implementational complexity. To trade off the revenue against the implementational complexity, we further study the partial price differentiation scheme and design a polynomial-time algorithm that can compute the optimal partial differentiation prices. We also consider the incomplete information case where the service provider does not know to which group each user belongs. We show that it is still possible to realize price differentiation under this scenario and provide the sufficient and necessary condition under which an incentive-compatible differentiation scheme can achieve the same revenue as under complete information.

Recent results have shown that selfish users do not have an incentive to participate in intersession network coding in a static noncooperative game setting. Because of this, the worst-case network efficiency (i.e., the price-of-anarchy) can be as low as 20%. In this paper, we show that if the same game is played repeatedly, then the price-of-anarchy can be improved to 36%. We design a grim-trigger strategy that encourages users to cooperate and participate in the intersession network coding. A key challenge is to determine a common cooperative coding rate that the users should mutually agree on. We resolve the conflict of interest among the users through a bargaining process and obtain tight upper bounds for the price-of-anarchy that are valid for any possible bargaining scheme. Moreover, we propose a simple and efficient min-max bargaining solution that can achieve these upper bounds, as confirmed through simulation studies. The coexistence of multiple selfish network coding sessions as well as the coexistence of selfish network coding and routing sessions are also investigated. Our results represent a first step toward designing practical intersession network coding schemes that achieve reasonable performance for selfish users.

The successful deployment of a TV white space network requires the coordination and cooperation of all involved parties (including licensees, databases, secondary operators, and end-users), which form the White Space Ecosystem. In this paper, we study the white space ecosystem from the perspective of secondary network operators. Specifically, we consider a competitive white space network, where multiple secondary operators compete for the same pool of end-users. Each operator serves the attracted end-users by using either the dedicated spectrum (pre-ordered in advance) or the shared spectrum (requested in real-time). The key problem for each operator is to (i) determine the order quantity of dedicated spectrum, considering the uncertainty of end-user demand, and (ii) decide the price to the end-users, considering the competition of other operators. We formulate the interaction of operators as a non-cooperative Price-Quantity competition game (PQ-game), and study the existence and uniqueness of the Nash equilibrium (NE) systematically. We further characterize the impacts of the operator competition on the social welfare and the operators' own profits. Our results show that such impacts depend largely on the operators' cost of purchasing spectrum from the database or licensee: when the cost is low, the operator competition will decrease the social welfare and the operators' profits; when the cost is high, however, the competition will increase the social welfare and the operators' profits.

In this paper, we study the distributed spectrum sharing problem with spatial reuse and without explicit message passing. We propose tow novel threshold-based decentralized spatial spectrum access algorithms, which do not require information exchange among secondary users and channel switching at the equilibrium state. Moreover, we show that the proposed algorithms can converge to either an approximate Nash equilibrium or an approximate Pareto optimum, based on the different threshold designs. Numerical results show that the performance loss of the proposed algorithms is less than 10%, compared with the centralized optimal solution.

To accommodate users' ever-increasing traffic in wireless broadband services, the Federal Communications Commission (FCC) in the U.S. is considering allocating additional spectrum to the wireless market. There are two major directions: licensed (e.g. 3G) and unlicensed services (e.g. Wi-Fi). On the one hand, 3G service can realize a high spectrum efficiency and provide ubiquitous connection. On the other hand, the Wi-Fi service (often with limited coverage) can provide users with high-speed local connections, but is subject to uncontrollable interferences. Regarding spectrum allocation, prior studies only focused on revenue maximization. However, one of FCC's missions is to better improve all wireless users' utilities. This motivates us to design a spectrum allocation scheme that jointly considers social welfare and revenue. In this paper, we formulate the interactions among the FCC, typical 3G and Wi-Fi operators, and the endusers as a three-stage dynamic game and derive the equilibrium of the entire game. Compared to the benchmark case where the FCC only maximizes its revenue, the consideration of social welfare will encourage the FCC to allocate more spectrum to the service which lacks spectrum to better serve its users. Such consideration for the social welfare, to our delight, brings limited revenue loss for the FCC.

This paper analyzes two pricing schemes commonly used in WiFi markets: flat-rate pricing and usage-based pricing. The flat-free pricing encourages users to achieve the maximum WiFi usage and targets at users with high valuations in mobile Internet access, whereas the usage-based pricing is flexible to attract more users - even those with low valuations. First, we show that for a local provider, the flat-rate pricing provides more revenue than the usage-based pricing, which is consistent with the common practice in today's local markets. Second, we study how Skype may work with many local WiFi providers to provide a global WiFi service. We formulate the interactions between Skype, local providers, and users as a two-stage dynamic game. In Stage I, Skype bargains with each local provider to determine the global Skype WiFi service price and revenue sharing agreement; in Stage II, local users and travelers decide whether and how to use local or Skype WiFi service. Our analysis discovers two key insights behind Skype's current choice of usage-based pricing for its global WiFi service: to avoid severe competition with local providers and attract travelers to the service. We further show that at the equilibrium, Skype needs to share the majority of his revenue with a local provider to compensate the local provider's revenue loss due to competition. When there are more travelers or fewer local users, the competition between Skype and a local provider becomes less severe, and Skype can give away less revenue and reduce its usage-based price to attract more users.

As the successor to the 3G standard, 4G provides much higher data rates to address cellular users' ever-increasing demands for high-speed multimedia communications. This paper analyzes the cellular operators' timing of network upgrades and models that users can switch operators and services. Being the first to upgrade 3G to 4G service, an operator increases his market share but takes more risk or upgrade cost because 4G technology matures over time. This paper first studies a 4G monopoly market with one dominant operator and some small operators, where the monopolist decides his upgrade time by trading off increased market share and upgrade cost. The paper also considers a 4G competition market and develops a game theoretic model for studying operators' interactions. The analysis shows that operators select different upgrade times to avoid severe competition. One operator takes the lead to upgrade, using the benefit of a larger market share to compensate for the larger cost of an early upgrade. This result matches well with many industry observations of asymmetric 4G upgrades. The paper further shows that the availability of 4G upgrade may decrease both operators' profits due to increased competition. Perhaps surprisingly, the profits can increase with the upgrade cost.

Mobile data offloading is a promising approach to alleviate network congestion and enhance quality of service (QoS) in mobile cellular networks. In this paper, we investigate the economics of mobile data offloading through third-party WiFi or femtocell access points (APs). Specifically, we consider a market-based data offloading solution, where macrocellular base stations (BSs) pay APs for offloading traffic. The key questions arising in such a marketplace are following: (i) how much traffic should each AP offload for each BS? and (ii) what is the corresponding payment of each BS to each AP? We answer these questions by using the non-cooperative game theory. In particular, we define a multi-leader multi-follower data offloading game (DOFF), where BSs (leaders) propose market prices, and accordingly APs (followers) determine the traffic volumes they are willing to offload. We characterize the subgame perfect equilibrium (SPE) of this game, and further compare the SPE with two other classic market outcomes: (i) the market balance (MB) in a perfect competition market (i.e., without price participation), and (ii) the monopoly outcome (MO) in a monopoly market (i.e., without price competition). Our results analytically show that (i) the price participation (of BSs) will drive market prices down, compared to those under the MB outcome, and (ii) the price competition (among BSs) will drive market prices up, compared to those under the MO outcome.

Today's wireless networks are facing tremendous growth and many applications have more demanding quality of service (QoS) requirements than ever before. However, there is only a finite amount of wireless resources (such as spectrum) that can be used to satisfy these demanding requirements. We present a general QoS satisfaction game framework for modeling the issue of distributed spectrum sharing to meet QoS requirements. Our study is motivated by the observation that finding globally optimal spectrum sharing solutions with QoS guarantees is NP hard. We show that the QoS satisfaction game has the finite improvement property, and the users can self-organize into a pure Nash equilibrium in polynomial time. By bounding the price of anarchy, we demonstrate that the worst case pure Nash equilibrium can be close to the global optimal solution when users' QoS demands are not too diverse.

We propose a general framework to analyze incentives for user cooperation, and characterize the tradeoff between fairness and efficiency for cooperative networks. More specifically, we define the incentive region as a set of action profiles that provides cooperation benefits to all users and focus on the optimization of efficiency and fairness within this region. We introduce a linear resource allocation (LRA) scheme and show that most existing fairness measures can be converted to LRA with different linear coefficient vectors. We then propose the concept of strong price of fairness (SPoF) to study the network efficiency of the strong equilibrium. We show that both the SPoF and fairness measures are connected to the linear coefficient vector of LRA, which makes it possible to study the fairness and efficiency relationship. We then use the random access (RA) system as an example to show how to use the proposed framework to study a specific wireless network.

In this paper, we propose a design framework for achieving efficient multimedia multicast services in cognitive radio (CR) networks. The framework incorporates the characteristics of both heterogeneous network environment and the scalable video content. By adopting cooperative transmissions for the delivery of enhancement layer data, we can not only improve the achieved video quality but also protect the rights of subscribed secondary users. We also utilize network coding and superposition coding to achieve efficient multicast transmissions of the layered video packets in multi-channel CR networks. Numerical examples show the proposed framework can improve the average received data rate by up to 15%. When achieving the same video quality, the proposed framework can save 30% transmission time comparing with the scenario using direct transmission alone.

Efficient distributed spectrum sharing mechanism is crucial for improving the spectrum utilization. The spatial aspect of spectrum sharing, however, is less understood than many other aspects. In this paper, we generalize a recently proposed spatial congestion game framework to design efficient distributed spectrum access mechanisms with spatial reuse. We first propose a spatial channel selection game to model the distributed channel selection problem with fixed user locations. We show that the game is a potential game, and develop a distributed learning mechanism that converges to a Nash equilibrium only based on users' local observations. We then formulate the joint channel and location selection problem as a spatial channel selection and mobility game, and show that it is also a potential game. We next propose a distributed strategic mobility algorithm, jointly with the distributed learning mechanism, that can converge to a Nash equilibrium.

According to FCC's ruling for white-space spectrum access, white-space devices are required to query a database to determine the spectrum availability. In this paper, we study the database-assisted distributed white-space access point (AP) network design. We first model the cooperative and non-cooperative channel selection problems among the APs as the system-wide throughput optimization and non-cooperative AP channel selection games, respectively, and design distributed AP channel selection algorithms that achieve system optimal point and Nash equilibrium, respectively. We then propose a state-based game formulation for the distributed AP association problem of the secondary users by taking the cost of mobility into account. We show that the state-based distributed AP association game has the finite improvement property, and design a distributed AP association algorithm that can converge to a state-based Nash equilibrium. Numerical results show that the algorithm is robust to the perturbation by secondary users' dynamical leaving and entering the system.

In this paper, we study energy-efficient transmissions for multiple-input multiple-output (MIMO) cognitive radio (CR) networks in which the secondary unlicensed users coexist with the primary licensed users. We want to optimize the time allocations and beamforming vectors for the secondary users (SUs), in order to minimize the energy consumption of the SUs while satisfying the SUs' rate requirements and the primary receivers' interference constraints. Compared with the tradition MIMO networks, the challenge here is that the SUs may not always be able to obtain the channel state information (CSI) to the primary receivers. We are interested in two different scenarios. The first is when the SUs have the luxury of knowing the CSI to the primary receivers, and the second is when the SUs do not have such an luxury. The corresponding optimization formulations involve joint time scheduling and beamforming, which are non-convex and are complicated to solve. Fortunately, we show that when the SUs are not able to obtain the CSI, the optimal time allocation and the optimal beamforming vectors can be found very efficiently in polynomial-time through a proper decomposition. When the SUs have perfect knowledge about the CSI, we show that the optimal solutions can still be obtained in polynomial time when the secondary system is under-utilized. If the traffic load to the secondary system is heavy, we propose a polynomial-time heuristic to generate a near-optimal solution. The simulation results show that our proposed energy-optimal-transmission algorithms can achieve an energy-saving of 30% to 91%, compared with the simplistic maximum-rate transmission policy, depending on the secondary system's traffic load.

Providing proper economic incentives to all parties involved is essential for the success of dynamic spectrum access. Market-driven secondary spectrum trading is an effective way to achieve this goal, where primary spectrum owners (POs) temporarily lease their licensed spectrum bands to unlicensed secondary users (SUs). In this paper, we consider the short-term secondary spectrum trading between one PO (seller) and multiple SUs (buyers) in a hybrid spectrum market with both guaranteed contracts (futures market) and spot transactions (spot market). In particular, we focus on the PO's expected profit maximization under stochastic network information. The optimal solution consists of (i) a policy that maximizes the ex-ante expected profit based on the stochastic distribution of network information, and (ii) a selling mechanism that determines the real-time allocation and charging based on the realized network information and the derived policy. We study the optimal solution systematically under both information symmetry and asymmetry, depending on whether the PO can observe the SUs' realized private information. Under information symmetry, we show that the optimal solution can be achieved by a perfect price discrimination mechanism, which maximizes both the PO's expected profit (optimality) and the social welfare (efficiency). Under information asymmetry, we propose an integrated contract and auction design-ContrAuction-to elicit SUs' private information effectively. We derive analytically the optimal ContrAuction mechanisms that maximize the PO's expected profit with and without the constraint of efficiency, and characterize systematically the tradeoff between the PO's profit and the social welfare.

This paper proposes a real-time pricing scheme that reduces the peak-to-average load ratio through demand response management in smart grid systems. The proposed scheme solves a two-stage optimization problem. On one hand, each user reacts to prices announced by the retailer and maximizes its payoff, which is the difference between its quality-of-usage and the payment to the retailer. On the other hand, the retailer designs the real-time prices in response to the forecasted user reactions to maximize its profit. In particular, each user computes its optimal energy consumption either in closed forms or through an efficient iterative algorithm as a function of the prices. At the retailer side, we develop a Simulated-Annealing-based Price Control (SAPC) algorithm to solve the non-convex price optimization problem. In terms of practical implementation, the users and the retailer interact with each other via a limited number of message exchanges to find the optimal prices. By doing so, the retailer can overcome the uncertainty of users' responses, and users can determine their energy usage based on the actual prices to be used. Our simulation results show that the proposed real-time pricing scheme can effectively shave the energy usage peaks, reduce the retailer's cost, and improve the payoffs of the users.

Cooperative spectrum sharing can effectively improve the spectrum usage by allowing secondary users (SUs) to dynamically and opportunistically share the licensed bands with primary users (PUs). In return, an SU will relay a PU's traffic to improve the PU's effective data rate. In this paper, we study how one PU and one SU achieve an efficient spectrum sharing through dynamic noncooperative bargaining. The key challenge is that the PU does not have complete information of the SU's energy cost. We model the dynamic bargaining with incomplete information as a dynamic Bayesian game, and investigate the equilibria under both single-slot and multi-slot bargaining models. Theoretical analysis and numerical results indicate that our proposed scheme can lead to a win-win situation, where both the PU and the SU obtain data rate improvements via the bargaining-based CSS mechanism. Furthermore, the SU can take advantage of the incomplete information to improve its bargaining power (also called reputation effect), and thus gain a higher data rate.

We analyze inter-session network coding in a wired network using game theory. We assume that users are selfish and act as strategic players to maximize their own utility, which leads to a resource allocation game among users. In particular, we study a butterfly network, where a bottleneck link is shared by network coding and routing flows. We assume that network coding is performed using pairwise XOR operations. We prove the existence of Nash equilibrium for a wide range of utility functions. We also show that the number of Nash equilibria can be large (even infinite) for certain choices of parameters. This is in sharp contrast to a similar game setting with traditional packet forwarding, where the Nash equilibrium is always unique. We characterize the worst-case efficiency bound, i.e., the Price-of-Anarchy (PoA), compared to an optimal and cooperative network design. We show that by using a discriminatory pricing scheme which charges encoded and forwarded packets differently, we can improve the PoA in comparison with the case where a single pricing scheme is used. However, even when a discriminatory pricing scheme is used, the PoA is still worse than for the case when network coding is not applied. This implies that, although inter-session network coding can improve performance compared to routing, it is much more sensitive to users' strategic behavior.

In this paper, we design distributed spectrum access mechanisms with both complete and incomplete network information. We propose an evolutionary spectrum access mechanism with complete network information, and show that the mechanism achieves an equilibrium that is globally evolutionarily stable. With incomplete network information, we propose a distributed learning mechanism, where each user utilizes local observations to estimate the expected throughput and learns to adjust its spectrum access strategy adaptively over time. We show that the learning mechanism converges to the same evolutionary equilibrium on the time average. Numerical results show that the proposed mechanisms achieve up to 35 percent performance improvement over the distributed reinforcement learning mechanism in the literature, and are robust to the perturbations of users' channel selections.

We propose a dynamic spectrum access scheme where secondary users cooperatively recommend "goodâ channels to each other and access accordingly. We formulate the problem as an average reward-based Markov decision process. We show the existence of the optimal stationary spectrum access policy and explore its structure properties in two asymptotic cases. Since the action space of the Markov decision process is continuous, it is difficult to find the optimal policy by simply discretizing the action space and use the policy iteration, value iteration, or Q-learning methods. Instead, we propose a new algorithm based on the model reference adaptive search method and prove its convergence to the optimal policy. Numerical results show that the proposed algorithms achieve up to 18 and 100 percent performance improvement than the static channel recommendation scheme in homogeneous and heterogeneous channel environments, respectively, and is more robust to channel dynamics.

Femtocells can effectively resolve the poor connectivity issue of indoor cellular users. This paper investigates the economic incentive for a cellular operator to add femtocell service on top of its existing macrocell service. We model the interactions between a cellular operator and users as a Stackelberg game: The operator first determines spectrum allocations and pricings of femtocell and macrocell services, and then heterogeneous users choose between the two services and the amount of resource to request. In the ideal case where the femtocell service has the same full spatial coverage as the macrocell service, we show that the operator will choose to provide femtocell service only, as this leads to a better user quality of service and a higher operator profit. However, if we impose the constraint that no users' payoffs decrease after introducing the femtocell service, then the operator will always continue providing the macrocell service (with or without the femtocell service). Furthermore, we study the impact of operational cost, limited coverage, and spatial reuse on femtocell service provision. As the operational cost increases, fewer users are served by femtocell service and the operator's profit decreases. When the femtocell service has limited spatial coverage, the operator always provides the macrocell service beside the femtocell service. However, when the coverage is high or the total resource is low, the operator will set the prices such that all users who can access femtocell will choose to use the femtocell service only. Finally, spatial reuse of spectrum will increase the efficiency of femtocell services and gives the operator more incentives to allocate spectrum to femtocells.

This paper proposes the concept of safe carrier-sensing range under the cumulative interference model that guarantees interference-safe (also known as hidden-node-free) transmissions in CSMA networks. Compared with a previous related concept of safe carrier-sensing range under the commonly assumed but less realistic pairwise interference model, we show that the safe carrier-sensing range under the cumulative interference model is larger by a constant multiplicative factor. For example, the factor is 1.4 if the SINR requirement is 10 dB and the path-loss exponent is 4 in a noiseless case. We further show that the concept of a safe carrier-sensing range, although amenable to elegant analytical results, is inherently not compatible with the conventional power-threshold carrier-sensing mechanism (e.g., that used in IEEE 802.11). Specifically, the absolute power sensed by a node in the conventional carrier-sensing mechanism does not contain enough information for the node to derive its distances from other concurrent transmitting nodes. We show that, fortunately, a new carrier-sensing mechanism called Incremental-Power Carrier-Sensing (IPCS) can realize the carrier-sensing range concept in a simple way. Instead of monitoring the absolute detected power, the IPCS mechanism monitors every increment in the detected power. This means that IPCS can separate the detected power of every concurrent transmitter, and map the power profile to the required distance information. Our extensive simulation results indicate that IPCS can boost spatial reuse and network throughput by up to 60 percent relative to the conventional carrier-sensing mechanism under the same carrier-sensing power thresholds. If we compare the maximum throughput in the interference-free regime, the throughput improvement of IPCS is still more than 15 percent. Last but not least, IPCS not only allows us to implement the safe carrier-sensing range, but also ties up a loose end in many other prior theoretical works that implicitly used a carrier-sensing range (interference-safe or otherwise) without an explicit design to realize it.

The successful coexistence of secondary users (SUs) and primary users (PUs) in cognitive radio networks requires SUs to be spectrum aware and know which spectrum bands are occupied by PUs. Such awareness can be achieved in several ways, one of which is spectrum sensing. While existing spectrum sensing methods usually assume known distributions of the received primary signals, such an assumption is often too strong and unrealistic, and leads to unreliable detection performance in practical networks. In this paper, we design robust spectrum sensing algorithms under the distribution uncertainty of primary signals. After formulating the optimal sensing design as a robust optimization problem, we decompose it into a series of analytically tractable semi-definite programs, and propose an iterative algorithm to search the optimal decision threshold while maintaining the desirable false alarm probability during the iterations. Numerical results verify that our robust sensing algorithm improves the worst-case detection probability and reduces the system sensitivity on decision variables.

This paper studies a wireless network where multiple users cooperate with each other to improve the overall network performance. Our goal is to design an optimal distributed power allocation algorithm that enables user cooperation, in particular, to guide each user on the decision of transmission mode selection and relay selection. Our algorithm has the nice interpretation of an auction mechanism with multiple auctioneers and multiple bidders. Specifically, in our proposed framework, each user acts as both an auctioneer (seller) and a bidder (buyer). Each auctioneer determines its trading price and allocates power to bidders, and each bidder chooses the demand from each auctioneer. By following the proposed distributed algorithm, each user determines how much power to reserve for its own transmission, how much power to purchase from other users, and how much power to contribute for relaying the signals of others. We derive the optimal bidding and pricing strategies that maximize the weighted sum rates of the users. Extensive simulations are carried out to verify our proposed approach.

In this paper, we present a novel framework for spectrum sharing in cognitive radio networks. The secondary users (SUs) can share the spectrum resource with primary users (PUs) in a cooperative manner, where PUs trade their information and surplus resource, and SUs access the primary spectrum intelligently based on SUs' heterogeneous demands and PUs' resource prices. After paying PUs a subscription fee for the spectrum information, SUs become spectrum-aware and avoid the overhead on spectrum sensing. During SUs' channel access, PUs further charge SUs based on the amount of resource taken by SUs. We model this sharing problem in a flexible time-slotted structure, where SUs' decisions include the selection of proper transmission channel and slot length to meet their demands. This joint decision problem is studied as a spectral temporal allocation game. We prove the existence of a Nash equilibrium and design a strategy update process which can converge to an equilibrium.

Geo-location database driven white space network is a very promising approach for improving secondary spectrum utilization. In this paper, we consider the business modeling for geo-location database driven white space network. In our proposed model, the database acts as a spectrum broker buying (reserving) bandwidth from spectrum licensees in advance, and then resells the reserved bandwidth to unlicensed white space devices (WSDs) in real-time. We study the optimal bandwidth reservation for the database with WSDs' demand uncertainty under both information symmetry and asymmetry. Under information symmetry, the database and the WSD experience the same degree of uncertainty about the market demand. We derive the optimal bandwidth reservations in a centralized/integrated manner (as a benchmark). Under information asymmetry, the WSD has more information (i.e., with less uncertainty) about demand (due to the proximity to end-users). We propose a contract-based bandwidth reservation mechanism, which ensures WSDs share their local information with the database credibly. We further characterize the optimal bandwidth reservation contract systematically. Simulations show that under information asymmetry, the optimal bandwidth reservation contract improves both the database's profit and the social welfare significantly (larger than 30% in our simulations) without sacrificing the WSDs' benefits, comparing to those mechanisms without information sharing.

In this paper, we study a cognitive virtual network operator's profit maximization problem in a dynamic network environment. We consider various network dynamics, including dynamic user demands, unstable sensing spectrum resources, dynamic spectrum prices, and time-varying channel conditions. We develop a low-complexity on-line control policy that determines pricing and resource scheduling without knowing the distribution of dynamic network parameters. We show that the proposed algorithm can achieve arbitrarily close to the optimal profit with a proper trade-off of the queuing delay.

According to FCC's ruling for white-space spectrum access, white-space devices are required to query a database to determine the spectrum availability. In this paper, we adopt a game theoretic approach for the database-assisted white-space access point (AP) network design. We first model the channel selection problem among the APs as a distributed AP channel selection game, and design a distributed AP channel selection algorithm that achieves a Nash equilibrium. We then propose a state-based game formulation for the distributed AP association problem of the secondary users by taking the cost of mobility into account. We show that the state-based distributed AP association game has the finite improvement property, and design a distributed AP association algorithm can converge to a state-based Nash equilibrium. Numerical results show that the algorithm is robust to the perturbation by secondary users' dynamical leaving and entering the system.

This paper analyzes and compares different incentive mechanisms for a client to motivate the collaboration of smartphone users on both data acquisition and distributed computing applications. Data acquisition from a large number of users is essential to build a rich database and support emerging location-based services. We propose a reward-based collaboration mechanism, where the client announces a total reward to be shared among collaborators, and the collaboration is successful if there are enough users willing to collaborate. We show that if the client knows the users' collaboration costs, then he can choose to involve only users with the lowest costs by offering a small total reward. However, if the client does not know users' private cost information, then he needs to offer a larger total reward to attract enough collaborators. Users will benefit from knowing their costs before the data acquisition. Distributed computing aims to solve computational intensive problems in a distributed and inexpensive fashion. We study how the client can design an optimal contract by specifying different task-reward combinations for different user types. Under complete information, we show that the client will involve a user type as long as the client's preference for that type outweighs the corresponding cost. All collaborators achieve a zero payoff in this case. But if the client does not know users' private cost information, he will conservatively target at a smaller group of efficient users with small costs. He has to give most benefits to the collaborators, and a collaborator's payoff increases in his computing efficiency.

The successful coexistence of cognitive radio systems and licensed systems requires the secondary users to have the capability of sensing and keeping track of primary transmissions. While existing spectrum sensing methods usually assume known distributions of the primary signals, such an assumption is often not true in practice. As a result, applying existing sensing methods directly will often lead to unreliable detection performance in practical networks. In this paper, we try to improve the sensing performance under the distribution uncertainty of primary signals. We formulate the optimal sensing design as a robust optimization problem, and propose an iterative algorithm to determine the optimal decision threshold for each user. Extensive simulations demonstrate the effectiveness of our proposed algorithm.

Cognitive radio gives users the ability to switch channels and make use of dynamic spectrum opportunities. However, switching channels takes time, and may affect the quality of a user's transmission. When a cognitive radio user's channel becomes unavailable, sometimes it may be better waiting until its current channel becomes available again. Motivated by the recent FCC ruling on TV white space, we consider the scenario where cognitive radio users are given the foreknowledge of channel availabilities. Using this information, each user must decide when and how to switch channels. The users wish to exploit spectrum opportunities, but they must take account of the cost of switching channels and the congestion that comes from sharing channels with one another. We model the scenario as a game which, as we show, is equivalent to a network congestion game in the literature after proper and non-trivial transformations. This allows us to design a protocol which the users can apply to find Nash equilibria in a distributed manner. We further evaluate how the performance of the proposed schemes depends on switching cost using real channel availability measurements.

A key feature of wireless communications is the spatial reuse. However, the spatial aspect is not yet well understood for the purpose of designing efficient spectrum sharing mechanisms. In this paper, we propose a framework of spatial spectrum access games on directed interference graphs, which can model quite general interference relationship with spatial reuse in wireless networks. We show that a pure strategy equilibrium exists for the two classes of games: (1) any spatial spectrum access games on directed acyclic graphs, and (2) any games satisfying the congestion property on directed trees and directed forests. Under mild technical conditions, the spatial spectrum access games with random backoff and Aloha channel contention mechanisms on undirected graphs also have a pure Nash equilibrium. We then propose a distributed learning algorithm, which only utilizes users' local observations to adaptively adjust the spectrum access strategies. We show that the distributed learning algorithm can converge to an approximate mixed-strategy Nash equilibrium for any spatial spectrum access games. Numerical results demonstrate that the distributed learning algorithm achieves up to 100% performance improvement over a random access algorithm.

In this paper, we study random access in a drive-thru scenario, where roadside access points (APs) are installed on a highway to provide temporary Internet access for vehicles. We consider vehicle-to-roadside (V2R) communications for a vehicle that aims to upload a file when it is within the APs' coverage ranges, where both the channel contention level and transmission data rate vary over time. The vehicle will pay a fixed amount each time it tries to access the APs, and will incur a penalty if it cannot finish the file uploading when leaving the APs. First, we consider the problem of finding the optimal transmission policy with a single AP and random vehicular traffic arrivals. We formulate it as a finite-horizon sequential decision problem, solve it using dynamic programming (DP), and design a general dynamic optimal random access (DORA) algorithm. We derive the conditions under which the optimal transmission policy has a threshold structure, and propose a monotone DORA algorithm with a lower computational complexity for this special case. Next, we consider the problem of finding the optimal transmission policy with multiple APs and deterministic vehicular traffic arrivals thanks to perfect traffic estimation. We again obtain the optimal transmission policy using DP and propose a joint DORA algorithm. Simulation results based on a realistic vehicular traffic model show that our proposed algorithms achieve the minimal total cost and the highest upload ratio as compared with some other heuristic schemes. In particular, we show that the joint DORA scheme achieves an upload ratio 130% and 207% better than the heuristic schemes at low and high traffic densities, respectively.

Collaborative spectrum sensing is vulnerable to data falsification attacks, where malicious secondary users (attackers) submit manipulated sensing reports to mislead the fusion center's decision on spectrum occupancy. This paper considers a challenging attack scenario, where multiple attackers cooperatively maximize their aggregate spectrum utilization. Without attack-prevention mechanisms, we show that honest secondary users (SUs) are unable to opportunistically transmit over the licensed spectrum and may even get penalized for collisions caused by attackers. To prevent such attacks, we propose two attack-prevention mechanisms with direct and indirect punishments. Our key idea is to identify collisions with the primary user (PU) that should not happen if all SUs follow the fusion center's decision. Unlike prior work, the proposed simple mechanisms do not require the fusion center to identify and exclude attackers. The direct punishment can effectively prevent all attackers from behaving maliciously. The indirect punishment is easier to implement and can prevent attacks when the attackers care enough about their long-term reward.

This paper presents a comprehensive analytical study of two competitive secondary operators' investment (i.e., spectrum leasing) and pricing strategies, taking into account operators' heterogeneity in leasing costs and users' heterogeneity in transmission power and channel conditions. We model the interactions between operators and users as a three-stage dynamic game, where operators simultaneously make spectrum leasing decisions in Stage I, and pricing decisions in Stage II, and then users make purchase decisions in Stage III. Using backward induction, we are able to completely characterize the dynamic game's equilibria. We show that both operators' investment and pricing equilibrium decisions process interesting threshold properties. For example, when the two operators' leasing costs are close, both operators will lease positive spectrum. Otherwise, one operator will choose not to lease and the other operator becomes the monopolist. For pricing, a positive pure strategy equilibrium exists only when the total spectrum investment of both operators is less than a threshold. Moreover, two operators always choose the same equilibrium price despite their heterogeneity in leasing costs. Each user fairly achieves the same service quality in terms of signal-to-noise ratio (SNR) at the equilibrium, and the obtained predictable payoff is linear in its transmission power and channel gain. We also compare the duopoly equilibrium with the coordinated case where two operators cooperate to maximize their total profit. We show that the maximum loss of total profit due to operators' competition is no larger than 25 percent. The users, however, always benefit from operators' competition in terms of their payoffs. We show that most of these insights are robust in the general SNR regime.

In this paper, we introduce and analyze the properties of a class of games, the atomic congestion games on graphs (ACGGs), which is a generalization of the classical congestion games. In particular, an ACGG captures the spatial information that is often ignored in a classical congestion game. This is useful in many networking problems, e.g., wireless networks where interference among the users heavily depends on the spatial information. In an ACGG, a player's payoff for using a resource is a function of the number of players who interact with it and use the same resource. Such spatial information can be captured by a graph. We study fundamental properties of the ACGGs: under what conditions these games possess a pure strategy Nash equilibrium (PNE), or the finite improvement property (FIP), which is sufficient for the existence of a PNE. We show that a PNE may not exist in general, but that it does exist in many important special cases including tree, loop, or regular bipartite networks. The FIP holds for important special cases including systems with two resources or identical payoff functions for each resource. Finally, we present two wireless network applications of ACGGs: power control and channel contention under IEEE 802.11.

In this paper, we consider a cognitive radio network where multiple heterogenous secondary users (SUs) compete for transmissions on idle primary channels. We model this as a singleton congestion game, where the probability for an SU to successfully access a channel decreases with the number of SUs selecting the same channel. In particular, we consider player-specific payoffs that depend not only on the shares of the channel but also on different preference constants. Such system can be modeled as a congestion game, and we study the price of anarchy (PoA) for four families of such a game: identical, player-specific symmetric, resource-specific symmetric, and asymmetric games. We characterize the worst-case PoA in terms of the number of SUs and channels, and illustrate the network scenarios under which the worse case performance is reached. We further illustrate the PoA results with two Medium Access Control (MAC) schemes: uniform MAC and slotted Aloha. For both cases, we observe that the average performance of the game equilibrium is better than the worst-case PoA. Our study sheds light on how to design stable systems with smaller efficiency loss of the equilibrium.

Supporting the quality of service of unlicensed users in cognitive radio networks is very challenging, mainly due to the dynamic resource availability induced by the licensed users' activities. In this paper, we derive the optimal admission control and channel allocation decisions in cognitive overlay networks to support delay sensitive communications of unlicensed users. We formulate it as a Markov decision process problem, and solve it by transforming the original formulation into a stochastic shortest path problem. We then propose a simple heuristic control policy, which includes a threshold-based admission control scheme and and a largest-delay-first channel allocation scheme, and prove the optimality of the largest-delay-first channel allocation scheme. We further propose an improved policy using the rollout algorithm. By comparing the performance of both proposed policies with the upper-bound of the maximum revenue, we show that our policies achieve close-to-optimal performances with low complexities.

In this paper, we consider the open spectrum access mechanism design with both complete and incomplete network information in a many-users regime. We propose an evolutionary spectrum access mechanism with complete network information, and show that the mechanism achieves an equilibrium that is both evolutionarily stable and globally stable. With incomplete network information, we propose a distributed learning mechanism, where each user utilizes local observations to estimate the channel quality and learns to adjust its spectrum access strategy adaptively over time. Numerical results show that the proposed mechanisms achieve efficient spectrum sharing among the users, and are robust to the perturbations of users' channel selections.

NA

Cooperative spectrum sharing can effectively improve spectrum usage by allowing secondary users (SUs) to dynamically share the licensed bands with primary users (PUs). Meanwhile, an SU can relay a PU's traffic to improve the PU's effective data rate. In this paper, we consider a sequential spectrum bargaining process to achieve cooperative spectrum sharing between one PU and one SU over multiple time slots. The SU may be a Low type or a High type, depending on its energy cost. Such information is private to the SU and is unknown to the PU. We model such a dynamic bargaining with incomplete information as a dynamic Bayesian game, and characterize several types of equilibria under different system parameters. In particular, we show that a Low type SU may maximize its total utility by utilizing the reputation effect, i.e., rejects profitable offers initially in order to create the reputation of a High type SU.

In a drive-thru scenario where vehicles drive by a roadside access point (AP) to obtain temporary Internet access, it is important to design efficient resource allocation schemes to fully utilize the limited communication opportunities. In this paper, we study the random access problem in drive thru communications in a dynamic environment, where both the channel contention level and channel capacity vary over time. We assume that a vehicle has a file to upload when it is within the coverage range of the AP. The vehicle will pay a fixed amount each time it tries to access the AP, and will incur a penalty if it cannot finish the file uploading when leaving the AP. We first formulate the optimal transmission problem as a finite-horizon sequential decision problem. Then we solve the problem using dynamic programming, and design a dynamic optimal random access algorithm. Simulation results based on a realistic vehicular traffic model show that our algorithm achieves the minimal total cost, the highest probability of completing file upload, and the highest upload ratio as compared with two other heuristic schemes.

Today's wireless networks are interconnected. A network provider can charge other network providers "access prices'' for serving communication sessions originated from other networks. Meanwhile, the network provider also charges its users directly for using the network services. This paper looks at the proper choices of user pricing and access pricing from a regulator's point of view. We first derive the social optimal user prices when the regulator can directly control them. We characterize and explain how the social optimal user prices change with network's market shares and bandwidth costs. When such direct control is not possible or desirable, we further derive the regulator's optimal choice of access prices, which align the profit maximizing behaviors of the networks providers with the social optimality objective. We further characterize the relationship between the socially optimal access pricing and the market share as well as the users' utility elasticities.

Video is becoming the dominant traffic over the wireless networks. Given the limited wireless resources, supporting multi-user video streaming with good video playback quality- of-service (QoS) is very challenging. The key difficulties involve providing good playback quality while also satisfy- ing the stringent video packet delay bounds. The allocation of wireless resources need to be efficient and coordination of mobile video users should have a distributed fashion. In this paper we present a distributed framework for multi-user video streaming over an ad-hoc 802.11 like networks. The proposed algorithm is based on a utility-driven scheme that adjusts the video users' sending rates according to APP layer video buffer status. Simulation results demonstrate that the proposed scheme is quite efficient on radio resource while have better QoS than content blind 802.11 DCF scheme.

This paper studies the optimal investment and pricing decisions of a cognitive mobile virtual network operator (C-MVNO) under spectrum supply uncertainty. Compared with a traditional MVNO who often leases spectrum via long-term contracts, a C-MVNO can acquire spectrum dynamically in short-term by both sensing the empty “spectrum holes” of licensed bands and dynamically leasing from the spectrum owner. As a result, a C-MVNO can make flexible investment and pricing decisions to match demands of the secondary unlicensed users. Compared to dynamic spectrum leasing, spectrum sensing is typically cheaper, but the obtained useful spectrum amount is random due to primary licensed users' stochastic traffic. The C-MVNO needs to determine the optimal amounts of spectrum sensing and leasing by evaluating the trade-off between cost and uncertainty. The C-MVNO also needs to determine the optimal price to sell the spectrum to the secondary unlicensed users, taking into account wireless heterogeneity of users such as different maximum transmission power levels and channel gains. We model and analyze the interactions between the C-MVNO and secondary unlicensed users as a Stackelberg game. We show several interesting properties of the network equilibrium, including threshold structures of the optimal investment and pricing decisions, the independence of the optimal price on users' wireless characteristics, and guaranteed fair and predictable QoS among users. We prove that these properties hold for general SNR regime and general continuous distributions of sensing uncertainty. We show that spectrum sensing can significantly improve the C-MVNO's expected profit and users' payoffs.

This paper studies the problem of energy conservation of mobile terminals in a multi-cell TDMA network supporting real-time sessions. The corresponding optimization problem involves joint scheduling, rate control, and power control, which is often highly complex to solve. To reduce the solution complexity, we decompose the overall problem into two sub-problems: intra-cell energy optimization and inter-cell interference control. The solution of the two subproblems results in a "win-win" situation: both the energy consumptions and inter-cell interference are reduced simultaneously. We simulate our decomposition method with the typical parameters in WiMAX system, and the simulation results show that our decomposition method can achieve an energy reduction of more than 70% compared with the simplistic maximum transmit power policy. Furthermore, the inter-cell interference power can be reduced by more than 35% compared with the maximum transmit power policy. We find that the interference power stays largely constant throughout a TDMA frame in our decomposition method. Based on this premise, we derive an interesting decoupling property: if the idle power consumption of terminals is no less than their circuit power consumption, or when both are negligible, then the energy-optimal transmission rates of the users are independent of the inter-cell interference power.

We consider the channel selection problem in a cognitive radio network with heterogenous channel availabilities at different nodes. We formulate the maximum channel selection (MCS) problem as a binary integer nonlinear optimization problem, with an objective of maximizing the total channel utilization for all secondary nodes. We first prove that MCS problem is NP-complete. Then we design a centralized greedy channel selection (GCS) algorithm. The GCS algorithm is polynomial in computational complexity, and achieves a close-to-optimal (higher than 95%) numerical performance. We further propose a distributed priority order channel selection algorithm, which has significantly less signaling overhead compared with the GCS algorithm. We study the performance of the distributed algorithm both theoretically and numerically.

Proper admission control in cognitive radio networks is critical in providing QoS guarantees to secondary unlicensed users. In this paper, we study the admission control and channel allocation problem in overlay cognitive radio networks under the maximum cumulative delay constraint. We formulate it as a Markov decision process problem, and then solve it by transforming the original formulation into a stochastic shortest path problem. We further simulate the performance of a class of threshold-based admission control with the largest-delay-first channel allocation policy, and show its advantage over other two benchmark policies.

This paper presents the first analytical study of optimal investment and pricing decisions of a cognitive mobile virtual network operator (C-MVNO) under spectrum supply uncertainty. Compared with a traditional MVNO who only obtains spectrum by long-term leasing contracts, a C-MVNO can acquire short-term spectrum by both sensing the empty "spectrum holes" of licensed bands and dynamically leasing from the spectrum owner. As a result, a C-MVNO can make flexible investment and pricing decisions to match the current demands of the secondary unlicensed users. Spectrum sensing is typically cheaper than dynamic spectrum leasing, but the obtained useful spectrum amount is random due to primary licensed users' stochastic traffic. The CMVNO needs to determine the optimal amounts of sensing and leasing spectrum, considering the trade-offs between cost and uncertainty. The C-MVNO also needs to determine the optimal retail price to sell the spectrum to the secondary unlicensed users, taking into account wireless heterogeneity of users such as different maximum transmission power levels and channel gains. We model and analyze these decisions and the interactions between the C-MVNO and secondary users as a multi-stage Stackelberg game. We show several interesting properties of the network equilibrium, such as threshold structures of the optimal investment and pricing decisions, independence between the optimal price and users' wireless characteristics, and fair and predictable spectrum allocations to the users. Compared with the traditional MVNO, spectrum sensing can significantly improve the C-MVNO's expected profit and users' payoffs.

This paper proposes and investigates the concept of a safe carrier-sensing range that guarantees interference-safe (also termed hidden-node-free) transmissions in CSMA networks under the cumulative interference model. Compared with the safe carrier-sensing range under the commonly assumed but less realistic pairwise interference model, we show that the safe carrier-sensing range required under the cumulative interference model is larger by a constant multiplicative factor. For example, the factor is 1:4 if the SINR requirement is 10dB and the pathloss exponent is 4. We further show that the concept of a safe carrier-sensing range, although amenable to elegant analytical results, is inherently not compatible with the conventional power-threshold carrier-sensing mechanism (e.g., that used in IEEE 802.11). Specifically, the absolute power sensed by a node in the conventional mechanism does not contain enough information for it to derive its distances from other concurrent transmitter nodes. We show that, fortunately, a carrier-sensing mechanism called Incremental-Power Carrier-Sensing (IPCS) can realize the carrier-sensing range concept in a simple way. Instead of monitoring the absolute detected power, the IPCS mechanism monitors every increment in the detected power. This means that IPCS can separate the detected power of every concurrent transmitter, and map the power profile to the required distance information. Our extensive simulation results indicate that IPCS can boost spatial reuse and network throughput by more than 60% relative to the conventional carrier-sensing mechanism. Last but not least, IPCS not only allows us to implement our safe carrier-sensing range, it also ties up a loose end in many other prior theoretical works that implicitly assume the use of a carrier-sensing range (safe or otherwise) without an explicit design to realize it.

Most of the previous work on network coding has assumed that the users are not selfish and always follow the designed coding schemes. However, recent results have shown that selfish users do not have the incentive to participate in inter-session network coding in a static non-cooperative game setting. As a result, the worst-case network efficiency (i.e., the price-of-anarchy) can be as low as 22%. In this paper, we show that if the same game is played repeatedly, then the price-of-anarchy can be significantly improved to 48%. We propose a grim-trigger strategy that encourages users to cooperate and participate in the inter-session network coding. A key challenge is to determine a common cooperative coding rate that the users should mutually agree on. We propose to resolve the conflict of interest among the users through a bargaining process. We derive a tight upper bound for the price-of-anarchy which is valid for any bargaining scheme. Moreover, we propose a simple and efficient min-max bargaining solution that can achieve this upper bound. Our results represent one of the first steps towards designing practical inter-session network coding schemes that can achieve reasonable performance for selfish users.

In this paper, we study the joint allocation of three types of resources, namely, power, subcarriers and relay nodes, in multi-relay assisted dual-hop cooperative OFDM systems. All the relays adopt the amplify-and-forward protocol and assist the transmission from the source to destination simultaneously but on orthogonal subcarriers. The objective is to maximize the system transmission rate subject to individual power constraints on each node or a total network power constraint. We formulate such a problem as a subcarrier-pair based resource allocation that seeks the joint optimization of subcarrier pairing, subcarrier-pair-to-relay assignment, and power allocation. Using a dual approach, we solve this problem efficiently in an asymptotically optimal manner. Specifically, for the optimization problem with individual power constraints, the computational complexity is polynomial in the number of subcarriers and relay nodes, whereas the complexity of the problem with a total power constraint is polynomial in the number of subcarriers.We further propose two suboptimal algorithms for the former to trade off performance for complexity. Simulation studies are conducted to evaluate the average transmission rate and outage probability of the proposed algorithms. The impact of relay location is also discussed.

This paper studies the problem of finding a minimum-length schedule of a power-controlled wireless network subject to traffic demands and SINR (signal-to-interference-plus-noise ratio) constraints. We propose a column generation based algorithm that finds the optimal schedules and transmit powers. The column generation method decomposes a complex linear optimization problem into a restricted master problem and a pricing problem. We develop a new formulation of the pricing problem using the Perron-Frobenius eigenvalue condition, which enables us to integrate link scheduling with power control in a single framework. This new formulation reduces the complexity of the pricing problem, and thus improves the overall efficiency of the column generation method significantly - for example, the average runtime is reduced by 99.86% in 18-link networks compared with the traditional column generation method. Furthermore, we propose a branch-and-price method that combines column generation with the branch-and-bound technique to tackle the integer constraints on time slot allocation. We develop a new branching rule in the branch-and-price method that maintains the size of the pricing problem after each branching. Our branch-and-price method can obtain optimal integer solutions efficiently for example, the average runtime is reduced by 99.72% in 18-link networks compared with the traditional branch-and-price method. We further suggest efficient heuristic algorithms based on the structure of the optimal algorithms. Simulation results show that the heuristic algorithms can reach solutions within 10% of optimality for networks with less than 30 links.

By Lingyang Song, Yan Zhang, Nirwan Ansari, Jianwei Huang and Bechir Hamdaoui, Guest Editors Welcome to this special issue of Wiley Journal of Wireless Communications and Mobile Computing (WCMC). The title of this special issue literally adopts the theme of the 2010 International Wireless Communications and Mobile Computing Conference (IWCMC 2010), as it attempts to represent the ‘best’ of IWCMC 2010 by soliciting representative quality research works presented at the conference for inclusion in this issue via a rigorous selection and review process. This special issue covers a quite broad range of topics of wireless networks, wireless communications, and mobile computing, from the physical layer through application and system design. The goal of this special issue is to create a great opportunity for high impact research from both the mobile communications industry and academia to present and discuss new trends, developments, emerging technologies, and new industrial standards. To guarantee the quality, in this special issue, we have selectively collected 11 expanded papers from the proceedings of IWCMC 2010, and clustered them in three groups: three papers dealing with physical layer aspects, six papers investigating MAC and network layer issues, and two papers focusing on applications as well as prototypes. Detailed overview of the selected works is given below. The first group includes three papers, which provide physical layer results for wireless communications and mobile computing. The first paper, by Takeda et al., studies joint transmit and iterative receive frequency-domain equalization for DS-CDMA. In the proposed scheme, simple one-tap frequency-domain equalization at the transmitter and iterative one-tap FDE at the receiver are jointly performed using the common knowledge of channel state information, and at the same time taking channel estimation constraints into account. The paper by Fan et al. investigates the relay position selection problem for the diamond network over Nakagami-m fading channels. This paper discusses the impact on the performance of diamond network caused by the relays' position for a general Nakagami-m fading channel, which extends the previous work for a special Rayleigh fading case, and gives clear restrictions of their positions based on the requirement of the throughput improvement and network stability. The third paper, by Stuber et al., studies outage probability for cooperative diversity with selective combining in cellular networks. The analysis mainly focuses on outage probability for amplify-and-forward and decode-and-forward cooperative diversity systems with selective combining, for the case of a log-normal Nakagami faded desired signal and log-normal Rayleigh faded co-channel interferers. The second group of papers mainly investigates MAC and network layer issues. The first paper, by Wong et al., deals with switching cost minimization in the IEEE 802.16e mobile WiMAX sleep mode operation in order to improve the battery lifetime of the mobile station. The paper proposes a novel approach to resolve this issue by making a heuristic decision during the listening interval to minimize the switching frequency for better energy efficiency. The second paper by Lin et al. studies Multicast Broadcast Service (MBS) zone configuration for wireless multicast and broadcast service. Two schemes, the overlapping scheme and the enhanced overlapping scheme, are provided for more flexible MBS zone configuration to achieve better performance for MBS in terms of QoS and radio resource utilization. The third paper, by Kumar et al., investigates the issue of trust advisory and its establishment in mobile networks, with application to ad hoc networks, including DTNs. The authors utilized encounters in novel ways, noticing that mobility provides opportunities to build proximity, location and similarity based trust. The fourth paper by Znati et al. proposes robust multicast routing algorithms for mobile wireless networks by considering more practical challenges, e.g., the mobility of nodes, the tenuous status of communication links, limited resources, and indefinite knowledge of the network topology. This paper addresses these difficulties by providing a framework and architecture with proactive and reactive components to support multicasting to guarantee reliability and efficiency of end-to-end packet delivery. The fifth paper, by Pu et al., redefines the fairness concept regarding the application utility for time-constraint flows and then presents novel utility-based fair bandwidth sharing approaches in vehicular networks. Accordingly, two practical bandwidth-sharing schemes are provided for transferring data by fast-moving wireless nodes such as vehicles in order to guarantee QoS. The sixth paper, by Ali et al., provides a MAC protocol for cognitive wireless sensor body area networks to increases the critical traffic throughput. The proposed cognitive radio based MAC protocol prioritizes the critical packets access to the transmission medium by transmitting them with higher power while transmitting lower priority packets using lower transmission power. The third group consists of two papers focusing on applications and prototypes. The first paper by Fantacci et al. introduces a novel communication infrastructure for emergency management to interconnect several heterogeneous systems and provide multimedia access to groups of people involved in emergency operations as foreseen by the In.Sy.Eme. (Integrated System for Emergency) project. The main scope of the In.Sy.Eme system is to facilitate functional integration of new technologies with actual or off-the-shelf technologies to provide fast responses to any emergency situations and efficient use of all available resources. The second paper, by Manfrin et al., demonstrates the CalRAdio-Based advanced Spectrum Scanner, an open platform developed to monitor the ISM 2.4-2.499 GHz band, and reveals opportunities for a better utilization of the available spectrum resources. This solution provides sensing capabilities while preserving the 802.11b standard compatibility on the CalRadio 1 platform. Moreover, it capitalizes on the ULLA framework to export spectrum occupancy information to prospective cognitive radio manager engines, through a standardized set of sensing APIs. In conclusion, this issue of WCMC offers a state-of-the-art view of recent advances in wireless network, wireless communications, and mobile computing. It also offers both academic and industry appeal—the former as a basis toward future research directions and the latter toward viable commercial applications. In the long term, innovative wireless communications and mobile computing techniques will be characterized by their criticalness in consumer, business, and government applications to enhance the development of the whole world in realizing a better future. Finally, we would like to thank all the authors who have submitted their papers for consideration for publishing their work in this issue. We would like to extend our gratitude to the anonymous reviewers who spent much of their precious time reviewing all the papers. Their timely reviews and comments greatly helped us select the best papers in this special issue. We also would like to thank the devoted staff of Wiley for their high level of professionalism, and particularly express our gratitude to the Editor-in-Chief of WCMC, Professor Mohsen Guizani, for his advice, patience, and encouragement from the beginning until the final stage. We hope you will enjoy reading the great selection of papers in this issue.

We study the joint allocation of three types of resources, namely, power, subcarriers and relay nodes, in cooperative two-hop multi-relay OFDM systems. Each relay adopts the amplify-and-forward (AF) protocol. The objective is to maximize the system transmission rate subject to individual power constraints on each node. We formulate such a problem as a subcarrier-pair based resource allocation that seeks the joint optimization of subcarrier pairing, subcarrier-pair-to-relay assignment, and power allocation. Using a dual decomposition method, we solve this problem efficiently in an asymptotically optimal manner. We further propose two suboptimal algorithms to trade off performance for complexity. Simulation results demonstrate that the proposed subcarrier-pair based resource allocation schemes significantly outperform the symbol based benchmark scheme. Moreover, it is shown that subcarrier pairing plays an important role in improving the system performance.

In this paper, we model and analyze the interactions between secondary users in a spectrum overlay cognitive system as a cognitive MAC game. In this game, each secondary user can sense (and transmit) one of several channels, the availability of each channel is determined by the activity of the corresponding primary user. We show that this game belongs to the class of congestion game and thus there exists at least one Nash Equilibrium. We focus on analyzing the worst case efficiency loss (i.e., price of anarchy) at any Nash Equilibrium of such a game. Closed-form expressions of price of anarchy are derived for both symmetric and asymmetric games, with arbitrary channel and user heterogeneity. Several insights are also derived in terms of how to design better cognitive radio systems with less severe efficiency loss.

We study the optimal usage-based pricing problem in a resource-bounded network with one profit-maximizing service provider and multiple groups of surplus-maximizing users. We first analytically derive the optimal pricing mechanism that the service provider maximizes the service provider's revenue under complete network information. Then we consider the incomplete information case, and propose two incentive compatible pricing schemes that achieve different complexity and performance tradeoff. Finally, by properly combining the two pricing schemes, we can show that it is possible to maintain a very small revenue loss (e.g., 0.5% in a two-group case) without knowing detailed information of each user in the network.

A common assumption in the network coding literature is that the users are cooperative and will not pursue their own interests. However, this assumption can be violated in practice. In this paper, we analyze inter-session network coding in a wired network, assuming that the users are selfish and act as strategic players to maximize their own utility. We prove the existence of Nash equilibria for a wide range of utility functions. The number of Nash equilibria can be large (even infinite) under certain conditions, which is in sharp contrast to a similar game setting with traditional packet forwarding. We then characterize the worst-case efficiency bounds, i.e., the price-of-anarchy (PoA), compared to an optimal and cooperative network design. We show that by using a novel discriminatory pricing scheme that charges encoded and forwarded packets differently, we can improve PoA in comparison with the case where a single pricing scheme is being used. However, PoA is still worse than the case when network coding is not applied. This implies that inter-session network coding is more sensitive to strategic behavior. For example, for the case where only two network coding flows share a single bottleneck link, the efficiency at certain Nash equilibria can be as low as 48%. These results generalize the well-known result of guaranteed 67% efficiency bounds shown by Johari and Tsitsiklis for traditional packet forwarding networks.

We study the joint power control and minimum-frame-length scheduling problem in wireless networks, under the physical interference model and subject to consecutive transmission constraints. We start by investigating the complexity of the problem and present the first NP-completeness proof in the literature. We propose a polynomial-time approximation algorithm, called guaranteed and greedy scheduling (GGS) algorithm, to tackle this problem. We prove a bounded approximation ratio of the proposed algorithm relative to the optimal scheduling algorithm. Moreover, the proposed algorithm significantly outperforms the state-of-the-art related algorithm. Interestingly, our algorithm together with its bounded approximation ratio is applicable even when the consecutive transmission constraint is relaxed. To the best of our knowledge, the proposed algorithm is the first known polynomial-time algorithm with a proven bounded approximation ratio for the joint power control and scheduling problem under the physical interference model. We further demonstrate the performance and advantages of our algorithm through extensive simulations.

Orthogonal frequency division multiplexing (OFDM) with dynamic scheduling and resource allocation is a key component of most emerging broadband wireless access networks such as WiMAX and LTE (long term evolution) for 3GPP. However, scheduling and resource allocation in an OFDM system is complicated, especially in the uplink due to two reasons: (i) the discrete nature of subchannel assignments, and (ii) the heterogeneity of the users' subchannel conditions, individual resource constraints and application requirements. We approach this problem using a gradient-based scheduling framework. Physical layer resources (bandwidth and power) are allocated to maximize the projection onto the gradient of a total system utility function which models application-layer Quality of Service (QoS). This is formulated as a convex optimization problem and solved using a dual decomposition approach. This optimal solution has prohibitively high computational complexity but reveals guiding principles that we use to generate lower complexity sub-optimal algorithms. We analyze the complexity and compare the performance of these algorithms via extensive simulations.

We consider the problem of scheduling and resource allocation for multiuser video streaming over downlink orthogonal frequency division multiplexing (OFDM) channels. The video streams are precoded using the scalable video coding (SVC) scheme that offers both quality and temporal scalabilities. The OFDM technology provides the flexibility of resource allocation in terms of time, frequency, and power. We propose a gradient-based scheduling and resource allocation algorithm, which prioritizes the transmissions of different users by considering video contents, deadline requirements, and transmission history. Simulation results show that the proposed algorithm outperforms the content-blind and deadline-blind algorithms with a gain of as much as 6 dB in terms of average PSNR when the network is congested.

We consider scheduling and resource allocation for the downlink of a cellular OFDM system, with various practical considerations including integer tone allocations, different sub-channelization schemes, maximum SNR constraint per tone, and "self-noise" due to channel estimation errors and phase noise. During each time-slot a subset of users must be scheduled, and the available tones and transmission power must be allocated among them. Employing a gradient-based scheduling scheme presented in earlier papers reduces this to an optimization problem to be solved in each time-slot. Using a dual formulation, we give an optimal algorithm for this problem when multiple users can time-share each tone. We then give several low complexity heuristics that enforce integer tone allocations. Simulations are used to compare the performance of different algorithms.

Achieving weighted throughput maximization (WTM) through power control has been a long standing open problem in interference-limited wireless networks. The complicated coupling between the mutual interferences of links gives rise to a non-convex optimization problem. Previous work has considered the WTM problem in the high signal to interference-and-noise ratio (SINR) regime, where the problem can be approximated and transformed into a convex optimization problem through proper change of variables. In the general SINR regime, however, the approximation and transformation approach does not work. This paper proposes an algorithm, MAPEL, which globally converges to a global optimal solution of the WTM problem in the general SINR regime. The MAPEL algorithm is designed based on three key observations of the WTM problem: (1) the objective function is monotonically increasing in SINR, (2) the objective function can be transformed into a product of exponentiated linear fraction functions, and (3) the feasible set of the equivalent transformed problem is always ldquonormalrdquo, although not necessarily convex. The MAPEL algorithm finds the desired optimal power control solution by constructing a series of polyblocks that approximate the feasible SINR region in an increasing precision. Furthermore, by tuning the approximation factor in MAPEL, we could engineer a desirable tradeoff between optimality and convergence time. MAPEL provides an important benchmark for performance evaluation of other heuristic algorithms targeting the same problem. With the help of MAPEL, we evaluate the performance of several existing algorithms through extensive simulations.

In this paper, we propose two distributed contention-based medium access control (MAC) algorithms for solving a network utility maximization (NUM) problem in wireless ad hoc networks. Most of the previous NUM-based random access algorithms have one or more of the following performance bottlenecks: (1) extensive signaling among the nodes to achieve semi-distributed implementations, (2) synchronous updates of contention probabilities, (3) small update stepsizes to ensure convergence but with typically slow speed, and (4) supporting a limited range of utility functions under which the NUM is shown to be convex. Our proposed algorithms overcome the bottlenecks in all four aspects. First, only limited amount of message passing among nodes is required. Second, fully asynchronous updates of contention probabilities are allowed. Furthermore, our algorithms are robust to arbitrary large message passing delay and message loss. Third, we do not utilize any stepsize during updates, thus our algorithms can achieve faster convergence. Finally, our proposed algorithms have provable convergence, optimality, and robustness properties under a wider range of utility functions, even if the NUM problem is non-convex. Simulation results show the optimality and fast convergence of our algorithms, performance improvements compared with the subgradient-based MAC, and better efficiency-fairness tradeoff compared with the IEEE 802.11 distributed coordination function.

Random access has been studied for decades as a simple and practical wireless medium access control (MAC). Some of the recently developed distributed scheduling algorithms for throughput or utility maximization also take the form of random access, although extensive message passing among the nodes is required. In this paper, we would like to answer this question: is it possible to design a MAC algorithm that can achieve the optimal network utility without message passing? We provide the first positive answer to this question through a simple Aloha-type random access protocol. We prove the convergence of our algorithm for certain sufficient conditions on the system parameters, e.g., with a large enough user population. If each wireless node is capable of decoding the source MAC address of the transmitter from the interferring signal, then our algorithm indeed converges to the global optimal solution of the NUM problem. If such decoding is inaccurate, then the algorithm still converges, although optimality may not be always guaranteed. Proof of these surprisingly strong performance properties of our simple random access algorithm leverages the idea from distributed learning: each node can learn as much about the contention environment through the history of collision as through instantaneous but explicit message passing.

Resource allocation is considered for cooperative transmissions in multiple-relay wireless networks. Two auction mechanisms, SNR auctions and power auctions, are proposed to distributively coordinate the allocation of power among multiple relays. In the SNR auction, a user chooses the relay with the lowest weighted price. In the power auction, a user may choose to use multiple relays simultaneously, depending on the network topology and the relays' prices. Sufficient conditions for the existence (in both auctions) and uniqueness (in the SNR auction) of the Nash equilibrium are given. The fairness of the SNR auction and efficiency of the power auction are further discussed. It is also proven that users can achieve the unique Nash equilibrium distributively via best response updates in a completely asynchronous manner.

This paper concerns the problem of finding the minimum-length TDMA frame of a power-controlled wireless network subject to traffic demands and SINR (signal- to-interference-plus-noise ratio) constraints. We formulate the general joint link scheduling and power control problem as an integer linear programming (ILP) problem. The linear relaxation of the ILP problem has been claimed to be NP-hard in the literature. We present a computationally efficient heuristic algorithm, called the increasing demand greedy scheduling (IDGS) algorithm, to solve the general ILP problem. In addition, we propose using a column generation (CG) method as an augmentation to IDGS to further improve its performance. Simulation results show that integration of IDGS and CG can achieve superior performance in terms of both algorithm run time and solution optimality.

Efficient delivery of multimedia contents over wireless network is essential for future communication networks. However, content distribution and network engineering are traditionally studied separately, which leads to suboptimal network performance. In this paper, we consider the problem of scheduling and resource allocation for multi-user video streaming over downlink OFDM channels. The video streams are preceded with the SVC coding scheme, which offers both quality and temporal scalabilities. The OFDM technology provides the maximum flexibility of resource allocation in terms of time, frequency, and power. We propose a gradient-based scheduling and resource allocation algorithm, which explicitly takes account of video contents, deadline requirements, and the previous transmission results when calculating users' priority weights. Simulation results show that our proposed algorithm always outperforms the content- blind and deadline-blind algorithms, with a performance gain as much as 6 dB in terms of average user PSNR improvement in a congested network.

The Internet includes thousands of Internet service providers (ISPs) which are interconnected to provide connectivity and service for end-users. Traditionally, the settlement between the ISPs are determined based on bilateral agreements that result from pair-wise negotiations. Although this settlement mechanism is intuitive and easy to implement, it does not encourage network- wide cooperation, as the bilateral charges typically do not lead to a fair division of revenue among all ISPs that are involved in carrying the same flows of traffic. This problem is getting more severe with various emerging new Internet business models. In this paper, we try to determine the existence and realizability of bilateral prices that can achieve fair revenue division among ISPs. In particular, we use Shapley value as the basis for deriving fair prices. Under a quite general topology and traffic model, we find that there exists prices that make the revenue division under bilateral settlement equal to that calculated under Shapley value. The corresponding "fair price" exhibits several nice and desirable characteristics. Moreover, it could be realized approximately.

Robustness of optimization models for networking problems has been an under-explored area. Yet most existing algorithms for solving robust optimization problems are centralized, thus not suitable for many communication networking problems that demand distributed solutions. This paper represents the first step towards building a framework for designing distributed robust optimization algorithms. We first discuss several models for describing parameter uncertainty sets that can lead to decomposable problem structures. These models include general polyhedron, D-norm, and ellipsoid. We then apply these models to solve robust power control in wireless networks and robust rate control in wireline networks. In both applications, we propose distributed algorithms that converge to the optimal robust solution. Various tradeoffs among performance, robustness, and distributiveness are illustrated both analytically and through simulations.

Distributed and efficient resource allocation is critical for fully realizing the benefits of cooperative communications in large scale communication networks. This paper proposes two auction mechanisms, the SNR auction and the power auction, that determine relay selection and relay power allocation in a distributed fashion. A single-relay network is considered first, and the existence and uniqueness of the Nash Equilibrium (i.e., the auction's outcome) are proved. It is shown that the power auction achieves the efficient allocation by maximizing the total rate increase, and the SNR auction is flexible in trading off fairness and efficiency. For both auctions, the distributed best response bid updates globally converge to the unique Nash Equilibrium in a completely asynchronous manner. The analysis is then generalized to networks with multiple relays, and the existence of the Nash Equilibrium is shown under appropriate conditions. Simulation results verify the effectiveness and robustness of the proposed algorithms.

The 26 papers in this special issue focus on game theory in communication systems. The papers are grouped in four clusters according to their topics: (1) Physical layer models in wireless communications, (2) higher layer and cross-layer issues in wireless communications, (3) wire-line communication networks, and (4) specific topics including peer-to-peer networking, network coding, and network security.

Multi-user video streaming over wireless channels is a challenging problem, where the demand for better video quality and small transmission delays needs to be reconciled with the limited and often time-varying communication resources. This paper presents a framework for joint network optimization, source adaptation, and deadline-driven scheduling for multi-user video streaming over wireless networks. We develop a joint adaptation, resource allocation and scheduling (JARS) algorithm, which allocates the communication resource based on the video users' quality of service, adapts video sources based on smart summarization, and schedules the transmissions to meet the frame delivery deadlines. The proposed algorithm leads to near full utilization of the network resources and satisfies the delivery deadlines for all video frames. Substantial performance improvements are achieved compared with heuristic schemes that do not take the interactions between multiple users into consideration.

In lightweight mobile ad hoc networks, both probabilistic and deterministic key management schemes are fragile to node fabrication attacks. Our simulation results show that the Successful Attack Probability (SAP) can be as high as 42.6% with the fabrication of only 6 copies from captured nodes comprising only 3% of all nodes. In this paper, we propose two low-cost secure-architecture-based techniques to improve the security against such node fabrication attacks. Our new architectures, specifically targeted at the sensor-node platform, protect long-term keys using a root of trust embedded in the hardware System-on-a-Chip (SoC). This prevents an adversary from extracting these protected long-term keys from a captured node to fabricate new nodes. The extensive simulation results show that the proposed architecture can significantly decrease the SAP and increase the security level of key management for mobile ad hoc networks.

Cooperative transmission can greatly improve communication system performance by taking advantage of the broadcast nature of wireless channels. Most previous work on resource allocation for cooperation transmission is based on centralized control. In this paper, we propose two share auction mechanisms, the SNR auction and the power auction, to distributively coordinate the resource allocation among users. We prove the existence, uniqueness and effectiveness of the auction results. In particular, the SNR auction leads to a fair resource allocation among users, and the power auction achieves a solution that is close to the efficient allocation.

This is an overview of the ongoing FAST Copper project, which is aimed at substantial improvements in rate, reach, reliability, and quality in copper-last-mile broadband access through fiber/DSL deployment, engineering innovations, and fundamental research. The project is funded by NSF, and is currently pursued jointly by Princeton University, Stanford University, and Fraser Research Lab. In this article, we outline the motivations, challenges, and research issues associated with the project, and report some of the recent results by the Princeton team in each of the four dimensions: frequency, amplitude, space, and time.

Most previous work in statistical multiplexing only considered the case where the link transmission rates are fixed. In this paper, we consider statistical multiplexing in networks with adaptive transmission rates, with focus on DSL broadband access networks. This requires a jointly optimized allocation of buffer space and transmission bandwidth to traffic flows, which takes the flow traffic characteristics, the user QoS requirements, and the user interactions at the physical layer into consideration. Using the effective bandwidth concept, we propose a class of alternate maximization (AM) algorithms (AM-D and AM-M), which solve the statistical multiplexing problem for both delay insensitive data traffic and delay sensitive multimedia traffic. With low complexity as a design goal, the AM algorithms incorporate our recently proposed autonomous spectrum balancing (ASB) algorithm, which was originally designed for DSL physical layer spectrum management. Our numerical results show that the AM algorithms combines the gain due to statistical multiplexing and that due to spectrum management.

It is widely believed that although being more complex, a probabilistic key predistribution scheme is much more resilient against node capture than a deterministic one in lightweight wireless ad hoc networks. Backed up by the surprisingly large successful attack probabilities computed in this paper, we show that the probabilistic approaches have only limited performance advantages over deterministic approaches. We first consider a static network scenario as originally considered in the seminal paper by Eschenauer and Gligor [1], where any node capture happens after the establishment of all pairwise links, and show that the deterministic approach can achieve a performance as good as the probabilistic one. Furthermore in a mobile network, the probabilistic key management as described in [1] can lead to a successful attack probability of one order of magnitude larger than the one in a static network.

This paper reverse-engineers backoff-based random-access MAC protocols in ad-hoc networks. We show that the contention resolution algorithm in such protocols is implicitly participating in a non-cooperative game. Each link attempts to maximize a selfish local utility function, whose exact shape is reverse-engineered from the protocol description, through a stochastic subgradient method in which the link updates its persistence probability based on its transmission success or failure. We prove that existence of a Nash equilibrium is guaranteed in general. Then we establish the minimum amount of backoff aggressiveness needed, as a function of density of active users, for uniqueness of Nash equilibrium and convergence of the best response strategy. Convergence properties and connection with the best response strategy are also proved for variants of the stochastic-subgradient-based dynamics of the game. Together with known results in reverse-engineering TCP and BGP, this paper further advances the recent efforts in reverse-engineering layers 2-4 protocols. In contrast to the TCP reverse-engineering results in earlier literature, MAC reverse-engineering highlights the non-cooperative nature of random access.

Video streaming is becoming an important application in wireless communications. In a typical scenario, a base station needs to serve multiple video users with a total transmitting power constraint. How to make appropriate video coding decisions and allocate limited transmitting power among users to achieve optimal total utility is an important problem. In this paper we develop a pricing based downlink power allocation scheme with collaborative video summarization among users. The scheme exploits the multiuser diversity in channel states and utility-resource tradeoff characteristics in video contents to achieve better resource utilization. The computational burden can be distributed among video sources and base station. Simulation results demonstrate the effectiveness of the proposed algorithm.

For frequency selective interference channels where interference is treated as noise, distributively attaining the boundary of the rate region is an open problem, and is particularly important for broadband DSL access. This paper develops, analyzes, and simulates a new algorithm for power allocation in frequency selective interference channels called autonomous spectrum balancing (ASB). It utilizes the concept of a "reference line", which mimics a typical victim line in the interference channel. Compared with the state-of-the-art iterative watefilling and optimum spectrum balancing methods, the ASB algorithm is completely autonomous, has linear complexity in both the number of users and tones, and gives close to near-optimal performance. Convergence of a version of ASB is proven for any number of users

This paper reverse engineers backoff-based random-access MAC protocols in ad-hoc networks. We show that the contention resolution algorithm in such protocols is implicitly participating in a non-cooperative game. Each link attempts to maximize a selfish local utility function, whose exact shape is reverse engineered from the protocol description, through a stochastic subgradient method in which the link updates its persistence probability based on its transmission success or failure. We prove that existence of a Nash equilibrium is guaranteed in general. The minimum amount of backoff aggressiveness needed for uniqueness of Nash equilibrium and convergence of the best response strategy are established as a function of user density. Convergence properties and connection with the best response strategy are also proved for variants of the stochastic-subgradient-based dynamics of the game. Together with known results in reverse engineering TCP and BGP, this paper completes the recent efforts in reverse engineering the main protocols in layers 2-4.

We consider a distributed power control scheme for wireless ad hoc networks, in which each user announces a price that reflects compensation paid by other users for their interference. We present an asynchronous distributed algorithm for updating power levels and prices. By relating this algorithm to myopic best response updates in a fictitious game, we are able to characterize convergence using supermodular game theory. Extensions of this algorithm to a multichannel network are also presented, in which users can allocate their power across multiple frequency bands.

We consider a distributed power control scheme in a spread spectrum (SS) wireless ad hoc network, in which each user announces a price that reflects his current interference level. Given these prices, we present an asynchronous distributed algorithm for updating power levels, and provide conditions under which this algorithm converges to an optimal power allocation. We relate this algorithm to myopic best response updates of a fictitious game, and characterize the algorithm's convergence using supermodular game theory

A model for downlink wireless scheduling is studied, which takes into account both user-channel conditions and retransmissions with packet combining hybrid [automatic repeat request (ARQ)]. Quality-of-service (QoS) requirements for each user are represented by a cost function, which is an increasing function of queue length. The objective is to find a scheduling rule that minimizes the average cost over time. We consider two scenarios: 1) the cost functions are linear, and packets arrive to the queues according to a Poisson process and 2) the cost functions are increasing, convex, and there are no new arrivals (draining problem). In each case, we transform the system model into a different model that fits into a framework for stochastic scheduling developed by Klimov. Applying Klimov's results, we show that the optimal schedulers for the transformed models in both scenarios are specified by fixed priority rules. Applying the inverse transformation in each case gives the optimal scheduling policy for the original problem. The priorities can be explicitly computed, and in the first scenario, are given by simple closed-form expressions. For the draining problem, we show that the optimal policy never interrupts the retransmissions of a packet. We also show that a simple myopic scheduling policy, called the U'R rule, performs very close to the optimal scheduling policy in specific cases. We present numerical examples, which compare the performance of the optimal scheduling rule with several heuristic rules.