Talal Rahwan

AIJ Journal 2024 Journal Article

Adversarial analysis of similarity-based sign prediction

• Michał T. Godziszewski
• Marcin Waniek
• Yulin Zhu
• Kai Zhou
• Talal Rahwan
• Tomasz P. Michalak

Adversarial social network analysis explores how social links can be altered or otherwise manipulated to hinder unwanted information collection. To date, however, problems of this kind have not been studied in the context of signed networks in which links have positive and negative labels. Such formalism is often used to model social networks with positive links indicating friendship or support and negative links indicating antagonism or opposition. In this work, we present a computational analysis of the problem of attacking sign prediction in signed networks, whereby the aim of the attacker (a network member) is to hide from the defender (an analyst) the signs of a target set of links by removing the signs of some other, non-target, links. While the problem turns out to be NP-hard if either local or global similarity measures are used for sign prediction, we provide a number of positive computational results, including an FPT-algorithm for eliminating common signed neighborhood and heuristic algorithms for evading local similarity-based link prediction in signed networks.

IS Journal 2023 Journal Article

Rethinking Homework in the Age of Artificial Intelligence

• Hazem Ibrahim
• Rohail Asim
• Fareed Zaffar
• Talal Rahwan
• Yasir Zaki

The evolution of natural language processing techniques has led to the development of advanced conversational tools such as ChatGPT, capable of assisting users with a variety of activities. Media attention has centered on ChatGPT’s potential impact, policy implications, and ethical ramifications, particularly in the context of education. As such tools become more accessible, students across the globe may use them to assist with their homework. However, it is still unclear whether ChatGPT’s performance is advanced enough to pose a serious risk of plagiarism. We fill this gap by evaluating ChatGPT on two introductory and two advanced university-level courses. We find that ChatGPT receives near-perfect grades on the majority of questions in the introductory courses but has not yet reached the level of sophistication required to pass in advanced courses. Moreover, adding a few full stops or typos may fool a machine learning algorithm designed to detect ChatGPT-generated text. These findings suggest that, at least for some courses, current artificial intelligence tools pose a real threat that can no longer be overlooked by educational institutions.

TIST Journal 2021 Journal Article

How Members of Covert Networks Conceal the Identities of Their Leaders

• Marcin Waniek
• Tomasz P. Michalak
• Michael Wooldridge
• Talal Rahwan

Centrality measures are the most commonly advocated social network analysis tools for identifying leaders of covert organizations. While the literature has predominantly focused on studying the effectiveness of existing centrality measures or developing new ones, we study the problem from the opposite perspective, by focusing on how a group of leaders can avoid being identified by centrality measures as key members of a covert network. More specifically, we analyze the problem of choosing a set of edges to be added to a network to decrease the leaders’ ranking according to three fundamental centrality measures, namely, degree, closeness, and betweenness. We prove that this problem is NP-complete for each measure. Moreover, we study how the leaders can construct a network from scratch, designed specifically to keep them hidden from centrality measures. We identify a network structure that not only guarantees to hide the leaders to a certain extent but also allows them to spread their influence across the network.

AAMAS Conference 2021 Conference Paper

Strategic Evasion of Centrality Measures

• Marcin Waniek
• Jan Woźnica
• Kai Zhou
• Yevgeniy Vorobeychik
• Talal Rahwan
• Tomasz P. Michalak

Among the most fundamental tools for social network analysis are centrality measures, which quantify the importance of every node in the network. This centrality analysis typically disregards the possibility that the network may have been deliberately manipulated to mislead the analysis. To solve this problem, a recent study attempted to understand how a member of a social network could rewire the connections therein to avoid being identified as a leader of that network. However, the study was based on the assumption that the network analyzer—the seeker—is oblivious to any evasion attempts by the evader. In this paper, we relax this assumption by modelling the seeker and evader as strategic players in a Bayesian Stackelberg game. In this context, we study the complexity of various optimization problems, and analyze the equilibria of the game under different assumptions, thereby drawing the first conclusions in the literature regarding which centralities the seeker should use to maximize the chances of detecting a strategic evader.

AAAI Conference 2020 Conference Paper

Hiding in Multilayer Networks

• Marcin Waniek
• Tomasz Michalak
• Talal Rahwan

Multilayer networks allow for modeling complex relationships, where individuals are embedded in multiple social networks at the same time. Given the ubiquity of such relationships, these networks have been increasingly gaining attention in the literature. This paper presents the first analysis of the robustness of centrality measures against strategic manipulation in multilayer networks. More specifically, we consider an “evader” who strategically chooses which connections to form in a multilayer network in order to obtain a low centrality-based ranking—thereby reducing the chance of being highlighted as a key figure in the network—while ensuring that she remains connected to a certain group of people. We prove that determining an optimal way to “hide” is NPcomplete and hard to approximate for most centrality measures considered in our study. Moreover, we empirically evaluate a number of heuristics that the evader can use. Our results suggest that the centrality measures that are functions of the entire network topology are more robust to such a strategic evader than their counterparts which consider each layer separately.

AIJ Journal 2019 Journal Article

Attachment centrality: Measure for connectivity in networks

• Oskar Skibski
• Talal Rahwan
• Tomasz P. Michalak
• Makoto Yokoo

Centrality indices aim to quantify the importance of nodes or edges in a network. Much interest has been recently raised by the body of work in which a node's connectivity is understood less as its contribution to the quality or speed of communication in the network and more as its role in enabling communication altogether. Consequently, a node is assessed based on whether or not the network (or part of it) becomes disconnected if this node is removed. While these new indices deliver promising insights, to date very little is known about their theoretical properties. To address this issue, we propose an axiomatic approach. Specifically, we prove that there exists a unique centrality index satisfying a number of desirable properties. This new index, which we call the Attachment centrality, is equivalent to the Myerson value of a certain graph-restricted game. Building upon our theoretical analysis we show that, while computing the Attachment centrality is #P-complete, it has certain computational properties that are more attractive than the Myerson value for an arbitrary game. In particular, it can be computed in chordal graphs in polynomial time.

AAMAS Conference 2019 Conference Paper

Attacking Similarity-Based Link Prediction in Social Networks

• Kai Zhou
• Tomasz P. Michalak
• Marcin Waniek
• Talal Rahwan
• Yevgeniy Vorobeychik

Link prediction is one of the fundamental problems in computational social science. A particularly common means to predict existence of unobserved links is via structural similarity metrics, such as the number of common neighbors; node pairs with higher similarity are thus deemed more likely to be linked. However, a number of applications of link prediction, such as predicting links in gang or terrorist networks, are adversarial, with another party incentivized to minimize its e�ectiveness by manipulating observed information about the network. We o�er a comprehensive algorithmic investigation of the problem of attacking similarity-based link prediction through link deletion, focusing on two broad classes of such approaches, one which uses only local information about target links, and another which uses global network information. While we show several variations of the general problem to be NP-Hard for both local and global metrics, we exhibit a number of well-motivated special cases which are tractable. Additionally, we provide principled and empirically e�ective algorithms for the intractable cases, in some cases proving worst-case approximation guarantees.

TIST Journal 2019 Journal Article

Enumerating Connected Subgraphs and Computing the Myerson and Shapley Values in Graph-Restricted Games

• Oskar Skibski
• Talal Rahwan
• Tomasz P. Michalak
• Michael Wooldridge

At the heart of multi-agent systems is the ability to cooperate to improve the performance of individual agents and/or the system as a whole. While a widespread assumption in the literature is that such cooperation is essentially unrestricted, in many realistic settings this assumption does not hold. A highly influential approach for modelling such scenarios are graph-restricted games introduced by Myerson [36]. In this approach, agents are represented by nodes in a graph, edges represent communication channels, and a group can generate an arbitrary value only if there exists a direct or indirect communication channel between every pair of agents within the group. Two fundamental solution-concepts that were proposed for such games are the Myerson value and the Shapley value. While an algorithm has been developed to compute the Shapley value in arbitrary graph-restricted games, no such general-purpose algorithm has been developed for the Myerson value to date. With this in mind, we set out to develop for such games a general-purpose algorithm to compute the Myerson value, and a more efficient algorithm to compute the Shapley value. Since the computation of either value involves enumerating all connected induced subgraphs of the game’s underlying graph, we start by developing an algorithm dedicated to this enumeration, and then we show empirically that it is faster than the state of the art in the literature. Finally, we present a sample application of both algorithms, in which we test the Myerson value and the Shapley value as advanced measures of node centrality in networks.

AAAI Conference 2019 Conference Paper

Random Walk Decay Centrality

• Tomasz Wąs
• Talal Rahwan
• Oskar Skibski

We propose a new centrality measure, called the Random Walk Decay centrality. While most centralities in the literature are based on the notion of shortest paths, this new centrality measure stems from the random walk on the network. We provide an axiomatic characterization and show that the new centrality is closely related to PageRank. More in detail, we show that replacing only one axiom, called Lack of Self- Impact, with another one, called Edge Swap, results in the new axiomatization of PageRank. Finally, we argue that Lack of Self-Impact is desirable in various settings and explain why violating Edge Swap may be beneficial and may contribute to promoting diversity in the centrality measure.

TAAS Journal 2018 Journal Article

A Measure of Added Value in Groups

• Bedoor K. Alshebli
• Tomasz P. Michalak
• Oskar Skibski
• Michael Wooldridge
• Talal Rahwan

The intuitive notion of added value in groups represents a fundamental property of biological, physical, and economic systems: how the interaction or cooperation of multiple entities, substances, or other agents can produce synergistic effects. However, despite the ubiquity of group formation, a well-founded measure of added value has remained elusive. Here, we propose such a measure inspired by the Shapley value —a fundamental solution concept from Cooperative Game Theory. To this end, we start by developing a solution concept that measures the average impact of each player in a coalitional game and show how this measure uniquely satisfies a set of intuitive properties. Then, building upon our solution concept, we propose a measure of added value that not only analyzes the interactions of players inside their group, but also outside it, thereby reflecting otherwise-hidden information about how these individuals typically perform in various groups of the population.

JAIR Journal 2018 Journal Article

Axiomatic Characterization of Game-Theoretic Centrality

• Oskar Skibski
• Tomasz P. Michalak
• Talal Rahwan

One of the fundamental research challenges in network science is centrality analysis, i.e., identifying the nodes that play the most important roles in the network. In this article, we focus on the game-theoretic approach to centrality analysis. While various centrality indices have been recently proposed based on this approach, it is still unknown how general is the game-theoretic approach to centrality and what distinguishes some game-theoretic centralities from others. In this article, we attempt to answer this question by providing the first axiomatic characterization of game-theoretic centralities. Specifically, we show that every possible centrality measure can be obtained following the game-theoretic approach. Furthermore, we study three natural classes of game-theoretic centrality, and prove that they can be characterized by certain intuitive properties pertaining to the well-known notion of Fairness due to Myerson.

AAAI Conference 2018 Conference Paper

How AI Wins Friends and Influences People in Repeated Games With Cheap Talk

• Mayada Oudah
• Talal Rahwan
• Tawna Crandall
• Jacob Crandall

Research has shown that a person’s financial success is more dependent on the ability to deal with people than on professional knowledge. Sage advice, such as “if you can’t say something nice, don’t say anything at all” and principles articulated in Carnegie’s classic How to Win Friends and In- fluence People, offer trusted rules-of-thumb for how people can successfully deal with each other. However, alternative philosophies for dealing with people have also emerged. The success of an AI system is likewise contingent on its ability to win friends and influence people. In this paper, we study how AI systems should be designed to win friends and influence people in repeated games with cheap talk (RGCTs). We create several algorithms for playing RGCTs by combining existing behavioral strategies (what the AI does) with signaling strategies (what the AI says) derived from several competing philosophies. Via user study, we evaluate these algorithms in four RGCTs. Our results suggest sufficient properties for AIs to win friends and influence people in RGCTs.

IJCAI Conference 2018 Conference Paper

Quantifying Algorithmic Improvements over Time

• Lars Kotthoff
• Alexandre Fréchette
• Tomasz Michalak
• Talal Rahwan
• Holger H. Hoos
• Kevin Leyton-Brown

Assessing the progress made in AI and contributions to the state of the art is of major concern to the community. Recently, Frechette et al. [2016] advocated performing such analysis via the Shapley value, a concept from coalitional game theory. In this paper, we argue that while this general idea is sound, it unfairly penalizes older algorithms that advanced the state of the art when introduced, but were then outperformed by modern counterparts. Driven by this observation, we introduce the temporal Shapley value, a measure that addresses this problem while maintaining the desirable properties of the (classical) Shapley value. We use the tempo- ral Shapley value to analyze the progress made in (i) the different versions of the Quicksort algorithm; (ii) the annual SAT competitions 2007–2014; (iii) an annual competition of Constraint Programming, namely the MiniZinc challenge 2014–2016. Our analysis reveals novel insights into the development made in these important areas of research over time.

AAAI Conference 2017 Conference Paper

Axiomatic Characterization of Game-Theoretic Network Centralities

• Oskar Skibski
• Tomasz Michalak
• Talal Rahwan

One of the fundamental research challenges in network science is the centrality analysis, i. e. , identifying the nodes that play the most important roles in the network. In this paper, we focus on the game-theoretic approach to centrality analysis. While various centrality indices have been proposed based on this approach, it is still unknown what distinguishes this family of indices from the more classical ones. In this paper, we answer this question by providing the first axiomatic characterization of game-theoretic centralities. Specifically, we show that every centrality can be obtained following the game-theoretic approach, and show that two natural classes of game-theoretic centrality can be characterized by two intuitive properties pertaining to Myerson’s notion of Fairness.

AAMAS Conference 2017 Conference Paper

On the Construction of Covert Networks

• Marcin Waniek
• Tomasz P. Michalak
• Talal Rahwan
• Michael Wooldridge

Centrality measures are widely used to identify leaders of covert networks. We study how a group of such leaders can avoid being detected by such measures. More concretely, we study the hardness of choosing a set of edges that can be added to the network in order to decrease the leaders’ ranking according to two fundamental centrality measures, namely degree, and closeness. We prove that this problem is NP-complete for each measure. We then study how the leaders can construct a network from scratch, designed specifically for them to hide in disguise. We identify a network structure that not only guarantees to hide the leaders to a certain extent, but also allows them to spread their influence across the network.

IS Journal 2017 Journal Article

Online Prediction via Continuous Artificial Prediction Markets

• Fatemeh Jahedpari
• Talal Rahwan
• Sattar Hashemi
• Tomasz P. Michalak
• Marina De Vos
• Julian Padget
• Wei Lee Woon

Prediction markets are well-established tools for aggregating information from diverse sources into accurate forecasts. Their success has been demonstrated in a wide range applications, including presidential campaigns, sporting events, and economic outcomes. Recently, they've been introduced to the machine learning community in the form of artificial prediction markets, in which algorithms trade contracts reflecting their levels of confidence. To date, these markets have mostly been studied in the context of offline classification, with promising results. The authors extend them to enable their use in online regression and introduce adaptive trading strategies informed by individual trading history and the ability of participants to revise their predictions by reflecting on the wisdom of the crowd, which is manifested in the collective performance of the market. The authors empirically evaluate their model using multiple datasets and show that it outperforms several well-established techniques from the literature on online regression.

AAAI Conference 2017 Conference Paper

Strategic Social Network Analysis

• Tomasz Michalak
• Talal Rahwan
• Michael Wooldridge

How can individuals and communities protect their privacy against social network analysis tools? How do criminals or terrorists organizations evade detection by such tools? Under which conditions can these tools be made strategy proof? These fundamental questions have attracted little attention in the literature to date, as most social network analysis tools are built around the assumption that individuals or groups in a network do not act strategically to evade such tools. With this in mind, we outline in this paper a new paradigm for social network analysis, whereby the strategic behaviour of network actors is explicitly modeled. Addressing this research challenge has various implications. For instance, it may allow two individuals to keep their relationship secret or private. It may also allow members of an activist group to conceal their membership, or even conceal the existence of their group from authoritarian regimes. Furthermore, it may assist security agencies and counter terrorism units in understanding the strategies that covert organizations use to escape detection, and give rise to new strategy-proof countermeasures.

AIJ Journal 2016 Journal Article

A hybrid exact algorithm for complete set partitioning

• Tomasz Michalak
• Talal Rahwan
• Edith Elkind
• Michael Wooldridge
• Nicholas R. Jennings

In the Complete Set Partitioning problem we are given a finite set of elements where every subset is associated with a value, and the goal is to partition this set into disjoint subsets so as to maximise the sum of subset values. This abstract problem captures the Coalition Structure Generation problem in cooperative games in characteristic function form, where each subset, or coalition, of agents can make a profit when working together, and the goal is to partition the set of agents into coalitions to maximise the total profit. It also captures the special case of the Winner Determination problem in combinatorial auctions, where bidders place bids on every possible bundle of goods, and the goal is to find an allocation of goods to bidders that maximises the profit of the auctioneer. The main contribution of this article is an extensive theoretical analysis of the search space of the Complete Set Partitioning problem, which reveals that two fundamentally different exact algorithms can be significantly improved upon in terms of actual runtime. These are (1) a dynamic programming algorithm called “DP” [48, 36] and (2) a tree-search algorithm called “IP” [32]. We start by drawing a link between DP and a certain graph describing the structure of the search space. This link reveals that many of DP's operations are in fact redundant. Consequently, we develop ODP—an optimal version of DP that avoids all of its redundant operations. Since ODP and IP are based on different design paradigms, each has its own strengths and weaknesses compared to the other. Thus, one has to trade off the advantages of one algorithm for the advantages of the other. This raises the following question: Is this trade-off inevitable? To answer this question, we develop a new representation of the search space, which links both algorithms, and allows for contrasting the workings of the two. This reveals that ODP and IP can actually be combined, leading to the development of ODP-IP—a hybrid algorithm that avoids the limitations of its constituent parts, while retaining and significantly improving upon the advantages of each part. We benchmark our algorithm against that of Björklund et al. (2009) [8], which runs in O ( 2 n ) time given n agents. We observe that the algorithm of Björklund et al. relies on performing arithmetic operations with very large integers, and assumes that any such operation has unit cost. In practice, however, working with large integers on a modern PC is costly. Consequently, when implemented, our O ( 3 n ) algorithm outperforms that of Björklund et al. by several orders of magnitude on every problem instance, making ours the fastest exact algorithm for complete set partitioning to date in practice.

ECAI Conference 2016 Conference Paper

An Extension of the Owen-Value Interaction Index and Its Application to Inter-Links Prediction

• Piotr L. Szczepanski
• Tomasz Pawel Michalak
• Talal Rahwan
• Michael J. Wooldridge

Link prediction is a key problem in social network analysis: it involves making suggestions about where to add new links in a network, based solely on the structure of the network. We address a special case of this problem, whereby the new links are supposed to connect different communities in the network; we call it the interlinks prediction problem. This is particularly challenging as there are typically very few links between different communities. To solve this problem, we propose a local node-similarity measure, inspired by the Owen-value interaction index-a concept developed in cooperative game theory and fuzzy systems. Although this index requires an exponential number of operations in the general case, we show that our local node-similarity measure is computable in polynomial time. We apply our measure to solve the inter-links prediction problem in a number of real-life networks, and show that it outperforms all other local similarity measures in the literature.

AAMAS Conference 2016 Conference Paper

Attachment Centrality: An Axiomatic Approach to Connectivity in Networks

• Oskar Skibski
• Talal Rahwan
• Tomasz P. Michalak
• Makoto Yokoo

Centrality indices aim to quantify the importance of nodes or edges in a network. A number of new centrality indices have recently been proposed to try and capture the role of nodes in connecting the network. While these indices seem to deliver new insights, to date not enough is known about their theoretical properties. To address this issue, we propose an axiomatic approach. Specifically, we prove that there exists a unique centrality index satisfying some intuitive properties related to network connectivity. This new index, which we call Attachment Centrality, is equivalent to the Myerson value of a particular graph-restricted coalitional game. Building upon our theoretical analysis, we show that our Attachment Centrality has certain computational properties that are more attractive than the Myerson value for an arbitrary game. General Terms Measurement, Theory

AAAI Conference 2016 Conference Paper

Closeness Centrality for Networks with Overlapping Community Structure

• Mateusz Tarkowski
• Piotr Szczepański
• Talal Rahwan
• Tomasz Michalak
• Michael Wooldridge

Certain real-life networks have a community structure in which communities overlap. For example, a typical bus network includes bus stops (nodes), which belong to one or more bus lines (communities) that often overlap. Clearly, it is important to take this information into account when measuring the centrality of a bus stop—how important it is to the functioning of the network. For example, if a certain stop becomes inaccessible, the impact will depend in part on the bus lines that visit it. However, existing centrality measures do not take such information into account. Our aim is to bridge this gap. We begin by developing a new game-theoretic solution concept, which we call the Configuration semivalue, in order to have greater flexibility in modelling the community structure compared to previous solution concepts from cooperative game theory. We then use the new concept as a building block to construct the first extension of Closeness centrality to networks with community structure (overlapping or otherwise). Despite the computational complexity inherited from the Configuration semivalue, we show that the corresponding extension of Closeness centrality can be computed in polynomial time. We empirically evaluate this measure and our algorithm that computes it by analysing the Warsaw public transportation network.

AIJ Journal 2016 Journal Article

Efficient algorithms for game-theoretic betweenness centrality

• Piotr L. Szczepański
• Tomasz P. Michalak
• Talal Rahwan

Betweenness centrality measures the ability of different nodes to control the flow of information in a network. In this article, we extend the standard definition of betweenness centrality using Semivalues—a family of solution concepts from cooperative game theory that includes, among others, the Shapley value and the Banzhaf power index. Any Semivalue-based betweenness centrality measure (such as, for example, the Shapley value-based betweenness centrality measure) has the advantage of evaluating the importance of individual nodes by considering the roles they each play in different groups of nodes. Our key result is the development of a general polynomial-time algorithm to compute the Semivalue-based betweenness centrality measure, and an even faster algorithm to compute the Shapley value-based betweenness centrality measure, both for weighted and unweighted networks. Interestingly, for the unweighted case, our algorithm for computing the Shapley value-based centrality has the same complexity as the best known algorithm for computing the standard betweenness centrality due to Brandes [15]. We empirically evaluate our measures in a simulated scenario where nodes fail simultaneously. We show that, compared to the standard measure, the ranking obtained by our measures reflects more accurately the influence that different nodes have on the functionality of the network.

ECAI Conference 2016 Conference Paper

Non-Utilitarian Coalition Structure Generation

• Oskar Skibski
• Henryk Michalewski
• Andrzej Nagórko
• Tomasz Pawel Michalak
• Andrew James Dowell
• Talal Rahwan
• Michael J. Wooldridge

The coalition structure generation problem is one of the key challenges in multi-agent coalition formation. It involves partitioning a set of agents into coalitions so that system performance is optimized. To date, the multi-agent systems literature has focused exclusively on the utilitarian version of this problem which seeks to maximize the sum of the values of the coalitions involved. However, there are many examples of situations in which other performance metrics are of interest. In particular, in games with non-transferable utility, we may be more interested in an egalitarian optimal coalition structure, or in minimizing the difference between the utilities of the most affluent and poorest agents. In this paper, we present a number of exact algorithms to solve such non-utilitarian formulations of the coalition structure generation problem.

AAAI Conference 2016 Conference Paper

Using the Shapley Value to Analyze Algorithm Portfolios

• Alexandre Fréchette
• Lars Kotthoff
• Tomasz Michalak
• Talal Rahwan
• Holger Hoos
• Kevin Leyton-Brown

Algorithms for NP-complete problems often have different strengths and weaknesses, and thus algorithm portfolios often outperform individual algorithms. It is surprisingly difficult to quantify a component algorithm’s contribution to such a portfolio. Reporting a component’s standalone performance wrongly rewards near-clones while penalizing algorithms that have small but distinct areas of strength. Measuring a component’s marginal contribution to an existing portfolio is better, but penalizes sets of strongly correlated algorithms, thereby obscuring situations in which it is essential to have at least one algorithm from such a set. This paper argues for analyzing component algorithm contributions via a measure drawn from coalitional game theory—the Shapley value—and yields insight into a research community’s progress over time. We conclude with an application of the analysis we advocate to SAT competitions, yielding novel insights into the behaviour of algorithm portfolios, their components, and the state of SAT solving technology.

AIJ Journal 2015 Journal Article

Coalition structure generation: A survey

• Talal Rahwan
• Tomasz P. Michalak
• Michael Wooldridge
• Nicholas R. Jennings

The coalition structure generation problem is a natural abstraction of one of the most important challenges in multi-agent systems: How can a number of agents divide themselves into groups in order to improve their performance? More precisely, the coalition structure generation problem focuses on partitioning the set of agents into mutually disjoint coalitions so that the total reward from the resulting coalitions is maximized. This problem is computationally challenging, even under quite restrictive assumptions. This has prompted researchers to develop a range of algorithms and heuristic approaches for solving the problem efficiently. This article presents a survey of these approaches. In particular, it surveys the main dynamic-programming approaches and anytime algorithms developed for coalition structure generation, and considers techniques specifically developed for a range of compact representation schemes for coalitional games. It also considers settings where there are constraints on the coalitions that are allowed to form, as well as settings where the formation of one coalition could influence the performance of other co-existing coalitions.

IS Journal 2015 Journal Article

Defeating Terrorist Networks with Game Theory

• Tomasz P. Michalak
• Talal Rahwan
• Oskar Skibski
• Michael Wooldridge

This column discusses the problem of identifying key members of a terrorist network. Game-theoretic centrality measures offer solutions but also raise computational challenges. The authors present a survey of this work and show how some of the computational challenges can be overcome.

IJCAI Conference 2015 Conference Paper

Spiteful Bidding in the Dollar Auction

• Marcin Waniek
• Agata Nieścieruk
• Tomasz Michalak
• Talal Rahwan

Shubik’s (all-pay) dollar auction is a simple yet powerful auction model that aims to shed light on the motives and dynamics of conflict escalation. Common intuition and experimental results suggest that the dollar auction is a trap, inducing conflict by its very design. However, O’Neill [1986] proved the surprising fact that, contrary to the experimental results and the intuition, the dollar auction has an immediate solution in pure strategies, i. e. , theoretically it should not lead to conflict escalation. In this paper, inspired by the recent literature on spiteful bidders, we ask whether the escalation in the dollar auction can be induced by meanness. Our results confirm this conjecture in various scenarios.

IJCAI Conference 2015 Conference Paper

The Game-Theoretic Interaction Index on Social Networks with Applications to Link Prediction and Community Detection

• Piotr Lech Szczepański
• Aleksy Stanisław Barcz
• Tomasz Paweł Michalak
• Talal Rahwan

Measuring similarity between nodes has been an issue of extensive research in the social network analysis literature. In this paper, we construct a new measure of similarity between nodes based on the game-theoretic interaction index (Grabisch and Roubens, 1997). Despite the fact that, in general, this index is computationally challenging, we show that in our network application it can be computed in polynomial time. We test our measure on two important problems, namely link prediction and community detection, given several real-life networks. We show that, for the majority of those networks, our measure outperforms other local similarity measures from the literature.

AAMAS Conference 2013 Conference Paper

AgentSwitch: Towards Smart Energy Tariff Selection

• Sarvapali D. Ramchurn
• Michael A. Osborne (University of Oxford, UK)
• Oliver Parson
• Talal Rahwan
• Sasan Maleki
• Steve Reece
• Trung D. Huynh
• Muddasser Alam

We present AgentSwitch, a prototype agent-based platform to solve the tariff selection problem for homeowners. AgentSwitch incorporates novel algorithms that work on the coarse data provided by smart meters to make predictions of hourly energy usage as well as detect (and suggest to the user) deferrable loads that could be shifted to off-peak times to maximise savings. Our demo will allow users to interact with AgentSwitch and explore test user accounts in order to understand the impact of different usage profiles and appliance loads.

IJCAI Conference 2013 Conference Paper

An Efficient Vector-Based Representation for Coalitional Games

• Long Tran-Thanh
• Tri-Dung Nguyen
• Talal Rahwan
• Alex Rogers
• Nicholas R. Jennings

We propose a new representation for coalitional games, called the coalitional skill vector model, where there is a set of skills in the system, and each agent has a skill vector—a vector consisting of values that reflect the agents’ level in different skills. Furthermore, there is a set of goals, each with requirements expressed in terms of the minimum skill level necessary to achieve the goal. Agents can form coalitions to aggregate their skills, and achieve goals otherwise unachievable. We show that this representation is fully expressive, that is, it can represent any characteristic function game. We also show that, for some interesting classes of games, our representation is significantly more compact than the classical representation, and facilitates the development of efficient algorithms to solve the coalition structure generation problem, as well as the problem of computing the core and/or the least core. We also demonstrate that by using the coalitional skill vector representation, our solver can handle up to 500 agents.

IJCAI Conference 2013 Conference Paper

Coalitional Games via Network Flows

• Talal Rahwan
• Tri-Dung Nguyen
• Tomasz P. Michalak
• Maria Polukarov
• Madalina Croitoru
• Nicholas R. Jennings

We introduce a new representation scheme for coalitional games, called coalition-flow networks (CF-NETs), where the formation of effective coalitions in a task-based setting is reduced to the problem of directing flow through a network. We show that our representation is intuitive, fully expressive, and captures certain patterns in a significantly more concise manner compared to the conventional approach. Furthermore, our representation has the flexibility to express various classes of games, such as characteristic function games, coalitional games with overlapping coalitions, and coalitional games with agent types. As such, to the best of our knowledge, CF-NETs is the first representation that allows for switching conveniently and efficiently between overlapping/nonoverlapping coalitions, with/without agent types. We demonstrate the efficiency of our scheme on the coalition structure generation problem, where near-optimal solutions for large instances can be found in a matter of seconds.

IJCAI Conference 2013 Conference Paper

Computational Analysis of Connectivity Games with Applications to the Investigation of Terrorist Networks

• Tomasz P. Michalak
• Talal Rahwan
• Nicholas R. Jennings
• Piotr L. Szczepanski
• Oskar Skibski
• Ramasuri Narayanam
• Michael J. Wooldridge

We study a recently developed centrality metric to identify key players in terrorist organisations due to Lindelauf et al. [2013]. This metric, which involves computation of the Shapley value for connectivity games on graphs proposed by Amer and Gimenez [2004], was shown to produce substantially better results than previously used standard centralities. In this paper, we present the first computational analysis of this class of coalitional games, and propose two algorithms for computing Lindelauf et al. ’s centrality metric. Our first algorithm is exact, and runs in time linear by number of connected subgraphs in the network. As shown in the numerical simulations, our algorithm identifies key players in the WTC 9/11 terrorist network, constructed of 36 members and 125 links, in less than 40 minutes. In contrast, a general-purpose Shapley value algorithm would require weeks to solve this problem. Our second algorithm is approximate and can be used to study much larger networks.

AAAI Conference 2012 Conference Paper

A Hybrid Algorithm for Coalition Structure Generation

• Talal Rahwan
• Tomasz Michalak
• Nicholas Jennings

The current state-of-the-art algorithm for optimal coalition structure generation is IDP-IP—an algorithm that combines IDP (a dynamic programming algorithm due to Rahwan and Jennings, 2008b) with IP (a tree-search algorithm due to Rahwan et al. , 2009). In this paper we analyse IDP-IP, highlight its limitations, and then develop a new approach for combining IDP with IP that overcomes these limitations.

AAMAS Conference 2012 Conference Paper

A New Approach to Betweenness Centrality Based on the Shapley Value

• Piotr Szczepa
• nacute; ski
• Tomasz Michalak
• Talal Rahwan

In many real-life networks, such as urban structures, protein interactions and social networks, one of the key issues is to measure the centrality of nodes, i. e. to determine which nodes and edges are more central to the functioning of the entire network than others. In this paper we focus on \emph{betweenness centrality} - a metric based on which the centrality of a node is measured involving the number of shortest paths that pass through that node. This metric has been shown to be well suited for many, often complex, networks. In itsstandard form, the betweenness centrality, just like other centrality metrics, evaluates nodes based on their individual contributions to the functioning of the network. For instance, the importance of an intersection in a road network can be computed as the difference between the full capacity of this network and its capacity when the intersection is completely shut down. However, as recently argued in the literature, such an approach is inadequate for many real-life applications, as, for example, multiple nodes can fail simultaneously. Thus, what would be desirable is to refine the existing centrality metrics such that they take into account not only the functioning of nodes as individual entities but also as members of groups of nodes. One recently-proposed way of doing this is based on the \emph{Shapley Value} - a solution concept in cooperative game theory that measures in a fair way the contributions of players to all the coalitions that they could possibly participate in. Although this approach has been used to extend various centrality metrics, such an extension to betweenness centrality is yet to be developed. The main challenge when developing such a refinement is to tackle the computational complexity; the Shapely Value generally requires an exponential number of operations, making its use limited to a small number of player (or nodes in our context). Against this background, our main contribution in this paper is to refine the betweenness centrality metric based on the Shapley Value: we develop an algorithm for computing this new metric, and show that it has the same complexity as the best known algorithm due to Brandes to compute the standard betweenness centrality (i. e. , polynomial in the size of the network). Finally, we show that our results can be extended to another important centrality metric called stress centrality.

ECAI Conference 2012 Conference Paper

An Anytime Algorithm for Finding the? -Core in Nontransferable Utility Coalitional Games

• Greg Hines
• Talal Rahwan
• Nicholas R. Jennings

We provide the first anytime algorithm for finding the ϵ -core in a nontransferable utility coalitional game. For a given set of possible joint actions, our algorithm calculates ϵ , the maximum utility any agent could gain by deviating from this set of actions. If ϵ is too high, our algorithm searches for a subset of the joint actions which leads to a smaller ϵ . Simulations show our algorithm is more efficient than an exhaustive search by up to 2 orders of magnitude.

AIJ Journal 2012 Journal Article

Anytime coalition structure generation in multi-agent systems with positive or negative externalities

• Talal Rahwan
• Tomasz Michalak
• Michael Wooldridge
• Nicholas R. Jennings

Much of the literature on multi-agent coalition formation has focused on Characteristic Function Games, where the effectiveness of a coalition is not affected by how the other agents are arranged in the system. In contrast, very little attention has been given to the more general class of Partition Function Games, where the emphasis is on how the formation of one coalition could influence the performance of other co-existing coalitions in the system. However, these inter-coalitional dependencies, called externalities from coalition formation, play a crucial role in many real-world multi-agent applications where agents have either conflicting or overlapping goals. Against this background, this paper is the first computational study of coalitional games with externalities in the multi-agent system context. We focus on the Coalition Structure Generation (CSG) problem which involves finding an exhaustive and disjoint division of the agents into coalitions such that the performance of the entire system is optimized. While this problem is already very challenging in the absence of externalities, due to the exponential size of the search space, taking externalities into consideration makes it even more challenging as the size of the input, given n agents, grows from O ( 2 n ) to O ( n n ). Our main contribution is the development of the first CSG algorithm for coalitional games with either positive or negative externalities. Specifically, we prove that it is possible to compute upper and lower bounds on the values of any set of disjoint coalitions. Building upon this, we prove that in order to establish a worst-case guarantee on solution quality it is necessary to search a certain set of coalition structures (which we define). We also show how to progressively improve this guarantee with further search. Since there are no previous CSG algorithms for games with externalities, we benchmark our algorithm against other state-of-the-art approaches in games where no externalities are present. Surprisingly, we find that, as far as worst-case guarantees are concerned, our algorithm outperforms the others by orders of magnitude. For instance, to reach a bound of 3 given 24 agents, the number of coalition structures that need to be searched by our algorithm is only 0. 0007% of that needed by Sandholm et al. (1999) [1], and 0. 5% of that needed by Dang and Jennings (2004) [2]. This is despite the fact that the other algorithms take advantage of the special properties of games with no externalities, while ours does not.

AAAI Conference 2011 Conference Paper

Constrained Coalition Formation

• Talal Rahwan
• Tomasz Michalak
• Edith Elkind
• Piotr Faliszewski
• Jacek Sroka
• Michael Wooldridge
• Nicholas Jennings

The conventional model of coalition formation considers every possible subset of agents as a potential coalition. However, in many real-world applications, there are inherent constraints on feasible coalitions: for instance, certain agents may be prohibited from being in the same coalition, or the coalition structure may be required to consist of coalitions of the same size. In this paper, we present the first systematic study of constrained coalition formation (CCF). We propose a general framework for this problem, and identify an important class of CCF settings, where the constraints specify which groups of agents should/should not work together. We describe a procedure that transforms such constraints into a structured input that allows coalition formation algorithms to identify, without any redundant computations, all the feasible coalitions. We then use this procedure to develop an algorithm for generating an optimal (welfare-maximizing) constrained coalition structure, and show that it outperforms existing state-of-the-art approaches by several orders of magnitude.

IJCAI Conference 2011 Conference Paper

Minimum Search to Establish Worst-Case Guarantees in Coalition Structure Generation

• Talal Rahwan
• Tomasz Michalak
• Nicholas R. Jennings

Coalition formation is a fundamental research topic in multi-agent systems. In this context, while it is desirable to generate a coalition structure that maximizes the sum of the values of the coalitions, the space of possible solutions is often too large to allow exhaustive search. Thus, a fundamental open question in this area is the following: Can we search through only a subset of coalition structures, and be guaranteed to find a solution that is within a desirable bound beta from optimum? If so, what is the minimum such subset? To date, the above question has only been partially answered by Sandholm et al. in their seminal work on anytime coalition structure generation Sandholm et al. (AIJ 1999). More specifically, they identified minimum subsets to be searched for two particular bounds: β = n and β = [n/2]. Nevertheless, the question remained open for other values of β . In this paper, we provide the complete answer to this question.

AAMAS Conference 2010 Conference Paper

A Distributed Algorithm for Anytime Coalition Structure Generation

• Tomasz Michalak
• Jacek Sroka
• Talal Rahwan
• Michael Wooldridge
• Peter McBurney
• Nicholas R. Jennings

A major research challenge in multi-agent systems is theproblem of partitioning a set of agents into mutually disjoint coalitions, such that the overall performance of thesystem is optimized. This problem is difficult because thesearch space is very large: the number of possible coalition structures increases exponentially with the number ofagents. Although several algorithms have been proposed totackle this Coalition Structure Generation (CSG) problem, all of them suffer from being inherently centralized, whichleads to the existence of a performance bottleneck and a single point of failure. In this paper, we develop the first decentralized algorithm for solving the CSG problem optimally. In our algorithm, the necessary calculations are distributedamong the agents, instead of being carried out centrally bya single agent (as is the case in all the available algorithmsin the literature). In this way, the search can be carriedout in a much faster and more robust way, and the agentscan share the burden of the calculations. The algorithmcombines, and improves upon, techniques from two existingalgorithms in the literature, namely DCVC and IP, and applies novel techniques for filtering the input and reducing the inter-agent communication load.

AAMAS Conference 2010 Conference Paper

A Logic-Based Representation for Coalitional Games with Externalities

• Tomasz Michalak
• Dorota Marciniak
• Marcin Szamotulski
• Talal Rahwan
• Michael Wooldridge
• Peter McBurney
• Nicholas R. Jennings

We consider the issue of representing coalitional games in multi-agent systems that exhibit externalities from coalition formation, i. e. , systems in which the gain from forming a coalition may be affected by the formation of other co-existing coalitions. Althoughexternalities play a key role in many real-life situations, very littleattention has been given to this issue in the multi-agent system literature, especially with regard to the computational aspects involved. To this end, we propose a new representation which, in the spiritof Ieong and Shoham, is based on Boolean expressions. Theidea behind our representation is to construct much richer expressions that allow for capturing externalities induced upon coalitions. We show that the new representation is fully expressive, at least asconcise as the conventional partition function game representationand, for many games, exponentially more concise. We evaluate theefficiency of our new representation by considering the problem ofcomputing the Extended and Generalized Shapley value, a powerful extension of the conventional Shapley value to games withexternalities. We show that by using our new representation, theExtended and Generalized Shapley value, which has not been studied in the computer science literature to date, can be computed intime linear in the size of the input.

ECAI Conference 2010 Conference Paper

A Network Flow Approach to Coalitional Games

• Talal Rahwan
• Tomasz Pawel Michalak
• Madalina Croitoru
• Jacek Sroka
• Nicholas R. Jennings

In this paper we propose a novel approach to represent coalitional games, called a Coalition-Flow Network (CF-NET), that builds upon a generalization of the network flow literature. Specifically, this representation is based on our observation that the coalition formation process can be viewed as the problem of directing the flow through a network where every edge has certain capacity constraints.

ECAI Conference 2010 Conference Paper

Computational Aspects of Extending the Shapley Value to Coalitional Games with Externalities

• Tomasz Pawel Michalak
• Talal Rahwan
• Dorota Marciniak
• Marcin Szamotulski
• Nicholas R. Jennings

Until recently, computational aspects of the Shapley value were only studied under the assumption that there are no externalities from coalition formation, i. e. , that the value of any coalition is independent of other coalitions in the system. However, externalities play a key role in many real-life situations and have been extensively studied in the game-theoretic and economic literature. In this paper, we consider the issue of computing extensions of the Shapley value to coalitional games with externalities proposed by Myerson [21], Pham Do and Norde [23], and McQuillin [17]. To facilitate efficient computation of these extensions, we propose a new representation for coalitional games with externalities, which is based on weighted logical expressions. We demonstrate that this representation is fully expressive and, sometimes, exponentially more concise than the conventional partition function game model. Furthermore, it allows us to compute the aforementioned extensions of the Shapley value in time linear in the size of the input.

IJCAI Conference 2009 Conference Paper

• Talal Rahwan
• Tomasz Michalak
• Nicholas R. Jennings
• Michael Wooldridge
• Peter McBurney

Coalition structure generation has received considerable attention in recent research. Several algorithms have been proposed to solve this problem in Characteristic Function Games (CFGs), where every coalition is assumed to perform equally well in any coalition structure containing it. In contrast, very little attention has been given to the more general Partition Function Games (PFGs), where a coalition’s effectiveness may change from one coalition structure to another. In this paper, we deal with PFGs with positive and negative externalities. In this context, we identify the minimum search that is required in order to establish a bound on the quality of the best coalition structure found. We then develop an anytime algorithm that improves this bound with further search, and show that it outperforms the existing state-of-the-art algorithms by orders of magnitude.

AAMAS Conference 2008 Conference Paper

An Improved Dynamic Programming Algorithm for Coalition Structure Generation

• Talal Rahwan
• NICK JENNINGS

AAAI Conference 2008 Conference Paper

Coalition Structure Generation: Dynamic Programming Meets Anytime Optimization

• Talal Rahwan

Coalition structure generation involves partitioning a set of agents into exhaustive and disjoint coalitions so as to maximize the social welfare. What makes this such a challenging problem is that the number of possible solutions grows exponentially as the number of agents increases. To date, two main approaches have been developed to solve this problem, each with its own strengths and weaknesses. The state of the art in the first approach is the Improved Dynamic Programming (IDP) algorithm, due to Rahwan and Jennings, that is guaranteed to find an optimal solution in O(3n ), but which cannot generate a solution until it has completed its entire execution. The state of the art in the second approach is an anytime algorithm called IP, due to Rahwan et al. , that provides worst-case guarantees on the quality of the best solution found so far, but which is O(nn ). In this paper, we develop a novel algorithm that combines both IDP and IP, resulting in a hybrid performance that exploits the strength of both algorithms and, at the same, avoids their main weaknesses. Our approach is also significantly faster (e. g. given 25 agents, it takes only 28% of the time required by IP, and 0. 3% of the time required by IDP).

IJCAI Conference 2007 Conference Paper

• Talal Rahwan
• Sarvapali D. Ramchurn
• Viet Dung Dang
• Nicholas R. Jennings

Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best set of agents that should articipate in a given team. To this end, in this paper, we present a novel, anytime algorithm for coalition structure generation that is faster than previous anytime algorithms designed for this purpose. Our algorithm can generate solutions that either have a tight bound from the optimal or are optimal (depending on the objective) and works by partitioning the space in terms of a small set of elements that represent structures which contain coalitions of particular sizes. It then performs an online heuristic search that prunes the space and only considers valid and non-redundant coalition structures. We empirically show that we are able to find solutions that are, in the worst case, 99% efficient in 0. 0043% of the time to find the optimal value by the state of the art dynamic programming (DP) algorithm (for 20 agents), using 33% less memory.

AIJ Journal 2007 Journal Article

An algorithm for distributing coalitional value calculations among cooperating agents

• Talal Rahwan
• Nicholas R. Jennings

The process of forming coalitions of software agents generally requires calculating a value for every possible coalition which indicates how beneficial that coalition would be if it was formed. Now, instead of having a single agent calculate all these values (as is typically the case), it is more efficient to distribute this calculation among the agents, thus using all the computational resources available to the system and avoiding the existence of a single point of failure. Given this, we present a novel algorithm for distributing this calculation among agents in cooperative environments. Specifically, by using our algorithm, each agent is assigned some part of the calculation such that the agents' shares are exhaustive and disjoint. Moreover, the algorithm is decentralized, requires no communication between the agents, has minimal memory requirements, and can reflect variations in the computational speeds of the agents. To evaluate the effectiveness of our algorithm, we compare it with the only other algorithm available in the literature for distributing the coalitional value calculations (due to Shehory and Kraus). This shows that for the case of 25 agents, the distribution process of our algorithm took less than 0. 02% of the time, the values were calculated using 0. 000006% of the memory, the calculation redundancy was reduced from 383229848 to 0, and the total number of bytes sent between the agents dropped from 1146989648 to 0 (note that for larger numbers of agents, these improvements become exponentially better).

AAAI Conference 2007 Conference Paper

Anytime Optimal Coalition Structure Generation

• Talal Rahwan
• Viet D. Dang

A key problem when forming effective coalitions of autonomous agents is determining the best groupings, or the optimal coalition structure, to select to achieve some goal. To this end, we present a novel, anytime algorithm for this task that is significantly faster than current solutions. Specifically, we empirically show that we are able to find solutions that are optimal in 0. 082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents), using much less memory (O(2n ) instead of O(3n ) for n agents). Moreover, our algorithm is the first to be able to find solutions for more than 17 agents in reasonable time (less than 90 minutes for 27 agents, as opposed to around 2 months for the best previous solution).

EUMAS Conference 2006 Conference Paper

Near-Optimal Anytime Coalition Structure Generation

• Talal Rahwan
• Sarvapali D. Ramchurn
• Viet Dung Dang
• Nicholas R. Jennings

Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best set of agents that should participate in a given team. To this end, in this paper, we present a novel, anytime algorithm for coalition structure generation that is faster than previous anytime algorithms designed for this purpose. Our algorithm can generate solutions that either have a tight bound from the optimal or are optimal (depending on the objective) and works by partitioning the space in terms of a small set of elements that represent structures which contain coalitions of the same size. It then performs an online heuristic search that prunes the space and only considers valid and non-redundant coalition structures. We empirically show that we are able to find solutions that are, in the worst case, 99% efficient in 0. 0129% of the time to find the optimal value by the state of the art dynamic programming algorithm (for 20 agents).

AAAI Conference 2005 Conference Paper

Distributing Coalitional Value Calculations among Cooperative Agents

• Talal Rahwan

The process of forming coalitions of software agents generally requires calculating a value for every possible coalition which indicates how beneficial that coalition would be if it was formed. Now, since the number of possible coalitions increases exponentially with the number of agents involved, having one agent calculate all the values is inefficient. Given this, we present a novel algorithm for distributing this calculation among agents in cooperative environments. Specifically, by using our algorithm, each agent is assigned some part of the calculation such that the agents’ shares are exhaustive and disjoint. Moreover, the algorithm is decentralized, requires no communication between the agents, and has minimal memory requirements. To evaluate the effectiveness of our algorithm we compare it with the only other algorithm available in the literature (due to Shehory and Kraus). This shows that for the case of 25 agents, the distribution process of our algorithm took 0. 00037% of the time, the values were calculated using 0. 000006% of the memory, the calculation redundancy was reduced from 477826101 to 0, and the total number of bytes sent between the agents dropped from 674047872 to 0 (note that for larger numbers of agents, these improvements become exponentially better).

EUMAS Conference 2005 Conference Paper

Distributing coalitional value calculations among cooperative agents

• Talal Rahwan
• Nicholas R. Jennings