The Shapley value, introduced by Lloyd Shapley in 1953, is a solution concept which can be thought of as a way to distribute the total surplus of a coalitional game to each one of finitely many players. While the Shapley value of a player is completely characterized by a collection of technical conditions, it can also be defined explicitly as the average change in surplus when that player enters in a given ordering. A priori this distribution can be intractable to compute.

In this talk we will discuss this problem in a geometric setting; namely, our players will be points on the Euclidean plane, and the surplus of a coalition (i.e., set of points) will be determined by some geometric object parametrized by that coalition, e.g. the area of a minimal bounding box. We will then furnish algorithms to solve two such problems in sub-quadratic time. A subroutine of fast polynomial multiplication will be a crucial component of these algorithms.

This talk is based on a paper by Sergio Cabello.