拥塞与路由
Congestion &
Routing
n
问题描述 Problem Description
拥塞现象几乎触目可及。日常交通会因车辆过多、突发车祸甚至是管理不善导致拥塞。Internet会因突发流量、物理资源崩溃甚至人为管理失误导致网络拥塞直至瘫痪。另外诸如其它研究小组提到的酒吧问题、自私路由等都是拥塞各个层面的表现。拥塞会导致系统性能的急剧下降，因此如何较好的避免拥塞是个值得研究的课题。我们认为避免拥塞的前提是预测，即要能较早的感知拥塞产生，从而较早的进行拥塞控制，才能有效的避免网络崩溃，而一旦网络进入剧烈拥塞的状态，任何改善策略的效果都是有限的，也就是说必须牺牲非常大的资源或性能才能恢复网络的性能。
基于最近复杂网络研究中对各种现实网络诸如Internet、WWW、Airport-net的拓扑结构的研究成果，我们提出了一类可以感知拥塞的路由策略。通过对网络局部流量信息的收集并结合最短路径算法，新的路由算法可以提早感知网络是否产生了局部拥塞，并通过在拥塞等待时间和最短路径传输时间之间进行权衡折中从而更有效的传输数据包。对于另外一些通过改变网络结构来缓解拥塞或者提高传输效率的方法，我们认为几乎不可能去改变已有网络的拓扑结构，而实施新的路由算法相对更容易实现，因此具有更大的现实意义。
n
参考文献 References
Ø
Congestion & Routing
[1]
Guimerà,
Díaz-Guilera, Arenas, Communication and optimal hierarchical networks, 2001,
Physica A, 299, 247-252.
[2]
Goh
K I, Kahng B, Kim D, Universal Behavior of Load Distribution in Scale-Free
Networks, Physical Review Letters, 87(27): 278701.
[3]
Guimerà,
Arenas A, Díaz-Guilera, et al., Optimal network topologies for local search
with congestion, 2002, Physical Review Letters, 89, 248701.
[4]
Holme
P, Congestion and centrality in complex networks, 2003, Advances in Complex
Systems 6, 163-176.
[5]
Arenas
A, Cabrales A, Díaz-Guilera A, et al., Search and congestion in complex
networks, 2003, Lecture Notes in Physics: Statistical mechanics of complex
networks, XVIII Sitges conference on statistical mechanics, 175-194.
[6]
Brajendra
K Singh, Neelima G, Congestion and decongestion in a communication network,
arXiv:cond-mat/0404353.
[7] Arrowsmith D K, Mondragn R J,
Pittsy J M, et al., Phase transitions in packet traffic on regular networks: a
comparison of source types and topologies, 2004.
[8] Pablo E, Jesus G G, Yamir M,
Improved routing strategies for Internet traffic delivery, 2004, Physical
Review E 70: 056105.
[9]
Pablo
E, Jesus G G, Yamir M, Dynamics of jamming transitions in complex networks, arXiv:cond-mat/0412053.
[10]
Krause
W, Glauche I, Sollacher R, et al., Impact of network structure on the performance
of wireless multihop ad hoc communication, 2004, Physica A, 338, 633-658.
[11]
Glauche
I, Krause W, Sollacher R, et al., Distributive routing & congestion control
in wireless multihop ad hoc communication networks, 2004, Physica A, 341,
677-701.
[12]
Toroczkai
Z, Bassler K E, Jamming is limited in scale-free systems, 2004, Nature, 428,
716.
[13]
Toroczkai
Z, Kozma B, Bassler K E, Gradient Networks, cond-mat/0408262.
[14]
Toroczkai
Z, Complex networks, the challenge of Interaction topology,
[15]
Park
K, Lai Y C, Zhao L, et al., Jamming in complex gradient networks, 2005,
Physical Review E, 71, 065105.
[16] Yan G, Zhou T,
Hu B, et al., Efficient routing on complex network, 2005, cond-mat/0505366.
[17]
Zhao
L, Lai Y C, Park K, et al., Onset of traffic congestion in complex networks,
2005, Physical Review E, 71, 026125.
[18]
Krause
W, Sollacher R, Glauche I, Optimized network structure and routing metric in
wireless multihop ad hoc communication, 2005, cond-mat/0503010.
n
相关链接 Related Links
n
我们的研究 Our Researches
²
提出一种拥塞避免策略，针对各种不同网络拓扑结构，表明该路由策略可以更大的提高网络吞吐量。
Zhen Yi Chen, Xiao Fan Wang, Effects
of network capacity under variations of network structure and routing strategy,
2005, ICNSC06 to appear.
摘要：吞吐量主要描述了网络在没有拥塞的情况下能够达到的最大端到端流量，这是描述网络性能的一个非常重要的指标。本文研究了不同网络结构以及不同路由算法对网络吞吐量产生的影响。结果表明，网络结构对网络吞吐量有着本质性的影响，网络越趋于均匀，网络吞吐量将越大。通过将最短路径路由算法改为可以感知拥塞的一类新的路由算法，我们发现新的路由算法可以大幅增加网络的吞吐量。
Abstract：Network capacity, characterized by the
maximum end-to-end traffic flow the network is able to handle without
overloading, is an important index for network performance of real
communication systems. In this paper, we estimate the effects of variations of
network structure and routing strategy on network capacity. Simulation results
reveal that the capacity depends on the underlying network structure and the
capacity increases as the network becomes more homogeneous. It is also observed
that the network capacity is greatly enhanced when the new traffic awareness
routing strategy is adopted in each network structure.
²
提出一种拥塞避免策略，并针对具有不同聚类系数的无尺度网络验证了该算法的有效性。
Zhen
Yi Chen, Xiao Fan Wang, A Congestion Awareness Routing Strategy for Scale-Free
Networks with Tunable Clustering, Physica
A, to appear, 2005.
摘要：考虑到最短路径路由算法不能感知网络的拥塞状况，本文通过对网络局部信息进行收集，并将该信息与网络的最短路径信息相结合，提出了一种通过调节参数可以感知拥塞信息并可以在传输时间和等待时间之间进行权衡的新的路由策略。针对具有不同聚类系数的无尺度网络，我们验证了新的路由算法在不同拥塞状态下的有效性，并且可以得到该路由算法的一个最优参数设置。我们还发现这个最优值几乎和网络的聚类系数无关，然而当网络聚类系数变大时，和最短路径路由算法相比教，新的路由算法的有效性随之增大。
Abstract：By incorporating local traffic
information into the basic shortest path routing policy, we propose a
congestion awareness routing strategy with a tunable parameter. We investigate
the effectiveness of the proposed routing strategy for scale-free networks with
different clustering coefficients and in different congestion phases. We find
that there exists an optimal value for the tunable parameter in the congestion
awareness strategy. Though the optimal value increases slowly as the traffic in
the network becomes heavier, it is almost independent of the clustering
property of the scale-free network. Furthermore,
the performance upgrade of the new routing strategy compared with the basic
shortest path routing policy becomes more significant as the network becomes
more clustered.
²
通过对网络中关键hub节点的控制，表明只需要对网络中很少的节点进行控制就可以最大程度的缓解网络拥塞。
陈振毅, 汪小帆, 无尺度网络中的拥塞及其控制, 系统工程学报, 2005, 20(2): 132-138.
摘要：实际网络经常承受超负荷的流量，由于网络节点自身容量或者处理速度的限制，往往导致严重的拥塞产生,使得网络具有较大的时延并且性能下降。已有研究表明，实际的通信网络具有无尺度特征。本文研究了无尺度网络模型中的拥塞现象及其控制方法，结果表明网络节点的性质和网络的无尺度特性均对拥塞现象的产生和控制有显著影响。因此,仅需要对一些最关键的节点加以控制作用,就可以得到类似控制所有节点所产生的控制效果,从而节约成本。
Abstract：Real networks often experience over-loaded
traffic, congestion will occur due to the limited capacity and process rate of
network nodes, which will cause network experience serious
delays and performance degrade. It has been shown that real communication networks are scale-free. In this paper, the congestion and
decongestion problems in scale-free networks are studied. Simulation results
show that congestion and decongestion in a scale-free network are significantly
influenced by both the property of the nodes and the scale-free feature of the
network Thus, it would be cost saving by only applying control strategy on some
most important hub nodes while achieves similar control effect.
拥塞博弈
Congestion Game
n
问题描述 Problem Description
当今社会中存在着各种各样的拥塞问题，如交通拥塞、Internet拥塞等，拥塞博弈(congestion game)是实际系统中各种拥塞现象的简化形式。它们准确地模拟了交通、经济、网络、生态以及其它领域中，面对有限的资源相互独立的agents之间的竞争行为。其中具有代表性的是酒吧问题（bar
problem）及其简化模型少数者博弈（minority game)。由于个体的决定可以影响整个系统的合作效应，这两种模型引起了人们的极大关注。 在agents的行为是自私的前提下，如何提出有效的控制策略，提高整个系统的性能一直以来是物理学家和经济学家致力解决的问题。
n
参考文献 References
Ø
Congestion Game
[1]
Milchtaich I, Social optimality and cooperation in
nonatomic congestion games, Journal of Economic Theory, 2004, 114: 56–87.
[2]
Holzman R, Law-yone N, Network structure and strong equilibrium in
route selection games, Mathematical Social Sciences, 2003, 46: 193-205.
[3]
Milchtaich I, Generic uniqueness of equilibrium in large
crowding games, Mathematics of Operations Research, 2000, 25: 349–364.
[4]
Fudenberg
D, Levine D K, The theory of learning in games, MIT Press, Cambridge, MA, 1998.
[5]
Claus
C, Boutilier C, The dynamics of reinforcement learning in cooperative
multiagent systems, Proceedings of the Fifteenth National Conference on Artificial
Intelligence (AAAI-98), 1998, 746-752.
[6]
Konishi H, Le Breton M, Weber S, Equilibrium in a model with
partial rivalry, Journal of Economic Theory, 1997, 72: 225-237.
[7]
Holzman R, Law-yone N, Strong equilibrium in congestion games,
Games and Economic Behavior, 1997, 21: 85-101.
[8]
Milchtaich I, Congestion games with player-specific payoff functions, Games and
Economic Behavior, 1996, 13: 111-124.
[9]
Neumann
J, Morgenstern O, Theory of games and economic behavior, Princeton University
Press, Princeton, NJ, 1994.
[10] Arnott R, Small K, The
economics of traffic congestion, American Scientist, 1994, 82: 446-455.
[11] Fudenberg D, Tirole J, Game
theory.
[12] Myerson R B, Game theory: analysis
of conflict,
[13] Mahmassani H,
Jayakrishnan R, System performance and user response under real-time
information in a congested traffic corridor, Transportation Research, 1991,
[14] Godin J G J,
Keenleyside M H A, Foraging on patchily distributed prey by a cichlid fish
(teleostei, cichlidae): a test of the ideal free distribution theory, Animal Behavior, 1984, 32:
120-131.
[15] Milinsky M, An evolutionary stable
feeding strategy in sticklebacks, Zeitschrift
für.Tierpsychologie, 1984, 51:36-40.
[16] Harper D G C,
Competitive foraging in mallards: ideal free ducks, Animal Behavior, 1982, 30:
575-584.
[17] Rosenthal R, A class
of games possessing pure strategy Nash equilibria, The International Journal of
Game Theory, 1973, 2: 65-67.
[18] Nash J,
Non-cooperation games, Annals of Mathematics, 1951, 54(1): 286-295.
Ø
El Farol Bar Problem
[19] Challet D, Marsili M, Ottino G,
Shedding light on El Farol, Physica A, 2004, 332(3-4): 469-482.
[20] Zambrano E, The interplay between
analytics and computation in the study of congestion externalities: the case of
the El Farol Problem, Journal of Public Economic Theory, 2004, 6(2): 375-395.
[21] Bell A, Sethares W, Bucklew J,
Coordination failure as a source of congestion in information networks, IEEE
Transactions on Signal Processing, 2003, 51(3): 875 -885.
[22] Leady J, If nobody is going there
anymore because it’s too crowded, then who is going? Experimental evidence of
learning and imitation in the El Farol coordination game, Manuscript,
http://web.centre.edu/leady/docs/ElFarol2002Nov14.pdf
[23] Farago J, Greenwald A, Hall K,
Fair and efficient solutions to the Santa Fe Bar Problem, Proceedings of Grace Hopper Celebration of Women in
Computing 2002, Vancouver, 2002, 27-33.
[24] Greenwald A,
Jafari A, Ercal G, et al., On no-regret learning, Nash equilibrium, and
fictitious play, Proceedings of Eighteenth International Conference on Machine
Learning, Williamstown, 2001, 226–233.
[25] Bell A, Sethares W, Avoiding
global congestion using decentralized adaptive agents, IEEE Transactions on
Signal Processing, 2001, 49(11): 2873 –2879.
[26] Hart S, Mas-Colell A, A general
class of adaptive strategies, Journal of Economic Theory, 2001, 98(1): 26-54.
[27] Hart S, Mas-Colell A, A simple
adaptive procedure leading to correlated equilibrium, Economic Theory, 2001,
98: 26-54.
[28] Wolpert D, Wheeler K, Tumer K,
Collective intelligence for control of distributed dynamical systems, Europhysics Letters, 2000, 49(6): 708-714.
[29] Marsili M, Challet D, Zecchina R,
Exact solution of a modified El Farol’s Bar Problem: efficiency and the role of
market impact, Physica A, 2000, 280: 522-559.
[30] Marsili M, Challet D, Zecchina R,
Exact solution of a modified El Farol’s Bar Problem: efficiency and the role of
market impact, Physica A, 2000, 280(3-4): 522-559.
[31] Fogel D B, Chellapilla K, Angeline
J P, Inductive reasoning and bounded rationality reconsidered, IEEE
Transactions on Evolutionary Computation, 1999, 3(2): 142 –146.
[32] Edmonds B, Modeling bounded
rationality in agent-based simulations using the evolution of mental models,
Computational Techniques for Modelling Learning in Economics, Boston, 1999,
305-332.
[33] Greenwald A, Mishra B, Parikh R, Learning
to play network games, New York University Dissertation, May 1999. http://gunther.smeal.psu.edu/greenwald99learning.html
[34] Edmonds B. Gossip, sexual
recombination and the El Farol Bar: modeling the emergence of heterogeneity, Journal of Artificial Societies and Social Simulation,
1999, 2(3): 1-21.
[35] Sethares, W, Bell A, An adaptive
solution to the EL Farol Problem, Proceedings of the
Thirty-Sixth Annual Allerton Conference on Communication, Control, and
Computing, Allerton, IL, 1998, 3769-3774.
[36] Johnson N, Jarvis S, Jonson R, et
al., Volatility and agent adaptability in a self-organized market, Physica A,
1998, 256(1-2): 230-236.
[37] Greenwald A, Mishra B, Parikh R,
Learning in the Santa Fe Bar Problem, Manuscript,
[38] Greenwald A, Mishra B, Parikh R,
The Santa Fe Bar Problem revisited: theoretical and practical implications, Presented at Stonybrook Festival on Game Theory:
Interactive Dynamics and Learning, July 1998. http://citeseer.nj.nec.com/greenwald98santa.html
[39] Nachbar J, Prediction,
optimization, and learning in repeated games, Econometrica, 1997, 65(2):
275-309.
[40] Nachbar J, Prediction,
optimization, and learning in repeated games, Econometrica, 1997, 65: 275-309.
[41] Casti J, Seeing the light at El
Farol, Complexity, 1996, 1(5): 7-10.
[42] Mackie-Mason J, Varian H, Pricing
congestible resources, IEEE Journal of Selected Areas in Communications, 1995,
13(7): 1141-1149.
[43] Mackie-Mason J, Varian H, Pricing
the internet,
[44] Arthur W B, Inductive reasoning
and bounded rationality, American Economic Review, 1994, 84(2): 406-411.
[45] Arthur B, On learning and
adaptation in the economy, Santa Fe Institute Paper, 1992, 92-07-038.
[46] Hardin G, The tragedy of the
commons, Science, 1968, 162:1243-1248.
Ø
Minority Game
[47] Tedeschi
A, De Martino A, Giardina I, Coordination, intermittency and trends in
generalized minority games, Physica A, 2005, 358: 529-544.
[48] Anghel M, Toroczkai Z, Bassler K
E, Korniss G, Competition
in social networks: emergence of a scale-free leadership structure and
collective efficiency, Physical Review Letters, 2004, 92: 058701.
[49] Lo T S, Chan H Y, Hui P M, Johnson
N F, Theory of networked minority game based on strategy pattern dynamics, Physical Review E, 2004, 70: 056102.
[50] De Martino
A, Giardina I, Marsili M, Tedeschi A, Generalized minority games with adaptive
trend-followers and contrarians, Physical Review E, 2004, 70: 025104.
[51] Caridi I, Ceva H, The Minority
game with interactions, Physica A, 2004, 339: 574-582.
[52] Burgos E, Ceva H, Perazzo R P J,
The evolutionary minority game with local coordination, Physica A, 2004, 337:
635-644.
[53] Chau H F, Chow F K, Ho K H,
Minority game with peer pressure, Physica A, 2004, 332: 483-495.
[54] Metzler R,
Horn C, Evolutionary minority games: the benefits of imitation, Physica A,
2003, 329: 484-498.
[55] Yip K F, Hui P M, Lo T S, Johnson
N F, Efficient resource distribution in a minority game with a biased pool of
strategies, Physica A, 2003,
321: 318-324.
[56] Lee K, Hui P M, Johnson N F, The
minority game with different payoff functions: crowd-anticrowd theory, Physica A, 2003, 321: 309-317.
[57] Quan H J, Wang B H., Hui P M, Luo
X S, Self-segregation and enhanced cooperation in an evolving population
through Local Information transmission, Physica A, 2003, 321: 300-308.
[58] Chow F K,
Chau H F, Multiple choice minority game, Physical A, 2003, 319: 601-615.
[59] Hod S, Nakar E, Self-segregation
versus clustering in the evolutionary minority game, Physical Review Letter,
2002, 88: 238702.
[60] Galstyan A, Lerman K, Adaptive
Boolean networks and minority games with time-dependent capacities, Physical
Review E, 2002, 66: 015103.
[61] Moelbert S, De
Los Rios P, The local
minority game, Physica A, 2002, 302: 217-227.
[62] Marsili M, Market mechanism and
expectations in minority and majority games, Physica A, 2001, 299: 93-103.
[63] Hart M,
Jefferies P, Johnson N F, Hui P M, Crowd-anticrowd theory of the minority game,
Physica A, 2001, 298: 537-544.
[64] Hart M,
Jefferies P, Hui P M, Johnson N F, Crowd-anticrowd theory of multi-agent market
games, The
European Physical Journal B, 2001, 20(4): 547-550.
[65] Ein-Dor L,
Metzler R, Kanter I, Kinzel W, Multichoice minority game, Physical Review E,
2001, 63: 066103.
[66] Quan H J, Wang B H, Hui P M, Luo X
S, Cooperation in the mixed population minority game with imitation , Chinese
Physics Letters, 2001, 18 (9): 1156-1158.
[67] Hui P M, Lo T S, Johnson N F,
Segregation in a competing and evolving population, Physica A, 2000, 288:
451-458.
[68] Lo T S, Lim S W, Hui P M, Johnson
N F, Evolutionary minority game with heterogeneous strategy distribution,
Physica A, 2000, 287: 313-320.
[69] Slanina F,
Social organization in the minority game, Physica A, 2000, 286: 367-376.
[70] Burgos E, Ceva H, Self
organization in a minority game: the role of memory and a probabilistic
approach, Physica A, 2000, 284: 489-495.
[71] Ceva H, Self-organization,
resources and strategies in a minority game, Physica A, 2000, 277: 496-501.
[72] Kalinowski T, Schulz H
J, Brieze M, Cooperation in the minority game with local information, Physica
A, 2000, 277: 502-508.
[73] Hart M,
Jefferies P, Johnson N F, From market games to real-world market, European
Physical Journal B, 2000, 20: 493-501.
[74] Lo T S, Hui P M, Johnson N F,
Theory of the evolutionary minority game, Physical Review E, 2000, 62: 4393-4396.
[75] Challet D, Marsili M,
Relevance of memory in minority game, Physical Review E, 2000, 62: 1862-1868.
[76] Cavagna A, Comment on "adaptive
competition, market efficiency, and phase transitions", Physical
Review Letter, 2000, 84:
1058-1058.
[77] Paczuski M,
Nassler K E, Corral A, Self-organized networks of competing Boolean agents,
Physical Review Letter, 2000, 84: 3185-3188.
[78] Challet D, Marsili M, Phase
transition and symmetry breaking in the minority game, Physical Review E, 1999,
60: R6271-R6274.
[79] Cavagna A,
Irrelevance of memory in the minority game, Physical Review E, 1999,
59: 3783-3786.
[80] D’hulst R, Rodgers G J, The
hamming distance in the minority game, Physica A, 1999, 270: 514-525.
[81] Johnson N, Hui P, Zheng D, Tai C,
Minority game with arbitrary cutoffs, Physical A, 1999, 269: 493-502.
[82] Johnson N F , Hui P M, Zheng D,
Hart M, Enhanced winnings in a mixed ability population playing a minority game,
Journal
of Physics A: Mathematical and General, 1999, 32: L427-L431.
[83] Cavagna
A, Garrahan J P, Giardina I, Sherrington D, A thermal model for adaptive
competition in a market, Physical Review Letter, 1999, 83: 4429-4432.
[84] Savit R,
Manuca R, Riolo R, Adaptive competition, market efficiency, phase transition,
Physical Review Letter, 1999, 82 (10): 2203-2206.
[85] Johnson N F, Hui P M, Jonson R, Lo
T S, Self-organization within an evolving population, Physical Review Letter,
1999, 82: 3360-3363.
[86] Zhang Y C, Modelling market
mechanism with evolutionary games, Europhysics News, 1998, 29: 51-54.
[87] Challet D, Zhang Y C, On the
minority game: analytical and numerical studies, Physica A, 1998, 256: 514-532.
[88] Challet D, Zhang Y C, Emergence of
cooperation and organization in an evolutionary game, Physica A, 1997, 246:
407-418.
n
相关链接 Related Links
n
我们的研究 Our Researches
²
针对演化少数博弈，在Kauffman布尔网络上提出了一个新的网络博弈模型，并且将该局部交流机制引入到了多个资源的演化博弈中。
Shang L H, Wang X F, A modified evolutionary minority game with local imitation, Physica A, to appear.
摘要：在这篇文章中，我们基于Kauffman布尔网络，提出了一种网络上的演化少数者博弈模型。在这个模型中，每个人可以模仿财富高于自己的邻居的策略，其中我们主要研究了网络平均连接度K对系统性能的影响。仿真结果表明随着策略的演化，在稳定状态下agents自组织分成了人数几乎相同的两组人群，每组人群分别采取一种极端行为；并且当K=2的时候，agents之间的相互协调行为最好。此外，我们还把这种局部信息交流机制扩展到了多资源的演化少数博弈模型中，通过与随机博弈模型比较发现系统的性能得到了很大的提高。
Abstract：In this work we consider a network of agents
that compete for limited resources through a modified evolutionary minority
game model based on Kauffman network. The properties of such a system for
different values of mean connectivity of the network are studied. Simulation results
suggest that the agents also tend to self-segregate into opposing groups
characteri
²
针对酒吧问题，提出了一种PI控制算法，该算法使得博弈结果最后收敛于纯策略的纳什均衡。
Shang L H, Wang X F, Decentralized PI control
for a congestion game, Proceedings of 8th International Conference
on Control, Automation, Robotics and Vision, 2004, 316-319.
摘要：酒吧问题是各种拥塞和协调行为的简化模型。在这篇文章中，我们从控制理论角度出发，提出并研究了一种分散PI控制算法。该算法没有使用历史信息，每个人选取一个概率作为表征自己行为的策略。仿真结果表明最后博弈结果收敛于纯策略的纳什均衡。分散控制算法为大型复杂系统中的独立决策者提供了一个简化策略机制。
Abstract：The El Farol bar problem is a simple model of congestion and coordination behaviors that occur with shared resources. From a control-theoretic point of view, this problem can be viewed as a decentralized control problem. This work is a first step towards solving the El Farol bar congestion problem based on control theory. A decentralized proportional-integral (PI) control strategy is proposed and investigated via simulation. This strategy provides a simple mechanism for a large collection of decentralized decision makers to solve a complex congestion problem.
²
针对酒吧问题，提出了一种AIMD控制算法，该算法使得博弈结果最后收敛于混合策略的纳什均衡。
Shang L H, Wang X F, AIMD control of a
congestion game, Proceedings of 23rd Chinese Control Conference, 2004,
1321-1325.
摘要：在这篇文章中，我们将TCP拥塞控制中的AIMD策略应用到了酒吧问题中，并提出了一种自适应算法。该模型没有使用历史信息，每个人选取一个概率作为表征自己行为的策略。仿真结果显示AIMD学习算法使博弈结果最后收敛于混合策略的纳什均衡，结果既没有出现过度的资源浪费也没有出现严重的拥塞行为。在复杂系统中，面对资源有限的情况，这种简化机制是独立的决策者解决拥塞和促进协调的一种有效控制方法。
Abstract：The El Farol bar
problem is a simple model of congestion and coordination behaviors that occur
with shared resources. In this paper we apply the AIMD
idea used in TCP congestion control schemes to the bar congestion problem and
propose an adaptive algorithm. Simulation results
indicate that the learning algorithm converges to the symmetric mixed-strategy
Nash equilibrium in the bar problem and the system has little under-utilization
or over-utilization of the resource. Thus, this strategy provides a simple mechanism
for a large collection of decentralized decision makers to solve a complex
congestion problem.
²
针对酒吧问题，综述了到目前为止研究酒吧问题的各个方向和各种方法，并对下一步的研究方向作了展望。
尚丽辉，汪小帆，一类拥塞问题研究综述，控制与决策，2004，19（11）：1201-1207.
摘要：基于分散控制与决策策略以控制和避免各种各样网络拥塞问题是网络时代复杂系统研究中的一个重要课题。El Farol酒吧拥塞问题是多种实际拥塞问题的一个简化模型，这类问题的关键是如何协调各参与者的行为。本文综述了从纳什均衡、学习算法和预测规则等不同角度研究这类拥塞问题的主要进展，指出了存在的问题和进一步的研究方向。