סמינר מחלקתי

Game for the Strategic Spreading of Ideas on a Network

Shimon Ben Ishay - Department of Industrial Engineering

Abstract

This M.Sc. thesis describes the problem domain and the intricacies of a new game called, “Spread-It” which simulates the spread of ideas or regimes in social networks. “Spread-It” is a strategic game that can be played for fun, for improving strategic thinking or for achieving greater power by successfully pushing an agenda through any social group.

Studies have shown that people’s decisions on whether to adopt an innovation or product are not purely based on the objective factors of the object but rather are the result of the influence of the opinions of colleagues or friends. This makes “Spread-It” interesting to play. This research used a game-theoretic approach to model the competitive process where the players are firms trying to market their products, ideas, or trends to a targeted group of people who in turn influence some of their friends, who in turn influence others. Eventually, a cascade of recommendations is created.

“Spread-It” combines ideas and theories from the fields of mathematics (Chip Firing Game model) and computer science, particularly artificial intelligence (AI), game theory (combinatorial games), graph theory and network analysis (centrality measures, diffusion models).

“Spread-It” is a deterministic game played on a finite graph (the game board), which represents a network of people, organizations, entities. “Spread-It” can be played as a board game, on a computer or as a mobile game version. “Spread-It” rules are as simple and as intuitive as possible; while at the same time, “Spread-It” is a challenging and highly complex game. It was developed with the aim of creating a game where humans can excel. There are some game properties, most notably the high branching factor, that make “Spread-It” hard for even computers. In this thesis, “Spread-It” was analyzed and implemented using different artificial intelligence techniques.

In order to create a “Spread-It” agent that played well, we have adjusted known game-playing techniques such as the Minimax and the Alpha Beta algorithms coupled with heuristics, and investigated many new ideas, among them the Monte Carlo Search algorithm which, surprisingly, looks more promising than others. Out of these techniques only a few proved to be fruitful

Experiments were performed using both computer agents and human players to test the AI agents’ performances against other AI agents and human players, analyze possible game strategies, and receive feedback on this new game. In order to examine all of these techniques, an engine called “SPRITE” (Spread-It Engine), a novel playing program that encapsulates enhanced variants of artificial intelligence algorithms was developed. Thus, with the accumulation of experience, it is not hard to imagine that human players can derive better strategies. This new area is, however, far too broad to be fully covered by any one thesis.

This work was performed under the supervision of Prof. Irad Ben Gal.

ההרצאה תתקיים ביום חמישי 25.06.15, בשעה 13:00 בחדר 206, בנין וולפסון הנדסה, הפקולטה להנדסה, אוניברסיטת תל-אביב.