Welcome to the hedonic game simulator! I presented this at the 2017 Algorithmic Decision Theory Doctoral Consortium. I uploaded my extended abstract to arXiv. This software works okay on smartphones but better on laptops.

Enter adjacency list:

Enter partition to color graph:

Below you can compute every player's score of every other coalition in the partition. (A player i's score of a coalition C is actually i's score of C \cup {i}.)

You have a set of people which for some reason needs to split into groups. The people are called *players* and the groups are called *coalitions*. Maybe the set of people is your kindergarten class and they need to split up so each group can build a lego tower. A player might really want to be in some coalitions, but not in others. These are the player's *preferences*. Once the whole set of players is split into coalitions, it's called a *partition* or a *coalition formation*. **Hedonic games are the study of how people cooperate and form groups together and when partitions are stable and when partitions fall apart.**

More at Wikipedia or in [Woe2013].

Hedonic games were independently introduced in [BKS2001] and [BJ2002].

is the set of players, is the number of players, and is a partition of . Usually, is a coalition and is a player in . And is a player from anywhere in .

If some player would rather be in coalition than coalition , then we say . In principle, 's preferences are defined by listing all the subsets of which contain in order of decreasing desirability. But that would take tons of computer memory or paper and ink, so we mainly focus on hedonic games which are *compactly representable*. This means that there is some concise way of describing each player's preferences over the possible coalitions. Sometimes that means you have a *score function* which takes a player and a coalition as input and outputs a real number; the larger the number the more that player likes that coalition. Once you know the score functions, you can concisely say that if and only if .

Most of the notation here is from [NRRRS2016]. Other stuff I added to make it more programmer-friendly.

A player is **friend-oriented** if she tries to maximize friends and, in the case of a tie, minimize enemies. This preference relation is defined by the score function

Introduced in [DBHS2006].

A player is **enemy-oriented** if she tries to minimize enemies and, in the case of a tie, maximize friends. This preference relation is defined by the score function

Introduced in [DBHS2006].

A player is **selfish-first** if she uses her own preferences first and only uses her friends' preferences to break ties. This preference relation is defined by the score function

Introduced in [NRRRS2016].

A player is **equal-treatment** if she puts equal weight on her own opinion and each friend's opinion. This preference relation is defined by the score function

Introduced in [NRRRS2016].

A player is **altruistic-treatment** if she uses her friends' preferences first and only uses her own preferences to break ties. This preference relation is defined by the score function

Introduced in [NRRRS2016].

In **fractional hedonic games**, a player's score of a coalition is the average of her scores of the players in it. Scores could be anything, but this simulator only allows scores that are simple and symmetric.

Introduced in [ABH2014].

In **additively seperable hedonic games**, a player's score of a coalition is the sum of her scores of the players in it. In unweighted, undirected graphs, this is simply the degree of the player in the coalition.

I don't know when/where additively seperable hedonic games were introduced. If you know, then please email me!

A partition is **individually rational** if every player is happier in her home coalition than she would be alone. In other words, is individually rational iff

A partition is **Nash-stable** if every player is happier in her home coalition than she would be in any other coalition. In other words, is Nash-stable iff

A partition is **individually stable** if every player who wants to transfer to a new coalition is unwanted by someone in that coalition. In other words, is individually stable iff

A partition is **contractually individually** stable if every player who wants to transfer to a new coalition is either unwanted by someone in that coalition or is not permitted to leave by someone in her home coalition. In other words, is contractually individually stable iff

A partition is **popular** if the majority of players weakly prefer it to any other partition. In other words, is strictly popular iff

A partition is **strictly popular** if the majority of players strictly prefer it to any other partition. In other words, is strictly popular iff

A partition is **core-stable** if there is no possible strictly blocking coalition. (A coalition strictly blocks if everyone prefers it to their current homes.) In other words, is core-stable iff

A partition is **strictly core-stable** if there is no possible weakly blocking coalition. (A coalition weakly blocks if everyone is at least as happy in the new one and someone is even happier.) In other words, is strictly core-stable iff

A partition is **perfect** if every player is in one of their favorite possible coalitions. In other words, is perfect iff

In chronological order:

[BKS2001]: Suryapratim Banerjee, Hideo Konishi, and Tayfun Sönmez. "Core in a simple coalition formation game." Social Choice and Welfare. 2001.

[BJ2002]: Anna Bogomolnaia and Matthew O Jackson. "The Stability of Hedonic Coalition Structures." Games and Economic Behavior. 2002.

[DBHS2006]: Dinko Dimitrov, Peter Borm, Ruud Hendrickx, and Shao Chin Sung. "Simple priorities and core stability in hedonic games." Social Choice and Welfare. 2006. PDF.

[Woe2013]: Gerhard J Woeginger. "Core Stability in Hedonic Coalition Formation." SOFtware SEMinar (SOFSEM). 2013. arXiv.

[ABH2014]: Haris Aziz, Feliz Brandt, and Paul Harrenstein. "Fractional Hedonic Games." The International Conference on Autonomous Agents and Multi-Agent Systems. 2014. arXiv.

[NRRRS2016]: Nhan-Tam Nguyen, Anja Rey, Lisa Rey, Jörg Rothe, and Lena Schend. "Altruistic Hedonic Games." The International Conference on Autonomous Agents and Multi-Agent Systems. 2016. PDF.

Public domain dedication. No rights reserved. Look at the source!

Hosted on Github. Using graph visualization library vis.js.

To request a feature or report a bug, you can use github or you can email luke.lambda@uky.edu . There is a standing bounty of $2.56, to be mailed to the first person to find a bug.