  We introduce a combinatorial variant of the cost sharing problem: several
services can be provided to each player and each player values every
combination of services differently. A publicly known cost function specifies
the cost of providing every possible combination of services. A combinatorial
cost sharing mechanism is a protocol that decides which services each player
gets and at what price. We look for dominant strategy mechanisms that are
(economically) efficient and cover the cost, ideally without overcharging
(i.e., budget balanced). Note that unlike the standard cost sharing setting,
combinatorial cost sharing is a multi-parameter domain. This makes designing
dominant strategy mechanisms with good guarantees a challenging task.
  We present the Potential Mechanism -- a combination of the VCG mechanism and
a well-known tool from the theory of cooperative games: Hart and Mas-Colell's
potential function. The potential mechanism is a dominant strategy mechanism
that always covers the incurred cost. When the cost function is subadditive the
same mechanism is also approximately efficient. Our main technical contribution
shows that when the cost function is submodular the potential mechanism is
approximately budget balanced in three settings: supermodular valuations,
symmetric cost function and general symmetric valuations, and two players with
general valuations.
