Convergence time to nash equilibria
Convergence Time to Nash Equilibria
Eyal Even-Dar ,Alex Kesselman,and Yishay Mansour
School of Computer Science,Tel-Aviv University,
{evend,alx,mansour}@cs.tau.ac.il.
Abstract.We study the number of steps required to reach a pure Nash
Equilibrium in a load balancing scenario where each job behaves self-
ishly and attempts to migrate to a machine which will minimize its cost.
We consider a variety of load balancing models,including identical,re-
stricted,related and unrelated machines.Our results have a crucial de-
pendence 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 mi-
grates to a machine which lowers its cost)and speci?c e?cient schedulers
(such as allowing the largest weight job to move?rst).
1Introduction
As the users population accessing Internet services grows in size and dispersion, it is necessary to improve performance and scalability by deploying multiple, distributed server sites.Distributing services has the bene?t reducing access la-tency,and improving service scalability by distributing the load among several sites.One important issue in such a scenario is how the user chooses the ap-propriate server.Similar problem occurs in the context of routing where the user has to select one of a few parallel links.For instance,many enterprise net-works are connected to multiple Internet service providers(ISPs)for redundant connectivity,and backbones often have multiple parallel trunks.
Users are likely to behave“sel?shly”in such cases,that is each user makes decisions so as to optimize its own performance,without coordination with the other users.Basically,each user would like to either maximize the resources allocated to it or,alternatively,minimize its cost.Load balancing and other resource allocation problems are prime candidates for such a“sel?sh”behavior.
A natural framework to analyze this class of problems is that of non-cooperative games,and an appropriate solution concept is that of Nash Equilibrium[22].A strategy for the users is at a Nash Equilibrium if no user can gain by unilater-ally deviating from its own policy.In this paper we focus on the load balancing problem.An interesting class of non-cooperative games,which is related to load balancing,is congestion games[24]and its equivalent model exact potential games[21].
Supported by the Deutsch Institute
Supported in part by a grant from the Israel Science Foundation.
2Eyal Even-Dar et al.
Traditionally in Computer Science research has been focused on?nding a global optimum.With the emerging interest in computational issues in game theory,the coordination ratio[17]has received considerable attention[2,7,8, 13,17,25].The coordination ratio is the ratio between the worst possible Nash equilibrium(the one with maximum social cost)and the social optimum(an optimal solution with the minimal social cost).One motivation is to show that the gap between a Nash Equilibrium and the optimal solution is in some cases not signi?cant,thus good performance can be achieved even without a centralized control.
In this work we are concerned with the time it takes for the system to con-verge to a Nash equilibrium,rather than the quality of the resulting allocation. The question of convergence to a Nash equilibrium has received signi?cant at-tention in the Game Theory literature(see[12]).Our approach is di?erent from most of that line of research in a few crucial aspects.First,we are interested in quantitative bounds,rather than showing a convergence in the limit.Second, we consider games with many players(jobs)and actions(machines)and study their asymptotic behavior.Third,We limit ourselves in this work to a subclass of games that arise from load balancing,for which there always exists a pure Nash equilibrium,and thus we can allow ourselves to study only deterministic policies.
Our Model.This paper deals with load balancing(see,[3]).Jobs(players) are allowed to select a machine to minimize their own cost.The cost that a job observes from the use of a machine is determined by the load on that machine. We consider weighted load functions,where each job has a corresponding weight and the load on a machine is sum of the weights of the jobs running on it.Until a Nash Equilibrium is reached,at least one job wishes to change its machine.In our model,similarly to the Elementary Stepwise System(see[23]),at every time step only one job is allowed to move,and a centralized controller decides which job would move in the current time step.By strategy we mean the algorithm used by the centralized controller for selecting which of the competing jobs would move.Due to the sel?sh nature of jobs,we assume that when a job migrates its observed load is strictly reduced,which we refer to as an improvement policy. We also consider the well known case of best reply policy,where each job moves to a machine in which its observed load is minimal.
Our Results.We assume that there are n jobs and m machines.We assume that K is the number of di?erent weights,W is the total weight of all the jobs and w max is the maximum weight assigned to a job.
For the general case of unrelated machines we show that the system always converges to a Nash equilibrium.This is done by introducing an order between the di?erent con?gurations and showing that when a job migrates we move to a“lower”con?guration in the order.Bounding the number of con?gurations
by min{[O(n
Km +1)]Km,m n}derives a general https://www.wendangku.net/doc/cd6677275.html,ing a potential base
argument we derive a bound of O(4W)for integer weights,where W is the worse case sum of the weights of the jobs.For the speci?c strategy that?rst
Convergence Time to Nash Equilibria3 selects jobs from the most loaded machine we can show an improved bound of O(mW+4W/m+w max).
In the simple case of identical machines and unrestricted assignments we show that if one moves the minimum weight job,the convergence may take an exponential number of steps.Speci?cally,the number of steps is at least,
(n
K
)K 2(K!)=?(
n
K
K
)
for K=m?1.In contrast,we show that if one moves the maximum weight job, and the jobs follow the best reply policy,a Nash Equilibrium is reached in at most n steps.This shows the importance of selecting of the“right”scheduling strategy.We also show that selecting the minimal weight job is“almost”the worst case for identical machines,by demonstrating that any strategy converges
in(n
K +1)K time steps.We also show that any strategy converges in O(W+n)
steps for integer weights.For the Random and FIFO strategies we show that they converge in O(n2)steps.
For restricted assignment and related machines we bound by O((W2S2max)/ the convergence time to -Nash,where no job can bene?t more than from unilaterally migrating to another https://www.wendangku.net/doc/cd6677275.html,ing the strategy that schedules ?rst jobs from the most loaded machine we can derive an improved convergence bound.Note that in our setting there always exists an min such that for any < min we have that any -Nash equilibrium is a Nash equilibrium.For example, in the case of identical machine with integer weights min=1.
For K integer weights,we are able to derive an interesting connection be-tween W and K,for the case of identical and related machines.We show that for any set V of K integer weights there is an equivalent set V of K integer weights such that the maximum weight in V is at most O(K(cS max n)4K)for some positive constant c.The equivalence guarantees that the relative cost of di?erent machines is maintained in all con?gurations.(In addition,we never need to compute V ,but rather it is only used in the convergence proofs.)The equivalence implies that W=O(Kn(cS max n)4K).Thus,all bounds that depend on W can depend on O(Kn(cS max n)4K).
Related https://www.wendangku.net/doc/cd6677275.html,chtaich[20]describes a class of non-cooperative games, which is related to load balancing.(In order to make the relations between the models clearer we use the load balancing terminology to describe his work.) The jobs(players)share a common set of machines(strategies).The cost of a job when selecting a particular machine depends only on the total number of jobs mapped to the machine(implicitly,all the weights are identical).However, each job has a di?erent cost function for each machine,this is in contrast to the load balancing model where the cost of all the jobs that map to the same machine is identical.It is shown that these games always possess at least one pure(deterministic)Nash Equilibrium and there exists a best reply improvement strategy that converges in polynomial time.However,for the weighted version of these games there are cases where a pure Nash Equilibrium does not exist. In contrast,we show that any improvement policy converges to a pure Nash Equilibrium in the load balancing setting.
4Eyal Even-Dar et al.
Our model is related to the makespan minimization problem since job moves can be viewed as a sequence of local improvements.The analysis of the approx-imation ratio of the local optima obtained by iterative improvement appears in
[5,6,26].The approximation ratio of a jump (one job moves at a time)iterative improvement has been studied in [10].In [6]it has been shown that for two iden-tical machines this heuristic requires at most n 2iterations,which immediately translates to an n 2upper bound for two identical machines with general weight setting in our model.In [26]they observe that the improvement strategy that moves the maximum weight job converges in n steps.
Some interesting related learning models are stochastic ?ctitious play [12],graphical games [19],and large population games [14].Uniqueness of Nash Equi-libria in communication networks with sel?sh users has been investigated in [23].An analysis of the convergence to a Nash Equilibrium in the limit appears in [1,4].
Paper organization:The rest of the paper is organized as follows.In Section 2we present our model.The analysis of unrelated,related and identical machines appears in Section 3,Section 4and Section 5,respectively.We conclude with Section 6.Due to space limitations some proofs are omitted and can found in
[9].
2Model Description
In our load balancing scenario there are m parallel machines and n independent jobs.Each job selects exactly one machine.
Machines Model.We consider identical,related and unrelated machines.We denote by S i the speed of M i .Let S min and S max denote the minimal and maximal speed,respectively.WLOG,we assume that S min =1.For identical and unrelated machines we have S i =1for 1≤i ≤m .
Jobs Model.We consider both restricted and unrestricted assignments of jobs to machines.In the unrestricted assignment case each job can select any machine while in the restricted assignment case each job J can only select a machine from a pre-de?ned subset of machines denoted by R (J ).
For a job J ,we denote by w i (J )the weight of J on machine M i (where i ∈R (J ))and by M (J,t )the index of the machine on which J runs at time t .When considering identical machines,each job J has a weight w (J )=w i (J ).We denote by W the maximal total weight of the jobs,that is W = n i =1max j ∈R (J i ){w j (J i )},and by w max =max i max j ∈R (J i ){w j (J i )}the maximum weight of a job.
We consider the following weight settings:General weight setting –the weights may be arbitrary real numbers.Discrete weight setting –there are K di?erent integer weights w 1≤...≤w K =w max .Integer weight setting –the weights are integers.
Load Model.We denote by B i (t )the set of jobs on machine M i at time t .The load of a machine M i at time t is the sum of the weights of the jobs that chose M i ,that is L i (t )= J ∈B i (t )w (J ),and its normalized load is T i (t )=L i (t )/S i .We also de?ne L max (t )=max i {L i (t )}and T max (t )=max i {T i (t )}.The cost of
Convergence Time to Nash Equilibria5 job J at time t is the normalized load on the machine M(J,t),i.e.,T M(J,t)(t). We de?ne the marginal load with respect to a job to be the load in the system when this job is removed.
System Model.The system state consists of the current assignment of the jobs to the machines.The system starts in an arbitrary state and each job has a full knowledge of the system state.A job wishes to migrate to another machine,if and only if,after the migration its cost is strictly reduced.Before migrating between machines,a job needs to receive a grant from the centralized controller.The controller has no in?uence on the selection of the target machine by a migrating job,it just gives the job a permission to migrate.The above is known in the literature as an Elementary Stepwise System(ESWS)(see[4,23]). Essentially,the controller serves as a critical section control.The execution is modeled as a sequence of steps and in each step one job changes its machine. Notice that if all jobs are allowed to move simultaneously,the system might oscillate and never ever reach a Nash Equilibrium.
Let A(t)be the set of jobs that may decrease the experienced load at time t by migrating to another machine.When a migrating job selects a machine which minimizes its cost(after the migration),we call to this best-reply policy. Otherwise,we call to this improvement policy.
The system is said to reach a pure(or deterministic)Nash Equilibrium if no job can bene?t from unilaterally migrating to another machine.The system is said to reach an -Nash Equilibrium if no job can bene?t more than from unilaterally migrating to another machine.We study the number of time steps it takes to reach a Nash Equilibrium(or -Nash equilibrium)for di?erent strategies of ESWS job scheduling.
Scheduling Strategies:We de?ne a few natural strategies for the centralized controller.The input at time t is always a set of jobs A(t)and the output is a job J∈A(t)which would migrate at time t.(For simplicity we assume each job has a unique weight,extension for unrelated machines is possible.)The speci?c strategies that we consider are:
Random:Selects J∈A(t)with probability1/|A(t)|.
Max Weight Job:Selects J∈A(t)such that w(J)=max J ∈A(T){w(J )}. Min Weight Job:Selects J∈A(t)such that w(J)=min J ∈A(T){w(J )}. FIFO:Let E(J)be the smallest time t such that J∈A(t )for every t ∈[t ,t].
FIFO selects J∈A(t)such that E(J)=min J ∈A(T){E(J )}.
Max Load Machine:Selects J∈A(t)such that T M(J,t)is maximal.
3Unrelated Machines
In this section we consider the unrelated machines case with the restricted as-signment.To show the convergence we de?ne a sorted lexicographic order of the vectors describing the machine loads as follows.Consider the sorted vector of the machine loads.One vector is called“larger”than another if its?rst(after the common beginning of the two vectors)load component is larger than the corresponding load component of the second vector.Formally,given two load
6Eyal Even-Dar et al.
vectors 1and 2,let s 1=sort ( 1)and s 2=sort ( 2)where sort ()returns a vector in the sorted order.We de?ne 1 2if s 1 s 2using a lexicographic ordering,i.e.,s 1[i ]=s 2[i ]for i
We demonstrate that the sorted lexicographic order of the load vector always decreases when a job migrates.To observe this one should note that only two machine are in?uenced by the migration of the job J at time t ,M i =M (J,t ),where job J was before the migration and M j =M (J,t +1),the machine J migrated to.Furthermore L i (t )>L j (t +1),otherwise job J would not have migrated.Also note that L i (t )>L i (t +1)since job J has left M i .Let L =max {L i (t +1),L j (t +1)}.Since L Claim 1.The sorted lexicographic order of the machine loads vector decreases when a job migrates. The above argument shows that any improvement policy converges to a Nash equilibrium,and gives us an upper bound on the convergence time equal to the number di?erent sorted machine loads vectors (which is trivially bounded by the number of di?erent system con?gurations). General Weights.In the general case,the number of di?erent system con-?gurations is at most m n ,which derives the following corollary. Corollary 1.For any ESWS strategy with an improvement policy,the system of multiple unrelated machines with restricted assignment reaches a Nash Equi-librium in at most m n steps. Discrete Weights.For the discrete weight setting,the number of di?erent weights is K .Let n i be the number of jobs with weight w i .The number of di?erent con?gurations of jobs with weight w i is bounded by m +n i m .Multiplying the number of con?gurations for the di?erent weights bounds the number of di?erent system con?gurations.Since,by de?nition, K i =1n i =n ,we can derive the following. Corollary 2.For any ESWS strategy with an improvement policy,the system of multiple unrelated machines with restricted assignment under the discrete weight setting reaches a Nash Equilibrium in at most K i =1 m +n i m ≤(c n Km +c )Km ,steps for some constant c >0. Integer Weights.To bound the convergence time for the integer weight setting,we introduce a potential function and demonstrate that it decreases when a job migrates.We de?ne the potential of the system at time t ,as P (t )= m i =14 L i (t ).After job J migrates from M i to M j then we have that L i (t )?1≥ Convergence Time to Nash Equilibria7 L j(t+1),since J migrated.Also,since we have integer weights,L i(t+1)≤L i(t)?1.Therefore,the reduction in the potential is at least, P(t)?P(t+1)=4L i(t)+4L j(t)?[4L i(t+1)+4L j(t+1)]≥4L i(t)/2≥2.(1) Since in the initial con?guration we have that P(0)≤4W we derive the following theorem. Theorem1.For any ESWS strategy with an improvement policy,the system of multiple machines under the integer weight setting reaches a Nash Equilibrium in4W/2steps. Next we show that this bound can be reduced to O(mW+m4W/m+w max) when using the Max Load Machine strategy. Theorem2.For Max Load Machine strategy with an improvement policy,the system of multiple machines under the integer weight setting reaches a Nash Equilibrium in at most4mW+m4W/m+w max/2steps. Proof.We divide the schedule into two phases with respect to the maximum load among the machines.The?rst phase continues until L max(t)≤W/m+w max, and then the second phase starts.At the start of the second phase,at time T,the potential is at most m4L max(T)≤m4W/m+w max.By(1),at every step the potential drops by at least two,therefore the length of the second phase is bounded by m4W/m+w max/2.Thus,it remains to bound the length of the ?rst phase,namely T.At any time t Two Weights.It is worth to note that for the special case of two di?erent weights there exists an e?cient ESWS strategy the converges in linear time. 4Related Machines In this section we consider the related machines.We?rst consider restricted assignments and assume that all jobs follow an improvement policy.We de?ne the potential of the system as follows: P(t)= m i=1 (L i(t))2 S i + n j=1 w2j S M(j,t) = m i=1 S i(T i(t))2+ n j=1 w2j S M(j,t) The following lemma shows that the potential drops after each improvement step. 8Eyal Even-Dar et al. Lemma 1.When a job of size w migrates from machine i to machine j at time t then P (t +1)?P (t )=2w (T j (t +1)?T i (t ))<0. We now like to bound the drop in the potential in each step.Clearly,if we are interested in -Nash equilibrium,then the drop is at least 2w > .Considering a Nash equilibrium,for integer weights and speeds the the drop is at least (S max )?2.Since the initial potential is bounded by W 2,we can derive the following Theorem. Theorem 3.For any ESWS strategy with an improvement policy,the system of multiple related machines with restricted assignment reaches an -Nash Equi-librium in at most O (W 2 )steps,and reaches a Nash Equilibrium,assuming both integer weights and speeds,in at most O (W 2S 2max )steps. For unrestricted assignment,by forcing to move the job from the most loaded machine we can improve the bound as follows. Theorem 4.Max Load Machine strategy with best reply policy reaches an -Nash Equilibrium in at most O (W mS max +nw max )steps. Discrete Weights.We show that for any K integer weight there is an equivalent model in which w max is bounded by O (K (S max n )4K ),and therefore W =O (Kn (S max n )4K ).This allows us to translate the results using W to the discrete weight model by replacing W by O (Kn (S max n )4K ).(We do not need to calculate the equivalent weights,since they are only used for the convergence time analysis.)We ?rst de?ne what we mean by an equivalent set of weights.De?nition 1.Two discrete set of weights w 1,...,w K and α1,...,αK are equiv-alent if for any two assignments,n 1,...,n K and 1,..., K we have K i =1n i w i > K i =1 i w i if and only if K i =1n i αi > K i =1 i αi ,and K i =1n i w i = K i =1 i w i if and only if K i =1n i αi = K i =1 i αi .(We require that both K i =1n i ≤n and K i =1 i ≤n .) Intuitively,the above de?nition says that as long as we use only comparisons,we can replace w 1,...,w K by α1,...,αK .Most important for us is that we can use in the potential the α’s rather than the w ’s.From the de?nition of an equivalent set of weights we can derive the following.Any strategy based on comparisons of job weights and machine loads and an improvement policy based on comparisons of machine loads (e.g.best reply)would produce the same sequence of job migrations starting from any initial con?guration. The following theorem,which is proven using standard linear integer pro-gramming techniques,bounds the size of the equivalent weights. Convergence Time to Nash Equilibria9 Theorem5.For any discrete set of weights w1,...,w K there exist an equiva-lent set of weightsα1,...,αK such thatαK≤K(cS max n)4K for some constant c>0. Unit Weight Jobs.We show that for unit weight jobs,there exists a strat-egy that converges in mn steps.The unit weight jobs is a special case of[20] with a symmetric cost function,where was derived an upper bound of O(mn2) on the convergence time of a speci?c strategy.We follow the proof of[20]and obtain a better bound in our model. Theorem6.There exists an ESWS strategy with an improvement policy such that the system of multiple related machines with restricted assignment reaches a Nash Equilibrium in at most mn steps in the case of unit weight jobs. The next theorem presents a lower bound of?(mn)on the convergence time of some ESWS strategy(di?erent from that of Theorem6). Theorem7.There exists an ESWS strategy with an improvement policy such that for the system of multiple related machines with unrestricted assignment, there exists a system con?guration that requires at least?(mn)steps to reach a Nash Equilibrium in the case of unit weight jobs. 5Identical Machines In this section we will show improved upper bounds that apply to identical ma-chines with unrestricted assignment.We also show a lower bound for K weights which is exponential in K.The lower bound is presented for the Min Weight Job policy.Clearly,this lower bound also implies a lower bound in all the other models.First we derive some general properties.The next observation states the minimal load cannot decrease. Observation1.At every time step the minimal load among the machines either remains the same or increases. Now we show that when a job moves to a new machine,this machine still remains a minimal marginal load machine for all jobs at that machine which have greater weight. Observation2.If job J has migrated to its best response machine M i at time t then M i is a minimal marginal load machine with regard to any job J ∈B i(t) such that w(J )≥w(J). Next we show that once a job has migrated to a new machine,it will not leave it unless a larger job arrives. Claim2.Suppose that job J has migrated to machine M at time t.If J∈A(t ) for t >t then another job J such that w(J )>w(J)switched to M at time t , and t 10Eyal Even-Dar et al. Next we present an upper bound on the convergence time of Max Weight Job strategy.(A similar claim(without proof)appears in[26].) Theorem8.The Max Weight Job strategy with best response policy,for the system of multiple identical machines with unrestricted assignment reaches a Nash Equilibrium in at most n steps. Proof.By Claim2,once the job has migrated to a new machine,it will not leave it unless a larger job arrives.But under Max Weight Job strategy only smaller jobs can arrive in the subsequent time steps,so each job stabilizes after the?rst migration,and the theorem follows. Now we present a lower bound for the Min Weight Job strategy. Theorem9.For the Min Weight Job strategy with best response policy,for the system of multiple identical machines with unrestricted assignment,there exists a system con?guration that requires at least(n K )K/(2(K!))steps to reach a Nash Equilibrium,where K=m?1. We also present a lower bound of n2/4on the convergence time of Min Weight Job and FIFO strategies for the case of two machines. Theorem10.For the Min Weight Job and FIFO strategies with best response policy,for the system of two identical machines with unrestricted assignment, there exists a system con?guration that requires at least n2/4steps to reach a Nash Equilibrium. Proof.Consider the following scenario.There are n/2classes of jobs C1,...,C n/2 and each class contains exactly2jobs and has weight w i=3i?1.Notice that a job in C i with weight w i=3i?1has weight equal to the total weight of all the jobs in the?rst i?1classes plus1. Initially,all jobs are located at the same machine.We divide the schedule into phases.Let C i j we denote all jobs from classes C j,...,C i.A k-phase is de?ned as follows.Initially,all jobs from classes C k1are located at one machine.During the phase these jobs,except one job from C k,migrate to the other machine.Thus, the duration of a k-phase is2k?1.It is easy to see that the schedule consists of the phases n/2,...,1for Min Weight Job strategy.One can observe that FIFO can generate the same schedule,if ties are broken using minimal weight. The following theorem shows a tight upped bound ofΘ(n2)on the conver-gence time of FIFO strategy. Theorem11.For FIFO strategy with best response policy,the system of multi-ple identical machines with unrestricted assignment reaches a Nash Equilibrium in at most n(n+1)/2steps. Similarly to FIFO,we bound the expected convergence tome of Random strategy by O(n2). Convergence Time to Nash Equilibria11 Theorem12.For Random strategy with best response policy,the system of mul-tiple identical machines with unrestricted assignment reaches a Nash Equilibrium in expected time of at most n(n+1)/2steps. Discrete Weights.For the discrete weight case,we demonstrate an upper bound of O((n/K+1)K)on the convergence time of any ESWS strategy,showing that the bound of Theorem9for the Min Weight Job is not far from the worst convergence time. Theorem13.For any ESWS strategy with best response policy,the system of multiple identical machines with unrestricted assignment under the discrete weight setting reaches a Nash Equilibrium in O((n/K+1)K)steps. Integer Weights.For the integer weight case,we show that the convergence time of any ESWS strategy is proportional to the sum of weights. Theorem14.For any ESWS strategy with best response policy,the system of multiple identical machines with unrestricted assignment under the integer weight setting reaches a Nash Equilibrium in W+n steps. Unit Weight Jobs.For the unit weight jobs,we present a lower bound on the convergence time of a speci?c strategy. Theorem15.There exists an ESWS strategy with the improvement policy for which the worst case number of steps for the system of multiple identical ma-chines with unrestricted assignment and unit weight jobs to reach a Nash Equi- })steps. librium is at least?(min{mn,n log n log m log log n 6Concluding Remarks In this paper we have studied the online load balancing problem that involves sel?sh jobs(users).We have focused on the number of steps required to reach a Nash Equilibrium and established the convergence time for di?erent strategies. While some strategies provably converge in polynomial time,for the others the convergence time might require an exponential number steps. In the real world,the convergence time is of high importance,since even if the system starts operation at a Nash Equilibrium,the users may join or leave dynamically.Thus,when designing distributed control algorithms for systems like the Internet,the convergence time should be taken into account. References 1. E.Altman,T.Basar,T.Jimenez and N.Shimkin,“Routing into two parallel links: Game-Theoretic Distributed Algorithms,”Journal of Parallel and Distributed Com-puting,pp.1367-1381,Vol.61,No.9,2001. 2. B.Awerbuh,Y.Azar,and Y.Richter,“Analysis of worse case Nash equilibria for restricted assignment,”unpublished manuscript. 12Eyal Even-Dar et al. 3.Y.Azar,“On-line Load Balancing Online Algorithms-The State of the Art,”chapter8,178-195,Springer,1998. 4.T.Boulogne,E.Altman and O.Pourtallier,“On the convergence to Nash equilib-rium in problems of distributed computing,”Annals of Operation research,2002. 5.P.Brucker,J.Hurink,and F.Werner,“Improving Local Search Heuristics for Some Scheduling Problems,Part I,”Discrete Applied Mathematics,65,pp.97-122,199 6. 6.P.Brucker,J.Hurink,and F.Werner,“Improving Local Search Heuristics for Some Scheduling Problems,Part II,”Discrete Applied Mathematics,72,pp.47-69,199 7. 7. A.Czumaj,P.Krysta and B.Vocking,“Sel?sh tra?c allocation for server farms,”STOC2002. 8. A.Czumaj and B.Vocking,“Tight bounds on worse case equilibria,”SODA2002. 9. E.Even-Dar,A.Kesselman and Y.Mansour,“Convergence Time To Nash Equilib-ria”,Technical Report,available at http://www.cs.tau.ac.il/?e vend/papers.html 10.G.Finn and E.Horowitz,“Linear Time Approximation Algorithm for Multipro-cessor Scheduling,BIT,vol.19,no.3,1979,pp.312-320. 11.Florian,M.and D.Hearn,“Network Equilibrium Models and Algorithms”,Net-work Routing.Handbooks in RO and MS,M.O.Ball et al.Editors,Elsevier,pp. 485-550.1995. 12. D.Fudenberg and D.Levine,“The theory of learning in games,”MIT Press,1998. 13. D.Fotakis,S.Kontogiannis,E.Koutsoupias,M.Mavronicolas,and P.Spirakis,“The Structure and Complexity of Nash Equilibria for a Sel?sh Routing Game,”In Proceedings of the29th ICALP,Malaga,Spain,July2002. 14.M.Kearns and Y.Mansour,“E?cient Nash Computation in Large Population Games with Bounded In?uence,”In Proceedings of UAI,2002. 15.Y.A.Korilis and https://www.wendangku.net/doc/cd6677275.html,zar,“On the Existence of Equilibria in Noncooperative Optimal Flow Control,”Journal of the ACM,Vol.42,pp.584-613,1995. 16.Y.A.Korilis,https://www.wendangku.net/doc/cd6677275.html,zar,and A.Orda.Architecting Noncooperative Networks. IEEE J.on Selected Areas in Communications,Vol.13,pp.1241-1251,1995. 17. E.Koutsoupias,C.H.Papadimitriou,“Worst-case equilibria,”STACS99. https://www.wendangku.net/doc/cd6677275.html, and V.Anantharam,“Optimal Routing Control:Game Theoretic Ap-proach,”Proceedings of the36rd IEEE Conference on Decision and Control,San Diego,CA,pp.2910-2915,Dec.1997. 19.M.Littman,M.Kearns,and S.Singh,“An e?cient exact algorithm for singly connected graphical games,”In Proceedings of NIPS,2002. https://www.wendangku.net/doc/cd6677275.html,chtaich,“Congestion Games with Player-Speci?c Payo?Functions,”Games and Economic Behavior,vol.13,pp.111-124,1996. 21. D.Monderer and L.S.Shapley,“Potential games,”Games and Economic Behavior, 14,pp.124-143,1996. 22.J.F.Nash,“Non-cooperative games,”Annals of Mathematics,Vol.54,pp.286-295, 1951. 23. A.Orda,N.Rom and N.Shimkin,“Competitive routing in multi-user communi-cation networks,”IEEE/ACM Transaction on Networking,Vol1,pp.614-627,1993. 24.R.W.Rosenthal,“A class of games possessing pure-strategy Nash equilibria,”International Journal of Game Theory,2,pp.65-67,1973. 25.T.Roughgarden and E,Tardos,“How Bad is Sel?sh Routing?,”In the Proceedings of the41st Annual IEEE Symposium on the Foundations of Computer Science,2000. 26.P.Schuurman and T.Vredeveld,“Performance guarantees of local search for mul-tiprocessor scheduling,”Proceedings IPCO,pp.370-382,2001. 27.S.Shenker,“Making greed work in networks a game-theoretic analysis of switch service disciplines,”IEEE/ACM Transactions on Networking,Vol.3,pp.819-831, 1995. 囚徒困境（prisoner's dilemma ）是博弈论的非零和博弈中具代表性的例子，反映个人最佳选择并非团体最佳选择。虽然困境本身只属模型性质，但现实中的价格竞争、环境保护等方面，也会频繁出现类似情况。 概念释义 囚徒困境（prisoner's dilemma ）：两个被捕的囚徒之间的一种特殊博弈，说明为什么甚至在合作对双方都有利时，保持合作也是困难的。 单次和多次重 单次发生的囚徒困境，和多次重复的囚徒困境结果不会一样。 在重复的囚徒困境中，博弈被反复地进行。因而每个参与者都有机会去“惩罚”另一个参与者前一回合的不合作行为。这时，合作可能会作为均衡的结果出现。欺骗的动机这时可能被受到惩罚的威胁所克服，从而可能导向一个较好的、合作的结果。作为反复接近无限的数量，纳什均衡趋向于帕累托最优。 囚徒困境的主旨 囚徒们虽然彼此合作，坚不吐实，可为全体带来最佳利益（无罪开释），但在资讯不明的情况下，因为出卖同伙可为自己带来利益（缩短刑期），也因为同伙把自己招出来可为他带来利益，因此彼此出卖虽违反最佳共同利益，反而是自己最大利益所在。但实际上，执法机构不可能设立如此情境来诱使所有囚徒招供，因为囚徒们必须考虑刑期以外之因素（出卖同伙会受到报复等），而无法完全以执法者所设立之利益（刑期）作考量。 固定局数的囚徒困境 试想像囚徒困境的情况进行十次。 我们可以合理地设想，如果囚徒第一次被对方指控，第二次这个囚徒也会指控对方。相反，如果第一次别人保持沉默，建立了互信的关系，你也会保持沉默，导致帕累托最优。 当然，两个囚徒都会有相似的想法，在第一局保持沉默，以期望建立互信关系，所以双方都会保持沉默。第二局时，双方亦应有相似的想法，继续保持沉默，以期继续在互信的情况下进行第三局，以致余下的八局。这种想法合理吗？ 在第十局时，互信的关系明显是没有意义的，因为十局已经完结，囚徒没有必要为维持互信的关系而沉默(没有第十一局)，所以第十局囚徒一定会背叛对方的，理由和只有一局囚徒困境一样。 问题是，既然大家都知道在第十局，无论如何对方都会背叛自己的，你在第九局保持沉默也是没有意思的，要知道，保持沉默(友好关系)的原因是为了希望下一局别人保持沉默。所以第九局双方都一定会背叛对方的。 下一个问题是，双方都有相同的想法，明知第九局对方会背叛自己，所以第八局保持沉默也是没有意思的，第七局亦然，如此类推，纳什均衡是十局都会互相背叛，建立互信关系是没有可能的。 只有在囚徒困境的局数大家都不肯定的情况下，上述的推论才不会发生，才会出现互相保持沉默的现象。 经典的囚徒困境 例子 1950年，由就职于兰德公司的梅里尔·弗勒德（Merrill Flood）和梅尔文·德雷希尔（Melvin Dresher）拟定出相关困境的理论，后来由顾问艾伯特·塔克（Albert Tucker）以囚徒方式阐述，并命名为“囚徒困境”。经典的囚徒困境如下： 警方逮捕甲、乙两名嫌疑犯，但没有足够证据指控二人入罪。于是警方分开囚禁嫌疑犯，分别和二人见面，并向双方提供以下相同的选择： 若一人认罪并作证检控对方（相关术语称“背叛”对方），而对方保持沉默，此人将即时获 1.纳什均衡：给出对方的策略，你所选的是最优的（至少不比其它策略差），如果每个局 中人都是这样，那么所构成的策略组合（对局），就称为纳什均衡。 2.效用：消费者偏好与收入之间的相互作用导致人们做出消费选择，效用则是人们从这种 消费选择中所获得的愉悦或满足。 3.边际产量：当其他要素不变时，可变要素增加一个单位所带来的总产量的增加量。 4.生产成本：经营一个企业，为达到利润最大化，必须支付一些资金来维持运营，如建造 厂房，采购机器及原料，雇用员工等支出都可视为厂家的生产成本。 5.帕累托标准：如果一种变化可以改善某些人的处境，同时对其他人都没有伤害。则这种 变化是好事，应该给予实行。 6.恩格尔系数：是食品支出总额占个人消费支出总额的比重。一个家庭收入越少，家庭收 入中或者家庭总支出中用来购买食物的支出所占的比例就越大，随着家庭收入的增加，家庭收入中或者家庭支出中用来购买食物的支出将会下降。恩格尔系数是用来衡量家庭富足程度的重要指标。 7.效用：消费者偏好与收入之间的相互作用导致人们做出消费选择，效用则是人们从这种 消费选择中所获得的愉悦或满足。 8.价格管制：是指政府对新药定价以及上市药品价格上涨实施严格的管制，企业不能自由 定价，而是由政府和制药企业谈判决定新药的价格。 9.软着陆：当一个国家经过强劲的经济增长后，仍维持缓和的增长，并未因此转入衰退， 即使“软着陆”。 10.硬着陆：一个国家的经济在高速增长的同时伴随着高度通货膨胀，使得经济迅速从增高 长直接走入低增长甚至衰退。 11.通货膨胀：平均物价水平持续上扬的状态，通货膨胀率通常是以消费者物价指数（CPI） 的变化率来表示。指数上升→物价上升，货币购买力下降。 12.再贴现率：一般商业银行可以直接向中央银行借贷的利率。所谓“贴现”：通过一定的 方式把发生在未来（或不同时间）的费用和效益转化为现值的方式就叫贴现。 13.机会成本：在资源一定的情况下，多生产一个单位的某种产品，就要以少生产若干单位 的另一种产品为代价。这种放弃若干单位另一种产品生产的代价，就是生产某种成品的机会成本。 14.需求价弹性价格：指在市场需求曲线的任何一点，价格每变动1%所导致的需求量变动 的百分比。它是衡量产品需求量对产品价格变动的敏感指标。 15.生产函数（生产成本）：企业在每个时期投入的各种生产要素的数量与获得的产出品的 数量之间的关系。 16.均衡及均衡价格：均衡：供给和需求达到平衡的状态。均衡价格：供需平衡时的价格。 有时被称为市场出清价格。 17.资源的概念及分类：指用于生产能满足人类需要的东西的那些物品或劳务。分类：自由 资源和经济资源 18.恩格尔曲线：某种商品的均衡购买量与消费者货币收入之间的关系。 1.药物需求与供给的特征：需求的特征：需求的不确定性、需求的最高优先性、需求的不 可替代性、需求的外部效应性、需求缺乏弹性、需求的被动性、独特的需求三方结构供给的特征：高质量性、高技术性、高投入性、高风险性、高回报性、高度集中性 2.影响药品需求的因素有哪些： （一）一般经济学因素：1.经济发展水平；2.价格水平（1）是否实施医疗保障制度（2）医疗保障制度下保障的范围（3）医疗保障制度的报销制度和自付比例等（二） 社会人口学因素（三）流行病学因素（四）临床医生和药师因素（五）医药技 浅析囚徒困境 囚徒困境是博弈论的非零和博弈中具代表性的例子，指反映个人最佳选择并非团体最佳选择。 囚徒困境的经典案例这里不再复述，让我们看一下身边的例子。囚徒困境在生活中最常见的表现就是挤公共汽车。从集体理性的角度来看,按次序上车是最有效率的做法,但是你挤我不挤,我就可能上得慢,所以每个人的最优战略都是挤,结果上车就更慢了。学生也同样遭遇囚徒困境：减轻中小学生过重负担喊了20多年，仅1985年至2000年的15年里，中央就下达“减负令”49次。但实际情况却是学生课业负担不但没减下来，反倒呈现出越演越烈之势，致使学生作业做到深夜、节假日仍然上课、业余时间奔忙于各种补习班等。可见“减负令”难以见效，中小学生课业负担不减反增。 又比如近年来炒得火热的楼市——“我没买房，结果房价还是涨了，因为我们无法保证大家都不买房。可是，我错了吗？没有。当初如果我买房了，房价下跌了呢？因为我不能保证大家都买房。人们根本不能预知在疾风暴雨式的调控之下，房价竟还能且调且涨。可是，我对了吗？没有。”这是一部眼下流行、充满黑色幽默的网络视频《北漂族的无房生活》中的经典对白。含泪的“调侃”折射出当下楼市的“囚徒困境”：买，难担高房价重负；不买，难受房价节节攀升的煎熬。 再看中国的法治之路。虽然法治让所有人都长期受益，甚至执政者自己也不例外，但是一个狭隘理性社会却偏偏无力支撑法治，以至最后每个理性人都不得不忍受法治缺位的非理性之苦。绝大多数中国人都是很识时务的理性人，不会故意给自己找茬，多数律师也不例外。不过，任何事物都有两面性，“理性”过了头也就成了非理性。这就是充斥着当今中国社会的“囚徒困境”：一种行为模式对于个人看起来是很理性的，但是对于个人构成的集体来说却是非理性的，最后对于每个人来说也是非理性的。我们都不敢站出来说话，对每个人来说都是很“理性”的一种行为方式，但最后的结果只能是让整个社会丧失法治。 但囚徒困境一定是坏事吗？就以囚徒困境的经典案例来说，作为一个比喻，我们会为囚犯不能合作而遗憾；可是如果它发生在现实中，我们就巴不得他们不能合作。 然而如果是多次博弈，人们就有了合作的可能性，囚徒困境就有可能破解，合作就有可能达成。连续的合作有可能成为重复的囚徒困境的均衡解，这也是博弈论上著名的“大众定理”的含义。但合作的可能性不是必然性。博弈论的研究表明，要想使合作成为多次博弈的均衡解，博弈的一方（最好是实力更强的一方）必须主动通过可信的承诺，向另一方表示合作的善意，努力把这个善意表达清楚，并传达出去。比如在楼市的囚徒困境中，政府能适当调控房价，给予购房者房价稳定合理的承诺，那么楼市的囚徒困境是有可能破解的。 在重复的囚徒困境中，博弈被反复地进行。因而每个参与者都有机会去“惩罚”另一个参与者前一回合的不合作行为。这时，合作可能会作为均衡的结果出 纳什均衡的存在性与多重性 对于数学家来说，一个数学概念的存在性与唯一性是特别需要加以关注的。这是因为，从形式逻辑角度看，如果某个事物并不存在，那么关于这个杜撰中的事物所给出的任何陈述或判断都可认为是正确的或错误的，因为对于不存在的事物来说，任何关于它的陈述或判断都不可能加以证伪。所以，倘若某个概念所对应的事物并不存在。那么，关于这个概念所给出的研究结论都必然不存在被证伪的可能。因而根据波普尔的证伪主义观点，这样的研究不具备科学上的意义。所以，我们在对任何新提出来的数学概念加以系统研究之前，首先需要弄清楚所研究的对象事物是否存在。 有许多被称为伪科学的东西，它们之所以被人们认为是“伪科学”的原因就是它们大肆谈论的东西并不存在或并未被证实其存在性。譬如，所谓的特异功能或“超灵学”并未得到证实，而UFO研究迷们至今也未能拿出一件存在球外生命的证据，所以，特异功能学或“超灵学”或“不明飞行物学”实际上都可被归入伪科学。除了存在性之外，概念事物的唯一性也是数学家们所关心的问题。从纯理论的兴趣上看，数学家们更多地是从审美的角度上看待概念的唯一性，但从波普尔的证伪主义哲学看，模型均衡解的唯一性关系到模型的预测功能，从而是科学理论应基本具有的特征。我们在第二章中曾指出，理论的预测功能是判别理论的科学性的准绳，而在第三章中，我们提出用纳什均衡作为模型的预测结果。按照这样的逻辑，一个自然的推论就是：模型能否具有科学意义取决于纳什均衡的唯一性。因为倘若纳什均衡不是唯一的，那么就难以根据模型对即将出现的结果加以预测，这种不确定性对于科学理论来说是不存在的。再加上前面谈到的存在性问题，我们可以这样说，模型能否具有科学意义取决于纳什均衡的存在性和唯一性，因为这正是科学理论所具有的基本性质。 博弈论目前发展的情况是这样的：已经证明在非常一般的情况下，纳什均衡是存在的，这是一个好的结果；但是，在许多情形，模型的纳什均衡解不是唯一的，这被称为纳什均衡的多重性问题。 纳什在1950年代证明了纳什均衡的存在性定理，为非合作博弈打下了重要基础。纳什的工作不仅解决了存在性问题，而且还为其后的博弈论研究提供了一整套方法论工具，即运用不动点定理(fixed point theorem)这一强有力的数学工具进行博弈论数学分析，这对后来的博弈论甚至数理经济学的发展产生了很大的影响。纳什均衡的多重性问题至今仍是困扰博弈论学者的一个主要问题。为了攻克这一问题，博弈论专家已经做出了许多贡献，如聚点均衡、相关均衡，子博弈精炼纳什均衡，颤抖手均衡，序贯均衡等概念的提出。但不幸的是，这类努力还未使得多重均衡问题完全得到解决，许多博弈论专家正在这一领域进行着不懈的工作。 本章将给出纳什均衡的存在性定理和讨论存在多重均衡情况下的均衡选择问题。 kano模型 目录 1简介 2内容分析 3需求分析 4操作意义 5优缺点 6满意度 7质量划分 8有关评价 简介 受行为科学家赫兹伯格的双因素理论的启发，东京理工大学教授狩野纪昭(Noriaki Kano)和他的同事Fumio Takahashi于1979年10月发表了《质量的保健因素和激励因素》(Motivator and Hygiene Factor in Quality)一文，第一次将满意与不满意标准引入质量管理领域，并于1982年日本质量管理大会第12届年会上宣读了《魅力质量与必备质量》﹙Attractive Quality and Must-be Quality﹚的研究报告。该论文于1984 年1月18日正式发表在日本质量管理学会(JSQC)的杂志《质量》总第l4期上，标志着狩野模式(Kano mode1)的确立和魅力质量理论的成熟。 2内容分析编辑 KANO模型定义了三个层次的顾客需求:基本型需求、期望型需求和兴奋型需求。这三种需求根据绩效指标分类就是基本因素、绩效因素和激励因素。 基本型需求是顾客认为产品“必须有”的属性或功能。当其特性不充足（不满足顾客需求）时，顾客很不满意；当其特性充足（满足顾客需求）时，无所谓满意不满意，顾客充其量是满意。 期望型需求要求提供的产品或服务比较优秀，但并不是“必须”的产品属性或服务行为有些期望型需求连顾客都不太清楚，但是是他们希望得到的。在市场调查中，顾客谈论的通常是期望型需求，期望型需求在产品中实现的越多，顾客就越满意;当没有满意这些需求时，顾客就不满意。 兴奋型需求要求提供给顾客一些完全出乎意料的产品属性或服务行为，使顾客产生惊喜。当其特性不充足时，并且是无关紧要的特性，则顾客无所谓，当产品提供了这类需求中的服务时，顾客就会对产品非常满意，从而提高顾客的忠诚度。 3需求分析 基本品质（需求） kano模型 也叫理所当然品质。如果此类需求没有得到满足或表现欠佳，客户的不满情绪会急剧增加，并且此类需求得到满足后，可以消除客户的不满，但并不能带来客户满意度的增加。产品的基本需求往往属于此类。对于这类需求，企业的做法应该是注重不要在这方面失分。 期望品质（需求） 也叫一元品质。此类需求得到满足或表现良好的话，客户满意度会显著增加，当此类需求得不到满足或表现不好的话，客户的不满也会显著增加。这是处于成长期的需求，客户、竞争对手和企业自身都关注的需求，也是体现竞争能力的需求。对于这类需求，企业的做法应该是注重提高这方面的质量，要力争超过竞争对手。魅力品质（需求） 此类需求一经满足，即使表现并不完善，也能到来客户满意度的急剧提高，同时此类需求如果得不到满足，往往不会带来客户的不满。这类需求往往是代表顾客的潜在需求，企业的做法就是去寻找发掘这样的需求，领先对手。 平新乔《微观经济学十八讲》第10讲 策略性博弈与纳什均衡 1．假设厂商A 与厂商B 的平均成本与边际成本都是常数，10A MC =，8B MC =，对厂商产出的需求函数是 50020D Q p =- （1）如果厂商进行Bertrand 竞争，在纳什均衡下的市场价格是多少？ （2）每个厂商的利润分别为多少？ （3）这个均衡是帕累托有效吗？ 解：（1）如果厂商进行Bertrand 竞争，纳什均衡下的市场价格是10B p ε=-，10A p =，其中ε是一个极小的正数。理由如下： 假设均衡时厂商A 和B 对产品的定价分别为A p 和B p ，那么必有10A p ≥，8B p ≥，即厂商的价格一定要高于产品的平均成本。其次，达到均衡时，A p 和B p 都不会严格大于10。否则，价格高的厂商只需要把自己的价格降得比对手略低，它就可以获得整个市场，从而提高自己的利润。所以均衡价格一定满足10A p ≤，10B p ≤。但是由于A p 的下限也是10，所以均衡时10A p =。给定10A p =，厂商B 的最优选择是令10B p ε=-，这里ε是一个介于0到2之间的正数，这时厂商B 可以获得整个市场的消费者。综上可知，均衡时的价格为10A p =，10B p ε=-。 （2）由于厂商A 的价格严格高于厂商B 的价格，所以厂商A 的销售量为零，从而利润也是零。下面来确定厂商B 的销售量，此时厂商B 是市场上的垄断者，它的利润最大化问题为： max pq cq ε>- ① 其中10p ε=-，()5002010q ε=-?-，把这两个式子代入①式中，得到： ()()0 max 1085002010εεε>----???? 解得0ε=，由于ε必须严格大于零，这就意味着ε可以取一个任意小的正数，所以厂商B 的利润为：()()500201010εε-?--????。 （3）这个结果不是帕累托有效的。因为厂商B 的产品的价格高于它的边际成本，所以 如果厂商B 和消费者可以为额外1单位的产品协商一个介于8到10ε-之间的价格，那么厂商B 的利润和消费者的剩余就都可以得到提高，同时又不损害厂商A 的剩余（因为A 的利润还是零）。 2．（单项选择）在下面的支付矩阵（表10-1）中，第一个数表示A 的支付水平，第二个数表示B 的支付水平，a 、b 、c 、d 是正的常数。如果A 选择“下”而B 选择“右”，那么： 表10-1 博弈的支付矩阵 . 卡诺模型 年提和他的同事FumioTakahashi1984于日本东京理工大学教授狩野纪昭(Noriaki Kano)。二维包含了两个维(Two-dimension Model)(Kano Mode]),又称作二维品质模型出了卡诺模型属,;从用户对产品的满意度进行考量度:从产品的品质角度考虑,属于客观的产品机能或功能于用户的主观感受。一维品质重要理论模型。其中的品质主要包括个四部分: 卡诺模型是产品品质创造。一(Attractive)、无差异品质(Indifference)(One-dimensional)、必要品质(Must-be)、魅力品质用户满意也因之提升；如不提供此维品质又称作线性品质、期望品质：当需求越得到满足,则会感到不满。一般而言品质越好，满意度越高，反之则受到负面评价；因此满意度需求, 与品质成正比。以获得更好的用户要求设计师聚焦在核心需求及其体验的优化,在设计策略中,一维品质满意度。产品的功能性、可用性、易用性及可扩展性都可以对一维品质造成影响。用户满意当需求得到优化时,必要品质是产品的基本要求。由于用户的满意度会有上限,必要品质要求设在设计策略中,;当不提供此需求时,用户满意度会大幅降低。度不一定会提升尽可能地满足用户的所有需求。因此设计策略要通过分,计师进行严谨而又细致的统筹工作析用户需求定义明确的产品功能。用户满意度不会,魅力品质是一种用户意想不到的品质。若不提供用户意想不到的需求魅力增幅远高于一维品质。,在设计策略中,降低;而若提供此需求,用户满意度则会有较大提升但往往成为品质是对产品创新及创新优良体验的追求。它在设计中不涵盖产品的所有模块,魅力品质需要建立产品的点睛之笔。每一个创新优良的体验都能为产品增加魅力值。因此,以发掘真正具有价值的品通过挖掘他们潜在的需求寻找设计的创新点,在目标用户的基础上, 质。不与用户满意度关联。无论,无差 囚徒困境和纳什均衡 当对手知道了你的决定之后，就能做出对自己最有利的决定------普林斯顿大学数学家约翰·纳什 囚徒困境 著名的“囚徒困境”，是纳什均衡理论的经典案例。 警方逮捕甲、乙两名嫌疑犯，但没有足够证据指控二人入罪。于是警方分开囚禁嫌疑犯，分别和二人见面，并向双方提供一下相同的选择：若有一人认罪并作证检控对方（背叛对方）而对方保持沉默，此人将立即获释，沉默者将判监禁十年。若两人都保持沉默(互相合作）则两人同时被判监禁半年。若两人都互相检举（互相背叛）则两人同时监禁两年。 如同博弈论的其他论证，囚徒困境假设每个囚徒都是利己的，激斗寻求自己的最大利益。囚徒到底应该选择哪一项策略，才能将自己的刑期缩至最短？两名囚徒由于相互隔离监禁，并不知道对方的选择。 试想困境中两名理性的囚徒会如何选择：若对方沉默，背叛会让我获释，所以对方会选择背叛。若对方背叛我，我也要指控对方才能得到较低的刑期，所以也是这样会选择背叛。二人面对的情况一样，所以二人的理想思考会得到相同的答案----选择背叛。背叛是两种策略之间的支配性策略。因此这场博弈中唯一可能达到的纳什均衡就是两人选择同时背叛对方，结果两人同时服刑两年。这场博弈的纳什均衡，显然不是最优的解决方案。如果两人都选择沉默，两人都只会被判刑半年。但根据以上假设，两人均为理性的个人，均衡状况回事两个囚徒都选择背叛。这就是“困境”所在。 寻找“纳什均衡点” 在现实生活中，纳什均衡理论影响着人们的行为。比如，在有些国家，报亭既无管理人员也不上锁，买报纸的人在自行放下前后拿走报纸。当然某些人可能取走报纸却不付钱（背叛）但由于大家意识到如果每个人都偷窃报纸（共同背叛）会造成以后不方便的有害结果，这种情形很少发生。 在商业活动中，也会出现各种各样的囚徒困境的例子。两个公司相互竞争，他们的广告互相影响，即一公司的广告较被顾客接受则会夺取对方的部分收入。但若二者同时期发出质量类似的广告，收入增加很少但成本增加。因此，这两家公司可以有两种选择:1.互相达成协议，减少广告的开支（合作）；2.增加广告开支，设法提升广告的质量，压倒对方（背叛）。若两家公司不信任对方，无法合作，背叛成为支配性策略时，它们将陷入广告战，而广告的成本的增加损害了两家公司的利益，这就是陷入囚徒困境。在现实中，要互相竞争的公司达成合作协议是比较困难的，多数会陷入囚徒困境中。 在自行车赛事或者长跑赛事中，也会出现一种博弈。例如，每年都会举行的的环法自行车赛事中有以下情况：选手们在到终点前的路程常以大部队方式前进，他们采取这种策略是为了令自己不至于太落后，又出力适中。最前方的选手在迎风时是最费力的，所以在前方是最差的策略。因此，在起先阶段，大家都不愿意在前面（共同背叛），所以这个时段，整体的速度很慢。而后，通常会有几位选手骑到前面，然后互相一段时间交换到最前面位置，以分担风的阻力（共同合作），使得全体的速度有所提升。而此时，如果前方的一人试图一直保持前方位置（背叛）其他选手以及大部队就会赶上（共同背叛）。通常情况是，在最前面次数最多的选手（合作），通常会到最后被落后的选手赶上，因为后面的选手骑在最前面选手的冲流中，比较不费力。 用科学的语言来描述纳什均衡，指的是在一组策略中，所有的参与者面临这样一种情况：当其他人不改变策略时，他此时的策略是最好的。在纳什均衡点上，每一个理性的参与者都不会有单独改变策略的冲动。 最早在腾讯的《在你身边为你设计》中看到这个模型，却一直没完全弄懂是怎么使用的，今天自己编造了一些数据，一步步做了一遍，总算理解了。 以下的引用部分引用自知乎。 1.卡诺模型简介-对用户满意度和需求进行分析的工具卡诺模型（KANC模型）是对用户需求分类和优先排序的有用工具，以分析用户需求对用户满意的影响为基础，体现了产品性能和用户满意之间的非线性关系。在卡诺模型中，将产品和服务的质量特性分为四种类型：⑴必备属性；⑵期望属性；⑶魅力属性；⑷无差异属性。 满意SiBi A 满意度低 KANO模型中的几种属性魅力属性：用户意想不到的，如果不提供此需求，用户满意度不会降低，但当提供此需求，用户满意度会有很大提升； 期望属性：当提供此需求，用户满意度会提升，当不提供此需求，用户满意度会降低； 必备属性：当优化此需求，用户满意度不会提升，当不提供此需求，用户满意度会大幅降低； 无差异属性：无论提供或不提供此需求，用户满意度都不会有改变，用户根本不在意； 反向属性：用户根本都没有此需求，提供后用户满意度反而会下降2.KANO模型的使用-问卷编制与数据处理 KANO问卷对每个质量特性都由正向和负向两个问题构成，分别测量用户在面对存在或不存在某项质量特性时的反应。需要注意： ①KANO可卷中与每个功能点相关的题目都有正反两个问题，正反问题之间的区别需注意强调，防止用户看错题意； ②功能的解释：简单描述该功能点，确保用户理解； ③选项说明：由于用户对“我很喜欢”“理应如此”“无所谓”“勉强接受” “我很不喜欢” 的理解不尽相同，因此需要在问卷填写前给出统一解释说明，让用户有一个相对一致的标准，方便填答。 我很喜欢：让你感到满意、开心、惊喜。 它理应如此：你觉得是应该的、必备的功能/ 服务。 无所谓：你不会特别在意，但还可以接受。 勉强接受：你不喜欢，但是可以接受。 我很不喜欢：让你感到不满意。 因此在编制问卷的时候，对每个项目都要有正反两道题来测，比如，“如果在中加入朋友圈功能，您怎样评价？”对应“如果在中去掉朋友圈功能，您怎样评价？” 均提供五个选项：我很喜欢、它理应如此、无所谓、勉强接受、我很不喜欢 那么每个用户对于某一个项目的态度必然落入下图表中的某个格子。而对所有的用户来说，共有5*5 即25种可能，统计每种可能下的用户人数占总人数的百分比，来填入下表。之后将下表中标A、O Ml、R、Q的格子中百分比相加，即可得到五种属性对应的百分比。从需求的角度来说，先满足M百分比最高的去掉R百分比最高的，再满足O百分比最高的，最后满足A百分比最高的。 浅析囚徒困境 令狐采学 囚徒困境是博弈论的非零和博弈中具代表性的例子，指反映个人最佳选择并非团体最佳选择。 囚徒困境的经典案例这里不再复述，让我们看一下身边的例子。囚徒困境在生活中最常见的表现就是挤公共汽车。从集体理性的角度来看,按次序上车是最有效率的做法,但是你挤我不挤,我就可能上得慢,所以每个人的最优战略都是挤,结果上车就更慢了。学生也同样遭遇囚徒困境：减轻中小学生过重负担喊了20多年，仅1985年至2000年的15年里，中央就下达“减负令”49次。但实际情况却是学生课业负担不但没减下来，反倒呈现出越演越烈之势，致使学生作业做到深夜、节假日仍然上课、业余时间奔忙于各种补习班等。可见“减负令”难以见效，中小学生课业负担不减反增。 又比如近年来炒得火热的楼市——“我没买房，结果房价还是涨了，因为我们无法保证大家都不买房。可是，我错了吗？没有。当初如果我买房了，房价下跌了呢？因为我不能保证大家都买房。人们根本不能预知在疾风暴雨式的调控之下，房价竟还能且调且涨。可是，我对了吗？没有。”这是一部眼下流行、充满黑色幽默的网络视频《北漂族的无房生活》中的 经典对白。含泪的“调侃”折射出当下楼市的“囚徒困境”：买，难担高房价重负；不买，难受房价节节攀升的煎熬。 再看中国的法治之路。虽然法治让所有人都长期受益，甚至执政者自己也不例外，但是一个狭隘理性社会却偏偏无力支撑法治，以至最后每个理性人都不得不忍受法治缺位的非理性之苦。绝大多数中国人都是很识时务的理性人，不会故意给自己找茬，多数律师也不例外。不过，任何事物都有两面性，“理性”过了头也就成了非理性。这就是充斥着当今中国社会的“囚徒困境”：一种行为模式对于个人看起来是很理性的，但是对于个人构成的集体来说却是非理性的，最后对于每个人来说也是非理性的。我们都不敢站出来说话，对每个人来说都是很“理性”的一种行为方式，但最后的结果只能是让整个社会丧失法治。 但囚徒困境一定是坏事吗？就以囚徒困境的经典案例来说，作为一个比喻，我们会为囚犯不能合作而遗憾；可是如果它发生在现实中，我们就巴不得他们不能合作。 然而如果是多次博弈，人们就有了合作的可能性，囚徒困境就有可能破解，合作就有可能达成。连续的合作有可能成为重复的囚徒困境的均衡解，这也是博弈论上著名的“大众定理”的含义。但合作的可能性不是必然性。博弈论的研究表明，要想使合作成为多次博弈的均衡解，博弈的一方（最好是实力更强的一方）必须主动通过可信的承诺，向另一方表示合 囚徒困境说明个人的理性选择不一定是集体的理性选择。（√） 子博弈精炼纳什均衡不是一个纳什均衡。（×） 若一个博弈出现了皆大欢喜的结局，说明该博弈是一个合作的正和博弈。（）博弈中知道越多的一方越有利。（×） 纳什均衡一定是上策均衡。（×） 上策均衡一定是纳什均衡。（√） 在一个博弈中只可能存在一个纳什均衡。（×） 在一个博弈中博弈方可以有很多个。（√） 在一个博弈中如果存在多个纳什均衡则不存在上策均衡。（√） 在博弈中纳什均衡是博弈双方能获得的最好结果。（×） 在博弈中如果某博弈方改变策略后得益增加则另一博弈方得益减少。（×）上策均衡是帕累托最优的均衡。（×） 因为零和博弈中博弈方之间关系都是竞争性的、对立的，因此零和博弈就是非合作博弈。 （×） 在动态博弈中，因为后行动的博弈方可以先观察对方行为后再选择行为，因此总是有利的。（×） 在博弈中存在着先动优势和后动优势，所以后行动的人不一定总有利，例如：在斯塔克伯格模型中，企业就可能具有先动优势。 囚徒的困境博弈中两个囚徒之所以会处于困境，无法得到较理想的结果，是因为两囚徒都不在乎坐牢时间长短本身，只在乎不能比对方坐牢的时间更长。 （×） 纳什均衡即任一博弈方单独改变策略都只能得到更小利益的策略组合。（√）不存在纯战略纳什均衡和存在惟一的纯战略纳什均衡，作为原博弈构成的有限次重复博弈，共同特点是重复博弈本质上不过是原博弈的简单重复，重复博弈的子博弈完美纳什均衡就是每次重复采用原博弈的纳什均衡。（√） 多个纯战略纳什均衡博弈的有限次重复博弈子博弈完美纳什均衡路径：两阶段都采用原博弈同一个纯战略纳什均衡，或者轮流采用不同纯战略纳什均衡，或者两次都采用混合战略纳什均衡，或者混合战略和纯战略轮流采用。（√） 如果阶段博弈G={A1, A2,…,An; u1, u2,…,un)具有多重Nash均衡，那么可能（但不必）存在重复博弈G(T)的子博弈完美均衡结局，其中对于任意的t 浅析囚徒困境 欧阳学文 囚徒困境是博弈论的非零和博弈中具代表性的例子，指反映个人最佳选择并非团体最佳选择。 囚徒困境的经典案例这里不再复述，让我们看一下身边的例子。囚徒困境在生活中最常见的表现就是挤公共汽车。从集体理性的角度来看,按次序上车是最有效率的做法,但是你挤我不挤,我就可能上得慢,所以每个人的最优战略都是挤,结果上车就更慢了。学生也同样遭遇囚徒困境：减轻中小学生过重负担喊了20多年，仅1985年至2000年的15年里，中央就下达“减负令”49次。但实际情况却是学生课业负担不但没减下来，反倒呈现出越演越烈之势，致使学生作业做到深夜、节假日仍然上课、业余时间奔忙于各种补习班等。可见“减负令”难以见效，中小学生课业负担不减反增。 又比如近年来炒得火热的楼市——“我没买房，结果房价还是涨了，因为我们无法保证大家都不买房。可是， 我错了吗？没有。当初如果我买房了，房价下跌了呢？因为我不能保证大家都买房。人们根本不能预知在疾风暴雨式的调控之下，房价竟还能且调且涨。可是，我对了吗？没有。”这是一部眼下流行、充满黑色幽默的网络视频《北漂族的无房生活》中的经典对白。含泪的“调侃”折射出当下楼市的“囚徒困境”：买，难担高房价重负；不买，难受房价节节攀升的煎熬。 再看中国的法治之路。虽然法治让所有人都长期受益，甚至执政者自己也不例外，但是一个狭隘理性社会却偏偏无力支撑法治，以至最后每个理性人都不得不忍受法治缺位的非理性之苦。绝大多数中国人都是很识时务的理性人，不会故意给自己找茬，多数律师也不例外。不过，任何事物都有两面性，“理性”过了头也就成了非理性。这就是充斥着当今中国社会的“囚徒困境”：一种行为模式对于个人看起来是很理性的，但是对于个人构成的集体来说却是非理性的，最后对于每个人来说也是非理性的。我们都不敢站出来说话，对每个人来说都是很“理性”的一种行为方式，但最后的结果只能是让整个社会丧失法 纳什均衡的存在性定理中的相关解释 教材（《经济博弈与应用》）p33，图2.1表明不动点是曲线()?f 与45o 线的交点。当函数()x f 定义在[]1,0∈x 区间上且因变量()x f y =的值域也为[]1,0区间时，如果()x f 是连续的，则必然存在不动点。 图2.1 [0,1]区间上的自变换函数的不动点 直接用来证明纳什存在性定理的不动点定理不是Brouwer 角谷静夫(Kakutani)不动点定理。 定义1 S 是凸的(Convex)当且仅当对任意的M M R y R x ∈∈,及满足1 ≤≤λ的λ，只要S x ∈和S y ∈，则有 ()S y x ∈-+λλ1 定义2 S 是闭的(Closed)当且仅当对每个收敛的序列()}{∞ =1j j x ，如果对每个 j 都有()S j x ∈，则有 ()S j x j ∈∞ →lim 定义3 R M 中的子集S 是开的(open)当且仅当它的补集R M /S 是闭的。 定义4 S 是有界的(bounded)当且仅当存在某个正数K 使得对S 中的每个元素x 都有 ∑ ∈≤M m m K x 定义5 当函数()x f 满足下述性质时，我们称其为凹的： ()()()()()[]n R x x x f x f x x f ∈∈-+≥-+212121, 1,0,11λλλλλ x x 第一季第二季第三季第四季)(x f x 1 如果当()1,0∈λ时上面的不等式严格成立，则称()x f 为严格凹的。一个函数 ()x f 是凸的当且仅当函数-()x f 是凹的；()x f 为严格凸函数当且仅当-()x f 为严 格凹函数。 拟凹函数是凹函数概念的一种推广，它包括了凹函数在内的一大类函数，而这类函数在经济学中有着广泛应用，关于拟凹函数的定义如下： 定义6 函数()x f 定义在R n 中的子集D 上，当且仅当()x f 满足如下性质时， ()x f 是拟凹的： ()()()()()2121,min 1x f x f x x f ≥-+λλ ∈λ[0,1] 显然，凹函数是拟凹的，但反过来并不成立，即拟凹函数不一定是凹函数。在下图中，函数()x f 是拟凹的，但不是凹的。 图 不是凹函数的拟凹函数 x 1 y x 2 x () x f 《经济博弈论》期末考试复习资料 第一章导论 1.博弈的概念： 博弈即一些个人、队组或其他组织，面对一定的环境条件，在一定的规则下，同时或先后，一次或多次，从各自允许选择的行为或策略中进行选择并加以实施，并从中各自取得相应结果的过程。它包括四个要素：参与者，策略，次序和得益。 2.一个博弈的构成要素： 博弈模型有下列要素：(1)博弈方。即博弈中决策并承但结果的参与者．包括个人或组织等：(2)策略。即博弈方决策、选择的内容，包括行为取舍、经济活动水平或多种行为的特定组合等。各博弈方的策略选择范围称策略空间。每个博弈方各选一个策略构成一个策略组合。(3)进行博弈的次序：次序不同一般就是不同的博弈，即使博弈的其他方面都相同。(4)得益。各策略组合对应的各博弈方获得的数值结果，可以是经济利益，也可以是非经济利益折算的效用等。 3.合作博弈和非合作博弈的区别： 合作博弈：允许存在有约束力协议的博弈；非合作博弈：不允许存在有约束力协议的博弈。主要区别:人们的行为互相作用时，当事人能否达成一个具有约束力的协议。 假设博弈方是两个寡头企业，如果他们之间达成一个协议，联合最大化垄断利润，并且各自按这个协议生产，就是合作博弈。 如果达不成协议，或不遵守协议，每个企业都只选择自己的最优产品（价格），则是非合作博弈。 合作博弈：团体理性（效率高，公正，公平） 非合作博弈：个人理性，个人最优决策（可能有效率，可能无效率） 4.完全理性和有限理性: 完全理性：有完美的分析判断能力和不会犯选择行为的错误。 有限理性：博弈方的判断选择能力有缺陷。 区分两者的重要性在于如果决策者是有限理性的，那么他们的策略行为和博弈结果通常与在博弈方有完全理想假设的基础上的预测有很大差距，以完全理性为基础的博弈分析可能会失效。所以不能简单地假设各博弈方都完全理性。 5.个体理性和集体理性： 个体理性：以个体利益最大为目标；集体理性：追求集体利益最大化。 第一章课后题：2、4、5 2.设定一个博弈模型必须确定哪几个方面? 设定一个博弈必须确定的方面包括:(1)博弈方，即博弈中进行决策并承担结果的参与者;(2)策略(空间)，即博弈方选择的内容，可以是方向、取舍选择，也可以是连续的数量水平等;(3)得益或得益函数，即博弈方行为、策略选择的相应后果、结果，必须是数量或者能够折算成数量;(4)博弈次序，即博弈方行为、选择的先后次序或者重复次数等;(5)信息结构，即博弈方相互对其他博弈方行为或最终利益 微观经济学作业 -从囚徒困境看纳什均衡和帕累托最优纳什均衡又称为非合作赛局平衡，是博弈论的一个重要概念。根据帕金的《经济学》一书对于纳什均衡的定义为：参与者A在给定B行为的条件下采取最好的行为，B也在给定A行为的条件下采取最好的行为。纳什均衡是一种策略组合，使得每个参与人的策略是对其他参与人策略的最优反应。设有n个局中人参与博弈，如果某情况下无一参与者可以独自行动而增加收益（即为了自身利益的最大化，没有任何单独的一方愿意改变其策略的），则此策略组合被称为纳什均衡。 帕累托最优，也称为帕累托效率，是指资源分配的一种理想状态，即假定固有的一群人和可分配的资源，从一种分配状态到另一种状态的变化中，在没有使任何人境况变坏的前提下，也不可能再使某些人的处境变好。换句话说，就是不可能再改善某些人的境况，而不使任何其他人受损。需要指出的是，帕累托最优只是各种理想态标准中的“最低标准”。也就是说，一种状态如果尚未达到帕累托最优，那么它一定是不理想的，因为还存在改进的余地，可以在不损害任何人的前提下使某一些人的福利得到提高。但是一种达到了帕累托最优的状态并不一定真的很“理想”。比如说，假设一个社会里只有一个百万富翁和一个快饿死的乞丐，如果这个百万富翁拿出自己财富的万分之一，就可以使后者免于死亡。但是因为这样无偿的财富转移损害了富翁的福利（假设这个乞丐没有什么可以用于回报富翁的资源或服务），所以进行这种财富转移并不是帕累托改进，而这个只有一个百万富翁和一个饿死乞丐的社会可以被认为是帕累托最优的。这里可以与古典功利主义的标准做一比较。按功利主义的标准，理想的状态是使人们的福利的总和最大化的状态。如果一个富翁损失很少的福利，却能够极大地增加乞丐的福利，使其免于死亡，那么社会的福利总和就增加了，所以从功利主义的角度看，这样的财富转移是一种改善，而最初的极端不平等状态则是不理想的，因为它的福利总和较低。可以看到，帕累托改进要求在提高某些人福利的时候不能减少任何一个人的福利，而功利主义则允许为了提高福利总和而减少一些人的福利。 囚徒困境的大意是囚徒困境是一个非零和博弈。大意是：一个案子的两个嫌疑犯被分开审讯，警官分别告诉两个囚犯，如果你招供，而对方不招供，则你将被判一年，而对方将被判刑十年；如果两人均招供，将均被判刑三年。如果两人均不招供，将最有利，只被判刑二年。于是，两人同时陷入招供还是不招供的两难处境。但两人无法沟通，于是从各自的利益角度出发，都依据各自的理性而选择了招供，这种情况就称为纳许均衡点。这时，个体的理性利益选择是与整体的理性利益选择不一致的。 论博弈论与纳什均衡的影响及局限 摘要：纳什均衡指的是这样一种战略组合，这种策略组合由所有参与人最优策略组成。即在给定别人策略的情况下，没有人有足够理由打破这种均衡。纳什均衡，从实质上说，是一种非合作博弈状态。同时，纳什均衡理论奠定了现代主流博弈理论和经济理论的根本基础。 关键词：纳什均衡、博弈论、影响、局限 引言：Nash平衡是指博弈中这样的局面，对于每个参与者来说，只要其他人不改变策略，他就无法改善自己的状况。Nash在证明了在每个参与者都只有有限种策略选择、并允许混合策略的前提下，Nash平衡一定存在。以两家公司的价格大战为例，Nash 平衡意味着两败俱伤的可能：在对方不改变价格的条件下，既不能提价，否则会进一步丧失市场；也不能降价，因为会出现赔本甩卖。于是两家公司可以改变原先的利益格局，通过谈判寻求新的利益评估分摊方案，也就是Nash平衡。纳什均衡理论正如克瑞普斯①书中所说，?在过去的一二十年内，经济学在方法论以及语言、概念等方面，经历了一场温和的革命，非合作博弈理论已经成为范式的中心……在经济学或者与经济学原理相关的金融、会计、营销和政治科学等学科中，现在人们已经很难找到不懂纳什均衡能够‘消费’近期文献的领域。? 博弈论是研究决策主体的行为发生直接相互作用时候的决 以及这种决策的均衡问题，具有斗争或竞争性质现象的数学理论和方法。也是运筹学的一个重要学科。博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。 一．博弈论的影响 一个完整的博弈应当包括五个方面的内容：第一，博弈的参加者，即博弈过程中独立决策、独立承担后果的个人和组织；第二，博弈信息，即博弈者所掌握的对选择策略有帮助的情报资料；第三，博弈方可选择的全部行为或策略的集合；第四，博弈的次序，即博弈参加者做出策略选择的先后；第五，博弈方的收益，即各博弈方做出决策选择后的所得和所失。 博弈论所研究的是理性的决策者之间冲突及合作的理论，可以为实际决策提供理论基础和方向指导。其最终追求结果是使博弈方达到利益最大化的均衡。 博弈论不仅仅存在于数学的运筹学中，也正在经济学中占据越来越重要的地位，但如果你认为博弈论的应用领域仅限于此的话，那你就大错了。实际上，博弈论甚至在我们的工作和生活中无处不在！在工作中，你在和上司博弈，也在和下属博弈，你也同样会跟其他相关部门人员博弈；而要开展业务，你更是在和你的客户以及竞争对手博弈。在生活中，博弈仍然无处不在。博弈论代表着一种全新的分析方法和全新的思想。诺贝尔经济学奖获得者包罗·萨缪尔逊如是说：要想在现代社会 Kano模型的数据统计分析 1、用户需求分类 1．1Kano模型 可以把基本品质、期望品质、和魅力品质理解为客户对产品的要求：功能要求---性价比/品牌效应---附加值/特殊性。 1．2用户需求分类 将每项用户需求按照Kano模型进行分类，即分为基本品质、期望品质和惊喜品质。先进行用户意见调查，然后对调查结果进行分类和统计。 1．2．1市场调查 对每项用户需求，调查表列出正反2个问题。例如，用户需求为“一键通紧急呼叫”，调查问题为“一键通紧急呼叫能随呼随通，您的感受如何?”以及“一键通紧急呼叫不能随呼随通，您的感受如何?”，每个问题的选项为5个，即满足、必须这样、保持中立、可以忍受和不满足。 注：√表示用户意见 1．2．2调查结果分类 通过用户对正反2个问题的回答，分析后可以归纳出用户的意见。例如，对某项用户需求，用户对正向问题的回答为“满足”，对反向问题的回答为“不满足”，则用户认为该项需求为“期望品质”。每项用户需求共5×5—25个可能结果。 基本品质、期望品质和惊喜品质是3种需要的结果。其他3种结果分别为可疑、反向和不关心，这是不需要的，必须排除。 (1)可疑结果（用户的回答自相矛盾）。可疑结果共2个，即用户对正反问题的回答均为“满足”或“不满足”。例如，对于“一键通紧急呼叫”，正向 问题为“一键通紧急呼叫能随呼随通，您的感受如何?”，用户回答是“满足”；反向问题为“一键通紧急呼叫不能随呼随通，您的感受如何?”，用户回答还是“满足”。这表明无论一键通紧急呼叫是否能随呼随通，用户都会满足，这显 然是自相矛盾的。出现可疑结果有2种可能：一是用户曲解了正反问题，二是用户填写时出现错误。统计时需要去除可疑结果。 (2)反向结果（用户回答与调查表设计者的意见相反）。正向问题表明产品 具有某项用户需求，反向问题表明不具备该用户需求，正向问题比反向问题具 有更高的用户满意，但用户回答却表明反向问题比正向问题具有更高的客户满 意度。例如，对用户需求“一键通紧急呼叫”，正向问题为“一键通紧急呼叫 能随呼随通，您的感受如何?”，用户回答为“不满足”，反向问题为“一键通紧急呼叫不能随呼随通，您的感受如何?”，用户的回答为“满足”，这显然与调查表设计者的意见相反。反向结果较多时，表明调查表的设计存在问题，需 要改进。 (3)不关心（用户对调查表所提出的问题漠不关心）。例如，对用户需求 “一键通紧急呼叫”，正向问题为“一键通紧急呼叫能随呼随通，您的感受如何?”，用户回答为“保持中立”，反向问题为“一键通紧急呼叫不能随呼随通，您的感受如何?”，用户回答还是“保持中立”，说明用户对“一键通紧急呼叫” 的存在与否，既不是满足，也不是不满足。统计时需要去除这类结果。 1．2．3调查结果统计 调查用户意见后，需要通过统计分析来判断每项用户需求属于哪种品质。 判定方法是：对调查结果进行统计，去除可疑、反向和不关心结果，根据基本、期望和惊喜3种品质统计结果的数量，确定用户需求属于哪种品质。例如，对用户需求“一键通紧急呼叫”，如通过统计调查结果表明，用户认为“一键通紧 急呼叫”是“基本品质”的最多，那么用户需求“一键通紧急呼叫”被确定为 基本品质。囚徒困境
纳什均衡
浅析囚徒困境与纳什均衡
纳什均衡不动点
kano模型
平新乔课后习题详解(第10讲--策略性博弈与纳什均衡)
卡诺模型
囚徒困境和纳什均衡
KANO模型详解
浅析囚徒困境与纳什均衡
博弈论复习题及答案(DOC)
浅析囚徒困境与纳什均衡
纳什均衡的存在性定理中的相关解释
《经济博弈论》期末考试复习解析
微经课程小论文-从囚徒困境看纳什均衡和帕累托最优
论博弈论与纳什均衡的影响及局限
Kano模型的数据统计分析
- 囚徒困境和纳什均衡
- 博弈论论文(囚徒困境案例纳什均衡案例完全信息静态博弈完全信息动态博弈)
- 囚徒困境的根源与启示
- 博弈论囚徒困境
- 博弈论经典案例“囚徒困境”及其实证分析
- 浅析囚徒困境与纳什均衡
- 纳什均衡与囚徒困境
- “囚徒困境”中非纳什均衡出现的可能性及其原因分析
- 囚徒困境的根源与启示
- 囚徒困境
- 《管理经济学(二)》-囚徒困境与纳什均衡的含义与应用 (2)
- 零和游戏与纳什均衡
- 浅析囚徒困境与纳什均衡
- 博弈论中的分析及启示囚徒困境
- 囚徒困境
- 浅析囚徒困境与纳什均衡
- 微经课程小论文-从囚徒困境看纳什均衡和帕累托最优
- 博弈论中的经典分析及启示囚徒困境
- 博弈论纳什均衡与穷途困境概念
- 第2章 纳什均衡与囚徒困境博弈