北京科学与工程计算研究院算法博弈论系列报告

Titile/报告题目:Non-submordularity in Influence Maximization Problem

Speaker /报告人:Dr. Jialin Zhang/ 张家琳 副研究员 中科院计算技术研究所

时间:119日(周三)14:30-15:30

地点:北京科学与工程计算研究院842报告厅(理科楼M8层)

Abstract/报告摘要:In recent years, with the rapid increasing popularity of Facebook, Google and Twitter etc., social networks have become powerful media for spreading information, ideas and products among individuals. In the research area, influence in social networks has been extensively studied. In this talk, I would like to introduce influence maximization problem firstly. I then talk about our recent results about two interesting variants. In "probabilistic guarantee" problem, we consider the task of selecting initial seed users of a topic with minimum size so that with a guaranteed probability the number of users discussing the topic would reach a given threshold. In "cumulative activation" problem, we consider a new activation model in which a node is cumulatively active if its active probability is beyond a given threshold. Both variants meet the difficulty of non-submordularity. I will show hardness results and approximation algorithms for those problems, so as to imply some ideas to handle with non-submordularity in this kind of problems.

Titile/报告题目:Agent Incentives of Strategic Behavior in Resource Exchange

Speaker /报告人:Dr. Yukun Cheng/ 程郁琨 副教授 浙江财经大学

时间:119日(周三)15:30-16:30

地点:北京科学与工程计算研究院842报告厅(理科楼M8层)

Abstract/报告摘要:The rapid growth of the wireless and mobile Internet has provided an opportunity for wide applications of exchanging resources or services over networks, which go beyond the peer-to-peer (P2P) bandwidth sharing idea. In this paper, we consider the popular proportional sharing mechanism and discuss the incentives and opportunities of an agent to lie for personal gains in resource exchange game. The main result is a proof that an agent manipulating the proportional sharing mechanism by cheating on its connectivity with the rest of network and misreporting its resource amount will not benefit its utility eventually. This result establishes a strategic stability property of the resource exchange protocol.

Titile/报告题目:Shapley's Conjecture on the Cores of Abstract Market Games

Speaker /报告人:Dr. Zhigang Cao/ 曹志刚 助理研究员 中科院数学与系统科学研究院

时间:119日(周三)16:30-17:30

地点:北京科学与工程计算研究院842报告厅(理科楼M8层)

Abstract/报告摘要:Shapley (1955) introduced the model of an abstract market game in whichplayers are partitioned into two sides, such that any two players on the same sideare substitutes and those on different sides are complements. The model is ageneralization of several familiar models of games including the assignment gamemodel. Shapley conjectured that abstract market games possess nonempty cores.We show that the conjecture is true if the number of players is no bigger thanfour or one side has a single player, but in general the structure of an abstractmarket game is not strong enough to guarantee the non-emptiness of the core. Weestablish necessary and sufficient supplemental conditions for symmetric abstractmarket games to possess nonempty cores.

联系人:王长军

联系方式:wcj@bjut.edu.cn