  We propose the study of computing the Shapley value for a new class of
cooperative games that we call budgeted games, and investigate in particular
knapsack budgeted games, a version modeled after the classical knapsack
problem. In these games, the "value" of a set $S$ of agents is determined only
by a critical subset $T\subseteq S$ of the agents and not the entirety of $S$
due to a budget constraint that limits how large $T$ can be. We show that the
Shapley value can be computed in time faster than by the na\"ive exponential
time algorithm when there are sufficiently many agents, and also provide an
algorithm that approximates the Shapley value within an additive error. For a
related budgeted game associated with a greedy heuristic, we show that the
Shapley value can be computed in pseudo-polynomial time. Furthermore, we
generalize our proof techniques and propose what we term algorithmic
representation framework that captures a broad class of cooperative games with
the property of efficient computation of the Shapley value. The main idea is
that the problem of determining the efficient computation can be reduced to
that of finding an alternative representation of the games and an associated
algorithm for computing the underlying value function with small time and space
complexities in the representation size.
