Shaheen Fatima

JAIR Journal 2024 Journal Article

Learning to Resolve Social Dilemmas: A Survey

• Shaheen Fatima
• Nicholas R. Jennings
• Michael Wooldridge

Social dilemmas are situations of inter-dependent decision making in which individual rationality can lead to outcomes with poor social qualities. The ubiquity of social dilemmas in social, biological, and computational systems has generated substantial research across these diverse disciplines into the study of mechanisms for avoiding deficient outcomes by promoting and maintaining mutual cooperation. Much of this research is focused on studying how individuals faced with a dilemma can learn to cooperate by adapting their behaviours according to their past experience. In particular, three types of learning approaches have been studied: evolutionary game-theoretic learning, reinforcement learning, and best-response learning. This article is a comprehensive integrated survey of these learning approaches in the context of dilemma games. We formally introduce dilemma games and their inherent challenges. We then outline the three learning approaches and, for each approach, provide a survey of the solutions proposed for dilemma resolution. Finally, we provide a comparative summary and discuss directions in which further research is needed.

IJCAI Conference 2024 Conference Paper

Learning to Resolve Social Dilemmas: A Survey (Abstract Reprint)

• Shaheen Fatima
• Nicholas Jennings
• Michael Wooldridge

Social dilemmasare situations of inter-dependent decision making in which individualrationality can lead to outcomes with poor social qualities. The ubiquity of social dilem-mas in social, biological, and computational systems has generated substantial researchacross these diverse disciplines into the study of mechanisms for avoiding deficient outcomes by promoting and maintaining mutual cooperation. Much of this research is focused on studying how individuals faced with a dilemma can learn to cooperate by adapting their behaviours according to their past experience. In particular, three types of learning approaches have been studied: evolutionary game-theoretic learning, reinforcement learning, and best-response learning. This article is a comprehensive integrated survey of these learning approaches in the context of dilemma games. We formally introduce dilemma games and their inherent challenges. We then outline the three learning approaches and, for eachapproach, provide a survey of the solutions proposed for dilemma resolution. Finally, we provide a comparative summary and discuss directions in which further research is needed.

KER Journal 2024 Journal Article

‘ I don’t want to play with you anymore ’: dynamic partner judgements in moody reinforcement learners playing the prisoner’s dilemma

• Grace Feehan
• Shaheen Fatima

Abstract Emerging reinforcement learning algorithms that utilize human traits as part of their conceptual architecture have been demonstrated to encourage cooperation in social dilemmas when compared to their unaltered origins. In particular, the addition of a mood mechanism facilitates more cooperative behaviour in multi-agent iterated prisoner dilemma (IPD) games, for both static and dynamic network contexts. Mood-altered agents also exhibit humanlike behavioural trends when environmental aspects of the dilemma are altered, such as the structure of the payoff matrix used. It is possible that other environmental effects from both human and agent-based research will interact with moody structures in previously unstudied ways. As the literature on these interactions is currently small, we seek to expand on previous research by introducing two more environmental dimensions; voluntary interaction in dynamic networks, and stability of interaction through varied network restructuring. From an initial Erdos–Renyi random network, we manipulate the structure of a network IPD according to existing methodology in human-based research, to investigate possible replication of their findings. We also facilitated strategic selection of opponents through the introduction of two partner evaluation mechanisms and tested two selection thresholds for each. We found that even minimally strategic play termination in dynamic networks is enough to enhance cooperation above a static level, though the thresholds for these strategic decisions are critical to desired outcomes. More forgiving thresholds lead to better maintenance of cooperation between kinder strategies than stricter ones, despite overall cooperation levels being relatively low. Additionally, moody reinforcement learning combined with certain play termination decision strategies can mimic trends in human cooperation affected by structural changes to the IPD played on dynamic networks—as can kind and simplistic strategies such as Tit-For-Tat. Implications of this in comparison with human data is discussed, and suggestions for diversification of further testing are made.

AAMAS Conference 2023 Conference Paper

Optimal Coalition Structures for Probabilistically Monotone Partition Function Games

• Shaheen Fatima
• Michael Wooldridge

We define probabilistically monotone partition function games, a subclass of the well-known partition function games in which we introduce uncertainty. We provide a constructive proof that an exact optimum can be found using a greedy approach, present an algorithm for finding an optimum, and analyze its time complexity.

JAAMAS Journal 2022 Journal Article

Optimal coalition structures for probabilistically monotone partition function games

• Shaheen Fatima
• Michael Wooldridge

Abstract For cooperative games with externalities, the problem of optimally partitioning a set of players into disjoint exhaustive coalitions is called coalition structure generation, and is a fundamental computational problem in multi-agent systems. Coalition structure generation is, in general, computationally hard and a large body of work has therefore investigated the development of efficient solutions for this problem. However, the existing methods are mostly limited to deterministic environments. In this paper, we focus attention on uncertain environments. Specifically, we define probabilistically monotone partition function games, a subclass of the well-known partition function games in which we introduce uncertainty. We provide a constructive proof that an exact optimum can be found using a greedy approach, present an algorithm for finding an optimum, and analyze its time complexity.

EUMAS Conference 2020 Conference Paper

Multiagent Task Coordination as Task Allocation Plus Task Responsibility

• Vahid Yazdanpanah
• Mehdi Dastani
• Shaheen Fatima
• Nicholas R. Jennings
• Devrim Murat Yazan
• W. Henk M. Zijm

Abstract In this work, we present a dynamic Task Coordination framework ( ) for multiagent systems. Here task coordination refers to a twofold problem where an exogenously imposed state of affairs should be satisfied by a multiagent system. To address this problem the involved agents or agent groups need to be assigned tasks to fulfill (task allocation) and the behavior of these agents needs to be monitored to evaluate whether their tasks are fulfilled so that responsibility for dismissing tasks can be determined (task responsibility). We believe the allocation of tasks should regard both the strategic abilities of agents and their epistemic limitations. To date, however, existing work on the application of logical strategic reasoning for task allocation assumes perfect information for agents (dismissing imperfect information settings) and allocates tasks to individual agents (dismissing task allocation to agent groups). In, we address this gap by modeling task allocation using imperfect information semantics for strategic reasoning and integrate it with a notion of task responsibility. We formally verify properties of: on validity as well as stability of task allocations and fairness as well as non-monotonicity of task responsibilities.

AAMAS Conference 2019 Conference Paper

Computing Optimal Coalition Structures in Polynomial Time

• Shaheen Fatima
• Michael Wooldridge

The optimal coalition structure determination problem is in general computationally hard. In this article, we identify some problem instances for which the space of possible coalition structures has a certain form and constructively prove that the problem is polynomial time solvable. Specifically, we consider games with an ordering over the players and introduce a distance metric for measuring the distance between any two structures. In terms of this metric, we define the property of monotonicity, meaning that coalition structures closer to the optimal, as measured by the metric, have higher value than those further away. Similarly, quasi-monotonicity means that part of the space of coalition structures is monotonic, while part of it is non-monotonic. (Quasi)-monotonicity is a property that can be satisfied by coalition games in characteristic function form and also those in partition function form. For a setting with a monotonic value function and a known player ordering, we prove that the optimal coalition structure determination problem is polynomial time solvable and devise such an algorithm using a greedy approach. We extend this algorithm to quasi-monotonic value functions and demonstrate how its time complexity improves from exponential to polynomial as the degree of monotonicity of the value function increases. We go further and consider a setting in which the value function is monotonic and an ordering over the players is known to exist but ordering itself is unknown. For this setting too, we prove that the coalition structure determination problem is polynomial time solvable and devise such an algorithm.

JAAMAS Journal 2018 Journal Article

Computing optimal coalition structures in polynomial time

• Shaheen Fatima
• Michael Wooldridge

Abstract The optimal coalition structure determination problem is in general computationally hard. In this article, we identify some problem instances for which the space of possible coalition structures has a certain form and constructively prove that the problem is polynomial time solvable. Specifically, we consider games with an ordering over the players and introduce a distance metric for measuring the distance between any two structures. In terms of this metric, we define the property of monotonicity, meaning that coalition structures closer to the optimal, as measured by the metric, have higher value than those further away. Similarly, quasi-monotonicity means that part of the space of coalition structures is monotonic, while part of it is non-monotonic. (Quasi)-monotonicity is a property that can be satisfied by coalition games in characteristic function form and also those in partition function form. For a setting with a monotonic value function and a known player ordering, we prove that the optimal coalition structure determination problem is polynomial time solvable and devise such an algorithm using a greedy approach. We extend this algorithm to quasi-monotonic value functions and demonstrate how its time complexity improves from exponential to polynomial as the degree of monotonicity of the value function increases. We go further and consider a setting in which the value function is monotonic and an ordering over the players is known to exist but ordering itself is unknown. For this setting too, we prove that the coalition structure determination problem is polynomial time solvable and devise such an algorithm.

EUMAS Conference 2016 Conference Paper

Heuristic Methods for Optimal Coalition Structure Generation

• Amir Hussin
• Shaheen Fatima

Abstract The problem of finding the optimal coalition structure arises frequently in multiagent systems. Heuristic approaches for solving this problem are needed because of its computational complexity. This paper studies two such approaches: tabu search and simulated annealing. Through simulations we show that tabu search generates better quality solutions than simulated annealing for coalition games in characteristic function form and those in partition function form.

JAAMAS Journal 2015 Journal Article

Majority bargaining for resource division

• Shaheen Fatima
• Michael Wooldridge

Abstract We address the problem of how a set of agents can decide to share a resource, represented as a unit-sized pie. The pie can be generated by the entire set but also by some of its subsets. We investigate a finite horizon non-cooperative bargaining game, in which the players take it in turns to make proposals on how the resource should for this purpose be allocated, and the other players vote on whether or not to accept the allocation. Voting is modelled as a Bayesian weighted voting game with uncertainty about the players’ weights. The agenda, (i. e. , the order in which the players are called to make offers), is defined exogenously. We focus on impatient players with heterogeneous discount factors. In the case of a conflict, (i. e. , no agreement by the deadline), no player receives anything. We provide a Bayesian subgame perfect equilibrium for the bargaining game and conduct an ex-ante analysis of the resulting outcome. We show that the equilibrium is unique, computable in polynomial time, results in an instant Pareto optimal outcome, and, under certain conditions provides a foundation for the core and also the nucleolus of the Bayesian voting game. In addition, our analysis leads to insights on how an individual’s bargained share is influenced by his position on the agenda. Finally, we show that, if the conflict point of the bargaining game changes, then the problem of determining the non-cooperative equilibrium becomes NP-hard even under the perfect information assumption. Our research also reveals how this change in conflict point impacts on the above mentioned results.

JAAMAS Journal 2015 Journal Article

Power and welfare in bargaining for coalition structure formation

• Shaheen Fatima
• Tomasz P. Michalak
• Michael Wooldridge

Abstract We investigate a noncooperative bargaining game for partitioning n agents into non-overlapping coalitions. The game has n time periods during which the players are called according to an exogenous agenda to propose offers. With probability \(\delta \), the game ends during any time period \(t<n\). If it does, the first t players on the agenda get a chance to propose but the others do not. Thus, \(\delta \) is a measure of the degree of democracy within the game (ranging from democracy for \(\delta =0\), through increasing levels of authoritarianism as \(\delta \) approaches 1, to dictatorship for \(\delta =1\) ). We determine the subgame perfect equilibrium (SPE) and study how a player’s position on the agenda affects his bargaining power. We analyze the relation between the distribution of power of individual players, the level of democracy, and the welfare efficiency of the game. We find that purely democratic games are welfare inefficient and that introducing a degree of authoritarianism into the game makes the distribution of power more equitable and also maximizes welfare. These results remain invariant under two types of player preferences: one where each player’s preference is a total order on the space of possible coalition structures and the other where each player either likes or dislikes a coalition structure. Finally, we show that the SPE partition may or may not be core stable.

ECAI Conference 2014 Conference Paper

Bargaining for Coalition Structure Formation

• Shaheen Fatima
• Tomasz Pawel Michalak
• Michael J. Wooldridge

Many multiagent settings require a collection of agents to partition themselves into coalitions. In such cases, the agents may have conflicting preferences over the possible coalition structures that may form. We investigate a noncooperative bargaining game to allow the agents to resolve such conflicts and partition themselves into non-overlapping coalitions. The game has a finite horizon and is played over discrete time periods. The bargaining agenda is defined exogenously. An important element of the game is a parameter 0&le; &delta; &le; 1 that represents the probability that bargaining ends in a given round. Thus, &delta; is a measure of the degree of democracy (ranging from democracy for &delta; =0, through increasing levels of authoritarianism as &delta; approaches 1, to dictatorship for &delta; =1). For this game, we focus on the question of how a player's position on the agenda affects his power. We also analyse the relation between the distribution of the power of individual players, the level of democracy, and the welfare efficiency of the game. Surprisingly, we find that purely democratic games are welfare inefficient due to an uneven distribution of power among the individual players. Interestingly, introducing a degree of authoritarianism into the game makes the distribution of power more equitable and maximizes welfare.

ECAI Conference 2014 Conference Paper

Multilateral Bargaining for Resource Division

• Shaheen Fatima
• Michael J. Wooldridge

We address the problem of how a group of agents can decide to share a resource, represented as a unit-sized pie. We investigate a finite horizon non-cooperative bargaining game, in which the players take it in turns to make proposals on how the resource should be allocated, and the other players vote on whether or not to accept the allocation. Voting is modelled as a Bayesian weighted voting game with uncertainty about the players' weights. The agenda, (i. e. , the order in which the players are called to make offers), is defined exogenously. We focus on impatient players with heterogeneous discount factors. In the case of a conflict, (i. e. , no agreement by the deadline), all the players get nothing. We provide a Bayesian subgame perfect equilibrium for the bargaining game and conduct an ex-ante analysis of the resulting outcome. We show that, the equilibrium is unique, computable in polynomial time, results in an instant Pareto optimal agreement, and, under certain conditions provides a foundation for the core of the Bayesian voting game. Our analysis also leads to insights on how an individual's bargained share is influenced by his position on the agenda. Finally, we show that, if the conflict point of the bargaining game changes, then the problem of determining a non-cooperative equilibrium becomes NP-hard even under the perfect information assumption.

IS Journal 2014 Journal Article

The Negotiation Game

• Shaheen Fatima
• Sarit Kraus
• Michael Wooldridge

Here, the authors consider some of the main ideas underpinning attempts to build automated negotiators--computer programs that can effectively negotiate on our behalf.

AAMAS Conference 2011 Conference Paper

On Optimal Agendas for Package Deal Negotiation

• Shaheen Fatima
• Michael Wooldridge
• Nicholas R. Jennings

This paper analyzes bilateral multi-issue negotiation where the issues are indivisible, there are time constraints in the form of deadlines and discount factors. The issues are negotiated using the package deal procedure. The set of issues to be negotiated is called the negotiation agenda. The agenda is crucial since the outcome of negotiation depends on the agenda. This paper therefore looks at the decision making involved in choosing a negotiation agenda. The scenario we look at is as follows. There are m > 2 issues available for negotiation. But from these, an agent must choose g < m issues and negotiate on them. Thus the problem for an agent is to choose an agenda (i. e, a subset of g issues). Clearly, from all possible agendas (i. e. , all possible combinations of g issues), an agent must choose the one that maximizes its expected utility and is therefore its optimal agenda. To this end, this paper presents polynomial time methods for choosing an agent's optimal agenda.

AAMAS Conference 2009 Conference Paper

An Analysis of Feasible Solutions for Multi-Issue Negotiation Involving Nonlinear Utility Functions

• Shaheen Fatima
• Michael Wooldridge
• Nicholas R. Jennings

This paper analyzes bilateral multi-issue negotiation between selfinterested agents. Specifically, we consider the case where issues are divisible, there are time constraints in the form of deadlines and discount factors, and the agents have different preferences over the issues. Given these differing preferences, it is possible to reach Pareto-optimal agreements by negotiating all the issues together using a package deal procedure (PDP). However, finding equilibrium strategies for this procedure is not always computationally easy. In particular, if the agents’ utility functions are nonlinear, then equilibrium strategies may be hard to compute. In order to overcome this complexity, we explore two different solutions. The first is to use the PDP for linear approximations of the given nonlinear utilities. The second solution is to use a simultaneous procedure (SP) where the issues are discussed in parallel but independently of each other. We then compare these two solutions both in terms of their computational properties (i. e. , time complexity of computing an approximate equilibrium and the associated error of approximation) and their economic properties (i. e. , the agents’ utilities and social welfare of the resulting outcome). By doing so, we show that an approximate equilibrium for the PDP and the SP can be found in polynomial time. In terms of the economic properties, although the PDP is known to generate Pareto optimal outcomes, we show that, in some cases, which we identify, the SP is better for one of the two agents and also increases the social welfare.

AAMAS Conference 2008 Conference Paper

An anytime approximation method for the inverse Shapley value problem

• Shaheen Fatima
• Michael Wooldridge
• NICK JENNINGS

Coalition formation is the process of bringing together two or more agents so as to achieve goals that individuals on their own cannot, or to achieve them more efficiently. Typically, in such situations, the agents have conflicting preferences over the set of possible joint goals. Thus, before the agents realize the benefits of cooperation, they must find a way of resolving these conflicts and reaching a consensus. In this context, cooperative game theory offers the voting game as a mechanism for agents to reach a consensus. It also offers the Shapley value as a way of measuring the influence or power a player has in determining the outcome of a voting game. Given this, the designer of a voting game wants to construct a game such that a player’s Shapley value is equal to some desired value. This is called the inverse Shapley value problem. Solving this problem is necessary, for instance, to ensure fairness in the players’ voting powers. However, from a computational perspective, finding a player’s Shapley value for a given game is #P-complete. Consequently, the problem of verifying that a voting game does indeed yield the required powers to the agents is also #P-complete. Therefore, in order to overcome this problem we present a computationally efficient approximation algorithm for solving the inverse problem. This method is based on the technique of ‘successive approximations’; it starts with some initial approximate solution and iteratively updates it such that after each iteration, the approximate gets closer to the required solution. This is an anytime algorithm and has time complexity polynomial in the number of players. We also analyze the performance of this method in terms of its approximation error and the rate of convergence of an initial solution to the required one. Specifically, we show that the former decreases after each iteration, and that the latter increases with the number of players and also with the initial approximation error.

AAMAS Conference 2006 Conference Paper

A Comparative Study of Sequential and Simultaneous Auctions

• Shaheen Fatima

AAMAS Conference 2005 Conference Paper

An analysis of the Shapley value and its uncertainty for the voting game

• Shaheen Fatima
• Michael Wooldridge
• Nicholas Jennings

EUMAS Conference 2005 Conference Paper

An analysis of the Shapley Value and its Uncertainty for the Voting Game

• Shaheen Fatima
• Michael J. Wooldridge
• Nicholas R. Jennings

AAMAS Conference 2004 Conference Paper

Optimal negotiation of multiple issues in incomplete information settings

• Shaheen Fatima
• Michael Wooldridge
• Nicholas Jennings

AAMAS Conference 2003 Conference Paper

Optimal Agendas for Multi-Issue Negotiation

• Shaheen Fatima
• Michael Wooldridge
• Nicholas R. Jennings