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.

Reinforcement learning algorithms applied to social dilemmas sometimes struggle with converging to mutual cooperation against like-minded partners, particularly when utilising greedy behavioural selection methods. Recent research has demonstrated how affective cognitive mechanisms, such as mood and emotion, might facilitate increased rates of mutual cooperation when integrated with these algorithms. This research has, thus far, primarily utilised mobile multi-agent frameworks to demonstrate this relationship - where they have also identified interaction structure as a key determinant of the emergence of cooperation. Here, we use a deterministic, static interaction structure to provide deeper insight into how a particular moody reinforcement learner might encourage the evolution of cooperation in the Iterated Prisoner’s Dilemma. In a novel grid environment, we both replicated original test parameters and then varied the distribution of agents and the payoff matrix. We found that behavioural trends from past research were present (with suppressed magnitude), and that the proportion of mutual cooperations was heightened when both the influence of mood and the cooperation index of the payoff matrix chosen increased. Changing the proportion of moody agents in the environment only increased mutual cooperations by virtue of introducing cooperative agents to each other.

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.

The traditional matrix factorisation (MF)-based recommender system methods, despite their success in making the recommendation, lack explainable recommendations as the produced latent features are meaningless and cannot explain the recommendation. This article introduces an MF-based explainable recommender system framework that utilises the user-item rating data and the available item information to model meaningful user and item latent features. These features are exploited to enhance the rating prediction accuracy and the recommendation explainability. Our proposed feature-based explainable recommender system framework utilises these meaningful user and item latent features to explain the recommendation without relying on private or outer data. The recommendations are explained to the user using text message and bar chart. Our proposed model has been evaluated in terms of the rating prediction accuracy and the reasonableness of the explanation using six real-world benchmark datasets for movies, books, video games, and fashion recommendation systems. The results show that the proposed model can produce accurate explainable recommendations.

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.

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≤δ≤1 that represents the probability that bargaining ends in a given round. Thus, δ is a measure of the degree of democracy (ranging from democracy for δ=0, through increasing levels of authoritarianism as δ approaches 1, to dictatorship for δ=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.

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.

A cross organisation compatible workflows generation and execution framework This item was submitted to Loughborough University's Institutional Repository by the/an author.

This paper proposes a new technique based on Hyper Genetic Algorithm (GA) and Particle Swarm Optimisation (PSO) to evolve optimal agenda for bilateral multi-issue negotiation. In sequential negotiation the agenda specifies the set of issues included in the negotiation and the order in which they will be discussed. A player's profit from negotiation depends on the agenda. Each player wants to find an agenda that yields the highest profit, i.e., his/her optimal agenda. Our proposed technique identifies the best set of issues to be included in the agenda as well as the best ordering for the issues in a way that increases the player's profit. The proposed technique is comprised of two GA systems. Firstly, we have an outer GA system that searches for the best set of issues to be included in the agenda. Secondly, we have an inner GA system that searches for the best order of the selected issues. PSO is used to automatically adjust the parameters of these two GA systems. Empirical evidence demonstrates that the proposed technique evolves better agendas than standard GA, 1+1 Evolutionary Strategy, Fixed Settings Hyper-GA and a simple random search.

Weighted voting games (WVGs) are an important mechanism for modeling scenarios where a group of agents must reach agreement on some issue over which they have different preferences. However, for such games to be effective, they must be well designed. Thus, a key concern for a mechanism designer is to structure games so that they have certain desirable properties. In this context, two such properties are proper and strong. A game is proper if for every coalition that is winning, its complement is not. A game is strong if for every coalition that is losing, its complement is not. In most cases, a mechanism designer wants games that are both proper and strong. To this end, we first show that the problem of determining whether a game is proper or strong is, in general, np-hard. Then we determine those conditions (that can be evaluated in polynomial time) under which a given WVG is proper and those under which it is strong. Finally, for the general np-hard case, we discuss two different approaches for overcoming the complexity: a deterministic approximation scheme and a randomized approximation method.

This paper presents a hyper GA system to evolve optimal agendas for package deal negotiation. The proposed system uses a Surrogate Model based on Radial Basis Function Networks (RBFNs) to speed up the evolution. The negotiation scenario is as follows. There are two negotiators/agents (a and b) and m issues/items available for negotiation. But from these m issues, the agents must choose g

In this paper, we present a co-evolutionary hyper-heuristic method for solving a sequential auction based resource allocation problem. The method combines genetic programming (GP) for evolving agent's bidding functions for the individual auctions with genetic algorithms (GAs) for evolving an optimal ordering for auctions. The framework is evaluated in the context of the exam timetabling problem (ETTP). In this problem, there is a set of exams, which have to be assigned to a predefined set of slots. Here, the exam time tabling system is the seller that sells a set of slots in a series of auctions. There is one auction for each slot. The exams are viewed as the bidding agents in need of slots. The problem is then to find a schedule (i.e., a slot for each exam) such that the total cost of conducting the exams as per the schedule is minimised. In order to arrive at such a schedule, we find the bidders optimal bids for an auction using GP. We combine this with a GA that finds an optimal ordering for conducting the auctions. The effectiveness of this co-evolutionary method is demonstrated experimentally by comparing it with some existing benchmarks for exam timetabling.

Sequential and simultaneous auctions are two important mechanisms for buying and selling multiple objects. These two mechanisms yield different outcomes (i.e., different surpluses, different revenues, and also different profits to the winning bidders). Given this, we compare the outcomes for the sequential and simultaneous mechanisms for the following scenario. There are multiple similar objects for sale, each object is sold in a separate auction, and each bidder needs only one object. Furthermore, each object has both common and private value components and bidders are uncertain about these values. We first determine the equilibrium bidding strategies for each individual auction for the simultaneous and sequential cases. We do this for the English auction rules, the first-price sealed bid rules, and the second-price sealed bid rules. We then consider the case where the private and common values have a uniform distribution and compare the two mechanisms in terms of a bidder's ex-ante expected profit, the auctioneer's expected cumulative revenue, and the expected cumulative surplus. Our study shows that, for all the three auction rules, the expected cumulative surplus and the auctioneer's expected cumulative revenue is higher for the sequential mechanism. However, the mechanism that generates a higher ex-ante expected profit for the bidders depends on the number of objects being auctioned and the number of participating bidders, and it is sometimes higher for sequential mechanism and sometimes for the simultaneous one.

This paper studies bilateral multi-issue negotiation between self-interested autonomous agents. Now, there are a number of different procedures that can be used for this process; the three main ones being the package deal procedure in which all the issues are bundled and discussed together, the simultaneous procedure in which the issues are discussed simultaneously but independently of each other, and the sequential procedure in which the issues are discussed one after another. Since each of them yields a different outcome, a key problem is to decide which one to use in which circumstances. Specifically, we consider this question for a model in which the agents have time constraints (in the form of both deadlines and discount factors) and information uncertainty (in that the agents do not know the opponent's utility function). For this model, we consider issues that are both independent and those that are interdependent and determine equilibria for each case for each procedure. In so doing, we show that the package deal is in fact the optimal procedure for each party. We then go on to show that, although the package deal may be computationally more complex than the other two procedures, it generates Pareto optimal outcomes (unlike the other two), it has similar earliest and latest possible times of agreement to the simultaneous procedure (which is better than the sequential procedure), and that it (like the other two procedures) generates a unique outcome only under certain conditions (which we define).