There are a few studies that focus on solution methods for finding a Nash equilibrium of zero-sum games. We discuss the use of Karmarkar’s interior point method to solve the Nash equilibrium problems of a zero-sum ga...There are a few studies that focus on solution methods for finding a Nash equilibrium of zero-sum games. We discuss the use of Karmarkar’s interior point method to solve the Nash equilibrium problems of a zero-sum game, and prove that it is theoretically a polynomial time algorithm. We implement the Karmarkar method, and a preliminary computational result shows that it performs well for zero-sum games. We also mention an affine scaling method that would help us compute Nash equilibria of general zero-sum games effectively.展开更多
We study the network routing problem with restricted and related links. There are parallel links with possibly different speeds, between a source and a sink. Also there are users, and each user has a traffic of some w...We study the network routing problem with restricted and related links. There are parallel links with possibly different speeds, between a source and a sink. Also there are users, and each user has a traffic of some weight to assign to one of the links from a subset of all the links, named his/her allowable set. The users choosing the same link suffer the same delay, which is equal to the total weight assigned to that link over its speed. A state of the system is called a Nash equilibrium if no user can decrease his/her delay by unilaterally changing his/her link. To measure the performance degradation of the system due to the selfish behavior of all the users, Koutsoupias and Papadimitriou proposed the notion Price of Anarchy （denoted by PoA）, which is the ratio of the maximum delay in the worst-case Nash equilibrium and in an optimal solution. The PoA for this restricted related model has been studied, and a linear lower bound was obtained. However in their bad instance, some users can only use extremely slow links. This is a little artificial and unlikely to appear in a real world. So in order to better understand this model, we introduce a parameter for the system, and prove a better Price of Anarchy in terms of the parameter. We also show an important application of our result in coordination mechanism design for task scheduling game. We propose a new coordination mechanism, Group-Makespan, for unrelated selfish task scheduling game with improved price of anarchy.展开更多
It has recently been established that quantum strategies have great advantage over classical ones in quantum games. However, quantum states are easily affected by the quantum noise resulting in decoherence. In this pa...It has recently been established that quantum strategies have great advantage over classical ones in quantum games. However, quantum states are easily affected by the quantum noise resulting in decoherence. In this paper, we investigate the effect of quantum noise on the restricted quantum game in which one player is restricted in classical strategic space, another in quantum strategic space and only the quantum player is affected by the quantum noise. Our results show that in the maximally entangled state, no Nash equilibria exist in the range of 0 〈 p ≤ 0.422 （p is the quantum noise parameter）, while two special Nash equilibria appear in the range of 0.422 〈 p 〈 1. The advantage that the quantum player diminished only in the limit of maximum quantum noise. Increasing the amount of quantum noise leads to the increase of the classical player＇s payoff and the reduction of the quantum player＇s payoff, but is helpful in forming two Nash equilibria.展开更多
文摘There are a few studies that focus on solution methods for finding a Nash equilibrium of zero-sum games. We discuss the use of Karmarkar’s interior point method to solve the Nash equilibrium problems of a zero-sum game, and prove that it is theoretically a polynomial time algorithm. We implement the Karmarkar method, and a preliminary computational result shows that it performs well for zero-sum games. We also mention an affine scaling method that would help us compute Nash equilibria of general zero-sum games effectively.
文摘We study the network routing problem with restricted and related links. There are parallel links with possibly different speeds, between a source and a sink. Also there are users, and each user has a traffic of some weight to assign to one of the links from a subset of all the links, named his/her allowable set. The users choosing the same link suffer the same delay, which is equal to the total weight assigned to that link over its speed. A state of the system is called a Nash equilibrium if no user can decrease his/her delay by unilaterally changing his/her link. To measure the performance degradation of the system due to the selfish behavior of all the users, Koutsoupias and Papadimitriou proposed the notion Price of Anarchy （denoted by PoA）, which is the ratio of the maximum delay in the worst-case Nash equilibrium and in an optimal solution. The PoA for this restricted related model has been studied, and a linear lower bound was obtained. However in their bad instance, some users can only use extremely slow links. This is a little artificial and unlikely to appear in a real world. So in order to better understand this model, we introduce a parameter for the system, and prove a better Price of Anarchy in terms of the parameter. We also show an important application of our result in coordination mechanism design for task scheduling game. We propose a new coordination mechanism, Group-Makespan, for unrelated selfish task scheduling game with improved price of anarchy.
基金Project supported by the National Natural Science Foundation of China （Grant No 10374025）.
文摘It has recently been established that quantum strategies have great advantage over classical ones in quantum games. However, quantum states are easily affected by the quantum noise resulting in decoherence. In this paper, we investigate the effect of quantum noise on the restricted quantum game in which one player is restricted in classical strategic space, another in quantum strategic space and only the quantum player is affected by the quantum noise. Our results show that in the maximally entangled state, no Nash equilibria exist in the range of 0 〈 p ≤ 0.422 （p is the quantum noise parameter）, while two special Nash equilibria appear in the range of 0.422 〈 p 〈 1. The advantage that the quantum player diminished only in the limit of maximum quantum noise. Increasing the amount of quantum noise leads to the increase of the classical player＇s payoff and the reduction of the quantum player＇s payoff, but is helpful in forming two Nash equilibria.
