Computing Stable Coalitions: Approximation Algorithms for Reward Sharing
Consider a setting where selfish agents are to be assigned to coalitions or projects from a fixed set P. Each project k is characterized by a valuation function; v_k(S) is the value generated by a set S of agents working on project k. We study the following classic problem in this setting: "how should the agents divide the value that they collectively create?". One traditional approach in cooperative game theory is to study core stability with the implicit assumption that there are infinite copies of one project, and agents can partition themselves into any number of coalitions. In contrast, we consider a model with a finite number of non-identical projects; this makes computing both high-welfare solutions and core payments highly non-trivial. The main contribution of this paper is a black-box mechanism that reduces the problem of computing a near-optimal core stable solution to the purely algorithmic problem of welfare maximization; we apply this to compute an approximately core stable solution that extracts one-fourth of the optimal social welfare for the class of subadditive valuations. We also show much stronger results for several popular sub-classes: anonymous, fractionally subadditive, and submodular valuations, as well as provide new approximation algorithms for welfare maximization with anonymous functions. Finally, we establish a connection between our setting and the well-studied simultaneous auctions with item bidding; we adapt our results to compute approximate pure Nash equilibria for these auctions.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Offline Learning of Nash Stable Coalition Structures with Possibly Overlapping Coalitions
Coalition formation concerns strategic collaborations of selfish agents that form coalitions based on their preferences. It is often assumed that coalitions are disjoint and preferences are fully known, which may not hol…
Stable partitions for proportional generalized claims problems
We consider a set of agents who have claims on an endowment that is not large enough to cover all claims. Agents can form coalitions but a minimal coalition size $\theta$ is required to have positive coalitional funding …
A Task-Driven Multi-UAV Coalition Formation Mechanism
With the rapid advancement of UAV technology, the problem of UAV coalition formation has become a hotspot. Therefore, designing task-driven multi-UAV coalition formation mechanism has become a challenging problem. Howeve…
QGShap: Quantum Acceleration for Faithful GNN Explanations
Graph Neural Networks (GNNs) have become indispensable in critical domains such as drug discovery, social network analysis, and recommendation systems, yet their black-box nature hinders deployment in scenarios requiring…
Recommendation SystemsDrug Discovery$\varepsilon$-fractional Core Stability in Hedonic Games
Hedonic Games (HGs) are a classical framework modeling coalition formation of strategic agents guided by their individual preferences. According to these preferences, it is desirable that a coalition structure (i.e. a pa…
BlockingPAC learning