Hedonic Game Related Research

Title:Welfare maximization in fractional hedonic games

authors:Haris Aziz, Serge Gaspers Joachim, Gudmundsson, Juli´an Mestre

• hedonic game: comprises a set of agents who express preferences over coalitions they are they are present in and outcomes are partitions of the agents into disjoint coalitions. It provides a natural framework to study coalition formation.
• fractional hedonic games: each vertex of the network can be considered as an agent. An agent $i's$ valuation $v_i(j)$ of an agent $j$ can be represented by the weight of the directed edge $(i,j)$. Agent $i's$ valuation of a coalition $S$ of agents is the mean valuation $\sum_{j\in S} v_i(j)/\mid S \mid$ of the members of $S$.

A hedonic game $(N,\succeq)$ is said to be a fractional hedonic game(FHG) if for each player $i$ in $N$ there is a value function $v_i$ such that for all coalitions $S,T\in N$,$S\succeq_i T$ if and only if $v_i(S)\ge v_i(T)$.

Main contributions:

1. simple examples that show that utilitarian, egalitarian, and Nash welfare maximizing outcomes need not coincide, even in simple symmetric FHGs.
2. a reduction that shows that maximizing utilitarian welfare, egalitarian welfare, or Nash welfare is NP-hard, even for simple symmetric FHGs.
3. a ploynomial-time 2-approximation algorithm for maximizing the utilitarian welfare of simple symmetric FHGs.
4. a polynomialtime 4-approximation algorithm for maximizing the utilitarian welfare of symmetric FHGs.
5. a polynomial-time 3-approximation algorithm for maximizing the egalitarian welfare of simple symmetric FHGs

Related work

• hedonic games based on graphs examined from a social welfare perspective.
• a related class of hedonic game: additive seperabel hedonic games, consider welfare maximizing or stable partitions of FHGs and why stable or efficient outcomes of FHGs provide better clusterings.
• Olsen[2012] examined a variant of FHGs and considered computation of Nash stable outcomes.
• the prior work on FHGs, most of the focus has been on stabel partitions, this has a disadvantage that a stable outcome may not be guaranteed to exist[Aziz et al., 2014; Bilo` et al., 2014; Brandl et al., 2015] or may suggest the partition consisting of the grand coalition [Bilo` et al., 2014].

Theorem

Definitions

• symmetric: an FHG is said to be symmetric if vi

今天的文章Hedonic Game Related Research分享到此就结束了，感谢您的阅读。