{"id":2748,"date":"2026-06-01T07:01:39","date_gmt":"2026-06-01T11:01:39","guid":{"rendered":"https:\/\/mathvoices.ams.org\/featurecolumn\/?p=2748"},"modified":"2026-05-29T13:21:37","modified_gmt":"2026-05-29T17:21:37","slug":"the-shapley-value-or-how-to-split-a-bill-in-n-easy-steps","status":"publish","type":"post","link":"https:\/\/mathvoices.ams.org\/featurecolumn\/2026\/06\/01\/the-shapley-value-or-how-to-split-a-bill-in-n-easy-steps\/","title":{"rendered":"The Shapley Value, or How to Split a Bill in n! Easy Steps"},"content":{"rendered":"

My first encounter with the Shapley value came in the unlikely context of video game design…<\/em><\/span><\/p>\n

The Shapley Value, or How to Split a Bill in $n!$ Easy Steps<\/h1>\n

Anil Venkatesh
\nAdelphi University<\/b><\/p>\n

Introduction<\/h1>\n

More often than not, a happy hour with my non-mathematician friends
\nends with the assumption that I\u2019ll work out how to split the tab. These
\nfriends assume that the total bill neatly breaks down as a sum of each
\nperson\u2019s expenditure, but this ignores the \u201cenabler effect\u201d: whenever a
\ncertain friend of ours is present, everyone seems to order a bit more
\nliberally for themselves. To the mathematically minded (and probably no
\none else), the enabler ought to own a share of the expense that their
\npresence tends to elicit. In 1951, the game theorist Lloyd Shapley made
\nthis sentiment precise in the following way (absent evidence to the
\ncontrary, we can only assume that he too was inspired by splitting one
\ntoo many happy hour bills.)<\/p>\n

\"A
The author and his friends celebrate a successful happy hour.<\/figcaption><\/figure>\n

Suppose you and your friend run up a $\\$55$ bill. You reckon you would
\nonly have spent $\\$20$ and $\\$25$ respectively, if dining alone. Shapley
\nproposed to consider each party\u2019s impact on the bill under every
\nattendance hypothetical: in your case, that means $+\\$20$ when dining alone and $+\\$30$ when dining with your friend. Likewise,
\nyour friend adds $\\$25$ when dining alone
\nand $\\$35$ when dining with you.<\/p>\n

\n\n\n\n\n\n
$\\begin{matrix}+\\$25\\\\ \\uparrow \\end{matrix}$<\/td>\n$\\begin{matrix}+\\$35\\\\ \\uparrow \\end{matrix}$<\/td>\n<\/td>\n<\/tr>\n
$\\$25$<\/td>\n$\\$55$<\/td>\n$\\rightarrow +\\$30$<\/td>\n<\/tr>\n
$\\$0$<\/td>\n$\\$20$<\/td>\n$\\rightarrow +\\$20$<\/td>\n<\/tr>\n<\/tbody>\n<\/table>
Table of restaurant bills under all attendance
\nhypotheticals.<\/figcaption><\/figure>\n

Each person\u2019s Shapley value<\/em> is the average of their
\ncontributions across the hypothetical cases, splitting the $\\$55$ bill into
\n$\\$25$ for you and $\\$30$ for your friend. Intuitively, you each pay what you
\nwould have spent alone, plus half of the extra $\\$10$ that was caused by
\nyour mutual enabling behavior. In theory, a party of $n$ friends simply needs to consider
\nall $n!$ orderings of themselves
\nand take each person\u2019s average marginal contribution to the bill. In
\npractice, your friends may not appreciate the time complexity of this
\nalgorithm!<\/p>\n

As we\u2019ll discuss in the next section, the properties of the Shapley
\nvalue allow us to reduce the number of computations from $n!$ to around $n \\cdot 2^{n}$, not that
\nthis will mollify your impatient friends. Facetious applications aside,
\nthe Shapley value has proven so useful that a tremendous amount of
\nresearch has been done to find ways to estimate it efficiently. Before
\nwe discuss its applications in the present day, though, let\u2019s stop and
\nask: how do we know that the Shapley value is right<\/em>?<\/p>\n

\n\"Economist
Lloyd Shapley. Photo by Bengt Nyman<\/a> – Flickr<\/a>: IMG_4826<\/a>, CC BY 2.0<\/a>.<\/figcaption><\/figure>\n

Evocative axioms<\/h1>\n

While the Shapley value\u2019s computational procedure is intuitive and
\nuseful, Shapley\u2019s great contribution was a proof that this is the
\nonly<\/em> fair way to divide a cost among a group of cooperative
\nactors. To get there, we need some axioms to agree on what a fair
\ndivision looks like.<\/p>\n

    \n
  1. \n

    Null player: an actor who always contributes 0 marginal cost must
    \nhave a Shapley value of 0.<\/p>\n<\/li>\n

  2. \n

    Symmetry: two actors whose marginal costs agree in all
    \nhypotheticals must have the same Shapley value.<\/p>\n<\/li>\n

  3. \n

    Efficiency: the sum of all actors\u2019 Shapley values must equal the
    \ntotal bill.<\/p>\n<\/li>\n

  4. \n

    Linearity: in the case of multiple bills, the same Shapley values
    \nresult whether treating the bills together or separately (and adding up
    \nafterwards).<\/p>\n<\/li>\n<\/ol>\n

    The latter two axioms combine to imply that we can group actors into
    \narbitrary coalitions, compute the Shapley value for each coalition, then
    \nfurther divide those values among the coalition members via an
    \nadditional Shapley calculation. This fact is leveraged in the     Random
    \nForest machine learning model<\/a>, a type of classification algorithm that
    \nconsists of many submodels that each use only a subset of the features
    \n(i.e. columns) of the data set. Once a Random Forest model is trained,
    \nwe can estimate the relative importance of each feature by examining the
    \naccuracy of the submodels that did or didn\u2019t include this feature.
    \nBecause of the linearity and efficiency axioms, we don\u2019t need to
    \nconsider every hypothetical subset of features to make this
    \ncalculation.<\/p>\n

    The axioms that give rise to the Shapley value are strikingly similar
    \nto those of entropy. The (Shannon) entropy $H(X)$ of a discrete random
    \nvariable $X$ is the average
    \n\u201csurprisingness\u201d of $X$. Just as
    \nwith the criterion of \u201cfair\u201d division of cost, this concept requires     an
    \naxiomatic basis<\/a> such as the one given below.<\/p>\n

      \n
    1. \n

      Expansibility: Adding an outcome with probability zero does not
      \nchange the entropy.<\/p>\n<\/li>\n

    2. \n

      Symmetry: Permuting the outcomes does not change the
      \nentropy.<\/p>\n<\/li>\n

    3. \n

      Subadditivity: $H(X,Y) \\leq H(X) + H(Y)$
      \nfor all $X$ and $Y$.<\/p>\n<\/li>\n

    4. \n

      Additivity: $H(X,Y) = H(X) + H(Y)$
      \nif $X$ and $Y$ are independent.<\/p>\n<\/li>\n

    5. \n

      Zero Limit: As a variable\u2019s distribution approaches
      \ndeterministic, its entropy approaches zero.<\/p>\n<\/li>\n<\/ol>\n

      The first two axioms of entropy are analogous to those of
      \nfair division, but there is clearly some departure in the matter of
      \nadditivity. This is partly due to a category error since the Shapley
      \nvalue is computed for each actor but a single entropy value is computed
      \nfor the entire system. By reformulating a bit, we can find a much
      \ntighter relationship between these concepts.<\/p>\n

      Suppose $X_1, X_2,\\ldots, X_n$
      \nare random variables with values in $\\{0,1\\}$. The entropy of this collection of
      \nrandom variables is computed as an expected value over their joint
      \ndistribution, visualized as the $2^n$ vertices of the $n$-dimensional cube. This is because
      \nwe have to consider every possible combination of 0\u2019s and 1\u2019s for each
      \nvariable. The Shapley value for $n$ actors is also computed on the
      \n$n$-cube since we have to
      \nconsider each hypothetical coalition of actors, but in this case we
      \ncompare the two opposite facets of the cube: those vertices that include
      \na certain actor and those that don\u2019t. This partitioning of the cube into
      \nhalves is exactly what happens in the computation of
      \nconditional<\/em> entropy $H(X_i | X_j\\mathrm{,~}j \\neq i)$,
      \nthe average amount of information (or \u201csurprisingness\u201d) gained by $X_i$ given prior
      \nknowledge of the other random variables.<\/p>\n

      In fact, the properties of conditional entropy have even more in
      \ncommon with those of fair division. Conditional entropy has an
      \nadditivity property called the chain rule, which states that $$\\begin{aligned}
      \nH(X_1,\\ldots, X_n) &= H(X_1) + H(X_2|X_1) + H(X_3|X_1, X_2) + \\cdots
      \n+ H(X_n|X_1,\\ldots, X_{n-1}) \\\\
      \n&= \\sum_{i=1}^n H(X_i | X_1,\\ldots,X_{i-1}).
      \n\\end{aligned}$$<\/p>\n

      This property holds without any independence assumption on the random
      \nvariables. To complete the comparison, let\u2019s introduce the novel
      \nnotation $\\Sigma(X_1, X_2 | X_3, X_4)$
      \nto represent the Shapley value of the coalition $\\{X_1, X_2\\}$
      \nin the presence of the other actors $X_3$ and $X_4$. (This nonstandard
      \nnotation draws inspiration from the origin of the entropy symbol as the
      \nGreek capital letter eta<\/em>.) The corresponding additive law of
      \n$\\Sigma$ is<\/p>\n

      $$\\begin{aligned}
      \n\\Sigma(X_1,\\ldots, X_n) = \\sum_{i=1}^n \\Sigma(X_i | X_j,\\mathrm{~}j\\neq
      \ni).
      \n\\end{aligned}$$<\/p>\n

      We can now see that the additive law of conditional entropy uses a
      \ntriangular sum where the corresponding law of $\\Sigma$ has an unconditional sum, a
      \nconsequence of quantifying the accumulation of information rather than
      \ndividing a fixed whole. For an even tighter connection between the
      \nconcepts, see the definition of uniqueness Shapley value<\/em> in       “What makes you unique?”<\/a> which is shown to
      \ncorrespond exactly to a linear combination of conditional entropies.<\/p>\n

      The
      \npower of averaging over symmetries<\/h1>\n

      So far we\u2019ve talked about a pair of famous quantities that are both
      \nthe result of averaging over a (possibly huge) space. Depending on your
      \nperspective, it\u2019s either marvelous or frustrating that a quantity with
      \nsome desirable and unique property would be the result of an intractable
      \ncomputation.<\/p>\n

      Both entropy and the Shapley value make use of the symmetrizing
      \neffect of averaging over every possible combination or coalition, giving
      \nan unbiased measurement in some sense. To me, this is reminiscent of
      \nanother apparently deep principle, that we should expect objects to
      \noccur inversely proportionally to the size of their symmetry group. In a
      \nsimple example, consider the case of rolling a pair of identical
      \nsix-sided dice. If you ask a person with absolutely no mathematical
      \ntraining to work out the number of possible outcomes, they may very well
      \ncome to 21 instead of 36. After all, the practice of imposing an order
      \non a pair of indistinguishable dice only makes sense if you already plan
      \nto use the machinery of independence. Even so, it\u2019s possible to recover
      \nthe correct distribution by weighting the six matching pairs by $\\frac{1}{2}$.
      \nHere, the principle in action is that the unordered pair $\\{1,1\\}$ has a
      \nsymmetry group $S_2$
      \nof two elements, the identity and the swap, while the unordered pair
      \n$\\{1,2\\}$ has only the identity symmetry. This principle crops up all over
      \ntopology and number theory, as detailed by       this lovely MathOverflow post<\/a>.<\/p>\n

      Closing thoughts<\/h1>\n

      My first encounter with the Shapley value came in the unlikely
      \ncontext of video game design. The enduring influence of Dungeons and
      \nDragons<\/em> in gaming has given us a common combat paradigm of dealing
      \na certain amount of damage $D$
      \nat a rate $R$, debited from an
      \nopponent\u2019s health pool, for a total damage-per-second of $DR$. Often, it\u2019s possible
      \nfor the player to enhance their weapon damage and rate of attack with
      \nmultiplicative bonuses. Some years ago, a game design collaborator asked
      \nme how I\u2019d go about computing the relative value of a damage bonus to an
      \nattack rate bonus. Representing these bonuses by $X$ and $Y$ respectively, we get the following
      \nmarginal value table.<\/p>\n

      \n\n\n\n\n\n
      $\\begin{matrix} +Y \\\\ \\uparrow \\end{matrix}$<\/td>\n$\\begin{matrix} +Y + XY \\\\ \\uparrow \\end{matrix}$<\/td>\n<\/td>\n<\/tr>\n
      $1 + Y$<\/td>\n$1 + X + Y + XY$<\/td>\n$\\rightarrow +X + XY$<\/td>\n<\/tr>\n
      $1$<\/td>\n$1 + X$<\/td>\n$\\rightarrow +X$<\/td>\n<\/tr>\n<\/tbody>\n<\/table>
      Table of damage per second values under all bonus
      \nhypotheticals.<\/figcaption><\/figure>\n

      Accordingly, we find that the relative contribution of the damage
      \nbonus $X$ to the attack rate
      \nbonus $Y$ is $(X + XY\/2)$ : $(Y + XY\/2)$.<\/p>\n

      \"A
      A screenshot from the author’s game.<\/figcaption><\/figure>\n

      Expository content on the Shapley value often highlights its
      \napplication to business. For example, the Wikipedia entry for Shapley value<\/a> describes a
      \nscenario with a business owner and a group of $n$ workers, ultimately deducing that
      \nthe owner is entitled to half of the profits and each worker is entitled
      \nto a share of $\\frac{1}{2n}$. While
      \nit\u2019s certainly true that no profit could occur without both the owner\u2019s
      \ncapital and the workers\u2019 labor, the symmetrizing effect of the Shapley
      \ncomputation assumes that each actor\u2019s presence in the coalition is
      \nequally irreplaceable, while this assumption generally does not hold in
      \nthe marketplace. So, caution is advised when applying the Shapley value
      \nto any group of actors whose terms of participation are not
      \nidentical.<\/p>\n

      I\u2019ll end by extending my sympathy to all the readers whose
      \nnon-mathematical friends expect them to figure out the bill. Little
      \nconsolation though it may be, I think we can all agree that this is
      \nstill preferable to splitting a bill with a group of other
      \nmathematicians, a task that is famously intractable.<\/p>\n","protected":false},"excerpt":{"rendered":"

      My first encounter with the Shapley value came in the unlikely context of video game design… The Shapley Value, or How to Split a Bill in $n!$ Easy Steps Anil Venkatesh Adelphi University Introduction More often than not, a happy hour with my non-mathematician friends ends with the assumption thatRead More →<\/a><\/span><\/p>\n","protected":false},"author":2,"featured_media":1599,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_post_was_ever_published":false},"categories":[213,109,137,25],"tags":[155,234,87,233,210],"class_list":["entry","author-uwhitcher","post-2748","post","type-post","status-publish","format-standard","has-post-thumbnail","category-213","category-anil-venkatesh","category-math-and-social-sciences","category-probability-and-statistics","tag-economics","tag-entropy","tag-information-theory","tag-shapley-value","tag-video-games"],"jetpack_featured_media_url":"https:\/\/i0.wp.com\/mathvoices.ams.org\/featurecolumn\/wp-content\/uploads\/sites\/2\/2023\/03\/mathvoices-banner-feat-col.png?fit=2760%2C580&ssl=1","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/posts\/2748","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/comments?post=2748"}],"version-history":[{"count":17,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/posts\/2748\/revisions"}],"predecessor-version":[{"id":2766,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/posts\/2748\/revisions\/2766"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/media\/1599"}],"wp:attachment":[{"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/media?parent=2748"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/categories?post=2748"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/tags?post=2748"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}