Constrained Coalition Formation on Valuation Structures: Formal Framework, Applications, and Islands of Tractability (Extended Abstract)
Abstract
Coalition structure generation is considered in a setting where feasible coalition structures must satisfy constraints of two different kinds modeled in terms of a valuation structure, which consists of a set of pivotal agents that are pairwise incompatible, plus an interaction graph prescribing that a coalition C can form only if the subgraph induced over the nodes/agents in C is connected. It is shown that valuation structures can be used to model a number of relevant problems in real-world applications. Moreover, complexity issues arising with them are studied, by focusing in particular on identifying islands of tractability based on topological properties of the underlying interaction graph. Stability issues on valuation structures are studied too.
Cite
Text
Greco and Guzzo. "Constrained Coalition Formation on Valuation Structures: Formal Framework, Applications, and Islands of Tractability (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2018. doi:10.24963/IJCAI.2018/795Markdown
[Greco and Guzzo. "Constrained Coalition Formation on Valuation Structures: Formal Framework, Applications, and Islands of Tractability (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2018.](https://mlanthology.org/ijcai/2018/greco2018ijcai-constrained/) doi:10.24963/IJCAI.2018/795BibTeX
@inproceedings{greco2018ijcai-constrained,
title = {{Constrained Coalition Formation on Valuation Structures: Formal Framework, Applications, and Islands of Tractability (Extended Abstract)}},
author = {Greco, Gianluigi and Guzzo, Antonella},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2018},
pages = {5612-5616},
doi = {10.24963/IJCAI.2018/795},
url = {https://mlanthology.org/ijcai/2018/greco2018ijcai-constrained/}
}