Georgios Chalkiadakis

AAMAS Conference 2026 Conference Paper

A Novel Framework for Uncertainty-Driven Adaptive Exploration

• Leonidas Bakopoulos
• Georgios Chalkiadakis

Adaptive exploration methods learn complex policies via alternating between exploration and exploitation. An important question for such methods is to determine the appropriate moment to switch between exploration and exploitation and vice versa. This is critical in domains that require the learning of long and complex sequences of actions. In this work, we present a generic adaptive exploration frameworkthatemploysuncertaintytoaddressthisimportantissue in a principled manner. Our framework includes previous adaptive exploration approaches as special cases. Moreover, it can incorporate any uncertainty-measuring mechanism of choice, such as mechanisms used in intrinsic motivation, or epistemic uncertaintybased exploration methods; and is experimentally shown to give rise to adaptive exploration strategies that outperform standard ones across several environments. Moreover, we showcase its potential for utilization in safety-critical domains. The code for this work can be found at https: //github. com/leoBakop/ADEU

AAMAS Conference 2025 Conference Paper

Conditional Max-Sum for Asynchronous Multiagent Decision Making

• Dimitrios Troullinos
• Georgios Chalkiadakis
• Ioannis Papamichail
• Markos Papageorgiou

In this paper we present a novel approach for multiagent decision making in dynamic environments based on Factor Graphs and the Max-Sum algorithm, considering asynchronous variable reassignments and distributed message-passing among agents. Motivated by the challenging domain of lane-free traffic where automated vehicles can communicate and coordinate as agents, we propose a more realistic communication framework for Factor Graph formulations that satisfies the above-mentioned restrictions, along with Conditional Max-Sum: an extension of Max-Sum with a revised message-passing process that is better suited for asynchronous settings. The overall application in lane-free traffic can be viewed as a hybrid system where the Factor Graph formulation undertakes the strategic decision making of vehicles, that of desired lateral alignment in a coordinated manner; and acts on top of a rule-based method we devise that provides a structured representation of the lane-free environment for the factors, while also handling the underlying control of vehicles regarding core operations and safety. Our experimental evaluation showcases the capabilities of the proposed framework in problems with intense coordination needs when compared to a domain-specific baseline without communication, and an increased adeptness of Conditional Max-Sum with respect to the standard algorithm.

AAAI Conference 2025 Conference Paper

Deep Implicit Imitation Reinforcement Learning in Heterogeneous Action Settings

• Iason Chrysomallis
• Georgios Chalkiadakis
• Ioannis Papamichail
• Markos Papageorgiou

Implicit imitation reinforcement learning (IIRL) is a framework that aims to aid a trainee agent’s learning process via observing the state transitions of a mentor, but without access to the latter's action information. Standard IIRL assumes a shared Markov decision process (MDP) between the mentor and trainee, consequently implying an identical action space. This restriction imposes limitations on the applicability of implicit imitation frameworks in real-life scenarios where, possibly due to variations in physical characteristics, the mentor agent may possess distinct own actions, thereby creating a heterogeneous action setting. In this work, we extend the deep implicit imitation Q-networks (DIIQN) method -an online, model-free, deep RL algorithm for implicit imitation- to allow for heterogeneous action sets between mentor and trainee agents. Equipped with our heterogeneous actions DIIQN (HA-DIIQN) method, a trainee agent can harvest the benefits of IIRL even in heterogeneous action settings, achieving accelerated learning and outperforming non-optimal mentor agents.

RLC Conference 2025 Conference Paper

Seldonian Reinforcement Learning for Ad Hoc Teamwork

• Edoardo Zorzi
• Alberto Castellini
• Leonidas Bakopoulos
• Georgios Chalkiadakis
• Alessandro Farinelli

Most offline RL algorithms return optimal policies but do not provide statistical guarantees on desirable behaviors. This could generate reliability issues in safety-critical applications, such as in some multiagent domains where agents, and possibly humans, need to interact to reach their goals without harming each other. In this work, we propose a novel offline RL approach, inspired by Seldonian optimization, which returns policies with good performance and statistically guaranteed properties with respect to predefined desirable behaviors. In particular, our focus is on Ad Hoc Teamwork settings, where agents must collaborate with new teammates without prior coordination. Our method requires only a pre-collected dataset, a set of candidate policies for our agent, and a specification about the possible policies followed by the other players---it does not require further interactions, training, or assumptions on the type and architecture of the policies. We test our algorithm in Ad Hoc Teamwork problems and show that it consistently finds reliable policies while improving sample efficiency with respect to standard ML baselines.

RLJ Journal 2025 Journal Article

Seldonian Reinforcement Learning for Ad Hoc Teamwork

• Edoardo Zorzi
• Alberto Castellini
• Leonidas Bakopoulos
• Georgios Chalkiadakis
• Alessandro Farinelli

Most offline RL algorithms return optimal policies but do not provide statistical guarantees on desirable behaviors. This could generate reliability issues in safety-critical applications, such as in some multiagent domains where agents, and possibly humans, need to interact to reach their goals without harming each other. In this work, we propose a novel offline RL approach, inspired by Seldonian optimization, which returns policies with good performance and statistically guaranteed properties with respect to predefined desirable behaviors. In particular, our focus is on Ad Hoc Teamwork settings, where agents must collaborate with new teammates without prior coordination. Our method requires only a pre-collected dataset, a set of candidate policies for our agent, and a specification about the possible policies followed by the other players---it does not require further interactions, training, or assumptions on the type and architecture of the policies. We test our algorithm in Ad Hoc Teamwork problems and show that it consistently finds reliable policies while improving sample efficiency with respect to standard ML baselines.

JAAMAS Journal 2024 Journal Article

A comprehensive analysis of agent factorization and learning algorithms in multiagent systems

• Andreas Kallinteris
• Stavros Orfanoudakis
• Georgios Chalkiadakis

Abstract In multiagent systems, agent factorization denotes the process of segmenting the state-action space of the environment into distinct components, each corresponding to an individual agent, and subsequently determining the interactions among these agents. Effective agent factorization significantly influences the system performance of real-world industrial applications. In this work, we try to assess the performance impact of agent factorization when using different learning algorithms in multiagent coordination settings; and thus discover the source of performance quality of the multiagent solution derived by combining different factorizations with different learning algorithms. To this end, we evaluate twelve different agent factorization instances—or agent definitions —in the warehouse traffic management domain, comparing the training performance of (primarily) three learning algorithms suitable for learning coordinated multiagent policies: the Evolutionary Strategies ( ES ), the Canonical Evolutionary Strategies ( CES ), and a genetic algorithm ( CCEA ) previously used in a similar setting. Our results demonstrate that the performance of different learning algorithms is affected in different ways by alternative agent definitions. Given this, we can conclude that many important multiagent coordination problems can eventually be solved more efficiently by a suitable agent factorization combined with an appropriate choice of a learning algorithm. Moreover, our work shows that ES and CES are effective learning algorithms for the warehouse traffic management domain, while, interestingly, celebrated policy gradient methods do not fare well in this complex real-world problem setting. As such, our work offers insights into the intrinsic properties of the learning algorithms that make them well-suited for this problem domain. More broadly, our work demonstrates the need to identify appropriate agent definitions-multiagent learning algorithm pairings in order to solve specific complex problems effectively, and provides insights into the general characteristics that such pairings must possess to address broad classes of multiagent learning and coordination problems.

EUMAS Conference 2024 Conference Paper

Adversarial Search and Deep Learning for Strategic Settlement Placement in the "Settlers of Catan"

• Diamantis Rafail Papadam
• Georgios Chalkiadakis

Abstract Despite recent deep neural network superhuman performance in many strategic board games, such as Chess and Go, there does not yet exist an algorithm that beats “Settlers of Catan” expert human players. Towards this direction, we present a combination of modern machine learning with a traditional tree-based adversarial search algorithm for initial settlement placement, and achieve performance that essentially matches the state-of-the-art. In particular, we use the n -player generalization of the classic Minimax search algorithm, known as Max \(^n\), with the novelty that the evaluation function at the leaf nodes is the result of a forward pass in a trained convolutional neural network. Our work consists of two distinct parts that can work independently. The first is the use of the simple Max \(^n\) algorithm for the first time in this game setting. The second is the use of the neural network as an evaluation function for evaluating the initial settlement placement, and which could potentially be plugged into any adversarial search algorithm. After 10000 simulated games, which is a sufficient number to draw conclusions in this demanding strategic board game, we achieve performance close to the state-of-the-art; with the advantages that (a) our approach does not make use of any human-generated data corpus; and (b) that our approach’s runtime is acceptable by human players, and much lower than the state-of-the-art’s for initial placement in this domain.

AAAI Conference 2024 Conference Paper

FairPlay: A Multi-Sided Fair Dynamic Pricing Policy for Hotels

• Errikos Streviniotis
• Athina Georgara
• Filippo Bistaffa
• Georgios Chalkiadakis

In recent years, popular touristic destinations face overtourism. Local communities suffer from its consequences in several ways. Among others, overpricing and profiteering harms local societies and economies deeply. In this paper we focus on the problem of determining fair hotel room prices. Specifically, we put forward a dynamic pricing policy where the price of a room depends not only on the demand of the hotel it belongs to but also on the demand of: (i) similar rooms in the area and (ii) their hotels. To this purpose, we model our setting as a cooperative game and exploit an appropriate game theoretic solution concept that promotes fairness both on the customers' and the providers' side. Our simulation results involving price adjustments across real-world hotels datasets, confirm that ours is a fair dynamic pricing policy, avoiding both over- and under-pricing hotel rooms.

EUMAS Conference 2024 Conference Paper

Protocol Design Patterns for Statecharts-Based Open MAS Development

• Nikolaos I. Spanoudakis
• Charilaos Akasiadis
• Georgios Kechagias
• Georgios Chalkiadakis

Abstract In this paper we define two novel design patterns that can be used with statecharts-based agent modeling in many real-world domains that call for open Multi-agent System architectures. The first pattern is based on the well-known factory design pattern, and the second on the composite pattern. The applicability of our proposed patterns is demonstrated with ASEME, an agent-oriented software engineering methodology that uses statecharts for the inter- and intra-agent control models and the popular, FIPA standards-compliant, JADE agent platform. We showcase the patterns usage through an application for the modern vehicle-to-grid (V2G) and grid-to-vehicle (G2V) energy transfer problem domain.

AAMAS Conference 2023 Conference Paper

A Novel Aggregation Framework for the Efficient Integration of Distributed Energy Resources in the Smart Grid

• Stavros Orfanoudakis
• Georgios Chalkiadakis

In this paper, we put forward a novel DER aggregation framework, encompassing a multiagent architecture and various types of mechanisms for the effective management and efficient integration of DERs in the Grid. One critical component of our architecture is the Local Flexibility Estimators (LFEs) agents, which are key for offloading the Aggregator from serious or resource-intensive responsibilities—such as addressing privacy concerns and predicting the accuracy of DER statements regarding their offered demand response services. The proposed aggregation framework allows the formation of efficient LFE cooperatives. Our experiments verify its effectiveness for incorporating heterogeneous DERs into the Grid in an efficient manner—showing that the use of appropriate mechanisms results in higher payments for participating LFEs.

ECAI Conference 2023 Conference Paper

Deep Reinforcement Learning with Implicit Imitation for Lane-Free Autonomous Driving

• Iason Chrysomallis
• Dimitrios Troullinos
• Georgios Chalkiadakis
• Ioannis Papamichail
• Markos Papageorgiou

Implicit imitation assumes that learning agents observe only the state transitions of an agent they use as a mentor, and try to recreate them based on their own abilities and knowledge of their environment. In this paper, we put forward a deep implicit imitation Q-network (DIIQN) model, which incorporates ideas from three well-known Deep Q-Network (DQN) variants. As such, we enable a novel implicit imitation method for online, model-free deep reinforcement learning. Our thorough experimentation in the complex environment of the emerging lane-free traffic paradigm, verifies the benefits of our approach. Specifically, we show that deep implicit imitation RL dramatically accelerates the learning process when compared to a “vanilla” DQN method; and, unlike explicit imitation reinforcement learning, it is able to outperform mentor performance without resorting to additional information, such as the mentor’s actions.

EUMAS Conference 2022 Conference Paper

Collaborative Decision Making for Lane-Free Autonomous Driving in the Presence of Uncertainty

• Pavlos Geronymakis
• Dimitrios Troullinos
• Georgios Chalkiadakis
• Markos Papageorgiou

Abstract The recently introduced lane-free traffic paradigm removes the restrictions of the traffic lanes, so that autonomous vehicles can move anywhere laterally across the road’s width. Previous research in this domain has employed the celebrated max-plus message-passing algorithm in order to allow the coordination of all (connected and autonomous) vehicles in the environment. However, when allowing for the realistic perspective that there exist vehicles that are unable or unwilling to communicate with others, the uncertainty introduced renders the aforementioned coordination approach ineffective. To combat this, in this paper we adjust the Max-plus algorithm accordingly so that agents using max-plus for coordination can also observe and take into consideration independent agents via emulated messages. We put forward different methods to form these messages—namely the Maximax, Maximin, Hurwicz, Minimax Regret and Laplace decision-making criteria. Finally, we provide a thorough evaluation of our approach, including a detailed comparison of all criteria used for message-forming.

AAMAS Conference 2022 Conference Paper

Max-sum with Quadtrees for Continuous DCOPs with Application to Lane-Free Autonomous Driving

• Dimitrios Troullinos
• Georgios Chalkiadakis
• Vasilis Samoladas
• Markos Papageorgiou

In this paper we put forward a novel extension of the classic Max- Sum algorithm to the framework of Continuous Distributed Constrained Optimization Problems (Continuous DCOPs), in which we model the exchanged messages by means of a popular geometric algorithm, Quadtrees. As such, the discretization process is dynamic and embedded in the internal Max-Sum operations (addition and marginal maximization). We apply our Max-Sum with Quadtrees approach to Lane-Free Autonomous Driving in a highway populated with vehicles. Our experimental evaluation verifies the efficiency of our approach in this challenging dynamic coordination domain, demonstrating its superior performance with respect to the standard Max-Sum algorithm.

IJCAI Conference 2022 Conference Paper

Max-Sum with Quadtrees for Decentralized Coordination in Continuous Domains

• Dimitrios Troullinos
• Georgios Chalkiadakis
• Vasilis Samoladas
• Markos Papageorgiou

In this paper we put forward a novel extension of the classic Max-Sum algorithm to the framework of Continuous Distributed Constrained Optimization Problems (Continuous DCOPs), by utilizing a popular geometric algorithm, namely Quadtrees. In its standard form, Max-Sum can only solve Continuous DCOPs with an a priori discretization procedure. Existing Max-Sum extensions to continuous multiagent coordination domains require additional assumptions regarding the form of the factors, such as access to the gradient, or the ability to model them as continuous piecewise linear functions. Our proposed approach has no such requirements: we model the exchanged messages with Quadtrees, and, as such, the discretization procedure is dynamic and embedded in the internal Max-Sum operations (addition and marginal maximization). We apply Max-Sum with Quadtrees to lane-free autonomous driving. Our experimental evaluation showcases the effectiveness of our approach in this challenging coordination domain.

AAMAS Conference 2021 Conference Paper

A Succinct Representation Scheme for Cooperative Games under Uncertainty

• Errikos Streviniotis
• Athina Georgara
• Georgios Chalkiadakis

In this work we present a novel succinct representation for large partially observed cooperative games. The proposed representation exploits estimates over marginal contributions to form compact rules representing collaboration patterns with uncertain value. Specifically, given an initial set of MC-nets rules that use prior beliefs over values instead of the actual ones, we propose two types of merging that lead to a new set of even more compact rules.

EUMAS Conference 2021 Conference Paper

Aiming for Half Gets You to the Top: Winning PowerTAC 2020

• Stavros Orfanoudakis
• Stefanos Kontos
• Charilaos Akasiadis
• Georgios Chalkiadakis

Abstract The PowerTAC competition provides a multi-agent simulation platform for electricity markets, in which intelligent agents acting as electricity brokers compete with each other aiming to maximize their profits. Typically, the gains of agents increase as the number of their customers rises, but in parallel, costs also increase as a result of higher transmission fees that need to be paid by the electricity broker. Thus, agents that aim to take over a disproportionately high share of the market, often end up with losses due to being obliged to pay huge transmission capacity fees. In this paper, we present a novel trading strategy that, based on this observation, aims to balance gains against costs; and was utilized by the champion of the PowerTAC-2020 tournament, TUC-TAC. The approach also incorporates a wholesale market strategy that employs Monte Carlo Tree Search to determine TUC-TAC’s best course of action when participating in the market’s double auctions. The strategy is improved by making effective use of a forecasting module that seeks to predict upcoming peaks in demand, since in such intervals incurred costs significantly increase. A post-tournament analysis is also included in this paper, to help draw important lessons regarding the strengths and weaknesses of the various strategies used in the PowerTAC-2020 competition.

AAMAS Conference 2021 Conference Paper

Collaborative Multiagent Decision Making for Lane-Free Autonomous Driving

• Dimitrios Troullinos
• Georgios Chalkiadakis
• Ioannis Papamichail
• Markos Papageorgiou

This paper addresses the problem of collaborative multi-agent autonomous driving of connected and automated vehicles (CAVs) in lane-free highway scenarios. We eliminate the lane-changing task, i. e. , CAVs may be located in any arbitrary lateral position within the road boundaries, hence allowing for better utilization of the available road capacity. As a consequence, vehicles operate in a much more complex environment, and the need for the individual CAVs to select actions that are efficient for the group as a whole is highly desired. We formulate this environment as a multiagent collaboration problem represented via a coordination graph, thus decomposing the problem with local utility functions, based on the interactions between vehicles. We produce a tractable and scalable solution by estimating the joint action of all vehicles via the anytime max-plus algorithm, with local utility functions provided by potential fields, designed to promote collision avoidance. Specifically, the fields have an ellipsoid form that is most suitable for lane-free highway environments. This novel use of max-plus with potential fields gives rise to a coordinated control policy that exploits only local information specific to each CAV. Our experimental evaluation confirms the effectiveness of our approach: lane-free movement allows for increased traffic flow rates, and vehicles are able to achieve speeds that are both high and close to their desired ones, even in demanding environments with high traffic flow.

AAMAS Conference 2021 Conference Paper

Optimising Long-Term Outcomes using Real-World Fluent Objectives: An Application to Football

• Ryan Beal
• Georgios Chalkiadakis
• Timothy J. Norman
• Sarvapali D. Ramchurn

In this paper, we present a novel approach for optimising longterm tactical and strategic decision-making in football (soccer) by encapsulating events in a league environment across a given time frame. We model the teams’ objectives for a season and track how these evolve as games unfold to give a fluent objective that can aid in decision-making games. We develop Markov chain Monte Carlo and deep learning-based algorithms that make use of the fluent objectives in order to learn from prior games and other games in the environment and increase the teams’ long-term performance. Simulations of our approach using real-world datasets from 760 matches shows that by using optimised tactics with our fluent objective and prior games, we can on average increase teams mean expected finishing distribution in the league by up to 35. 6%.

AAMAS Conference 2019 Conference Paper

An Open MAS Services Architecture for the V2G/G2V Problem

• Nikolaos Spanoudakis
• Charilaos Akasiadis
• Georgios Kechagias
• Georgios Chalkiadakis

In this paper we propose an original and open multi-agent system architecture for the important and challenging to engineer vehicleto-grid (V2G) and grid-to-vehicle (G2V) energy transfer problem domain. To address the features required, we define two novel design patterns that can be used with statecharts in many real-world situations. The first one is based on the well-known factory design pattern, and the second on the class generalization relationship. These patterns can be coupled with ASEME, an agent-oriented software engineering methodology that uses statecharts for the inter- and intra-agent control models. The latter also fits well with the FIPA standards-compliant JADE agent platform that we used for implementation.

AIJ Journal 2019 Journal Article

Cooperative games with overlapping coalitions: Charting the tractability frontier

• Yair Zick
• Georgios Chalkiadakis
• Edith Elkind
• Evangelos Markakis

The framework of cooperative games with overlapping coalitions (OCF games), which was proposed by Chalkiadakis et al. [1], generalizes classic cooperative games to settings where agents may belong to more than one coalition. OCF games can be used to model scenarios where agents distribute resources, such as time or energy, among several tasks, and then divide the payoffs generated by these tasks in a fair and/or stable manner. As the framework of OCF games is very expressive, identifying settings that admit efficient algorithms for computing ‘good’ outcomes of OCF games is a challenging task. In this work, we put forward two approaches that lead to tractability results for OCF games. First, we propose a discretized model of overlapping coalition formation, where each agent i has a weight W i ∈ N and may allocate an integer amount of weight to any task. Within this framework, we focus on the computation of outcomes that are socially optimal and/or stable. We discover that the algorithmic complexity of this task crucially depends on the amount of resources that each agent possesses, the maximum coalition size, and the pattern of communication among the agents. We identify several constraints that lead to tractable subclasses of discrete OCF games, and supplement our tractability results by hardness proofs, which clarify the role of our constraints. Second, we introduce and analyze a natural class of (continuous) OCF games—the Linear Bottleneck Games. We show that such games always admit a stable outcome, even assuming a large space of feasible deviations, and provide an efficient algorithm for computing such outcomes.

IJCAI Conference 2019 Conference Paper

Influence of State-Variable Constraints on Partially Observable Monte Carlo Planning

• Alberto Castellini
• Georgios Chalkiadakis
• Alessandro Farinelli

Online planning methods for partially observable Markov decision processes (POMDPs) have recently gained much interest. In this paper, we propose the introduction of prior knowledge in the form of (probabilistic) relationships among discrete state-variables, for online planning based on the well-known POMCP algorithm. In particular, we propose the use of hard constraint networks and probabilistic Markov random fields to formalize state-variable constraints and we extend the POMCP algorithm to take advantage of these constraints. Results on a case study based on Rocksample show that the usage of this knowledge provides significant improvements to the performance of the algorithm. The extent of this improvement depends on the amount of knowledge encoded in the constraints and reaches the 50% of the average discounted return in the most favorable cases that we analyzed.

EUMAS Conference 2018 Conference Paper

Deep Reinforcement Learning in Strategic Board Game Environments

• Konstantia Xenou
• Georgios Chalkiadakis
• Stergos D. Afantenos

Abstract In this paper we propose a novel Deep Reinforcement Learning (DRL) algorithm that uses the concept of “action-dependent state features”, and exploits it to approximate the Q-values locally, employing a deep neural network with parallel Long Short Term Memory (LSTM) components, each one responsible for computing an action-related Q-value. As such, all computations occur simultaneously, and there is no need to employ “target” networks and experience replay, which are techniques regularly used in the DRL literature. Moreover, our algorithm does not require previous training experiences, but trains itself online during game play. We tested our approach in the Settlers Of Catan multi-player strategic board game. Our results confirm the effectiveness of our approach, since it outperforms several competitors, including the state-of-the-art jSettler heuristic algorithm devised for this particular domain.

EUMAS Conference 2018 Conference Paper

Learning Hedonic Games via Probabilistic Topic Modeling

• Athina Georgara
• Thalia Ntiniakou
• Georgios Chalkiadakis

Abstract A usual assumption in the hedonic games literature is that of complete information; however, in the real world this is almost never the case. As such, in this work we assume that the players’ preference relations are hidden: players interact within an unknown hedonic game, of which they can observe a small number of game instances. We adopt probabilistic topic modeling as a learning tool to extract valuable information from the sampled game instances. Specifically, we employ the online Latent Dirichlet Allocation (LDA) algorithm in order to learn the latent preference relations in Hedonic Games with Dichotomous preferences. Our simulation results confirm the effectiveness of our approach.

EUMAS Conference 2018 Conference Paper

Markov Chain Monte Carlo for Effective Personalized Recommendations

• Michail-Angelos Papilaris
• Georgios Chalkiadakis

Abstract This paper adopts a Bayesian approach for finding top recommendations. The approach is entirely personalized, and consists of learning a utility function over user preferences via employing a sampling-based, non-intrusive preference elicitation framework. We explicitly model the uncertainty over the utility function and learn it through passive user feedback, provided in the form of clicks on previously recommended items. The utility function is a linear combination of weighted features, and beliefs are maintained using a Markov Chain Monte Carlo algorithm. Our approach overcomes the problem of having conflicting user constraints by identifying a convex region within a user’s preferences model. Additionally, it handles situations where not enough data about the user is available, by exploiting the information from clusters of (feature) weight vectors created by observing other users’ behavior. We evaluate our system’s performance by applying it in the online hotel booking recommendations domain using a real-world dataset, with very encouraging results.

AAMAS Conference 2018 Conference Paper

Overlapping Coalition Formation via Probabilistic Topic Modeling

• Michalis Mamakos
• Georgios Chalkiadakis

Research in cooperative games often assumes that agents know the coalitional values with certainty, and that they can belong to one coalition only. By contrast, this work assumes that the value of a coalition is based on an underlying collaboration structure emerging due to existing but unknown relations among the agents; and that agents can form overlapping coalitions. Specifically, we first propose Relational Rules, a novel representation scheme for cooperative games with overlapping coalitions, which encodes the aforementioned relations, and which extends the well-known MCnets representation to this setting. We then present a novel decisionmaking method for decentralized overlapping coalition formation, which exploits probabilistic topic modeling—and, in particular, online Latent Dirichlet Allocation. By interpreting formed coalitions as documents, agents can effectively learn topics that correspond to profitable collaboration structures.

AIJ Journal 2017 Journal Article

A cooperative game-theoretic approach to the social ridesharing problem

• Filippo Bistaffa
• Alessandro Farinelli
• Georgios Chalkiadakis
• Sarvapali D. Ramchurn

In this work, we adopt a cooperative game theoretic approach in order to tackle the social ridesharing (SR) problem, where a set of commuters, connected through a social network, form coalitions and arrange one-time rides at short notice. In particular, we address two fundamental aspects of this problem. First, we focus on the optimisation problem of forming the travellers' coalitions that minimise the travel cost of the overall system. To this end, we model the formation problem as a Graph-Constrained Coalition Formation (GCCF) one, where the set of feasible coalitions is restricted by a graph (i. e. , the social network). Our approach allows users to specify both spatial and temporal preferences for the trips. Second, we tackle the payment allocation aspect of SR, by proposing the first approach that computes kernel-stable payments for systems with thousands of agents. We conduct a systematic empirical evaluation that uses real-world datasets (i. e. , GeoLife and Twitter). We are able to compute optimal solutions for medium-sized systems (i. e. , with 100 agents), and high quality solutions for very large systems (i. e. , up to 2000 agents). Our results show that our approach improves the social welfare (i. e. , reduces travel costs) by up to 36. 22% with respect to the scenario with no ridesharing. Finally, our payment allocation method computes kernel-stable payments for 2000 agents in less than an hour—while the state of the art is able to compute payments only for up to 100 agents, and does so 84 times slower than our approach.

IS Journal 2017 Journal Article

Mechanism Design for Demand-Side Management

• Charilaos Akasiadis
• Georgios Chalkiadakis

As the penetration of renewables into the grid increases, so do the uncertainty and constraints that need to be taken into account during demand-side management (DSM). Mechanism design (MD) provides effective DSM solutions that incorporate end-user preferences and uncertain capabilities, without jeopardizing comfort. The authors discuss the state of the art in DSM methods, which they broadly classify as game theoretic (largely MD) and not. They then proceed to outline a novel scheme for large-scale coordinated demand shifting, a highly important problem. Their mechanism employs the services of cooperatives of electricity consumers, incentivizes truthfulness regarding the contributions promised by the participants, and incorporates profiling techniques that assess contributors' trustworthiness. It is shown via simulations over real-world datasets to effectively shift peak load and generate substantial economic benefits at cooperative and individual levels.

IJCAI Conference 2017 Conference Paper

Probability Bounds for Overlapping Coalition Formation

• Michail Mamakos
• Georgios Chalkiadakis

In this work, we provide novel methods which benefit from obtained probability bounds for assessing the ability of teams of agents to accomplish coalitional tasks. To this end, our first method is based on an improvement of the Paley-Zygmund inequality, while the second and the third ones are devised based on manipulations of the two-sided Chebyshev’s inequality and the Hoeffding’s inequality, respectively. Agents have no knowledge of the amount of resources others possess; and hold private Bayesian beliefs regarding the potential resource investment of every other agent. Our methods allow agents to demand that certain confidence levels are reached, regarding the resource contributions of the various coalitions. In order to tackle real-world scenarios, we allow agents to form overlapping coalitions, so that one can simultaneously be part of a number of coalitions. We thus present a protocol for iterated overlapping coalition formation (OCF), through which agents can complete tasks that grant them utility. Agents lie on a social network and their distance affects their likelihood of cooperation towards the completion of a task. We confirm our methods’ effectiveness by testing them on both a random graph of 300 nodes and a real-world social network of 4039 nodes.

AAMAS Conference 2017 Conference Paper

WITHDRAWN Post Processing & Paginating (4/6, LT) Evolutionary Game-theoretic Modeling of Past Societies' Organization Structure

• Angelos Chliaoutakis
• Georgios Chalkiadakis

In this work, we extend a generic agent-based model for simulating ancient societies, by blending, for the first time, evolutionary game theory with multiagent systems’ self-organization. Our approach models the evolution of social behaviours in a population of strategically interacting agents corresponding to households in the early Minoan era. To this end, agents participate in repeated games by means of which they exchange utility (corresponding to resources) with others. The results of the games contribute to both the continuous re-organization of the social structure, and the progressive adoption of the most successful agent strategies. Agent population is not fixed, but fluctuates over time. The particularity of the domain necessitates that agents in our games receive non-static payoffs, in contrast to most games studied in the literature; and that the evolutionary dynamics are formulated via assessing the perceived fitness of the agents, defined in terms of how successful they are in accumulating utility. We present a systematic evaluation of the performance of the various strategies, assuming several variations in the way agent fitness and agent organization fitness are defined, as well as in the way agents adopt new strategies. Overall, our results show that societies of strategic agents that self-organize via adopting the aforementioned evolutionary approach, demonstrate a sustainability that largely matches that of self-organizing societies of more cooperative agents; and that strategic cooperation is in fact, in many instances, an emergent behaviour in this domain. Our approach can provide intuitions to archaeological research, and help resolve open questions regarding the socio-economic dynamics at work in past societies. CCS Concepts •Computing methodologies → Multi-agent systems; Modeling and simulation; •Theory of computation → Self-organization; Algorithmic game theory; Multi-agent learning;

JAAMAS Journal 2016 Journal Article

Agent-based modeling of ancient societies and their organization structure

• Angelos Chliaoutakis
• Georgios Chalkiadakis

Abstract Some of the most interesting questions one can ask about early societies, are about people and their relations, and the nature and scale of their organization. In this work, we attempt to answer such questions with approaches introduced by multiagent systems. Specifically, we developed a generic agent-based model (ABM) for simulating ancient societies. Unlike most existing ABMs used in archaeology, our model includes agents that are autonomous and utility-based. Our model can (and does) also incorporate different social organization paradigms and technologies used in ancient societies. Equipped with such paradigms, our model allows us to explore the transition from a simple to a more complex society by focusing on the historical social dynamics—i. e. , the flexibility and evolution of power relationships depending on social context and time. As a case study, we employ our model to evaluate the impact of the implemented social and technological paradigms on an artificial Early Bronze Age “Minoan” society located at a particular region of the island of Crete. Model parameter choices are based on archaeological evidence and studies, but are not biased towards any specific assumption. Results over a number of different simulation scenarios demonstrate an impressive sustainability for settlements consisting of and adopting a socio-economic organization model based on self-organization, and which was inspired by a recent framework for modern self-organizing agent organizations. This is the first time a self-organization approach is incorporated in an archaeology ABM system.

AIJ Journal 2016 Journal Article

Characteristic function games with restricted agent interactions: Core-stability and coalition structures

• Georgios Chalkiadakis
• Gianluigi Greco
• Evangelos Markakis

In many real-world settings, the structure of the environment constrains the formation of coalitions among agents. These settings can be represented by characteristic function games, also known as coalitional games, equipped with interaction graphs. An interaction graph determines the set of all feasible coalitions, in that a coalition C can form only if the subgraph induced over the nodes/agents in C is connected. Our work analyzes stability issues arising in such environments, by focusing on the core as a solution concept, and by considering the coalition structure viewpoint, that is, without assuming that the grand-coalition necessarily forms. The complexity of the coalition structure core is studied over a variety of interaction graph structures of interest, including complete graphs, lines, cycles, trees, and nearly-acyclic graphs (formally, having bounded treewidth). The related stability concepts of the least core and the cost of stability are also studied. Results are derived for the setting of compact coalitional games, i. e. , for games that are implicitly described via a compact encoding, and where simple calculations on this encoding are to be performed in order to compute the payoff associated with any coalition. Moreover, specific results are provided for compact games defined via marginal contribution networks, an expressive encoding mechanism that received considerable attention in the last few years.

ECAI Conference 2016 Conference Paper

Decentralized Large-Scale Electricity Consumption Shifting by Prosumer Cooperatives

• Charilaos Akasiadis
• Georgios Chalkiadakis

In this work we address the problem of coordinated consumption shifting for electricity prosumers. We show that individual optimization with respect to electricity prices does not always lead to minimized costs, thus necessitating a cooperative approach. A prosumer cooperative employs an internal cryptocurrency mechanism for coordinating members decisions and distributing the collectively generated profits. The mechanism generates cryptocoins in a distributed fashion, and awards them to participants according to various criteria, such as contribution impact and accuracy between stated and final shifting actions. In particular, when a scoring rules-based distribution method is employed, participants are incentivized to be accurate. When tested on a large dataset with real-world production and consumption data, our approach is shown to provide incentives for accurate statements and increased economic profits for the cooperative.

EUMAS Conference 2016 Conference Paper

Efficient Multi-criteria Coalition Formation Using Hypergraphs (with Application to the V2G Problem)

• Filippos Christianos
• Georgios Chalkiadakis

Abstract This paper proposes, for the first time in the literature, the use of hypergraphs for the efficient formation of effective coalitions. We put forward several formation methods that build on existing hypergraph pruning, transversal, and clustering algorithms, and exploit the hypergraph structure to identify agents with desirable characteristics. Our approach allows the near-instantaneous formation of high quality coalitions, adhering to multiple stated quality requirements. Moreover, our methods are shown to scale to dozens of thousands of agents within fractions of a second; with one of them scaling to even millions of agents within seconds. We apply our approach to the problem of forming coalitions to provide (electric) vehicle-to-grid (V2G) services. Ours is the first approach able to deal with large-scale, real-time coalition formation for the V2G problem, while taking multiple criteria into account for creating the electric vehicle coalitions.

ECAI Conference 2016 Conference Paper

Employing Hypergraphs for Efficient Coalition Formation with Application to the V2G Problem

• Filippos Christianos
• Georgios Chalkiadakis

This paper proposes, for the first time in the literature, the use of hypergraphs for the efficient formation of effective coalitions. We put forward several formation methods that build on existing hypergraph algorithms, and exploit hypergraph structure to identify agents with desirable characteristics. Our approach allows the near-instantaneous formation of high quality coalitions, while adhering to multiple stated requirements regarding coalition quality. Moreover, our methods are shown to scale to dozens of thousands of agents within fractions of a second; with one of them scaling to even millions of agents within seconds. We apply our approach to the problem of forming coalitions to provide (electric) vehicle-to-grid (V2G) services. Ours is the first approach able to deal with large-scale, realtime coalition formation for the V2G problem, while taking multiple criteria into account for creating electric vehicle coalitions.

ECAI Conference 2016 Conference Paper

Evolutionary Agent-Based Modeling of Past Societies' Organization Structure

• Angelos Chliaoutakis
• Georgios Chalkiadakis

In this work, we extend a generic agent-based model for simulating ancient societies, by blending, for the first time, evolutionary game theory with multiagent systems' self-organization. Our approach models the evolution of social behaviours in a population of strategically interacting agents corresponding to households in the early Minoan era. To this end, agents participate in repeated games by means of which they exchange utility (corresponding to resources) with others. The results of the games contribute to both the continuous re-organization of the social structure, and the progressive adoption of the most successful agent strategies. Agent population is not fixed, but fluctuates over time. The particularity of the domain necessitates that agents in our games receive non-static payoffs, in contrast to most games studied in the literature; and that the evolutionary dynamics are formulated via assessing the perceived fitness of the agents, defined in terms of how successful they are in accumulating utility. Our results show that societies of strategic agents that self-organize via adopting the aforementioned evolutionary approach, demonstrate a sustainability that largely matches that of self-organizing societies of more cooperative agents; and that strategic cooperation is in fact, in many instances, an emergent behaviour in this domain.

IJCAI Conference 2016 Conference Paper

Optimal Prosumer Decision-Making Using Factored MDPs

• Angelos Angelidakis
• Georgios Chalkiadakis

Tackling the decision-making problem faced by a prosumer (i. e. , a producer that is simultaneously a consumer) when selling and buying energy in the emerging smart electricity grid, is of utmost importance for the economic profitability of such a business entity. In this work, we model, for the first time, this problem as a factored Markov Decision Process. By so doing, we are able to rep-resent the problem compactly, and provide an ex-act optimal solution via dynamic programming - notwithstanding its large size. Our model success-fully captures the main aspects of the business decisions of a prosumer corresponding to a community microgrid of any size. Moreover, it includes appropriate sub-models for prosumer production and consumption prediction. Experimental simulations verify the effectiveness of our approach; and show that our exact value iteration solution matches that of a state-of-the-art method for stochastic planning in very large environments, while outperforming it in terms of computation time.

EUMAS Conference 2016 Conference Paper

Probabilistic Topic Modeling, Reinforcement Learning, and Crowdsourcing for Personalized Recommendations

• Evangelos Tripolitakis
• Georgios Chalkiadakis

Abstract We put forward an innovative use of probabilistic topic modeling (PTM) intertwined with reinforcement learning (RL), to provide personalized recommendations. Specifically, we model items under recommendation as mixtures of latent topics following a distribution with Dirichlet priors; this can be achieved via the exploitation of crowdsourced information for each item. Similarly, we model the user herself as an “evolving” document represented by its respective mixture of latent topics. The user’s topic distribution is appropriately updated each time she consumes an item. Recommendations are subsequently based on the divergence between the topic distributions of the user and available items. However, to tackle the exploration versus exploitation dilemma, we apply RL to vary the user’s topic distribution update rate. Our method is immune to the notorious “cold start” problem, and it can effectively cope with changing user preferences. Moreover, it is shown to be competitive against state-of-the-art algorithms, outperforming them in terms of sequential performance.

EUMAS Conference 2015 Conference Paper

Factored MDPs for Optimal Prosumer Decision-Making in Continuous State Spaces

• Angelos Angelidakis
• Georgios Chalkiadakis

Abstract The economic profitability of Smart Grid prosumers (i. e. , producers that are simultaneously consumers) depends on their tackling of the decision-making problem they face when selling and buying energy. In previous work, we had modelled this problem compactly as a factored Markov Decision Process, capturing the main aspects of the business decisions of a prosumer corresponding to a community microgrid of any size. Though that work had employed an exact value iteration algorithm to obtain a near-optimal solution over discrete state spaces, it could not tackle problems defined over continuous state spaces. By contrast, in this paper we show how to use approximate MDP solution methods for taking decisions in this domain without the need of discretizing the state space. Specifically, we employ fitted value iteration, a sampling-based approximation method that is known to be well behaved. By so doing, we generalize our factored MDP solution method to continuous state spaces. We evaluate our approach using a variety of basis functions over different state sample sizes, and compare its performance to that of our original “exact” value iteration algorithm. Our generic approximation method is shown to exhibit stable performance in terms of accumulated reward, which for certain basis functions reaches 98 % of that gathered by the exact algorithm.

AAAI Conference 2015 Conference Paper

Towards Optimal Solar Tracking: A Dynamic Programming Approach

• Athanasios Aris Panagopoulos
• Georgios Chalkiadakis
• Nicholas Jennings

The power output of photovoltaic systems (PVS) increases with the use of effective and efficient solar tracking techniques. However, current techniques suffer from several drawbacks in their tracking policy: (i) they usually do not consider the forecasted or prevailing weather conditions; even when they do, they (ii) rely on complex closed-loop controllers and sophisticated instruments; and (iii) typically, they do not take the energy consumption of the trackers into account. In this paper, we propose a policy iteration method (along with specialized variants), which is able to calculate near-optimal trajectories for effective and efficient day-ahead solar tracking, based on weather forecasts coming from online providers. To account for the energy needs of the tracking system, the technique employs a novel and generic consumption model. Our simulations show that the proposed methods can increase the power output of a PVS considerably, when compared to standard solar tracking techniques.

ECAI Conference 2014 Conference Paper

Stochastic Filtering Methods for Predicting Agent Performance in the Smart Grid

• Charilaos Akasiadis
• Georgios Chalkiadakis

A variety of multiagent systems methods has been proposed for forming cooperatives of interconnected agents representing electricity producers or consumers in the Smart Grid. One major problem that arises in this domain is assessing participating agents uncertainty, and correctly predicting their future behaviour. In this paper, we adopt two stochastic filtering techniques -the Unscented Kalman Filter equipped with Gaussian Processes, and the Histogram Filter- and use these to effectively monitor the trustworthiness of agent statements regarding their final actions. The methods are incorporated within a directly applicable scheme for providing electricity demand management services. Simulation results confirm that these techniques provide tangible benefits regarding enhanced consumption reduction performance, and increased financial gains.

AAAI Conference 2013 Conference Paper

Agent Cooperatives for Effective Power Consumption Shifting

• Charilaos Akasiadis
• Georgios Chalkiadakis

In this paper, we present a directly applicable scheme for electricity consumption shifting and effective demand curve flattening. The scheme can employ the services of either individual or cooperating consumer agents alike. Agents participating in the scheme, however, are motivated to form cooperatives, in order to reduce their electricity bills via lower group prices granted for sizable consumption shifting from high to low demand time intervals. The scheme takes into account individual costs, and uses a strictly proper scoring rule to reward contributors according to efficiency. Cooperative members, in particular, can attain variable reduced electricity price rates, given their different load shifting capabilities. This allows even agents with initially forbidding shifting costs to participate in the scheme, and is achieved by a weakly budget-balanced, truthful reward sharing mechanism. We provide four variants of this approach, and evaluate it experimentally.

AAMAS Conference 2012 Conference Paper

Coalitional Stability in Structured Environments

• Georgios Chalkiadakis
• Vangelis Markakis
• NICK JENNINGS

In many real-world settings, the structure of the environment constrains the formation of coalitions among agents. Therefore, examining the stability of formed coalition structures in such settings is of natural interest. We address this by considering core-stability within various models of cooperative games with structure. First, we focus on characteristic function games defined on graphs that determine feasible coalitions. In particular, a coalition $S$ can emerge only if $S$ is a connected set in the graph. We study the (now modified) core, in which it suffices to check only feasible deviations. Specifically, we investigate core non-emptiness as well as the complexity of computing stable configurations. We then move on to the more general class of (graph-restricted) partition function games, where the value of a coalition depends on which other coalitions are present, and provide the first stability results in this domain. Finally, we propose a ``Bayesian' extension of partition function games, in which information regarding the success of a deviation is provided in the form of a probability distribution describing the possible reactions of non-deviating agents, and provide the first core-stability results in this model also.

AAAI Conference 2012 Conference Paper

Competing with Humans at Fantasy Football: Team Formation in Large Partially-Observable Domains

• Tim Matthews
• Sarvapali Ramchurn
• Georgios Chalkiadakis

We present the first real-world benchmark for sequentiallyoptimal team formation, working within the framework of a class of online football prediction games known as Fantasy Football. We model the problem as a Bayesian reinforcement learning one, where the action space is exponential in the number of players and where the decision maker’s beliefs are over multiple characteristics of each footballer. We then exploit domain knowledge to construct computationally tractable solution techniques in order to build a competitive automated Fantasy Football manager. Thus, we are able to establish the baseline performance in this domain, even without complete information on footballers’ performances (accessible to human managers), showing that our agent is able to rank at around the top percentile when pitched against 2. 5M human players.

IS Journal 2012 Journal Article

Cooperative Game Theory: Basic Concepts and Computational Challenges

• Georgios Chalkiadakis
• Edith Elkind
• Michael Wooldridge

Cooperative game theory studies situations in which agents can benefit by working together. This article outlines the key concepts of cooperative game theory, and discusess the challenges that arise in applying these in AI applications.

AAAI Conference 2012 Conference Paper

Cooperative Virtual Power Plant Formation Using Scoring Rules

• Valentin Robu
• Ramachandra Kota
• Georgios Chalkiadakis
• Alex Rogers
• Nicholas Jennings

Virtual Power Plants (VPPs) are fast emerging as a suitable means of integrating small and distributed energy resources (DERs), like wind and solar, into the electricity supply network (Grid). VPPs are formed via the aggregation of a large number of such DERs, so that they exhibit the characteristics of a traditional generator in terms of predictability and robustness. In this work, we promote the formation of such “cooperative” VPPs (CVPPs) using multi-agent technology. In particular, we design a payment mechanism that encourages DERs to join CVPPs with large overall production. Our method is based on strictly proper scoring rules and incentivises the provision of accurate predictions from the CVPPs—and in turn, the member DERs—which aids in the planning of the supply schedule at the Grid. We empirically evaluate our approach using the real-world setting of 16 commercial wind farms in the UK. We show that our mechanism incentivises real DERs to form CVPPs, and outperforms the current state of the art payment mechanism developed for this problem.

AAMAS Conference 2012 Conference Paper

Cooperative Virtual Power Plant Formation Using Scoring Rules

• Valentin Robu
• Ramachandra Kota
• Georgios Chalkiadakis
• Alex Rogers
• NICK JENNINGS

The growing focus on sustainable and environmentally friendly energy production has resulted in the proliferation of distributed energy resources (DERs), mainly based on renewable sources like wind and sunlight. However, their small size and the intermittent nature of their supply means that such generators cannot easily be assimilated into the current electricity network (Grid) like conventional generators. Against this background, Virtual Power Plants are fast emerging as a solution to this problem whereby a large number of small energy generators may be aggregated together such that they exhibit the characteristics like a traditional generator in terms of predictability and robustness. In this work, we propose a method to promote the formation of such “cooperative” VPPs (CVPPs) using multi-agent technology. In particular, we design a payment mechanism that encourages DERs to join CVPPs with large overall production. Our method is based on strictly proper scoring rules and elicits accurate probabilistic estimates of energy production from the CVPPs—and in turn, the member DERs— which aids in the planning of the supply schedule at the Grid. We empirically evaluate our approach using the real-world setting of 16 commercial wind farms in the UK, and we show that our mechanism incentivises real DERs to form CVPPs and, moreover, it outperforms the current state of the art payment mechanism developed for this problem.

ECAI Conference 2012 Conference Paper

Cooperatives for Demand Side Management

• Ramachandra Kota
• Georgios Chalkiadakis
• Valentin Robu
• Alex Rogers
• Nicholas R. Jennings

We propose a new scheme for efficient demand side management for the Smart Grid. Specifically, we envisage and promote the formation of cooperatives of medium-large consumers and equip them (via our proposed mechanisms) with the capability of regularly participating in the existing electricity markets by providing electricity demand reduction services to the Grid. Based on mechanism design principles, we develop a model for such cooperatives by designing methods for estimating suitable reduction amounts, placing bids in the market and redistributing the obtained revenue amongst the member agents. Our mechanism is such that the member agents have no incentive to show artificial reductions with the aim of increasing their revenues.

AAMAS Conference 2012 Conference Paper

Decentralized Bayesian Reinforcement Learning for Online Agent Collaboration

• Luke Teacy
• Georgios Chalkiadakis
• Alessandro Farinelli
• Alex Rogers
• NICK JENNINGS
• Sally McClean
• Gerard Parr

Solving complex but structured problems in a decentralized manner via multiagent collaboration has received much attention in recent years. This is natural, as on one hand, multiagent systems usually possess a structure that determines the allowable interactions among the agents; and on the other hand, the single most pressing need in a cooperative multiagent system is to coordinate the local policies of autonomous agents with restricted capabilities to serve a system-wide goal. The presence of uncertainty makes this even more challenging, as the agents face the additional need to learn the unknown environment parameters while forming (and following) local policies in an online fashion. In this paper, we provide the first Bayesian reinforcement learning (BRL) approach for distributed coordination and learning in a cooperative multiagent system by devising two solutions to this type of problem. More specifically, we show how the Value of Perfect Information (VPI) can be used to perform efficient decentralised exploration in both model-based and model-free BRL, and in the latter case, provide a closed form solution for VPI, correcting a decade old result by Dearden, Friedman and Russell. To evaluate these solutions, we present experimental results comparing their relative merits, and demonstrate empirically that both solutions outperform an existing multiagent learning method, representative of the state-of-the-art.

AAMAS Conference 2012 Conference Paper

Overlapping Coalition Formation Games: Charting the Tractability Frontier

• Yair Zick
• Georgios Chalkiadakis
• Edith Elkind

Cooperative games with overlapping coalitions (OCF games) model scenarios where agents can distribute their resources among several tasks; each task generates a profit which may be freely divided among the agents participating in the task. The goal of this work is to initiate a systematic investigation of algorithmic aspects of OCF games. We propose a discretized model of overlapping coalition formation, where each agent $i \in N$ has a weight $w_i \in \mathbb{N}$ and may allocate an integer amount of weight to any task. Within this framework, we focus on the computation of outcomes that are socially optimal and/or stable. We discover that the algorithmic complexity of the associated problems crucially depends on the amount of resources that each agent possesses, the maximum coalition size, and the pattern of interaction among the agents. We identify several constraints that lead to tractable subclasses of OCF games, and provideefficient algorithms for games that belong to these subclasses. We supplement our tractability results by hardness proofs, which clarify the role of our constraints.

ECAI Conference 2012 Conference Paper

Predicting the Power Output of Distributed Renewable Energy Resources within a Broad Geographical Region

• Athanasios Aris Panagopoulos
• Georgios Chalkiadakis
• Eftichios Koutroulis 0001

In recent years, estimating the power output of inherently intermittent and potentially distributed renewable energy sources has become a major scientific and societal concern. In this paper, we provide an algorithmic framework, along with an interactive web-based tool, to enable short-to-middle term forecasts of photovoltaic (PV) systems and wind generators output. Importantly, we propose a generic PV output estimation method, the backbone of which is a solar irradiance approximation model that incorporates free-to-use, readily available meteorological data coming from online weather stations. The model utilizes non-linear approximation components for turning cloud-coverage into radiation forecasts, such as an MLP neural network with one hidden layer. We present a thorough evaluation of the proposed techniques, and show that they can be successfully employed within a broad geographical region (the Mediterranean belt) and come with specific performance guarantees. Crucially, our methods do not rely on complex and expensive weather models and data, and our web-based tool can be of immediate use to the community as a simulation data acquisition platform.

AAMAS Conference 2011 Conference Paper

Cooperatives of Distributed Energy Resources for Efficient Virtual Power Plants

• Georgios Chalkiadakis
• Valentin Robu
• Ramachandra Kota
• Alex Rogers
• Nicholas R. Jennings

The creation of Virtual Power Plants (VPPs) has been suggested in recent years as the means for achieving the cost-efficient integration of the many distributed energy resources (DERs) that are starting to emerge in the electricity network. In this work, we contribute to the development of VPPs by offering a game-theoretic perspective to the problem. Specifically, we design cooperatives (or "cooperative VPPs"-CVPPs) of rational autonomous DER-agents representing small-to-medium size renewable electricity producers, which coalesce to profitably sell their energy to the electricity grid. By so doing, we help to counter the fact that individual DERs are often excluded from the wholesale energy market due to their perceived inefficiency and unreliability. We discuss the issues surrounding the emergence of such cooperatives, and propose a pricing mechanism with certain desirable properties. Specifically, our mechanism guarantees that CVPPs have the incentive to truthfully report to the grid accurate estimates of their electricity production, and that larger rather than smaller CVPPs form; this promotes CVPP efficiency and reliability. In addition, we propose a scheme to allocate payments within the cooperative, and show that, given this scheme and the pricing mechanism, the allocation is in the core and, as such, no subset of members has a financial incentive to break away from the CVPP. Moreover, we develop an analytical tool for quantifying the uncertainty about DER production estimates, and distinguishing among different types of errors regarding such estimates. We then utilize this tool to devise protocols to manage CVPP membership. Finally, we demonstrate these ideas through a simulation that uses real-world data.

JAAMAS Journal 2010 Journal Article

Sequentially optimal repeated coalition formation under uncertainty

• Georgios Chalkiadakis
• Craig Boutilier

Abstract Coalition formation is a central problem in multiagent systems research, but most models assume common knowledge of agent types. In practice, however, agents are often unsure of the types or capabilities of their potential partners, but gain information about these capabilities through repeated interaction. In this paper, we propose a novel Bayesian, model-based reinforcement learning framework for this problem, assuming that coalitions are formed (and tasks undertaken) repeatedly. Our model allows agents to refine their beliefs about the types of others as they interact within a coalition. The model also allows agents to make explicit tradeoffs between exploration (forming “new” coalitions to learn more about the types of new potential partners) and exploitation (relying on partners about which more is known), using value of information to define optimal exploration policies. Our framework effectively integrates decision making during repeated coalition formation under type uncertainty with Bayesian reinforcement learning techniques. Specifically, we present several learning algorithms to approximate the optimal Bayesian solution to the repeated coalition formation and type-learning problem, providing tractable means to ensure good sequential performance. We evaluate our algorithms in a variety of settings, showing that one method in particular exhibits consistently good performance in practice. We also demonstrate the ability of our model to facilitate knowledge transfer across different dynamic tasks.

IJCAI Conference 2009 Conference Paper

• Georgios Chalkiadakis
• Edith Elkind
• Nicholas R. Jennings

We introduce coalitional games with beliefs (CGBs), a natural generalization of coalitional games to environments where agents possess private beliefs regarding the capabilities (or types) of others. We put forward a model to capture such agent-type uncertainty, and study coalitional stability in this setting. Specifically, we introduce a notion of the core for CGBs, both with and without coalition structures. For simple games without coalition structures, we then provide a characterization of the core that matches the one for the full information case, and use it to derive a polynomial-time algorithm to check core nonemptiness. In contrast, we demonstrate that in games with coalition structures allowing beliefs increases the computational complexity of stability-related problems. In doing so, we introduce and analyze weighted voting games with beliefs, which may be of independent interest. Finally, we discuss connections between our model and other classes of coalitional games.

AAMAS Conference 2009 Conference Paper

The Price of Democracy in Coalition Formation

• Georgios Chalkiadakis
• Edith Elkind
• Maria Polukarov
• Nicholas R. Jennings

Whenever rational agents form coalitions to execute tasks, doing so via a decentralized negotiation process—while more robust and democratic—may lead to a loss of efficiency compared to a centralized solution. To quantify this loss, we introduce the notion of the Price of Democracy (PoD), which measures the amount of resources needlessly committed to the task(s) at hand. After defining this concept for general coalitional games, we instantiate it in the setting of weighted voting games, a simple but expressive class of coalitional games that can be used to model resource allocation in multiagent scenarios. We approach the problem of forming winning coalitions in this setting from a non-cooperative perspective, and put forward an intuitive deterministic bargaining process, which exhibits no delay of agreement (i. e. , the agents are guaranteed to form a winning coalition in round one) and allows for efficient computation of bargaining strategies. We show a tight bound of 3/2 on the PoD of our process if two rounds of bargaining are allowed, and demonstrate that this bound cannot improve with more rounds. We then generalize our bargaining process to settings where multiple coalitions are allowed to be formed, show that this generalization also exhibits no delay of agreement, and discuss the PoD in such settings.

ECAI Conference 2008 Conference Paper

Coalition Structures in Weighted Voting Games

• Edith Elkind
• Georgios Chalkiadakis
• Nicholas R. Jennings

Weighted voting games are a popular model of collaboration in multiagent systems. In such games, each agent has a weight (intuitively corresponding to resources he can contribute), and a coalition of agents wins if its total weight meets or exceeds a given threshold. Even though coalitional stability in such games is important, existing research has nonetheless only considered the stability of the grand coalition. In this paper, we introduce a model for weighted voting games with coalition structures. This is a natural extension in the context of multiagent systems, as several groups of agents may be simultaneously at work, each serving a different task. We then proceed to study stability in this context. First, we define the CS-core, a notion of the core for such settings, discuss its non-emptiness, and relate it to the traditional notion of the core in weighted voting games. We then investigate its computational properties. We show that, in contrast with the traditional setting, it is computationally hard to decide whether a game has a non-empty CS-core, or whether a given outcome is in the CS-core. However, we then provide an efficient algorithm that verifies whether an outcome is in the CS-core if all weights are small (polynomially bounded). Finally, we also suggest heuristic algorithms for checking the non-emptiness of the CS-core.

AAMAS Conference 2008 Conference Paper

Sequential Decision Making in Repeated Coalition Formation under Uncertainty

• Georgios Chalkiadakis
• Craig Boutilier

The problem of coalition formation when agents are uncertain about the types or capabilities of their potential partners is a critical one. In [3] a Bayesian reinforcement learning framework is developed for this problem when coalitions are formed (and tasks undertaken) repeatedly: not only does the model allow agents to refine their beliefs about the types of others, but uses value of information to define optimal exploration policies. However, computational approximations in that work are purely myopic. We present novel, non-myopic learning algorithms to approximate the optimal Bayesian solution, providing tractable means to ensure good sequential performance. We evaluate our algorithms in a variety of settings, and show that one, in particular, exhibits consistently good sequential performance. Further, it enables the Bayesian agents to transfer acquired knowledge among different dynamic tasks.

AAMAS Conference 2008 Conference Paper

Sequential Decision Making with Untrustworthy Service Providers

• Luke Teacy
• Georgios Chalkiadakis
• Alex Rogers
• NICK JENNINGS

In this paper, we deal with the sequential decision making problem of agents operating in computational economies, where there is uncertainty regarding the trustworthiness of service providers populating the environment. Specifically, we propose a generic Bayesian trust model, and formulate the optimal Bayesian solution to the exploration-exploitation problem facing the agents when repeatedly interacting with others in such environments. We then present a computationally tractable Bayesian reinforcement learning algorithm to approximate that solution by taking into account the expected value of perfect information of an agent’s actions. Our algorithm is shown to dramatically outperform all previous finalists of the international Agent Reputation and Trust (ART) competition, including the winner from both years the competition has been run.

IJCAI Conference 2007 Conference Paper

• Georgios Chalkiadakis
• Craig Boutilier

Coalition formation is a problem of great interest in AI, allowing groups of autonomous, individually rational agents to form stable teams. Automating the negotiations underlying coalition formation is, naturally, of special concern. However, research to date in both AI and economics has largely ignored the potential presence of uncertainty in coalitional bargaining. We present a model of discounted coalitional bargaining where agents are uncertain about the types (or capabilities) of potential partners, and hence the value of a coalition. We cast the problem as a Bayesian game in extensive form, and describe its Perfect Bayesian Equilibria as the solutions to a polynomial program. We then present a heuristic algorithm using iterative coalition formation to approximate the optimal solution, and evaluate its performance.

AAMAS Conference 2007 Conference Paper

Coalition Formation under Uncertainty: Bargaining Equilibria and the Bayesian Core Stability Concept

• Georgios Chalkiadakis
• Evangelos Markakisy
• Craig Boutilier

Coalition formation is a problem of great interest in AI, allowing groups of autonomous, rational agents to form stable teams. Fur- thermore, the study of coalitional stability concepts and their re- lation to equilibria that guide the strategic interactions of agents during bargaining has lately attracted much attention. However, research to date in both AI and economics has largely ignored the potential presence of uncertainty when studying either coalitional stability or coalitional bargaining. This paper is the first to relate a (cooperative) stability concept under uncertainty, the Bayesian core (BC), with (non-cooperative) equilibrium concepts of coali- tional bargaining games. We prove that if the BC of a coalitional game (and of each subgame) is non-empty, then there exists an equilibrium of the corresponding bargaining game that produces a BC element; and conversely, if there exists a coalitional bargain- ing equilibrium (with certain properties), then it induces a BC configuration. We thus provide a non-cooperative justification of the BC stability concept. As a corollary, we establish a sufficient condition for the existence of the BC. Finally, for small games, we provide an algorithm to decide whether the BC is non-empty.

AAMAS Conference 2004 Conference Paper

Bayesian Reinforcement Learning for Coalition Formation Under Uncertainty

• Georgios Chalkiadakis
• Craig Boutilier

AAMAS Conference 2003 Conference Paper

Coordination in Multiagent Reinforcement Learning: A Bayesian Approach

• Georgios Chalkiadakis
• Craig Boutilier