《布尔博弈系统中钉扎对资源分配效率的提升.doc》由会员分享，可在线阅读，更多相关《布尔博弈系统中钉扎对资源分配效率的提升.doc（20页珍藏版）》请在三一办公上搜索。
1、精品论文布尔博弈系统中钉扎对资源分配效率的提升张继强1，黄子罡1，董家奇1,黄亮1,2 ,黄铁桥1 ,来颖诚2,31 兰州大学物理科学与技术学院，兰州7300002 亚利桑那州立大学电子、 计算机与能源工程学院，坦佩，AZ 85287,USA3 亚利桑那州立大学物理系，坦佩，AZ 85287,USA摘要：资源分配在现实世界的复杂系统中以各种形式展现，比如交通系统（城市交通，航空系 统，Internet网等），社会服务机构，乃至整个生态系统。 这是系统中资源往往是有限的，个体 基于获得的局部信息竞争利用率更低的资源，并且最终少数者获胜。 在这类系统中，羊群行为 对资源分配效率是有害的，但在真实情
2、形下羊群行为却普遍存在，并表现为交通系统中的拥 堵，金融系统中的大事件，或者表现为不同类型的社会危机，他们的共同特征是资源分配的低 效率。 为了阻止羊群行为、 提高效率，本文给出固定（钉扎）某些个体选择的钉扎方案，并系 统的研究了钉扎对布尔博弈系统的资源分配的影响。 结果显示牺牲部分个体的选择权可能极大 地提高整个系统的效率。 在某些特殊情形，系统会通过自组织过程系统表现的比随机博弈系统 更优越。 本文同时建立了钉扎过程的解析理论，该理论基于离散时间主方程来描述钉扎效应。 设计有效地钉扎方案同样有所讨论。 这篇工作提供了一个基本并且普遍的数学框架来研究社 会、 生态等系统中的资源分配钉扎及涨落
3、问题。 关键词：理论物理，复杂系统，少数者博弈，资源分配中图分类号： O414.21Pinning improves resource allocation efficiency of boolean-game systemsJi-Qiang Zhang1, Zi-Gang Huang1 , Jia-QI Dong1 , Liang Huang1,2 , Tie-QiaoHuang1, Ying-Cheng Lai2,31 School of Physical Science and Technology,Lanzhou University, Lanzhou 730000, China2 S
4、chool of Electrical, Computer and Energy Engineering,Arizona State University, Tempe, AZ 85287, USA3 Department of Physics, Arizona State University, Tempe, Arizona 85287, USAAbstract: Resource allocation takes place in various kinds of real-world complex systems, such as the traffic systems (e.g.,
5、urban traffic system and flight systems), social services institutions or organizations (e.g., bank, theater, and mart, financial market), or even the ecosystems. Resources are always limited, and agents tend to choose the least used resource based on certain available information, obeying the funda
6、mental principle that the minority wins. In these systems, herd behavior is harmful for the efficiency of resource allocation.基金项目： NSF of China under Grants (11275003, 11135001, and 10905026.), Specialized Research Fund for theDoctoral Program of Higher Education (20090211120030), AFOSR under Grant
7、(FA9550-10-1-0083)作者简介： Zhang Jiqiang（1984-), male, master direction：Nonlinear Dynamics and complex systems. Corre- spondence author：Huang Zigang（1981- ), male, Associate Professor,ma jor research direction：Nonlinear Dynamics and complex systems.- 8 -However, it is ubiquitous in real cases, and pres
8、ent to be congestion in traffic system, extreme events in financial system, and other crisis in social system, all of which are commonly characterized by the low efficiency of resource allocation. For the sake of preventing herd behavior and improving the efficiency,it is proposed that pinning schem
9、e to fix certain individuals options, and it systematically is studied that the effect of pinning to the resource allocation dynamics of boolean game systems. The work demonstrates that, the sacrifice of certain individuals options may markedly improve the efficiency of the whole system. Especially,
10、 in certain cases, the system performs better than the random game system through self-organized processes. We develop an analytic theory based on the discrete time master equation to understand the effect of pinning. The rule to design effective pinning scheme are also discussed. The work represent
11、s a basic and general mathematical framework to address the fluctuation of the resource allocation in social, economical and political systems.Key words: theoretical physics, complex system, minority game, resource allocation.0 IntroductionResource allocation is an essential processes in real world,
12、 and the related complex sys- tems are ubiquity, which includes traffic systems (e.g., Internet, urban traffic system, rail and flight networks), social service institutions or organizations (e.g., school, mart, bank, financial market), and furthermore the whole ecosystems. All these systems support
13、 certain kinds of resources to the related populations, which are composed of equally ambitious (demanded) individuals with similar capabilities, i.e., agents adaptably chasing higher payoff. The discus- sion of the resource allocation dynamics in these aforesaid multi-agent real-world systems is an
14、 important issue, with high theoretical and practical significance.The perspective of complex adaptive systems (CAS) composed of agents under mutual influence have been proposed for understanding the rich and complex dynamics of real-world systems 1, 2, 3. And, one of the simplest model serve as a g
15、eneral paradigm for resource allocation in multi-agent dynamical systems is the minority game (MG) 4, which is introduced by Challet and Zhang as a simplification of Arthurs El Farol Bar attendance problem 5.Agents in the MG are designed to make choice (+1 or 1, i.e. to attend a bar or refrain) base
16、don the aggregate signal (the global information in memory), i.e., which option was minority for the last several time steps. The agents in the minority are rewarded, and those in the majority punished since resources are limited. Subsequently, the MG model was extensively studied in a series of wor
17、ks 6, 7, 8, 9, 10, 11, 12, 13, 14, 17, 18, 15, 16, 19, 20, 21, 22, 23, 24. In physics, MG has received a great deal of attention from the statistical-mechanics community, especially in terms of problems associated with non-equilibrium phase transitions 25, 26, 27.In contrast to this mean-field descr
18、iption of the MG, the Boolean game (BG) was studied considering that agent can also respond to the detailed information it receives from otherspecified agents, or from self-questioning processes 28, 30, 31, 29, 32, 33. It was established that coordination still arises out of local interactions in BG
19、, and the system as a whole may achieve “better than random” performance in terms of the utilization of resources.Herd behavior, which describes the condition that many agents display the same action, is one of the outcomes always present in social systems and ecosystems 34. The herd behavior has be
20、en extensively studied and is found to be one factor of the origins of complexity that may enhance the fluctuation and reduce the system profit 11, 35, 36, 37, 38. Obviously, for the resource allocation processes, the system performs best when all the resources are used properly, rather than the arr
21、angement of resources with some resources crowded while some other unoccupied.In the present work, we focus on the effect of pinning which is executable in real case, and may shed new insight in solving the problems in resource allocation. Take the urban traffic system as an example, to select certa
22、in individuals out of the free competition dynamics, and pin (fix) their options to a given rout (or time region), may improve the efficiency of the system. Pinning is similar to the issue of immunization in the research of spreading in social or technical systems, where certain individuals are pinn
23、ed to immunization state in the spreading dynamics 43, 39, 40, 41, 42. Our focal system with the function of resource allocation, is much different to the spreading system from the perspective of dynamic mechanism. As far as we know, there are rare works consider the effect of pinning to the resourc
24、e allocation of boolean game system. Thus, in this work, we systematically study how pinning affects the resource allocation dynamics of boolean game systems.The paper is organized as follows. Our pinning BG model is presented in Sec. II. A general theory is developed in Sec.III to elucidate the pro
25、cesses of different pinning schemes and network topology. Relevance to real-world systems and concluding remarks are also presented in Sec. IV.1 model1.1 Boolean gameIn the previous studies of the BG, each agent acts according to the Boolean function, i.e., gets its input from the time-varying neigh
26、borhoods, and maps the input to a state (the two alternative options +1 and 1) it will adopt in the subsequent round 31. Also, several specific networks are considered to be the static coupling behavior, and agent acts according to the local neighbors state with a probability named the strength of l
27、ocal interactions 29. The effect that agents make decisions based on the historical memory of the local knowledge was also discussed 32. To sum up, the main differences of BG from the previous studies on MG are, (1) agents make use of the local information which merely involved its conversant agents
28、, i.e., immediate neighbors on coupling networks, and (2) agents are ignorant of which choice was global winner, while trying to act as minority in its own local region. Here, we wouldlike to reiterate that, the agents behave as local minority does not mean they reward. In the BG system, agents comp
29、etition for the two alternative resources makes only the agents in the global minority rewarded by 1, and therefore the system profit equals to the number of agents in the global minority. We can see that, for a system of N agents and two alternative resources+1 and 1 (each has the accommodate capac
30、ity N/2), the optimal solution for the resourceallocation is A = N/2, with A denotes the number of agents choosing +1 in the system.Here, in our work, the BG model can be depicted in detail as: at each time step, each agent acts based on the last states of local neighbors, with the coupling relation
31、s depicted by networks. The probability of making a decision (choosing +1 or 1) for each agent depends on the ratio of the numbers of +1 and 1 agents in its neighbors, i.e., the agent chooses +1 with the probability,Pi = n/(n+ + n) = n/ki , (1)and 1 with the probability Pi = 1 Pi, where n+ and n are
32、 the numbers of +1 and 1 agents in neighbors, respectively. This model is the extreme case in Ref. 29 with the strength of local interaction to be 1.0.The variance of systemsT2 = 1 X(A Ttt=1N)2 , (2)2which is the cumulative standard deviation from the optimal resource utilization over time length T
33、29, can be considered as a global measure of the systems optimality. The smaller 2 corresponds to better optimality of resource allocation and thus higher efficiency. Here, At denotes the number of agents adopting +1 at time t. Actually, for this BG model, although agents are trying to behave as min
34、ority, the harmful herd behavior prevails, namely, the large durative oscillation of At takes place.1.2 Pinning schemeIn this paper, the way we proposed to reduce herd behavior is, to pin certain agents to freeze state. Pinning seems to be an intuitive and normal way to realize better resource alloc
35、ation, however, the effect of pinning scheme and topology are still of high interests, while lack of understanding at present. Here, we define the fraction of agents to be pinned (fixed) as pin , and therefore the fraction of unpinned free nodes is f ree = 1 pin . The number of free agents and pinne
36、d agents thus are Nf = N f ree and Np = N pin , respectively. The free agents make choices according to local information as we mentioned, while with certain information comes from the pinned neighbors.The pining scheme has two aspects, the order of pinning and the pinning pattern. (1) The order of
37、pinning imparts how to choose agents for pinning. Here we firstly propose the “Random Pinning” (RP), with pinned agents being randomly selected from free agents, and the “Degree Preferential Pinning” (DPP) which pins in the rank of agents degree, i.e., the number of neighbors on the underlying netwo
38、rks. For DPP, agents with higher degree will bepinned earlier. In the past lectures, we see the similarity of RP and DPP to the random error and intentional attack in the research about the robustness of network systems 44, 45, 46, 47. (2) The pinning pattern imparts what states the selected agents
39、to be pinned. Here we define “All +1” (or “All 1”) as all the pinned agent to choose +1 (or 1), and “Half 1” as agentsto be pinned as +1 and 1, alternately. In addition, the effect of pinning also closely dependson the topology of the system. Here, we consider the well-studied topologies: scale-free
40、 48, and random 49 networks.For the sake of contrastive analysis between the free system and the pinned system ofvariable pin , we defined a modified cumulative variance as,TN22 = 1 Pt=1 (At 2 )(3)T1 pinwhich makes the fluctuation of the systems with pin 0, 1) comparable.2 Simulation and Analytical
41、results2.1 Simulation resultsSimulations are carried out on the population located on the fully connected network (FCN), BA scale-free, and ER random networks. The pinned agents are selected according to the pinning scheme RP or DPP, and the states of them are set according to “Half 1”, “All+1”, and
42、 “All 1”. In the initial state, +1 and 1 are uniformly distributed among all the freeagents. The evolutionary time are set to be T = 104 . Take the DPP and “Half 1” on FCN and BA scale-free network as an example, the timeseries of At for different pinning fraction pin are plotted in Fig. 1. Obviousl
43、y, herd behavior prevails in the free system (pin = 0), and the subsequent oscillation causes extremely large variances 2 . From the dynamical rule, wesee that the fluctuation of At between 0 and N is the absorbing state of the free system. The system with very few pinned agents (such as the pin = 0
44、.01) escapes from the absorbing state, and then the fluctuation decreases rapidly. The distribution of At are also plotted in Fig. 1. The simulation results of 2 as a function of pin for different cases are also presented in figures in the following together with analytical results.2.2 Analytical th
45、eory for the free systemWe will firstly give analytical description to the free system (i.e. pin = 0), which is essential for further analysis to the pinning systems. In the mean-field assumption that agents with different states are well mixed in the system, one given individual i, with degree ki , willhave n+ = ki tneighbors who adopt +1. Here t= At /N is the density of +1 agents in thewhole system. Then, according to the updating rule Eq. (1), i will choose +1 for the next timestep with probability,ttPi = ki (1 )/ki = 1 (4)60
