Coalition Structure Generation Constrained by Trust and Utility Relationship

Xiangrong TONG; Ziyi REN

doi:10.11999/JEIT200509

Volume 43 Issue 7

Jul. 2021

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2021 > 43(7): 2055-2062

ZHANG Tianqi, QUAN Shengrong, QIANG Xingzi, JIANG Xiaolei. Time-frequency Analysis Method Based on Multi-scale Chirplet Sparse Decomposition and Wigner-Ville Transform[J]. Journal of Electronics & Information Technology, 2017, 39(6): 1333-1339. doi: 10.11999/JEIT160750

Citation:

Xiangrong TONG, Ziyi REN. Coalition Structure Generation Constrained by Trust and Utility Relationship[J]. Journal of Electronics & Information Technology, 2021, 43(7): 2055-2062. doi: 10.11999/JEIT200509

Citation:

PDF( 2710 KB)

Coalition Structure Generation Constrained by Trust and Utility Relationship

doi: 10.11999/JEIT200509

Xiangrong TONG^,,
Ziyi REN

School of Computer and Control Engineering, Yantai University, Yantai 264005, China

Funds: The National Natural Science Foundation of China (62072392,61972360), Shandong Province Major Science and Technology Innovation Project (2019JZZY020131)

Received Date: 2020-06-23
Rev Recd Date: 2020-12-26

Available Online: 2021-02-06

Publish Date: 2021-07-10

Abstract

Abstract

The coalition structure generation is an important domain of distributed artificial intelligence. Most coalition formation models are only based on the utility, and any number of coalitions are permitted, which makes it be NP complexity difficult to generate the optimal coalition structure. Actually, Trust is the base of cooperation and has direct effect on the final utility. So, not only utility but also trust relationship should be seriously considered. To this end, the utility constraint is extended to trust and utility constraint, a two-tuples is used to represent utility and trust, which is the base of coalition structure generation. Inspired by the classic s-t-cut algorithm for graph cut, coalition structure generation constrained by trust and utility relationship is investigated. Assuming that individual rationality of agents and the stability of coalition (there is no block) is satisfied, the network is cut by the relationship of utility and trust to formation coalitions. The proposed algorithms of coalition structure generation named MT-s-t-cut and MTU-s-t-cut (Trust s-t-cut) can output the optimal coalition structure in polynomial time. The results of simulated experiments show that the social utility increases with the number of agents, and the running time of the algorithms are far less than that of Dynamic Programming (DP) and Optimal Dynamic Programming and Integer Partition (ODP-IP) algorithms.
- Coalition structure generation,
- Trust utility relationship,
- Trust transitivity,
- Graph cut

FullText(HTML)

References(19)

References

[1]	智慧, 王飞跃, 黄子菊. 大规模MIMO系统中联合用户分组和联盟博弈的动态导频分配方案[J]. 电子与信息学报, 2020, 42(7): 1686–1693. doi: 10.11999/5EIT190445 ZHI Hui, WANG Feiyue, and HUANG Ziju. Dynamic pilot allocation scheme for joint user grouping and alliance game in massive MIMO systems[J]. Journal of Electronics &Information Technology, 2020, 42(7): 1686–1693. doi: 10.11999/5EIT190445
[2]	CHANGDER N, AKNINE S, and DUTTA A. An imperfect algorithm for coalition structure generation[C]. The Thirty-Third AAAI Conference on Artificial Intelligence, Hawaii, USA, 2019: 9923–9924. doi: 10.1609/aaai.v33i01.33019923.
[3]	UEDA S, IWASAKI A, CONITZER V, et al. Coalition structure generation in cooperative games with compact representations[J]. Autonomous Agents and Multi-Agent Systems, 2018, 32(4): 503–533. doi: 10.1007/s10458-018-9386-z
[4]	GALLARDO J M, JIMÉNEZ N, and JIMÉNEZ-LOSADA A. Nontransferable utility games with fuzzy coalition restrictions[J]. Fuzzy Sets and Systems, 2018, 349: 42–52. doi: 10.1016/j.fss.2017.08.004
[5]	KARAKAYA M and KLAUS B. Hedonic coalition formation games with variable populations: Core characterizations and (im)possibilities[J]. International Journal of Game Theory, 2017, 46(2): 435–455. doi: 10.1007/s00182-016-0533-y
[6]	İNAL H. The existence of a unique core partition in coalition formation games[J]. Games and Economic Behavior, 2019, 114: 215–231. d. doi: 10.1016/j.geb.2019.01.009
[7]	DENG Yuan, SHEN Weiran, and TANG Pingzhong. Coalitional permutation manipulations in the gale-Shapley algorithm[C]. The 17th International Conference on Autonomous Agents and Multiagent Systems, Stockholm, Sweden, 2018: 928–936.
[8]	LIN Dianchao and JABARI S E. Transferable utility games based intersection control for connected vehicles[C]. 2019 IEEE Intelligent Transportation Systems Conference (ITSC), Auckland, New Zealand, 2019: 3496–3501.
[9]	RAHWAN T, MICHALAK T P, WOOLDRIDGE M, et al. Coalition structure generation: A survey[J]. Artificial Intelligence, 2015, 229: 139–174. doi: 10.1016/j.artint.2015.08.004
[10]	王海艳, 杨文彬, 王随昌, 等. 基于可信联盟的服务推荐方法[J]. 计算机学报, 2014, 37(2): 301–311. doi: 10.3724/SP.J.1016.2014.00301 WANG Haiyan, YANG Wenbin, WANG Suichang, et al. A service recommendation method based on trustworthy community[J]. Chinese Journal of Computers, 2014, 37(2): 301–311. doi: 10.3724/SP.J.1016.2014.00301
[11]	SLESS L, HAZON N, KRAUS S, et al. Forming k coalitions and facilitating relationships in social networks[J]. Artificial Intelligence, 2018, 259: 217–245. doi: 10.1016/j.artint.2018.03.004
[12]	童向荣, 张伟, 龙宇. Agent主观信任的传递性[J]. 软件学报, 2012, 23(11): 2862–2870. doi: 10.3724/SP.J.1001.2012.04303 TONG Xiangrong, ZHANG Wei, and LONG Yu. Transitivity of Agent subjective trust[J]. Journal of Software, 2012, 23(11): 2862–2870. doi: 10.3724/SP.J.1001.2012.04303
[13]	WANG Xiaofeng, SU Jinshu, WANG Baosheng, et al. Trust description and propagation system: Semantics and axiomatization[J]. Knowledge-Based Systems, 2015, 90: 81–91. doi: 10.1016/j.knosys.2015.09.030
[14]	MAO Chengying, XU Changfu, and HE Qiang. A cost-effective algorithm for inferring the trust between two individuals in social networks[J]. Knowledge-Based Systems, 2019, 164: 122–138. doi: 10.1016/j.knosys.2018.10.027
[15]	KARGER D R. Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm[C]. The 4th Annual ACM-SIAM Symposium on Discrete Algorithms, Austin, USA, 1993: 21–30. doi: 10.1145/313559.313605
[16]	BRÂNZEI S and LARSON K. Coalitional affinity games[C]. The 8th International Conference on Autonomous Agents and Multiagent Systems, Budapest, Hungary, 2009: 1319–1320.
[17]	YEH D Y. A dynamic programming approach to the complete set partitioning problem[J]. Bit Numerical Mathematics, 1986, 26(4): 467–474. doi: 10.1007/BF01935053
[18]	MICHALAK T, RAHWAN T, ELKIND E, et al. A hybrid exact algorithm for complete set partitioning[J]. Artificial Intelligence, 2016, 230: 14–50. doi: 10.1016/j.artint.2015.09.006
[19]	WU Feng and RAMCHURN S D. Monte-Carlo tree search for scalable coalition formation[C]. The 29th International Joint Conference on Artificial Intelligence, Yokohama, Japan, 2020: 407–413.

Relative Articles

Supplements(0)

Cited By

Cited by

Periodical cited type(12)

1.	张艳睛，龙伟军，潘明海. 射频辐射源的高精度参数估计. 现代电子技术. 2022(15): 63-68 .
2.	陈万里，李伟，柴远波. 一种低信噪比下的LFM脉冲信号起始频率校正方法. 火力与指挥控制. 2021(02): 58-63 .
3.	孙同晶，刘桐，杨阳. 多阶次分数阶傅里叶域特征融合的主动声呐目标稀疏表示分类方法. 电子与信息学报. 2021(03): 809-816 . 本站查看
4.	李亚利，刘佳. 基于非平稳信号时频分析的DDoS攻击检测仿真. 计算机仿真. 2021(05): 353-356+370 .
5.	张玉，李天琪，张进，唐波. 基于集成固有时间尺度分解的IFF辐射源个体识别算法. 电子与信息学报. 2020(02): 430-437 . 本站查看
6.	邬俊阳，陈欣. 基于迭代搜索的线性调频脉冲信号参数估计方法. 探测与控制学报. 2020(04): 39-46 .
7.	林江刚，胡正新，李晶，翟怡萌，邓艾东. 低转速下基于AE信号与LMD的滚动轴承故障诊断. 动力工程学报. 2019(04): 293-298 .
8.	刘会杰，高新海，郭汝江. 一种低副瓣无混叠的线性调频信号时频分析方法. 电子与信息学报. 2019(11): 2614-2622 . 本站查看
9.	林江刚，胡正新，李晶，翟怡萌，邓艾东. 基于AE信号与VMD的滚动轴承故障诊断研究. 燃气轮机技术. 2018(03): 34-38 .
10.	欧国建，张淑芳，邓剑勋，蒋清平. 利用FFT实现对LFM信号的快速稀疏分解. 数据采集与处理. 2018(05): 865-871 .
11.	孙湘，华钢. 生物特征信号提纯算法的设计与实现. 生物医学工程研究. 2018(04): 492-495 .
12.	陈小龙，关键，黄勇，于晓涵，刘宁波，董云龙，何友. 雷达低可观测动目标精细化处理及应用. 科技导报. 2017(20): 19-27 .