NS Seminar

Date and Location

Jun 01, 2018 - 1:00pm to 2:00pm
Bldg 434, room 122


Topology Design Games and Dynamics in Adversarial Environments (presented by Kyle Carson, Computer Science)

Ciftcioglu, E. N., Pal, S., Chan, K. S., Cansever, D. H., Swami, A., Singh, A. K., & Basu, P. (2017). Topology design games and dynamics in adversarial environments. IEEE Journal on Selected Areas in Communications, 35(3), 628-642.

We study the problem of network topology design within a set of policy-compliant topologies as a game between a designer and an adversary. At any time instant, the designer aims to operate the network in an optimal topology within the set of policy compliant topologies with respect to a desired network property. Simultaneously, the adversary counters the designer trying to force operation in a suboptimal topology. Specifically, if the designer and the attacker choose the same link in the current topology to defend/grow and attack, respectively, then the latter is thwarted. However, if the defender does not correctly guess where the attacker is going to attack, and, hence, acts elsewhere, the topology reverts to the best policy-compliant configuration after a successful attack. We show the existence of various mixed strategy equilibria in this game and systematically study its structural properties. We study the effect of parameters, such as probability of a successful attack, and characterize the steady state behavior of the underlying Markov chain. While the intuitive adversarial strategy here is to attack the most important links, the Nash equilibrium strategy is for the designer to defend the most crucial links and for the adversary to focus attack on the lesser crucial links. We validate these properties through two use cases with example sets of network topologies. Next, we consider a multi-stage framework where the designer is not only interested in the instantaneous network property costs but a discounted sum of costs over many time instances. We establish structural properties of the equilibrium strategies in the multi-stage setting, and also demonstrate that applying algorithms based on the Q-Learning and Rollout methods can result in significant benefits for the designer compared with strategies resulting from a one-shot based game.


Limited individual attention and online virality of low-quality information (presented by Albert Chen, Computer Science)

Qiu, X., Oliveira, D. F., Shirazi, A. S., Flammini, A., & Menczer, F. (2017). Limited individual attention and online virality of low-quality information. Nature Human Behaviour, 1(7), 0132.

Social media are massive marketplaces in which memes compete for our attention. We investigate the conditions in which the best ideas prevail in a stylized model of online social network, where agents have behavioral limitations in managing a heavy flow of information. We measure the relationship between the quality of an idea and its likelihood to become prevalent at the system level. We find that both information overload and limited attention contribute to a degradation in the market’s discriminative power. A good tradeoff between discriminative power and diversity of information is possible according to the model. However, calibration with empirical data characterizing information load and finite attention in real social media reveals a weak correlation between quality and popularity of information. In these realistic conditions, the model predicts that low- quality information is just as likely to go viral, providing an interpretation for the high volume of misinformation we observe online.