# A Shapley-based Groves mechanism: when the mechanism designer plays the wise man

Michela Chessa

► To cite this version:

Michela Chessa. A Shapley-based Groves mechanism: when the mechanism designer plays the wise man. Operations Research Letters, 2019, 47 (6), pp.560-564. 10.1016/j.orl.2019.09.010. hal-02390679

HAL Id: hal-02390679

https://hal.science/hal-02390679

Submitted on 20 Jul 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# A Shapley-based Groves mechanism: when the mechanism designer plays the *wise man*

Michela Chessa<fnref n="1" />

Université Côte d'Azur, GREDEG, CNRS, France

## Abstract

We define two mechanisms. The first one implements the Shapley value to define some monetary transfers, but it is not incentive compatible. The second one implements only in expectation the same solution and it is a Groves mechanism. While inheriting all the properties of this family, it is also budget-balanced (still in expectation). The trick is to ask the mechanism designer to insert/remove some utility and to take/give it back at the end.

**Keywords:** Shapley value, Potential, Mechanism design, Budget-balanced

## 1. Introduction

Social decision processes in models with public goods represent one of the most discussed debate in economics. In such models, the social planner cannot observe certain characteristics of the players, but she has to rely on their revelation. However, the players may manipulate the situation, trying to improve their luck by not telling the truth and ending up in an equilibrium outcome that will suffer of what is well-known as “free rider” problem.

In within this framework, in this paper we deal with a standard public good economy in which the unobserved characteristic of a player is represented by her true valuation over a set of available alternatives, and with the so called *revelation mechanisms*. We focus on the specialized context of [7] and [8]. These assumptions have historically led to the definition of a subclass of revelation mechanisms, the so called *Groves revelation mechanisms*, which

<footnote n="1">¹Corresponding author.
Email address: michela.chessa@gredeg.cnrs.fr
Postal address: 250 rue Albert Einstein - CS 10269 06905 Sophia Antipolis Cedex</footnote>
are “optimal” in the sense that stating one’s true valuation is a dominant
strategy (*incentive compatibility*) and that a social welfare maximizing pub-
lic good (level) is selected (*successful*). In [6], the authors have then shown
that this class of mechanisms is in fact the only one which has these desirable
properties. Additionally, under some assumptions Groves mechanisms
are *ex post individually rational*, meaning that they do not make the players
worse off in the end than if they were not taking part in the mechanism.
However, the well-known *Hurwicz’ impossibility result* [11] has proved that
no revelation mechanism can achieve an additional appealing property, the
*budget-balanced*, which ensures that the mechanism does not need to pay to
or to win money from the players, without sacrificing either the efficiency
or the individual rationality property. Groves mechanisms may be, instead,
simply *weak budget-balanced*, as it is the case for the well-known Vickrey-
Clarke-Groves (VCG) mechanism [14, 3, 7], meaning that the mechanism
does not need to pay, but it wins money from the players. In many situa-
tions, however, this impossibility result represents a serious limit toward the
applicability of the mechanism (see example in Section 5).

1.1. *Our main contribution and results*

To overcome this problem, in this paper we propose two mechanisms: the *Shapley revelation* (SR) and the *Approximated Shapley revelation* (ASR) mechanisms. The first one is presented as a preliminary version of the second one: after building a natural cooperative extension of the original game, it defines some monetary transfers that aim at implementing the most known cooperative solution, the *Shapley value* [13]. The SR mechanism is naturally budget-balanced (Theorem 1), but it is not a Groves mechanism, and it lacks, for example, the incentive compatibility property. In the ASR mechanism, on the other side, the monetary transfers implement only in expectation the Shapley value: the mechanism designer is assumed to know the distribution of the valuation functions of the players (this is a pretty common assumption in the specific context of mechanism design) and, by consequence, is capable of estimating the surplus of cooperation and of distributing it between the players according to the cooperative solution proposed share. The resulting mechanism is a Groves mechanism and, as such, still satisfies all the good well-known properties of this family, but, in addition, it is budget-balanced in expected value (Theorem 2). Given the impossibility result of Hurwicz, we claim that this is the best we can achieve toward the “best” revelation mechanism. The implementation at the basis of the ASR mechanism is twofold.
(i) Technically, our procedure relies on an alternative interpretation of the Shapley value [9], which describes it as the discrete gradient of a potential function. The idea is to associate to every cooperative game a single number, the potential, and to give each player the marginal contribution to the grand coalition, computed according to these numbers. (ii) From the implementation point of view, the trick at the basis of our mechanism is to ask an additional player, namely the mechanism designer, to participate in the game and insert (or remove) some utility, before implementing the procedure, and to take back (or to give back) the corresponding amount at the end of the game. The intervention of the additional player does not affect the total amount of resources in expectation, as she acts simply for fairness in redistributing the total income. Here the small classical story [9] to illustrate the key concept: A Sheik died, leaving a will directing his three sons to divide the property as follows: one-half goes to the oldest son, one-third to the middle son, and one-ninth to the youngest. The property consisted of seventeen camels. The problem was solved by the “wise man” who rode into town by his camel. He added his own camel to the seventeen, and then the three brothers took their shares out of eighteen camels: nine, six, and two, respectively. One camel was left, on which the wise man rode out of town.

In the final part of the paper we show how the “trick” can be implemented
by the mechanism designer in an extremely efficient way, under some specific
assumptions and thanks to a generating function based method, making our
mechanism appealing in terms of possible applications.

The remainder of the paper is organized as follows. In Section 2, we
introduce the classical model of a revelation mechanism. Section 3 describes
our new mechanisms and provides the main results. Section 4 shows how
the incentives can be computed, in practice and efficiently. In Section 5 we
provide an illustrative example. Section 6 concludes. Section 7 presents few
related works.

2. The model

We are concerned with an economy with a set of players $N = \{1, \dots, n\}$,
a unique private good, such as money, which allows transfers among the play-
ers, and a set $\mathcal{X}$ (compact in a topological space) of available alternatives.
Each player $i \in N$ has a true valuation function $v_i : \mathcal{X} \to \mathbb{R}_+$, which se-
lects for each alternative $x \in \mathcal{X}$ her personal valuation. The true valuation
function $v_i$ is player $i$'s private information. In addition, we consider the
possibility to implement monetary transfers $t_i \in \mathbb{R}$ with $i = 1, \dots, n$ such that the utility of player $i$ is a separable function $u_i : \mathcal{X} \times \mathbb{R} \to \mathbb{R}$ defined as

$$u_i(x, t_i) = v_i(x) + t_i.$$

A revelation mechanism is a couple $RM = \{V, f\}$ where $V = \prod_{i=1}^{n} V_i$ is the state space and $V_i$ is the set of allowable (upper semi-continuous) valuation functions of player $i$ and $f: V \to \mathcal{X} \times \mathbb{R}^n$ defined as

$$f(w) = [x(w), t_1(w), \dots, t_n(w)],$$

is the function that, given a vector $w$ of $n$ valuation functions (one for each player), selects an alternative $x = x(w) \in X$, and a program of monetary transfers $t_1 = t_1(w), \dots, t_n = t_n(w) \in \mathbb{R}$. In a revelation mechanism, each player reveals a valuation function $w_i \in V_i$, which may be different by the true one, and then an outcome $x(w)$ is produced according to some given rules. Given a revelation mechanism $RM$ and a vector of valuation functions $w$, then the utility for player $i$ may be written with an abuse of notation as

$$u_i(w, RM) = u_i(x(w), t_i(w)). \qquad (1)$$

Given a revelation mechanism RM, then the players play a *revelation game* $(N, V, (u_i)_{i \in N})$, with set of players $N$, strategy space $V_i$ for each $i \in N$ and utility function $u_i$ given by (1). We denote by $w^*$ a pure strategy Nash equilibrium of the revelation game. Such an equilibrium may not be unique.

A revelation mechanism is said to be (i) *successful*, if when the players play at equilibrium $w^*$, the alternative which is selected is a maximizer of the utilitarian social choice function $\sum_{i \in N} v_i(x(w^*))$ (defined as the sum of the real valuation functions evaluated on the selected alternative); (ii) *strongly individual incentive compatible*, if revealing the real $v_i$ is a dominant strategy for each individual $i \in N$, i.e., $u_i(v_i, w_{-i}; RM) \ge u_i(w_i, w_{-i}; RM)$ for each $w \in V$, and where $w_{-i}$ denotes a vector of valuation functions of all the players but $i$, (iii) *ex post individual rational*, if when the players play at equilibrium $w^*$, they get a positive utility by participating in the mechanism, i.e., $u_i(x(w^*), RM) \ge 0$, for each $i \in N$; (iv) *weak budget-balanced*, if when the players play at equilibrium $w^*$, the mechanism does not lose money, i.e., $\sum_{i \in N} t_i(w^*) \le 0$, and (v) *budget-balanced* if when the players play at equilibrium $w^*$, the mechanism does not win and does not lose money, i.e., $\sum_{i \in N} t_i(w^*) = 0$.
In a particular class of revelation mechanisms, the *Groves mechanisms* [8], given $w \in V$, the decision function selects an alternative which maximizes the declared utilitarian social choice function, i.e., $x(w) = x^*$ such that

$$x^* \in \arg\max_{x \in \mathcal{X}} \sum_{i=1}^{n} w_i(x) \qquad (2)$$

and

$$t_i(w) = \sum_{j \in N, j \neq i} w_j(x^*) + h_i(w_{-i}), \qquad (3)$$

for each $i \in N$, with $h_i$ an arbitrary function of the vector $w_{-i}$ of the declared valuation functions of all the players but $i$. The assumption of having upper semi-continuous valuation functions on a compact set is sufficient to ensure that such an $x^*$ exists, i.e., that the set of maximizing projects is non-empty (the same reasoning will hold when defining functions $h_i$ and $z^w$ later on). A Groves mechanism is strongly individual incentive compatible, and then it is successful (by construction). The incentive compatibility relies on the fact that the function $h_i$ does not depend on the declaration of player $i$, and then it does not affect her incentives to tell the truth or lie.

The Vickey-Clarke-Groves (VCG) mechanism, the most known Groves mechanism, has functions $h_i$ defined as

$$h_i(w_{-i}) = -\max_{x \in \mathcal{X}} \sum_{j \in N, j \neq i} w_j(x),$$

for each $i \in N$. Intuitively, in a VCG mechanism each player pays her social cost, i.e., how much she “hurts” the others by being part of the mechanism. Under our assumptions, the VCG mechanism is ex post individual rational and it is weak budget-balanced, but it is not budget-balanced.

As we have already observed in the Introduction, and as we will see in more details in Section 5, the non budget-balanced, i.e., the necessity of making pay the players, is a serious limit toward the applicability of the proposed model. The following section illustrates our proposal to overrule this limit.

### 3. The Shapley-based revelation mechanisms

Our proposed mechanisms are based on a cooperative interpretation of the public good economy, that we will present in three steps. First, given a
vector $w \in V$ of valuation functions, we define the function $z^w : 2^N \to \mathbb{R}$ as

$$z^w(S) = \max_{x \in \mathcal{X}} \sum_{i \in S} w_i(x),$$

for each $S \subseteq N \setminus \emptyset$, and $z^w(\emptyset) = 0$. This can be naturally interpreted as the characteristic function of a cooperative game $(N, z^w)$, which may be shown to be monotonic whenever $w_i$ is positive for each $i \in N$. Intuitively, function $z^w$ defines the best each group of players can obtain collectively by reaching an agreement.

Second, we recall a result which has been shown in [9]: given a cooperative game $(N, z^w)$, it is possible to extend it in a unique way to a game $(N_0, z_0^w)$ with $N_0 = N \cup \{0\}$, in such a way that $z_0^w(S) = z^w(S)$ for all $S \subseteq N$ and the marginal contributions to the grand coalition and to all the subcoalitions are efficient, i.e., $z_0^w(S) = \sum_{i \in S}[z_0^w(S) - z_0^w(S \setminus \{i\})]$ for each $S \subseteq N_0$. For each $S \subseteq N$, the value $z_0^w(S \cup \{0\})$ coincides with the potential of the game $(N, z^w)$ restricted to $S$. Given the set of all games $\Gamma$, we call potential the function $P: \Gamma \to \mathbb{R}$ with $P(\emptyset, v) = 0$ and $\sum_{i \in N} (P(N, v) - P(N \setminus \{i\}, v)) = v(N)$ for each $(N, v) \in \Gamma$, where $(S, v)$ with $S \subseteq N$ is the restriction of $(N, v)$ to $S$. We have that $z_0^w(S \cup \{0\}) = P(S, v)$ for each $S \subseteq N$.

Moreover, the marginal contribution to the grand coalition for each player $i \in N$ to $N_0$ in game $(N_0, z_0^w)$ coincides with her Shapley value $\phi_i$ [13] in the game $(N, z^w)$

$$z_0^w(N_0) - z_0^w(N_0 \setminus \{i\}) = \phi_i(N, z^w) = \sum_{S \subseteq N, i \in S} \frac{(n-s)!(s-1)!}{n!} [z^w(S) - z^w(S \setminus \{i\})],$$

where $s = |S|$ for each $S \subseteq N$, and it is equal to $z_0^w(N_0) - z^w(N)$ for player 0. The Shapley value represents the most classical way to share the utility between the players in a cooperative setting. Its potential interpretation allows us to translate this allocation into some marginal contributions according to a different function, in this case $z_0^w$. The “zero player” of this extended game is a hidden player who explains the residual profit (or loss) resulting from the cooperation and that, in our case, will be played by the mechanism designer. In order to compute $z_0^w(N_0)$ (and, similarly, the value of the potential on all the subcoalitions), it is possible to implement the following formula

$$z_0^w(N_0) = \sum_{S \subseteq N} \frac{(s-1)!(n-s)!}{n!} z^w(S). \qquad (4)$$
Third, we define a subclass of revelation mechanisms such that, given a revelation vector $w \in V$, the decision function selects an alternative which maximizes the declared utilitarian social choice function, as in (2) for a Groves mechanism, but with monetary transfers defined as

$$ \bar{t}_i(w) = \sum_{j \in N, j \neq i} w_j(x^*) + \bar{h}_i(w), $$

for each $i \in N$, and function $\bar{h}_i$ defined as

$$ \bar{h}_i(w) = - \max_{x \in \mathcal{X}} \sum_{j \in N, j \neq i} w_j(x) + A(w) - b[z_0^w(N_0 \setminus \{i\}) - z^w(N \setminus \{i\})], \quad (5) $$

where $A: V \to \mathbb{R}$ and $b \in \mathbb{R}$ are such that the mechanism respects the ex post individual rationality property. In particular, $A(w) \equiv 0$ (null function) and $b = 0$ define the VCG mechanism. We observe that, differently from the definition of functions $h_i$ in (3), that had as argument the valuation functions of all the players but $i$, functions $\bar{h}_i$ may be a function of $w_i$ too and then these mechanisms are not in general Groves mechanisms.

We present now our first mechanism, defined for $b = 1$ and $A(w) = \bar{A}(w) := z_0^w(N_0) - z^w(N)$. This mechanism, that we call the Shapley Revelation (SR) mechanism, does not produce and does not destroy money. Moreover, it implements the Shapley value share, whenever the players reveal the real valuation vector.

**Theorem 1.** The SR mechanism is budget-balanced. Moreover, when the players reveal the real valuation vector $v \in V$, $u_i(v, SR) = \phi_i(N, z^v)$ for each $i \in N$.

*Proof.* We suppose that the players reveal $w \in V$. Then, the selected outcome $x^*$ is such that $\sum_{i \in N} w_i(x^*) = z^w(N)$. When $b = 1$ and $A(w) = z_0^w(N_0) - z^w(N)$, each player gets a utility $v_i(x^*)$ and an additional payment equal to

$$ \begin{aligned} \bar{t}_i(w) &= \sum_{j \in N, j \neq i} w_j(x^*) - z^w(N \setminus \{i\}) \\ & \quad + z_0^w(N_0) - z^w(N) - z_0^w(N_0 \setminus \{i\}) + z^w(N \setminus \{i\}) \\ &= z_0^w(N_0) - z_0^w(N_0 \setminus \{i\}) - w_i(x^*) \\ &= \phi_i(N, z^w) - w_i(x^*). \end{aligned} $$

Because of the efficiency property of the Shapley value, it follows that for each declared valuation vector $w \in V$
$$ \sum_{i \in N} \bar{t}_i(w) = \sum_{i \in N} [\phi_i(N, z^w) - w_i(x^*)] \\ = z^w(N) - z^w(N) = 0 $$

and then the SR mechanism is budget-balanced.

Moreover, whenever the players declare the real valuations $v \in V$, it follows that each player will get as utility share her Shapley value in the game $(N, z^v)$.

□

As interpretation of this solution, we assume that the mechanism designer, acting as “zero player”, adds to the total utility of each player the residual of cooperation, equal to the quantity $\bar{A}(w) = z_0^w(N_0) - z^w(N)$, shares the total income according to the marginal contribution for each player $i \in N$ to $N_0$ in game $(N_0, z_0^w)$, and finally she takes back the same initial amount $n \cdot (z_0^w(N_0) - z^w(N))$. However, as stated just before the theorem, the proposed mechanism is not a Groves mechanism: computing the quantity $z_0^w(N_0) - z^w(N)$ necessarily requires knowing the declared valuation of player $i$, and this has the natural drawback of affecting the strongly individual incentive compatibility property of our mechanism and, consequently, the possibility of getting an implementation of the Shapley value solution share.

To overcome this problem, we define our second mechanism, supposing that the mechanism designer is capable of making an estimation a priori (i.e., before the revelation of the players) of the quantity $z_0^v(N_0) - z^v(N)$, i.e, of the residual of cooperation on the real valuations $v$. This can be done, for example, each time the distribution of the players (i.e., of their valuation functions) is known a priori by the mechanism designer. Formally, given the state space $V$, let $\Delta(V)$ be the collection of all probability measures on $V$. We suppose that the mechanism designer can observe $\sigma \in \Delta(V)$, which corresponds to the distribution of a random variable that we call $R$. We now extend the definition of function $\bar{A}$, to the random variable $\bar{A}(R) = \bar{A}(r)$, with $r$ a realization of $R$. In this probabilistic framework, the declared valuation vector $w$ corresponds to a specific realization of the random variable $R$, and $\bar{A}(w)$ to the corresponding realization of the random variable $\bar{A}(R)$. Then, from $\sigma$, the mechanism designer can compute the expected value $\mathbb{E}[\bar{A}]$, which is an unbiased estimation of the quantity $\bar{A}(v)$, i.e., of the value of function $\bar{A}$ on the real valuations $v$. The *Approximated Shapley revelation* (ASR) mechanism is then defined with payments as in (5) and with choice of the parameters $b = 1$ and $A(w) \equiv \mathbb{E}[\bar{A}]$. We may observe that $\mathbb{E}[\bar{A}]$ is
not a function of the specific realization $w$, and in particular of $w_i$ anymore, as it is now the mean over all the possible realizations, and then the ASR mechanism is a Groves mechanism. It holds the following theorem:

**Theorem 2.** In a ASR mechanism, at equilibrium each player $i \in N$ declares her true valuation $v_i$. Moreover, $\mathbb{E}[u_i(v, ASR)] = \phi_i(N, z^v)$ for each $i \in N$.

*Proof.* The ASR mechanism is a Groves mechanism, then, at equilibrium, each player $i$ declares her true valuation function $v_i$. It follows that, at equilibrium

$$ 
\begin{aligned}
\mathbb{E}[u_i(v, ASR)] &= z^v(N) - z^v(N \setminus \{i\}) \\
&\quad + z_0^v(N_0) - z^v(N) - z^v(N_0 \setminus \{i\}) + z^v(N \setminus \{i\}) \\
&= z_0^v(N_0) - z^v(N_0 \setminus \{i\}) \\
&= \phi_i(N, z^v)
\end{aligned}
$$

□

Similarly to before and as interpretation of this mechanism, we assume that the mechanism designer, acting as “zero player”, adds to the total utility of each player the expected quantity $\mathbb{E}[\bar{A}]$, shares the total income according to the marginal contribution for each player $i \in N$ to $N_0$ in the extended game in which the valuation functions have been estimated through the observation $\sigma \in \Delta(V)$, and finally takes back the same initial amount. As, differently from before, the players have now incentives to declare their real valuation function $v_i$, each player is left in expectation with her Shapley value in game $(N, z^v)$.

**4. Implementation of the incentives**

In this section, we tackle a crucial point, i.e., we illustrate how the mechanism designer can make the “trick” of estimating the value $\mathbb{E}[\bar{A}]$ in the ASR mechanism. We suppose that she observes $(\delta_{v_1}, \dots, \delta_{v_n}) \in \Delta(V)$, i.e., the value distributions are Dirac masses at the real valuation functions $v_i$ for each $i \in N$. In particular, we consider the case of a public good project, such as buying a common item, and where the item will be pursued only if a minimum amount of money is collected (the cost $c$ of the item). In this case, the set of alternatives is simply given by $X = \{\text{buy, not buy}\}$. Moreover, we suppose that each player assigns value zero to the alternative “not buy”, but they have different valuations for the alternative “buy”. From now
on, we will assume these valuations to be strictly positive natural numbers $\nu_1, \dots, \nu_n \in \mathbb{N}_+$. We may observe that this hypothesis is, in practice, not restrictive, as soon as we assume our commodity for transfers, such as money, to have a fixed number of decimal digits. The valuation function of player $i \in N$ is then given by $v_i : \{\text{buy, not buy}\} \to \mathbb{N}$, such that $v_i(\text{not buy}) = 0$ and $v_i(\text{buy}) = \nu_i$. With an abuse of notation, given $\nu$ the vector of valuations in $\mathbb{N}_+^n$, we denote with $z^\nu$ and $z_0^\nu$ the corresponding characteristic functions. In this simplified setting, for the mechanism designer everything reduces to observing a vector $(\delta_{\nu_1}, \dots, \delta_{\nu_n})$ of Delta functions centered in $\nu_1, \dots, \nu_n$ respectively. We consider these Delta functions as defined on the continuous real line, even if centered on natural numbers.

In this context, when implementing the ASR mechanism, the value of function $z^\nu$ on $S \subseteq N$ is then described by the following distributions

$$ \left\{ \begin{array}{ll} \delta_{\sum_{i \in S} \nu_i - c} & \text{if } \sum_{i \in S} \nu_i > c \\ \delta_0 & \text{otherwise,} \end{array} \right. \qquad (6) $$

where $\delta_0$ is the Delta function centered in 0, where 0 represents the common valuation for not pursuing the item. Now, in order to obtain the estimation of the surplus of cooperation $z_0^w(N_0) - z^w(N)$ efficiently, we propose a combinatorial method based on generating functions. By (4) and (6) we observe that, when the valuations of the players are distributed as Dirac delta functions, also the surplus of cooperation is distributed as a Dirac delta function centered on

$$ t = \sum_{j=1}^{n} \frac{(j-1)!(n-j)!}{n!} \left( \sum_{k=c+1}^{W} A(k,j)(k-c) \right) - (W-c) \quad (7) $$

where $A(k, j)$ is the number of coalitions $S$ of $j$ players and $\sum_{i \in S} \nu_i = k$, and $\sum_{i=1}^n \nu_i = W$. Then, it holds the following theorem:

**Theorem 3.** (Cantor) Let $(N, z^\nu)$ be a cooperative game with characteristic function defined as in (6). Then, the generating function of the numbers $A(k, j)$ is given by $f(x, y) = \prod_{i \in N} (1 + yx^{\nu_i}) = \sum_{k \ge 0} \sum_{j \ge 0} A(k, j)x^k y^j$.

This result has been originally stated for the efficient computation of the Shapley-Shubik index, where the $\nu_i$'s are representing the weights of the players in a weighted majority game [2], but it still applies to our case in which the $\nu_i$'s represent the players' valuations. By (7) and Theorem 3, and assuming the logarithmic cost model of [2], we can show that the computation of the incentives can be done efficiently by the mechanism designer:
**Theorem 4.** Let $(N, z^\nu)$ be a cooperative game with characteristic function defined as in (6). If $C$ is the number of non-zero coefficients of function $f(x, y)$, then the time complexity of the generating algorithm for computing the expected surplus of cooperation is $O(nC)$.

*Proof.* There are two independent **for** loops:

$$ 
\begin{array}{l}
\texttt{gg(y) \leftarrow 0} \\
\textbf{for } k \in \{c+1, \dots, W\} \textbf{ do} \\
\quad \texttt{gg(y) \leftarrow gg(y) + A(k, j) \cdot (k-c)y^j}
\end{array}
$$

**endfor**

Thus, we obtain the polynomial $gg(y) = \sum_{j=1}^{n} b_j z^j$, whose coefficients appear in the next sum

$$ 
\begin{array}{l}
m \leftarrow 0 \\
\textbf{for } j \in \{1, \dots, n\} \textbf{ do} \\
\quad m \leftarrow m + b_j (j-1)!(n-j)! \\
\end{array}
$$

**endfor**

$$ m/n!-W+c $$

Thus, we can calculate the index in time $O(nC)$.

□

In the following example, we illustrate how the mechanism designer, acting as wise man, can implement the ASR mechanism and how this leads to a more applicable outcome, compared to the one of a classical VCG mechanism.

## 5. Example

Consider three roommates who would like to buy a TV that costs €100. They have respectively true valuation for the option “having a TV” equal to $\nu_1 = 30$, $\nu_2 = 50$ and $\nu_3 = 70$ (all the valuations are equal to zero for the complementary option). According to the VCG mechanism, they should declare their true valuation and be assigned the following monetary transfers:

$$ t_1 = 50 + 70 - 100 - (50 + 70 - 100) = 0 $$

$$ t_2 = 30 + 70 - 100 - (30 + 70 - 100) = 0 $$

$$ t_3 = 30 + 50 - 100 = -20. $$

In our example, roommates 1 and 2 pay nothing, while roommate 3 pays 20, and this is obviously not enough to cover the cost of the TV.
Implementing the ASR mechanism, we suppose that the distribution of the true valuations of the players is known a priori (before any declaration by them). The corresponding cooperative game defined as in Section 3 is $z(\{2, 3\}) = 20$, $z(\{1, 2, 3\}) = 50$ and $z(S) = 0$ otherwise. The Shapley value of such a game is equal to $\phi(z) = (10, 20, 20)$. We suppose the mechanism designer to be capable of making an unbiased estimation of the quantity $z_0^\nu(N_0) - z^\nu(N) = -30$, while the quantities $z_0^\nu(N_0 \setminus \{i\}) - z^\nu(N \setminus \{i\})$ are computed a posteriori after the declaration of the valuation functions, and at equilibrium they are equal to 0, when $i = 2, 3$, and $z_0^\nu(N_0 \setminus \{1\}) - z^\nu(N \setminus \{1\}) = 10$. According to the ASR mechanism, the roommates should declare their true valuation, buy the TV, and be assigned the following expected monetary transfers:

$$ \mathbb{E}(t_1) = 50 + 70 - 100 - (50 + 70 - 100) - 30 + 10 = -20 $$

$$ \mathbb{E}(t_2) = 30 + 70 - 100 - (30 + 70 - 100) - 30 = -30 $$

$$ \mathbb{E}(t_3) = 30 + 50 - 100 - 30 = -50. $$

Now, in expectation roommate 1 pays 20, roommate 2 pays 30 and roommate 3 pays 50, and this new share covers the cost of the TV.

The formal way to implement such a mechanism is the following one: having estimated the quantity $z_0^\nu(N_0) - z^\nu(N) = -30$, the mechanism designer asks each roommate to anticipate an amount equal to €30, for a total of €90. Then, the roommates declare their true valuation, and a Groves mechanism is implemented, where each player $i \in N$ receives a payment equal to the classical VCG payment plus an additional amount $z_0^\nu(N_0 \setminus \{i\}) - z^\nu(N \setminus \{i\})$. As a result of this Groves mechanism, roommate 3 has to pay €20 to the mechanism, while roommate 1 gets €10, for a total payment of €10. In the end, the mechanism designer gives them back the €90 she has taken at the beginning, and the three roommates will be left with a total of €100, that they will use to pay the TV.

## 6. Conclusions

The scope of this paper is to propose a new Groves mechanism that, additionally to satisfying all the good properties of this family of mechanisms, is also budget-balanced in expected value. We claim that, given the Hurwicz' impossibility result, this is the best we can achieve toward the “best” revelation mechanism. We have shown as such a mechanism, really intuitive in
the formulation, can also be easily implementable in a specific case of a public good project, in which the mechanism designer can observe some Delta masses distributions of the valuations of the players. The natural future work in this direction is to provide a more exhaustive analysis of the possibility of implementing our mechanism in a more general case.

## 7. Related work

In the literature, sparse examples of cooperative game theoretical analysis used withing the classical mechanism design problems are already present. In [1], the authors investigate how in a VCG auction it can be beneficial for the agents to coordinate and misreport their valuations. To investigate such a manipulation, they define a cooperative game, the so called *collusion game*. In [5], in a cost-sharing mechanism design problem, the authors define the *Shapley value mechanism*, a Shapley-like solution which has our same scope of proving a budget-balanced share of the resources. However, the proposed mechanism is not successful. In another work [4] and in the context of prediction markets, the author proposes the *Shapley value information mechanism*, exploiting the fact that this solution concept can be interpreted as the average of the marginal contribution to all the different orderings of the players. However, their proposed mechanism is simply ex interim incentive compatible.

Additionally to its original scope, this work broadens the *Nash pro-gram* related analysis, an agenda, initiated by Nash himself in 1953 [12], to bridge the gap between the non-cooperative and the cooperative approaches in game theory. Many authors have contributed, focusing on obtaining a non-cooperative implementation of the main cooperative solution concepts, such as the Nash bargaining solution, the core or the Shapley value [15, 10]. Differently from all this literature, that proposes some complex and often counter-intuitive procedures, our mechanism is extremely simple and “user-friendly”.

## Acknowledgments

The author would like to thank Vito Fragnelli, Roberto Lucchetti, Gian-vittorio Luria and the anonymous reviewers for their useful comments and suggestions.
[1] Y. Bachrach, Y. Zadimoghddam, and M. Key. A cooperative approach to collusion in auctions. *ACM SIGecom Exchanges*, 10:17–22, 2011.

[2] J.M. Bilbao, J.R. Fernandez, A. Jimenez Losada, and J.J. Lopez. Generating functions for computing power indices efficiently. *TOP*, 8:191–213, 2000.

[3] E. Clarke. Multipart pricing of public goods. *Public Choice*, 11:17–33, 1971.

[4] V. Conitzer. Prediction markets, mechanism design, and cooperative game theory. In *In Proceedings of UAI*, 2009, pages 101–108, 2009.

[5] S. Dobzinski, A. Mehta, T. Roughgarden, and M. Sundararajan. Is shapley cost sharing optimal? (for the special issue in honor of lloyd shapley). *Games and Economics Behavior*, 108, 2017.

[6] J. Green and J.J. Laffont. Characterization of satisfactory mechanisms for the revelation of preferences for public goods. *Econometrica*, 45:427–438, 1977.

[7] T. Groves. Incentives in teams. *Econometrica*, 41:617–631, 1973.

[8] T. Groves and M. Loeb. Incentives and public inputs. *Journal of Public Economics*, 4:211–226, 1975.

[9] S. Hart and A. Mas-Colell. The potential of the shapley value. In A. E. Roth, editor, *The Shapley Value, Essays in Honor of L.S. Shapley*, pages 127–137. Cambridge University Press, 1988.

[10] S. Hart and A. Mas-Colell. Bargaining and value. *Econometrica*, 64,2:357–380, 1996.

[11] L. Hurwicz. On informationally decentralized systems. In C.B. McGuire and R. Radner, editors, *Decision and organization*, pages 297–336. University of Minnesota Press, Minneapolis, 2nd edition, 1972.

[12] J. F. Nash. Two person cooperative games. *Econometrica*, 21:128–140, 1953.
[13] Lloyd S. Shapley. A value for n-person games. In A. W. Tucker and R. D. Luce, editors, *Contributions to the Theory of Games II*, pages 307–317. Princeton University Press, 1953.

[14] W. Vickrey. Counterspeculation, auctions, and competitive sealed tenders. *The Journal of Finance*, 16:8-37, 1961.

[15] E. Winter. The demand commitment bargaining and snowballing cooperation. *Economic Theory*, 4:255-273, 1994.