Game Models And Mechanism Design For Mobile Internet

The rapid development of mobile Internet and diverse mobile applications have significantly changed the lifestyle of people.For example,WeChat has changed the communication mode of people,mobile payment is replacing cash payment and acts as the major payment method,and bike sharing has filled the gap of last-mile transportation.The reliable and efficient operation of mobile Internet relies on the cooperation of mobile nodes,which are the organizations or individuals with different optimization goals.There exist conflicts between individual goals and the overall system objective.The rational and selfish behaviors of mobile nodes would lead the system to an anarchic state,and degrade system performance.Therefore,we need to design efficient mechanisms to incentivize the cooperation among mobile nodes,resisting the strategic behaviors and guaranteeing that mobile Internet runs in an efficient and ordered way.In this thesis,we leverage the tools of game theory and mechanism design to analyze the interaction of rational and selfish mobile users and the impact on system performance due to strategic behaviours.We design efficient incentive mechanisms for four classical and representative applications in mobile Internet: dynamic spectrum redistribution,mobile crowdsensing,data marketplace,and cloud bandwidth management,to stimulate selfish mobile users to cooperate,achieving a win-win situation.We conduct extensive simulations to evaluate the performance of the proposed mechanisms.Specifically,the main contents and contributions of this thesis are summarized as follows.We first study dynamic spectrum redistribution to improve the utilization of spectrum resources,guaranteeing the reliable wireless connections in mobile internet.We summarize the technical challenges of designing a practical spectrum allocation mechanism,including the strategic behaviors of rational and selfish mobile users,spectrum spatial reusability,spectrum heterogeneity,resource demand diversity,and the hardness of calculating the optimal social welfare.Jointly considering the above five design challenges,we leverage the auction theory to design a series of combinatorial heterogeneous spectrum auctions.We consider two different strategic game models: single dimensional game model(i.e.,users can only manipulate one piece of private information)and multiple dimensional game model(i.e.,users can cheat on multiple pieces of private information).For single dimensional game model,we propose a strategy-proof and near-optimal combinatorial heterogeneous spectrum auction,namely SMASHER.In the multiple dimensional game model,for single minded users,we design a direct reveal combinatorial spectrum auction,namely AEGIS-SG,achieving strategy-proofness;for multi-minded users,we design an iterative ascending combinatorial spectrum auction,namely AEGIS-MP,reaching undominated strategies equilibrium.We theoretically prove that both AEGIS-SG and AEGIS-MP can achieve approximation social welfare.Based on two public data sets,we conduct extensive simulations for the designed spectrum auction mechanisms.The evaluation results show that compared with existing spectrum auctions,our mechanisms can achieve better performance in terms of social welfare,revenue,satisfaction ratio and spectrum utilization.We then investigate incentive mechanism design for mobile crowdsensing,to stimulate enough mobile users to participate in data collection campaign,ensuring the success of mobile crwodsensing system in the long term.We also summarize the major challenges of designing practical incentive mechanisms: the strategic behaviors of rational mobile users,the budget constraint of rewards,the uncertainty of task execution,and the computational complexity of achieving optimal solution.We jointly consider these challenges,and investigate two complementary optimization problems: under budget constraint,maximizing the coverage area of collected sensed data;within the requirement of task completion probability,minimizing data acquisition cost.For the first optimization problem,we propose BEACON,including a task allocation algorithm and a reward determination scheme.We theoretically prove that BEACON satisfies the property of strategy-proofness,budget feasibility,and achieves a constant approximation ratio in polynomial time.For the second optimization problem,we study the impact of task execution uncertainty on incentive mechanism design.We propose a fault-tolerance incentive mechanism,namely TORCH,for such unreliable scenarios.Our analyses show that TORCH mechanism can achieve near-optimal data acquisition cost,and resist the users' strategic behaviours over the probability of success.We deploy a mobile crowdsensing system to construct the noise map in the campus of Shanghai Jiao Tong University,and evaluate the performance of the designed incentive mechanisms based on the collected data.We further study data transactions in data marketplaces,encouraging data vendors to contribute data,breaking the barriers of data sharing and revealing the economic values behind data.We mainly focus on the problems of data acquisition and data pricing in sensed data marketplaces.To design a practical data acquisition mechanism,we need to consider the strategic behaviours of rational and selfish data contributors,the uncertainty of sensed data,and the hardness of computing optimal data trading profit.Jointly considering these challenges,we propose a profit-driven data acquisition mechanism for crowd-sensed data markets,called VENUS.To determine the optimal expected payment for each data acquisition point,we design a data procurement auction,achieving strategy-proofness and the minimum expected payment.For the problem of data pricing,we also need to consider three design challenges: the uncertainty of sensed data,the conflict between flexibility and economic robustness of the data pricing scheme,and revenue maximization under incomplete information.We design an online learning based data pricing mechanism,called ARETE,including two components: versioning algorithm and online data pricing mechanism.Versioning algorithm generates multiple versions with different data accuracies for the data community.Online data pricing mechanism adaptively learns data consumers' valuations,and dynamically determines the price of the data community.We theoretically prove that ARETE can prevent the arbitrage behaviours of data consumers,and achieve a constant competitive ratio in terms of revenue.We finally study cloud bandwidth management to improve the utilization of cloud bandwidth resources,guaranteeing the reliable big data transfer in mobile internet.We focus on two basic optimization problems in cloud bandwidth market: social welfare maximization and revenue maximization.We leverage auction theory to design a series of cloud bandwidth auctions for multiple bandwidth demand models,and propose the first family of Strategy-prOof Auction mechanisms for cloud bandwidth Reservation(SOAR).We then study revenue maximizing pricing from the perspective of a network provider.Designing a practical bandwidth pricing scheme requires us to guaranteeing the requirements of envy-freeness and arbitragefreeness.Considering the non-convexity of the revenue maximization and the lack of information about users' utilities,we propose a computationally efficient pricing framework to approximately maximize revenue in a range of network topology environments.We first study the case of a single link accessed by many users,and design a(1+?)-approximation pricing scheme with polynomial computational complexity.Based on dynamic programming,we then extend the pricing scheme for tollbooth network,preserving the(1+?)approximation ratio and the computational complexity.We show that when users have similar utilities,uniform pricing can achieve a good approximation ratio.The pricing framework can be extended to multiple time slots,enabling time-dependent pricing.