Combinatorial Cost Sharing

1 Introduction

In their classic paper Littlechild and Owen [Littlechild and Owen, 1973] consider the problem of fairly dividing runways maintenance costs among airlines. In this problem, each aircraft has a certain size and the cost of maintaining the runway depends on the size of the largest aircraft that uses the runway. Littlechild and Owen propose the following cost allocation scheme: first divide the cost of serving only the smallest airplane among all airlines. Then, divide the incremental cost for the second smallest airplane equally among all the airlines but the airline with the smallest aircraft. Continue thus until finally the incremental cost of the largest aircraft is divided among the airlines that use such aircraft.

This paper is an abridged version of the paper "Combinatorial Cost Sharing" that appeared in EC'17 [Dobzinski and Ovadia, 2017].

Littlechild and Owen's work is an arch-typical example of a cost sharing problem, where the cost of a resource has to be divided among the participants. Cost sharing was extensively studied in game theory, and in fact, Littlechild and Owen show that their method coincides with the Shapley value [Shapley, 1953] - the only "fair" way to distribute cost under certain desirable properties.

In the AGT community, we are usually interested in truthful (dominant-strategy) mechanisms: a protocol where players' dominant strategy is to cooperate and reveal their true preferences. The influential paper of Moulin and Shenker [Moulin and Shenker, 2001] shows how to use the Shapley values in order to achieve a dominant-strategy cost-sharing mechanism: serve the largest set of players such that every player in this set is willing to pay his Shapley value. They prove that for every submodular cost function it holds that the Shapley value mechanism is groupstrategyproof - no set of players can misreport in order to pay less. Furthermore, the cost of the service is always covered.

The problem of cost sharing was extensively studied in both economics and algorithmic game theory and many variants were suggested and analyzed (e.g., [Moulin, 1999; Moulin and Shenker, 2001; Roughgarden and Sundararajan, 2009; Bleischwitz et al., 2007; Bleischwitz and Schoppmann, 2008; Deb and Razzolini, 1999; Mehta et al., 2007; Hashimoto and Saitoh, 2015]). Almost all the above variants considered the case of a single good, perhaps with different possible levels of services. One is naturally led to consider the following generalization of [Littlechild and Owen, 1973]: what if there are several runways that can be potentially be constructed, or maybe we consider simultaneously building several distant airports? The preferences of an airline become much more complicated now, for example, a long runway in New York is less attractive if all London runways are much smaller.

In our paper we attempt to fill this lacuna and introduce combinatorial cost sharing, where multiple goods can be provisioned and both costs and preferences depend on the selected combination of goods. While combinatorial cost sharing is a natural generalization of the basic cost sharing scenario, from a technical perspective it is radically different as we leave the relatively safe single parameter world and cross the bridge to the realm of multi parameter mechanism design. Nevertheless, we will see that good mechanisms for combinatorial cost sharing do exist.

2 The Model

The standard cost sharing setting (from now on, "simple cost sharing") involves a set N of players (|N| = n), where the value of player i is vi if player i receives a usage permission and 0 otherwise. A known cost function C : 2N → R+ specifies the cost of serving each subset of the players. The goal is to decide which players to serve and for what prices.

In combinatorial cost sharing we have n players as before, but now there are several public goods that can be constructed. We present two formulations of combinatorial cost sharing. The first is more direct formulation which might help the reader to digest the setting more easily. The second formulation - which is the one that is studied throughout the paper - is equivalent in power but is notationally more involved. We use it since it makes the technical proofs more readable.

AFirst Attempt As in simple cost sharing, there is a set N which consists of n players, but now there is a set M of public goods (for example, a pool, a gym, etc.). Players might have complicated preferences over the goods in M (e.g., a combined membership for the pool and the gym might be more valuable than the sum of the values of each membership alone), thus the private valuation of player i is vi : 2M →R. Note that this assumes that there are no externalities in the sense that value of each player is determined only by the goods he is served (in particular, the value does not depend on the other players who use these services).

Let C ′ : (2N )m → R be a known function that specifies the cost of every possible combination of services. For example, C(S1, . . . , Sn) is the cost of serving the first good in M to the players in S1 while serving the second good in M to the players in S2, and so on. We stress that we do not make any assumptions on S1, . . . , Sn and in particular these sets are typically not disjoint.

The Main Formulation The issue with the first formulation is that we often would like to assume that the cost function belongs to some standard class, e.g., C ′ is submodular or subadditive. However, as defined C ′ is not even a set function (its domain is (2N )m). We thus use a different formulation that is equivalent in power. Define - for notational convenience - for each player i a set Mi with Mi ∩Mi′ = ∅ for i ̸= i′ , where each j ∈ Mi represents a permission to consume a different good. For example, if M is the set of public goods that can be constructed, we define for each player i a set Mi, |Mi| = |M|, and think about the j'th item in Mi as permission for player i to use the j'th public good in M. In particular player i is never interested in items from Mi′ , for i ̸= i′ . The private valuation of player i is vi : 2Mi → R. The cost function C : 2M1 × · · · × 2Mn → R specifies the cost of every possible combination of services. Note that it is straightforward to express every cost function in the first formulation as a cost function in the main formulation. In particular, C is now a set function (the set of items is M1∪· · ·∪Mn - recall that Mi ∩Mj for i ̸= j), so standard notions such as subadditivity and submodularity are defined in the usual sense.

3 Combinatorial Cost-SharingMechanisms

A (direct) mechanism for combinatorial cost sharing problem receives as input the valuations of the players and outputs an allocation of services ---→ ALG where ALGi ⊆ Mi is the set of services provided to player i. Moreover for every player i the mechanism specifies his payment pi. It is standard to assume that the mechanism is individually rational (for every i, pi ≤ vi(ALGi)), pi ≥ 0 (no positive transfers) and moreover pi = 0 if player i is not served.

Work on cost sharing in the AGT community mostly focuses on incentive compatible mechanisms, either dominant strategy or groupstrategyproof, that at the very least always cover the cost. That is, in an instance where the mechanism outputs an allocation ---→ ALG we require to have C(---→ ALG) ≤ Σipi. Ideally, we will also not overcharge the players, at least not by much: a mechanism is β-budget balanced if in every instance C(---→ ALG) ≤ Σipi ≤ β · C(---→ ALG).

We look for mechanisms that are economically efficient. A desirable goal is to maximize the social welfare: SW(-→S ) = ∑i∈N vi(Si) - C(-→S ). Unfortunately, for a very simple cost-sharing problem there is no truthful cost-recovering mechanism that provides approximation to the social welfare [Feigenbaum et al., 2002]. Hence another notion of efficiency is required.

Following [Roughgarden and Sundararajan, 2009], we look for mechanisms that minimize the social cost, π(-→S ) = C(-→S ) + Σi∈N[vi(Mi) - vi(Si)], which is the construction cost plus the "lost value" from not providing all the services. Minimizing the social cost has some appealing properties, for example, the social cost and the social welfare induce the same order on allocations. Moreover, additive approximations to the social welfare imply multiplicative guarantees on the social cost. We refer the interested reader to the paper for a complete discussion.

The simple cost sharing literature is rich in beautiful results, but the jewel in the crown is probably the Shapley value mechanism [Moulin and Shenker, 2001], which is a groupstrategyproof mechanism that exactly shares the cost whenever C is a submodular function [Moulin and Shenker, 2001]. Roughgarden and Sundararajan [Roughgarden and Sundararajan, 2009] show that it gives an approximation ratio of Hn = Σni=1 1n to the social cost. It is known that the approximation ratio of any mechanism that always covers the cost is Ω(logn) and that this is true for every dominantstrategy mechanism. [Dobzinski et al., 2008] 1 .

1 This impossibility of [Dobzinski et al., 2008] is stated for budget balanced mechanisms, but the proof applies even to cost recovering mechanisms.

There were several attempts to generalize cost sharing. Most of previous work considered special cases with multiple symmetric services and decreasing marginal valuations, e.g., Mehta et al. [Mehta et al., 2007] consider non-metric faulttolerant uncapacitated facility location, and Bleischwitz and Schoppmann [Bleischwitz and Schoppmann, 2008] study metric fault tolerant uncapacitated facility location. The mechanisms of Mehta et al. and of Bleischwitz and Schoppmann are actually generalizations of Moulin mechanisms [Moulin, 1999; Moulin and Shenker, 2001] and rely in their core on pushing single parameter cost sharing techniques to their limit. The work of [Georgiou and Swamy, 2013] handles combinatorial cost sharing, however, their results are obtained via a reduction to the single parameter setting, e.g., by assuming additive valuations or considering "all or nothing" solutions. This approach leads to poor approximation ratios - linear in the number of goods.

4 Cost RecoveringMechanisms and the Potential Mechanism

The simple cost sharing domain is a single parameter one, where the private information of every player consists of one number. Thus, to design a dominant strategy mechanism one can focus on the quite powerful family of monotone algorithms. In fact, the literature contains powerful techniques for designing groupstrategyproof mechanisms, for various notions of groupstrategyproofness (e.g., the Moulin family of mechanisms [Moulin, 1999] and acyclic mechanisms [Mehta et al., 2007]).

In contrast, the combinatorial cost sharing domain is a multi-parameter one. The preferences of a player are represented by a function rather than a scalar. The difficulty of designing useful mechanisms for multi-parameter domains is well known. The root of evil is the lack of general design techniques except the VCG family. For example, if the domain is unrestricted, then the only possible dominant strategy mechanisms are affine maximizers [Roberts, 1979], a slight variation of VCG mechanisms. In general, more restricted domains as ours do allow for non VCG mechanisms, but the VCG family remains the main tool at our disposal.

However, while VCG is effective for welfare maximization, in cost sharing settings we also need to cover the construction cost. Unfortunately, conventional wisdom has it that the revenue of the VCG mechanism is uncontrollable and tends to be low 2 [Ausubel and Milgrom, 2006]. The main technical contribution of this paper challenges this - we do manage to "tame" the VCG beast and obtain VCG based mechanisms that are approximately budget balanced.

2 Some papers attempt to control the revenue of VCG in simpler auction settings by rebating the players, e.g., [Moulin, 2009; Guo and Conitzer, 2009; Cavallo, 2006]. Also relevant is the work of Blumrosen and Dobzinski [Blumrosen and Dobzinski, 2014] which is the closest in spirit to ours (and in fact is the inspiration to our work). One of their results essentially provide a cost-recovering VCG based mechanism for the excludable public good problem. Their mechanism can be derived as a special case of our constructions.

For simplicity, we start by constructing VCG based mechanisms that always cover the cost for simple cost sharing, so the valuation of each player i can be described by a single number: vi if served and 0 otherwise. In general, affine maximizers can have both (multiplicative) player weights and (additive) allocations weights. The former does not seem to be very useful, so we focus on affine maximizers of the form:

where H : 2N → R is a function that does not depend on the vi's. The payment of every player is his "social damage": if S is the allocation that maximizes (1) for the valuation profile v, then the payment of player i is:

where S-i is the allocation that maximizes (1) when the valuation of player i is identically 0. In words, player i pays the difference between the society gains with and without player i. The mechanism that outputs the set that maximizes (1) and charges the players according to (2) is a dominant-strategy mechanism that satisfies individual rationality and pi ≥ 0.

When H is the cost function C, we get a welfare maximizing mechanism. However, it is common for this mechanism to run a deficit, e.g., in the special case of excludable public good (C(S) = 1 for every S ̸= ∅), if vi > 1 for every player i, the revenue is 0.

Thus, to cover the incurred cost we need some other function H ̸= C. Notice from the definition of S-i that ∑j∈S-i vj -H(S-i) ≥ ∑j∈S-{i} vj -H(S-{i}). Hence, the payment of the i'th player pi is at least H(S) -H(S - {i}). A function H with the property that for every set S ⊆ N it holds that ∑i∈S H(S) - H(S - {i}) ≥ C(S) will lead to a dominant-strategy mechanism for simple cost sharing that always collects payments that cover the incurred cost. For example, in the special case of excludable public good, we can choose H(S) = H|S|, so if a set S is selected the marginal cost to H of each player i ∈ S is at least H(S)-H(S-{i}) = 1 |S| and the total payment is at least 1 (this special case was analyzed by Blumrosen and Dobzinski [Blumrosen and Dobzinski, 2014]).

Interestingly, for every cost function C the potential function of Hart and Mas-Colell [Hart and Mas-Colell, 1989] satisfies this property. Hart and Mas-Colell suggested the potential function as an alternative simple way of defining the Shapley values. Fix some cost function C, and consider some function PC that assigns a value to every coalition S ⊆ N and the cost function C. Suppose that PC is such that for every S ⊆ N the marginal contributions of the players add up to the cost of the coalition: Σi∈S(PC(S) - PC(S - {i})) = C(S). Hart and Mas-Collel show that PC exists and is unique. They term PC the potential function. It turns out that the Shapley value of player i in a coalition S is exactly its marginal contribution to PC (Shapleyi(S) = PC(S) - PC(S - {i})).

We generalize and adapt the potential function to our needs: the potential function as defined in [Hart and Mas-Colell, 1989] considers cooperative games, i.e., the cost function defined on subsets of N. Our generalization considers allocations. Specifically, we define the marginal contribution of player i to the allocation (S1, ..., Sn) by PC(S1, ..., Si-1, Si, Si+1, ..., Sn) - PC(S1, ..., Si-1, ∅, Si+1, ..., Sn).

We set the function H, which appears in (1) and (2), to be our generalization of the potential function, and name the new mechanism, a VCG mechanism using the potential function, the Potential Mechanism. Notice that this gives a dominant strategy cost-recovering mechanism for every cost function C. We are also able to prove efficiency guarantees if the cost function C is subadditive. Combined together, we get the following general result:

Theorem: Let C be a subadditive cost function. Then, the Potential mechanism always recovers the cost and provides an approximation ratio of 2Hn to the social cost. If C is submodular (or even XOS) the approximation ratio improves to Hn.

Again, the approximation ratio is essentially tight due to the impossibility result of [Dobzinski et al., 2008].

The Main Result

The main technical effort of this work is in identifying three settings in which the potential mechanism is not only efficient and cost recovering, but also budget balanced.

Theorem: Let C be a submodular cost function. The Potential Mechanism is Hn-budget-balanced and provides an approximation ratio of Hn to the social cost in each of the following settings:

• Supermodular valuations.
• General symmetric valuations and player-wise symmetric cost function 3 .
• Two players (n = 2) with general valuations.

In a recent work we generalized the potential mechanism and have shown that there exists a mechanism that always covers the cost and always approximately efficient, for every cost function and for every valuations functions.

Theorem: For every cost functionC there exists a dominantstrategy combinatorial cost-sharing mechanism that provides an approximation ratio of Hn+1 to the social cost and covers the cost.

5 Open Questions

We have presented a novel way to share the cost among participants. Yet, we do leave many exciting questions open.

Computational Issues. We focused on proving existence of mechanisms with good guarantees for combinatorial cost sharing. Of course we would like to have a mechanism that both runs in polynomial time and has good guarantees, such as economic efficiency and budget balance. We do not know whether such a mechanism exists in general, however, we note that in the case of supermodular valuations and a submodular cost function the potential mechanism is computationally efficient whenever the value of the potential function is easy to compute.

3 A valuation is symmetric if vi(S) = vi(T) whenever |S| = |T |. A cost function is player-symmetric if C(⃗S) = C( ⃗ T ) whenever |Si| = |Ti| for all i.

The Performance of the PotentialMechanism. The potential mechanism guarantees to cover the cost and to provide approximation ratio of 2Hn to the social cost for every subadditive cost function. It is not clear whether the mechanism is overcharging when considering a subadditive cost function (or even an XOS cost function) that is not submodular. A first step to make in order to understand the guarantees of the potential mechanism is to determine the overcharging of the mechanism for a simple cost sharing when the cost function is subadditive.

The Power of GSP vs. Strategyproof Mechanisms. The potential mechanism, which is a VCG-based mechanism, is known to be vulnerable to strategic behaviors of groups of players. We know very little about groupstrategyproof mechanisms for combinatorial cost sharing. In the paper we provide a mechanism that guarantees a poor approximation ratio of Ω(n). Are there groupstrategyproof mechanisms with better guarantees?

Impossibilities for Combinatorial Cost Sharing. In light of the impossibility result of [Dobzinski et al., 2008], which provides a lower bound of Ω(log n) to the approximation ratio of the social cost in simple cost sharing, we are looking for similar impossibilities results for combinatorial cost sharing, in particular for the setting of supermodular valuations and submodular cost function (recall that the potential mechanism is Hn-budget-balanced and provides an approximation ratio of Hn to the social cost in this case). Is there a mechanism which is β-budget-balanced and provides approximation ratio of ρ to the social cost where β, ρ < Hn?