Powered by OpenAIRE graph
Found an issue? Give us feedback
https://doi.org/10.6...arrow_drop_down
https://doi.org/10.65109/ppcd9...
Article . 2023 . Peer-reviewed
Data sources: Crossref
DBLP
Preprint . 2023
Data sources: DBLP
DBLP
Conference object
Data sources: DBLP
versions View all 4 versions
addClaim

Social Aware Coalition Formation with Bounded Coalition Size

Authors: Chaya Levinger; Amos Azaria; Noam Hazon;

Social Aware Coalition Formation with Bounded Coalition Size

Abstract

In many situations when people are assigned to coalitions the assignment must be social aware, i.e, the utility of each person is the number of friends in her coalition. Additionally, in many situations the size of each coalition should be bounded. This paper initiates the study of such coalition formation scenarios. We show that finding a partition that maximizes the utilitarian social welfare is computationally hard, and provide a polynomial-time approximation algorithm. We also investigate the existence and the complexity of finding stable partitions. Namely, we show that there always exists a Nash Stable (NS) partition and the Contractual Strict Core (CSC) is never empty, but the Strict Core (SC) of some games is empty. Finding partitions that are NS or in the CSC is computationally easy, but finding partitions that are in the SC is hard. The analysis of the core is more involved. When the coalition size is bounded by 3 the core is never empty, and we present a polynomial time algorithm for finding a member of the core. In all other cases, we provide additive and multiplicative approximations of the core. In addition, we show in simulation over 100 million games that a simple heuristic always finds a partition that is in the core.

Related Organizations
  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!