The Experts below are selected from a list of 9144 Experts worldwide ranked by ideXlab platform
Vincent W. S. Wong - One of the best experts on this subject based on the ideXlab platform.
-
hierarchical fog cloud computing for iot systems a computation offloading game
IEEE Internet of Things Journal, 2018Co-Authors: Hamed Shahmansouri, Vincent W. S. WongAbstract:Fog computing, which provides low-latency computing services at the network edge, is an enabler for the emerging Internet of Things (IoT) systems. In this paper, we study the allocation of fog computing resources to the IoT users in a hierarchical computing paradigm including fog and remote cloud computing services. We formulate a computation offloading game to model the competition between IoT users and allocate the limited processing power of fog nodes efficiently. Each user aims to maximize its own quality of experience (QoE), which reflects its satisfaction of using computing services in terms of the reduction in computation energy and delay. Utilizing a potential game approach, we prove the existence of a Pure Nash Equilibrium (NE) and provide an upper bound for the price of anarchy. Since the time complexity to reach the Equilibrium increases exponentially in the number of users, we further propose a near-optimal resource allocation mechanism and prove that in a system with ${N}$ IoT users, it achieves an $\epsilon$ -NE in ${O}$ ( ${N}/\epsilon$ ) time. Through numerical studies, we evaluate the users’ QoE as well as the Equilibrium efficiency. Our results reveal that by utilizing the proposed mechanism, more users benefit from computing services in comparison to an existing offloading mechanism. We further show that our proposed mechanism significantly reduces the computation delay and enables low-latency fog computing services for delay-sensitive IoT applications.
-
Hierarchical fog-cloud computing for IoT systems: A computation offloading game
IEEE Internet of Things Journal, 2018Co-Authors: Hamed Shah-mansouri, Vincent W. S. WongAbstract:Fog computing, which provides low-latency computing services at the network edge, is an enabler for the emerging Internet of Things (IoT) systems. In this paper, we study the allocation of fog computing resources to the IoT users in a hierarchical computing paradigm including fog and remote cloud computing services. We formulate a computation offloading game to model the competition between IoT users and allocate the limited processing power of fog nodes efficiently. Each user aims to maximize its own quality of experience (QoE), which reflects its satisfaction of using computing services in terms of the reduction in computation energy and delay. Utilizing a potential game approach, we prove the existence of a Pure Nash Equilibrium and provide an upper bound for the price of anarchy. Since the time complexity to reach the Equilibrium increases exponentially in the number of users, we further propose a near-optimal resource allocation mechanism and prove that in a system with $N$ IoT users, it can achieve an $\epsilon$-Nash Equilibrium in $O(N/\epsilon)$ time. Through numerical studies, we evaluate the users' QoE as well as the Equilibrium efficiency. Our results reveal that by utilizing the proposed mechanism, more users benefit from computing services in comparison to an existing offloading mechanism. We further show that our proposed mechanism significantly reduces the computation delay and enables low-latency fog computing services for delay-sensitive IoT applications.
-
Analysis of the Behavior of Electric Vehicle Charging Stations with Renewable Generations
2015Co-Authors: Woongsup Lee, Robert Schober, Lin Xiang, Vincent W. S. WongAbstract:Abstract—In this paper, we study the competitive interac-tions between electric vehicle charging stations (EVCSs) with renewable electricity generation facilities (REGFs). As electric vehicles (EVs) become more popular, there will be a competition between neighboring EVCSs to attract more EVs. Therefore, an EVCS is likely to set its electricity price by taking into account the competition with neighboring EVCSs, such that its revenue is maximized. We model the competitive interactions between EVCSs by using game theory. In this paper, we show that the game played by EVCSs is a supermodular game and there exists a unique Pure Nash Equilibrium for best response algorithms with arbitrary initial policy. Simulation results confirm the convergence of the game between EVCSs. The results also verify that it is beneficial for both EVs and EVCSs to have REGFs and all EVCSs will have REGFs in the long run. I
-
Electric Vehicle Charging Stations With Renewable Power Generators: A Game Theoretical Analysis
IEEE Transactions on Smart Grid, 2015Co-Authors: Woongsup Lee, Robert Schober, Lin Xiang, Vincent W. S. WongAbstract:In this paper, we study the price competition among electric vehicle charging stations (EVCSs) with renewable power generators (RPGs). As electric vehicles (EVs) become more pop- ular, a competition among EVCSs to attract EVs is inevitable. Thereby, each EVCS sets its electricity price to maximize its revenue by taking into account the competition with neighboring EVCSs. We analyze the competitive interactions between EVCSs using game theory, where relevant physical constraints such as the transmission line capacity, the distance between EV and EVCS, and the number of charging outlets at the EVCSs are taken into account.We showthat the game played by EVCSs is a supermodu- lar game and there exists a unique Pure Nash Equilibrium for best response algorithms with arbitrary initial policy. The electricity price and the revenue of EVCSs are evaluated via simulations, which reveal the benefits of having RPGs at the EVCSs.
Awi Federgruen - One of the best experts on this subject based on the ideXlab platform.
-
price competition under mixed multinomial logit demand functions
Social Science Research Network, 2013Co-Authors: Margaret Pierson, Gad Allon, Awi FedergruenAbstract:In this paper, we postulate a general class of price competition models with mixed multinomial logit demand functions under affine cost functions. In these models, the market is partitioned into a finite set of market segments. We characterize the Equilibrium behavior of this class of models in the case where each product in the market is sold by a separate, independent firm. We identify a simple and very broadly satisfied condition under which a Pure Nash Equilibrium exists and the set of Nash equilibria coincides with the solutions of the system of first-order-condition equations, a property of essential importance to empirical studies. This condition specifies that in every market segment, each firm captures less than 50% of the potential customer population when pricing at a specific level that, under the condition, is an upper bound for a rational price choice for the firm irrespective of the competitors' prices. We show that under a somewhat stronger, but still broadly satisfied, version of the above condition, a unique Equilibrium exists. We complete the picture by establishing the existence of a Nash Equilibrium, indeed a unique Nash Equilibrium, for markets with an arbitrary degree of concentration, under sufficiently tight price bounds. We discuss how our results extend to a continuum of customer types. A discussion of the multiproduct case is included. The paper concludes with a discussion of implications for structural estimation methods.
-
price competition under mixed multinomial logit demand functions
Management Science, 2013Co-Authors: Margaret Aksoypierson, Gad Allon, Awi FedergruenAbstract:In this paper, we postulate a general class of price competition models with mixed multinomial logit demand functions under affine cost functions. In these models, the market is partitioned into a finite set of market segments. We characterize the Equilibrium behavior of this class of models in the case where each product in the market is sold by a separate, independent firm. We identify a simple and very broadly satisfied condition under which a Pure Nash Equilibrium exists and the set of Nash equilibria coincides with the solutions of the system of first-order-condition equations, a property of essential importance to empirical studies. This condition specifies that in every market segment, each firm captures less than 50% of the potential customer population when pricing at a specific level that, under the condition, is an upper bound for a rational price choice for the firm irrespective of the competitors' prices. We show that under a somewhat stronger, but still broadly satisfied, version of the abov...
Fangzhen Lin - One of the best experts on this subject based on the ideXlab platform.
-
on computing optimal strategies in open list proportional representation the two parties case
National Conference on Artificial Intelligence, 2014Co-Authors: Ning Ding, Fangzhen LinAbstract:Open list proportional representation is an election mechanism used in many elections, including the 2012 Hong Kong Legislative Council Geographical Constituencies election. In this paper, we assume that there are just two parties in the election, and that the number of votes that a list would get is the sum of the numbers of votes that the candidates in the list would get if each of them would go alone in the election. Under these assumptions, we formulate the election as a mostly zero-sum game, and show that while the game always has a Pure Nash Equilibrium, it is NP-hard to compute it.
-
discovering theorems in game theory two person games with unique Pure Nash Equilibrium payoffs
Artificial Intelligence, 2011Co-Authors: Pingzhong Tang, Fangzhen LinAbstract:In this paper we provide a logical framework for two-person finite games in strategic form, and use it to design a computer program for discovering some classes of games that have unique Pure Nash Equilibrium payoffs. The classes of games that we consider are those that can be expressed by a conjunction of two binary clauses, and our program re-discovered Kats and Thisse@?s class of weakly unilaterally competitive two-person games, and came up with several other classes of games that have unique Pure Nash Equilibrium payoffs. It also came up with new classes of strict games that have unique Pure Nash equilibria, where a game is strict if for both player different profiles have different payoffs.
-
discovering theorems in game theory two person games with unique Pure Nash Equilibrium payoffs
International Joint Conference on Artificial Intelligence, 2009Co-Authors: Pingzhong Tang, Fangzhen LinAbstract:In this paper we provide a logical framework for using computers to discover theorems in two-person finite games in strategic form, and apply it to discover classes of games that have unique Pure Nash Equilibrium payoffs. We consider all possible classes of games that can be expressed by a conjunction of two binary clauses, and our program rediscovered Kats and Thisse's class of weakly unilaterally competitive two-person games, and came up with several other classes of games that have unique Pure Nash Equilibrium payoffs. It also came up with new classes of strict games that have unique Pure Nash equilibria, where a game is strict if for both player different profiles have different payoffs.
Jianwei Huang - One of the best experts on this subject based on the ideXlab platform.
-
Spatial Spectrum Access Game
IEEE Transactions on Mobile Computing, 2015Co-Authors: Xu Chen, Jianwei HuangAbstract: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.
-
Spatial Spectrum Access Game
arXiv: Networking and Internet Architecture, 2014Co-Authors: Xu Chen, Jianwei HuangAbstract: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 superior performance improvement over a random access algorithm.
-
spatial spectrum access game Nash equilibria and distributed learning
Mobile Ad Hoc Networking and Computing, 2012Co-Authors: Xu Chen, Jianwei HuangAbstract: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.
Yishay Mansour - One of the best experts on this subject based on the ideXlab platform.
-
how long to Equilibrium the communication complexity of uncoupled Equilibrium procedures
World Scientific Book Chapters, 2013Co-Authors: Sergiu Hart, Yishay MansourAbstract:AbstractWe study the question of how long it takes players to reach a Nash Equilibrium in uncoupled setups, where each player initially knows only his own payoff function. We derive lower bounds on the communication complexity of reaching a Nash Equilibrium, i.e., on the number of bits that need to be transmitted, and thus also on the required number of steps. Specifically, we show lower bounds that are exponential in the number of players in each one of the following cases: (1) reaching a Pure Nash Equilibrium; (2) reaching a Pure Nash Equilibrium in a Bayesian setting; and (3) reaching a mixed Nash Equilibrium. We then show that, in contrast, the communication complexity of reaching a correlated Equilibrium is polynomial in the number of players.
-
strong price of anarchy
Games and Economic Behavior, 2009Co-Authors: Nir Andelman, Michal Feldman, Yishay MansourAbstract:Abstract A strong Equilibrium is a Pure Nash Equilibrium which is resilient to deviations by coalitions. We define the strong price of anarchy (SPoA) to be the ratio of the worst strong Equilibrium to the social optimum. Differently from the Price of Anarchy (defined as the ratio of the worst Nash Equilibrium to the social optimum), it quantifies the loss incurred from the lack of a central designer in settings that allow for coordination. We study the SPoA in two settings, namely job scheduling and network creation. In the job scheduling game we show that for unrelated machines the SPoA can be bounded as a function of the number of machines and the size of the coalition. For the network creation game we show that the SPoA is at most 2. In both cases we show that a strong Equilibrium always exists, except for a well defined subset of network creation games.
-
convergence time to Nash Equilibrium in load balancing
ACM Transactions on Algorithms, 2007Co-Authors: Eyal Evendar, Alexander Kesselman, Yishay MansourAbstract:We study the number of steps required to reach a Pure Nash Equilibrium in a load balancing scenario where each job behaves selfishly and attempts to migrate to a machine which will minimize its cost. We consider a variety of load balancing models, including identical, restricted, related, and unrelated machines. Our results have a crucial dependence on the weights assigned to jobs. We consider arbitrary weights, integer weights, k distinct weights, and identical (unit) weights. We look both at an arbitrary schedule (where the only restriction is that a job migrates to a machine which lowers its cost) and specific efficient schedulers (e.g., allowing the largest weight job to move first). A by-product of our results is establishing a connection between various scheduling models and the game-theoretic notion of potential games. We show that load balancing in unrelated machines is a generalized ordinal potential game, load balancing in related machines is a weighted potential game, and load balancing in related machines and unit weight jobs is an exact potential game.
-
strong price of anarchy
Symposium on Discrete Algorithms, 2007Co-Authors: Nir Andelman, Michal Feldman, Yishay MansourAbstract:A strong Equilibrium (Aumann 1959) is a Pure Nash Equilibrium which is resilient to deviations by coalitions. We define the strong price of anarchy to be the ratio of the worst case strong Equilibrium to the social optimum. In contrast to the traditional price of anarchy, which quantifies the loss incurred due to both selfishness and lack of coordination, the strong price of anarchy isolates the loss originated from selfishness from that obtained due to lack of coordination. We study the strong price of anarchy in two settings, one of job scheduling and the other of network creation. In the job scheduling game we show that for unrelated machines the strong price of anarchy can be bounded as a function of the number of machines and the size of the coalition. For the network creation game we show that the strong price of anarchy is at most 2. In both cases we show that a strong Equilibrium always exists, except for a well defined subset of network creation games.
