Author name cluster

Jacek Sroka

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

2 author rows

AAAI Conference 2011 Conference Paper

Constrained Coalition Formation

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

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

PDF Details

AAMAS Conference 2010 Conference Paper

A Distributed Algorithm for Anytime Coalition Structure Generation

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

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

PDF

ECAI Conference 2010 Conference Paper

A Network Flow Approach to Coalitional Games

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

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

Details