›› 2018,Vol. 33 ›› Issue (4): 823-837.doi: 10.1007/s11390-018-1858-8

所属专题： Artificial Intelligence and Pattern Recognition

• Artificial Intelligence and Pattern Recognition • 上一篇    下一篇

一个保镖分配的双人联合机制

José Alberto Fernández-Zepeda1, Daniel Brubeck-Salcedo1, Daniel Fajardo-Delgado2, Héctor Zatarain-Aceves1   

  1. 1 Department of Computer Science, Center for Scientific Research and Higher Education of Ensenada Ensenada, BC 22860, Mexico;
    2 Department of Systems and Computation, Instituto Technológico de Ciudad Guzmán, Guzmán, JAL 49100, Mexico
  • 收稿日期:2017-04-27 修回日期:2017-04-27 出版日期:2018-07-05 发布日期:2018-07-05
  • 作者简介:José Alberto Fernández-Zepeda received his B.Sc. and M.Sc. degrees in electronics from the National Autonomous University of Mexico (UNAM) in 1991 and 1994, respectively, and his Ph.D. degree in computer engineering from Louisiana State University in 1999. Since 2000, he is an associate professor in the Department of Computer Science at Center for Scientific Research and Higher Education of Ensenada (CICESE), Ensenada. His research interests include analysis and design of parallel and distributed algorithms and software process improvement in small organizations.
  • 基金资助:

    This work was partially supported by National Council of Science and Technology (CONACyT) of Mexico under Grant No. 231224, the Program for Professional Teacher Development (PRODEP) of Mexico under Grant No. ITCGUZ-PTC-004, and the National Institute of Technology of Mexico (TecNM) under Grant No. 6307.17-P.

A Two-Player Coalition Cooperative Scheme for the Bodyguard Allocation Problem

José Alberto Fernández-Zepeda1, Daniel Brubeck-Salcedo1, Daniel Fajardo-Delgado2, Héctor Zatarain-Aceves1   

  1. 1 Department of Computer Science, Center for Scientific Research and Higher Education of Ensenada Ensenada, BC 22860, Mexico;
    2 Department of Systems and Computation, Instituto Technológico de Ciudad Guzmán, Guzmán, JAL 49100, Mexico
  • Received:2017-04-27 Revised:2017-04-27 Online:2018-07-05 Published:2018-07-05
  • About author:José Alberto Fernández-Zepeda received his B.Sc. and M.Sc. degrees in electronics from the National Autonomous University of Mexico (UNAM) in 1991 and 1994, respectively, and his Ph.D. degree in computer engineering from Louisiana State University in 1999. Since 2000, he is an associate professor in the Department of Computer Science at Center for Scientific Research and Higher Education of Ensenada (CICESE), Ensenada. His research interests include analysis and design of parallel and distributed algorithms and software process improvement in small organizations.
  • Supported by:

    This work was partially supported by National Council of Science and Technology (CONACyT) of Mexico under Grant No. 231224, the Program for Professional Teacher Development (PRODEP) of Mexico under Grant No. ITCGUZ-PTC-004, and the National Institute of Technology of Mexico (TecNM) under Grant No. 6307.17-P.

PDF (PC)

2475

我们研究是的保镖分配问题（BAP），这是一个问题优化，描述了分布式系统内具有冲突偏好的两类进程之间的利益冲突。当其中一类进程要最小化它与某个特殊进程（即根）之间的距离，而另一类却要最大化此距离。与此同时，所有的进程都致力于构建一个最大社会福利的通信生成树。此问题的最先进的两种算法总是确保生成树的产生，此生成树满足了系统里纳什均衡（Nash equilibrium）的某个条件；但是此树并不一定会产生最大社会福利。本文我们提出了一个双人联合机制，允许为了找到拥有更好社会福利的另一个进程，一些进程可以干扰或打断纳什均衡。通过使用此联合机制，我们为BAP提出了一个新的算法，FFC-BAPS。我们作了理论和实验分析，结果表明相比针对BAP之前的算法，该算法产生质量更好的近似解。

Abstract: We address the bodyguard allocation problem (BAP), an optimization problem that illustrates the conflict of interest between two classes of processes with contradictory preferences within a distributed system. While a class of processes prefers to minimize its distance to a particular process called the root, the other class prefers to maximize it; at the same time, all the processes seek to build a communication spanning tree with the maximum social welfare. The two state-of-the-art algorithms for this problem always guarantee the generation of a spanning tree that satisfies a condition of Nash equilibrium in the system; however, such a tree does not necessarily produce the maximum social welfare. In this paper, we propose a two-player coalition cooperative scheme for BAP, which allows some processes to perturb or break a Nash equilibrium to find another one with a better social welfare. By using this cooperative scheme, we propose a new algorithm called FFC-BAPS for BAP. We present both theoretical and empirical analyses which show that this algorithm produces better quality approximate solutions than former algorithms for BAP.

[1] Tanenbaum A S, van Steen M. Distributed Systems:Principles and Paradigms (2nd edition). Prentice-Hall, Inc., 2006.

[2] Nisan N, Roughgarden T, Tardos E, Vazirani V V. Algo?ithmic Game Theory. Cambridge University Press, 2007.

[3] Halpern J Y. Beyond Nash equilibrium:Solution concepts for the 21st century. In Proc. the 27th ACM Symp. Principles of Distributed Computing, August 2008.

[4] Manshaei M H, Zhu Q Y, Alpcan T, Baçsar T, Hubaux J P. Game theory meets network security and privacy. ACM Computing Surveys, 2013, 45(3):Article No. 25.

[5] Feldman M, Lai K, Stoica I, Chuang J. Robust incentive techniques for peer-to-peer networks. In Proc. the 5th ACM Conf. Electronic Commerce, May 2004, pp.102-111.

[6] Feldman M, Papadimitriou C, Chuang J, Stoica I. Freeriding and whitewashing in peer-to-peer systems. IEEE Journal on Selected Areas in Communications, 2006, 24(5):1010-1019.

[7] Roughgarden T. Selfish Routing and the Price of Anarchy. The MIT Press, 2005.

[8] Koutsoupias E, Papadimitriou C. Worst-case equilibria. Computer Science Review, 2009, 3(2):65-69.

[9] von Neumann J, Morgenstern O. Theory of Games and Economic Behavior. Princeton University Press, 2007.

[10] Fajardo-Delgado D, Fernández-Zepeda J A, Bourgeois A G. The bodyguard allocation problem. IEEE Trans. Parallel and Distributed Systems, 2013, 24(7):1465-1478.

[11] Nash J F Jr. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences of the United States of America, 1950, 36(1):48-49.

[12] Dasgupta A, Ghosh S, Tixeuil S. Selfish stabilization. In Stabilization, Safety, and Security of Distributed Systems, Datta A K, Datta M (eds.), Springer, 2006, pp.231-243.

[13] Cohen J, Dasgupta A, Ghosh S, Tixeuil S. An exercise in selfish stabilization. ACM Trans. Autonomous and Adaptive Systems, 2008, 3(4):Article No. 15.

[14] Zatarain-Aceves H, Fernández-Zepeda J A, Brizuela C A, Fajardo-Delgado D. A cascade evolutionary algorithm for the bodyguard allocation problem. Applied Soft Computing, 2015, 37:643-651.

[15] Raidl G R, Julstrom B A. Edge sets:An effective evolutionary coding of spanning trees. IEEE Trans. Evolutionary Computation, 2003, 7(3):225-239.

[16] Barabási A L, Albert R. Emergence of scaling in random networks. Science, 1999, 286(5439):509-512.

[17] Erdös P, Rényi A. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci., 1960, 5:17-61.

[18] Kumar R, Raghavan P, Rajagopalan S, Sivakumar D, Tomkins A, Upfal E. Stochastic models for the web graph. In Proc. the 41st Annual Symp. Foundations of Computer Science, November 2000, pp.57-65.

[19] Schulz A S, Moses N S. On the performance of user equilibria in traffic networks. In Proc. the 14th Annual ACMSIAM Symp. Discrete Algorithms, January 2003, pp.86-87.

[20] Anshelevich E, Dasgupta A, Kleinberg J, Tardos E, Wexler T, Roughgarden T. The price of stability for network design with fair cost allocation. In Proc. the 45th Annual IEEE Symp. Foundations of Computer Science, October 2004, pp.295-304.

[21] Blum C, Roli A. Metaheuristics in combinatorial optimization:Overview and conceptual comparison. ACM Computing Surveys, 2003, 35(3):268-308.

[22] Eiben A E, Jelasity M. A critical note on experimental research methodology in EC. In Proc. Congress on Evolutionary Computation, May 2002, pp.582-587.

[23] Crepinšek M, Liu S H, Mernik M. Replication and compa?ison of computational experiments in applied evolutionary computing:Common pitfalls and guidelines to avoid them. Applied Soft Computing, 2014, 19:161-170.

[24] Lilliefors H W. On the Kolmogorov-Smirnov test for normality with mean and variance unknown. Journal of the American Statistical Association, 1967, 62(318):399-402.

[25] Conover W J. Practical Nonparametric Statistics. Wiley Series in Probability and Statistics, John Wiley & Sons, 1980.
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 李未;. A Structural Operational Semantics for an Edison Like Language(2)[J]. , 1986, 1(2): 42 -53 .
[2] 陈世华;. On the Structure of Finite Automata of Which M Is an(Weak)Inverse with Delay τ[J]. , 1986, 1(2): 54 -59 .
[3] 李万学;. Almost Optimal Dynamic 2-3 Trees[J]. , 1986, 1(2): 60 -71 .
[4] 冯玉琳;. Recursive Implementation of VLSI Circuits[J]. , 1986, 1(2): 72 -82 .
[5] C.Y.Chung; 华宣仁;. A Chinese Information Processing System[J]. , 1986, 1(2): 15 -24 .
[6] 孙钟秀; 商陆军;. DMODULA:A Distributed Programming Language[J]. , 1986, 1(2): 25 -31 .
[7] 陈世华;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[8] 金兰; 杨元元;. A Modified Version of Chordal Ring[J]. , 1986, 1(3): 15 -32 .
[9] 潘启敬;. A Routing Algorithm with Candidate Shortest Path[J]. , 1986, 1(3): 33 -52 .
[10] 吴恩华;. A Graphics System Distributed across a Local Area Network[J]. , 1986, 1(3): 53 -64 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持：support@magtech.com.cn
总访问量：