What cooperative game theory says about the Israeli parliament
TL;DR: Hedonic games are a way of modeling team formation, where participants have a preference for whom they are grouped with. We present the first demonstration of the effectiveness of hedonic games for modeling real world data. We distinguish governmental and opposition blocs in the Israeli parliament based only on their voting patterns, and pick out politicians known to deviate from party lines. These results are comparable to machine learning approaches, but avoids shoehorning individuals into teams when they lack data to make that judgement. Try our demo.
Teams form when people recognize the need to cooperate to get things done. Naturally, people have preferences on how teams should be divided. Some people will have complementary skills. Some people are friends. Others just work well (or poorly) together. Cooperative game theory is the study of how a group of individuals can be divided into teams. A particularly interest class of these games are hedonic games where individuals only care about who their team members will be, and not about how other teams are formed.
These assumptions make hedonic games a compelling model that captures real world human behaviors. However, until now, it has not been applied to study real world phenomena. To do this, we need to find a suitable dataset — one that contains a consistent set of players who repeatedly form teams. More than that, they must also belong to a canonical set of teams that act as a ground truth for comparison with our model’s output.
The Israeli parliament — the Knesset — presents an ideal dataset. It is a body of 120 members (MKs) that meet regularly to vote on bills. We focus on the 20th Knesset (the most recent Knesset at the time of writing), which had 147 politicians (due to turnover) who voted upon 7515 bills. The voting patterns of the politicians were made available by the Knesset data team (curated data forthcoming to PrefLib).
We hypothesize that MKs of the same party would vote in a similar way. That is, they would prefer to be placed in the same team. But members from opposing parties will differ. Our hedonic games model reflects this: MKs would prefer being in a team with “friends”, where friends are those whose votes support you more often than they oppose you.
This formulation of the hedonic game model gives rise to the following Sankey diagram. The blocks on the left represent the party affiliations of the MKs — these represent the ground truth. These are color coded either as part of the governmental coalition in warm tones, or the opposition in cool tones. The blocks on the right represent the teams produced by our model. Each MK is represented as a line connecting their party on the left to a team on the right.
We see our model easily distinguishes the governmental and opposition blocs. However, we do not see any separation by individual parties. We hypothesize that this is due to a high degree of consistency in votes within both the governmental coalition and the opposition. Instead, we find that attendance drives this separation— a useful feature that highlights individuals with insufficient data to draw a useful conclusion.
Interestingly, we observe three MKs who appear to be grouped into the “wrong” side — Avigdor Lieberman, Daniel Atar, and Orly Levy. However, upon further investigation, we find that these individuals have a colorful political history, and often vote in ways that deviate from party lines.
We compare our model with two machine learning algorithms. A classic algorithm for this type of task is k-means clustering, which groups items based on attribute similarity (in this case, similarity in voting patterns).
We see that while it recognizes two of our colorful politicians, k-means also produces an implausible team that comprises of MKs from both the government and the opposition blocs.
We also consider an algorithm for community detection. If we view a history of voting together on a bill as a social tie, then party affiliations may form tightly-knit communities. Stochastic block model (SBC) is an algorithm to identify these communities, and has also been used to examine parliamentary voting data.
Once again, we see that the MKs are largely separated into governmental and opposition blocs. However, we see more “rogue” MKs. Moreover, while SBC produces several distinct teams, a closer examination of the team members show that these grouping are not politically meaningful.
In summary, we present the first application of cooperative games on real world data. We show that it offers comparable performance over machine learning approaches, but is more conservative in its conclusions — it highlights when individuals do not have sufficient data to draw appropriate conclusions. We examined many more model than we have space to present here. So instead, we invite you to check out our interactive demo.
Paper: Omer Lev, Wei Lu, Alan Tsang and Yair Zick. Learning Cooperative Solution Concepts From Voting Behavior: A Case Study on the Israeli Knesset
