A running list, with descriptions, of ideas I had for research that ultimately fell flat (and why).
Most of the ideas I have don’t turn out to be worth pursuing, but that doesn’t mean good work wasn’t done! I’m going to be putting as many of these failed ideas as I can in this post, with the hope that it is a useful resource to others. If you’re reading something and think I made a mistake or believe there is a way to overcome the roadblock that stopped me, I would be delighted to hear about it in the comments.
Over the summer I chatted with Professor Luca de Alfaro a few times about research, and one of the topics was related to Shapley values. Additionally, I’m working as a data scientist with the Center for Motivation and Change: Foundation for Change, a nonprofit related to therapy and substance abuse. The nonprofit offers trainings in their evidence-based techniques, and the trainings go for a handful of weeks. Surveys are administered before beginning the training, as well as at the end.
A question we could be interested in answering is how each week contributes to the overall learning of clients. One might opt for hierarchical linear modeling approaches or panel designs, but I thought that Shapley values might be a possible approach. By treating each week of the training as a player in a cooperative game, you can estimate the contribution of each week to overall learning by considering coalitions. This sort of setup, with a series of sessions in which learning or growth is the goal, occurs frequently. Corporate trainings, school, or skills-based therapies such as cognitive behavioral therapy are common examples. Coalitions naturally arise due to people missing sessions. While it would require some investigation, I don’t think it’s entirely implausible that absences would be completely at random (MCAR)
In practice, Shapley values are difficult to estimate because they require considering all $2^n$ coalitions for a game that has $n$ players. For a game with value function $v$ and set of players $N$, the Shapley value for player $i$ is defined as
\[\varphi_i(v) = \sum_{S\subseteq N \setminus \{i\}} \frac{\vert S \vert ! (n - \vert S \vert - 1)!}{n!}[v(S \cup \{i\}) - v(S)] = \frac{1}{n}\sum_{S\subseteq N \setminus \{i\}} \binom{n-1}{\vert S \vert}^{-1}[v(S \cup \{i\}) - v(S)].\]In our case, the exponential number of coalitions is particularly distressing due to the small sample size of the surveys. This would lead to Shapley value estimates with considerable variance. Additionally, Shapley values don’t naturally consider ordering when distinguishing between coalitions. Now, there has been work on modifications to Shapley values that consider orderings or players
In the setting of trainings however, each coalition can only occur in one order, since the trainings are offered in successive weeks. Furthermore, a participant is typically not allowed to miss as many sessions as they would like. An organizer may inform pariticipants that the outset that they are not allowed to miss more than $k$ sessions or they are removed. This is a very natural thing to do, as those who do not attend enough sessions are likely to miss out on synergistic elements across weeks and not properly represent learning. Again, I assumed missingness completely at random.
With these observations, I decided to restrict the coalitions used to compute Shapley values to only those for which less than $k$ sessions missed. Now, the number of coalitions to consider polynomial in $k$ and $n$! In the Shapley value formula there is a scaling constant to satisfy the axioms, and I was unsure what it would be for mine, so I denoted it as $c$. Then, we will compute our modified Shapley values as
\[\psi_i(v) = \sum_{S \subseteq N \setminus \{i\},\vert S \vert \geq n-k} c[v(S \cup \{i\}) - v(S)].\]Now on to attempting to prove the axioms for the Shapley values. The first axiom is efficiency, that
\[\sum_i \psi_i(v) = v(N).\]This is where things break down. For Shapley values, the easiest way to see efficiency is observe that the sum of Shapley values ends up being a telescoping sum, leaving $v(N) - v(\emptyset)$, which just ends up as $v(N)$. Unfortunately, by restricting the coalitions to only those above a certain size, the sum no longer telescopes, meaning there is no efficiency.
At this point, I decided that the idea was no longer worth pursuing. To me, efficiency is a fundamental property of the Shapley value and what makes it so desirable.