An Asymptotically Optimal VCG Redistribution Mechanism for the Public Project Problem

1 Introduction

1.1 ProblemDescription

The public project problem is a classic mechanism design problem that has been studied extensively in economics and computer science [Mas-Colell et al., 1995; Moore, 2006; Moulin, 1988]. In this problem, n agents decide whether or not to build a non-excludable public project (e.g., a bridge that can be accessed by everyone). There are two possible outcomes: build and not build. Without loss of generality, we assume that the project costs 1. We use θi (0 ≤ θi ≤ 1) 1

1 Naroditskiy et al. [2012] showed that for the objective of maximizing worst-case efficiency ratios, it is without loss of generality

to denote agent i's valuation for the project if it is built. If the decision is not to build, then everyone retains her share of the cost, which equals 1/n. That is, agent i's valuation is either θi (if the project is built) or 1/n (if the project is not built). Our model is identical to those used in existing literature on VCG redistribution mechanisms for public project problems [Guo et al., 2011; Naroditskiy et al., 2012; Guo et al., 2013; Guo, 2016; Guo and Shen, 2017].

We focus on mechanisms that are efficient, strategy-proof, and weakly budget-balanced (the mechanisms should never incur deficits). Due to a characterization result from [Holmstr¨om, 1979], the only mechanisms with the above properties are the VCG redistribution mechanisms. Under a VCG redistribution mechanism, we first run the VCG mechanism, then every agent receives (or pays additionally) an amount that is independent of her own type as her redistribution payment. Since an agent's redistribution is independent of her own type, this guarantees that the incentives are not affected, therefore maintaining efficiency and strategy-proofness of VCG. To maintain weakly budget-balance, the total amount redistributed should never exceed the total VCG payment. Essentially, VCG redistribution mechanisms are just Groves mechanisms that are weakly budget-balanced.

We aim to maximize the worst-case efficiency ratio:

Definition 1. (Due to Moulin [2009]) A mechanism's worstcase efficiency ratio is the worst-case ratio between the achieved total utility and the first-best total utility. Here, the worst case is taken over all possible type profiles.

The first-best total utility is defined as the maximum total utility assuming that the agents act unselfishly.

One way to interpret the first-best total utility is that we assume the agents would voluntarily reveal their private types. We then solve the mechanism design problem as a pure optimization problem, ignoring incentives altogether. The firstbest total utility often cannot be achieved by strategy-proof mechanisms. The worst-case ratio between the achieved total utility and the first-best total utility is then an indication of the cost of implementing truthfulness.

to assume that the agents' valuations (the θi) are bounded above by the project cost (i.e., 1). Any mechanism can be easily generalized to handle θi values that are larger than 1, and the generalization does not reduce the mechanism's worst-case efficiency ratio.

Under our public project problem, if the agents act unselfishly, then the optimal total utility (considering the weakly budget-balance constraint) is achieved by the following trivial mechanism: no payments are needed, build if and only if the agents' total valuation exceeds the project cost. It should be noted that this trivial mechanism is only used as a benchmark as it is not strategy-proof. The first-best total utility equals max{∑ θi, 1}.

It should be noted that the worst-case efficiency ratio is at most 1 for weakly budget-balanced mechanisms. Under a minor technical assumption, we are able to derive a mechanism whose worst-case efficiency ratio approaches 1 as the number of agents approaches infinity. Therefore, even though we focus on strategy-proof and efficient mechanisms, for asymptotic cases, strategy-proofness and efficiency are "free constraints" - even if we drop these constraints, we cannot get better worst-case efficiency ratios. In other words, we have identified an asymptotically optimal weakly budget-balanced mechanism for the public project problem, and the resulting optimal mechanism is efficient and strategy-proof.

1.2 Related Research and Our Contributions

VCG redistribution mechanisms have been studied extensively in resource allocation settings. For the single-item auction, Cavallo [Cavallo, 2006] identified an asymptotically optimal VCG redistribution mechanism, whose worst-case efficiency ratio approaches 1 as the number of agents approaches infinity. Guo [Guo, 2011] proposed a similar asymptotically optimal mechanism for resource allocation with gross substitutes (i.e., multi-unit auctions with non-increasing marginal values, heterogeneous-item auctions with single demand). For non-asymptotic cases with specific numbers of agents, optimal VCG redistribution mechanisms have also been identified for various resource allocation settings, such as multiunit auctions and heterogeneous-item auctions [Guo and Conitzer, 2009; Moulin, 2009; Gujar and Narahari, 2011; Guo, 2012]. Manisha et.al. [Manisha et al., 2018] studied applying Deep Learning to the design of redistribution mechanisms.

VCG redistribution mechanisms have also been studied extensively for the public project problem [Guo et al., 2013; Guo et al., 2011; Naroditskiy et al., 2012; Guo, 2016; Guo and Shen, 2017]. Unfortunately, previous research on the public project problem has been less successful. Our paper significantly improves on previous results on multiple aspects. We summarize the related results from previous research and our contributions as follows:

Previous Results (PR) and Our Contributions (OC)

• PR Naroditskiy et al. [2012] conjectured that for the public project problem, the asymptotic worst-case efficiency ratio can reach 1. The authors discretized the type spaces and used Automated Mechanism Design to derive the upper bounds on the worst-case efficiency ratios for small n values. The upper bounds follow a pattern, which shows that as n approaches infinity, the upper bound approaches 1. This is a conjectured result because the upper bounds are not shown to be strict. Also, the pattern on the upper bounds was based on experi-
• mental results on small n values, so it may or may not hold for larger n.
• OC We confirm that the asymptotic worst-case efficiency ratio can indeed reach 1, under a minor technical assumption: we assume the agents' valuations are rational numbers with bounded denominators. For example, if the agents' valuations are expressed in terms of real-life currency values, then our assumption holds.
• PR Guo [2016] proposed a mechanism with a constant asymptotic worst-case efficiency ratio of 0.102.
• OC With the aforementioned technical assumption, we have achieved a ratio of 1. Even without the assumption, we have identified another mechanism with a constant asymptotic worst-case efficiency ratio of 0.5.
• PR For non-asymptotic cases with specific numbers of agents, several mechanisms have been proposed that achieved constant worst-case efficiency ratios, including one heuristic-based SBR mechanism [Naroditskiy et al., 2012], another heuristic-based ABR mechanism [Guo, 2016], and mechanisms derived via Automated Mechanism Design (AMD) [Guo and Shen, 2017]. These mechanisms are either computationally expensive to generate [Guo and Shen, 2017] or the worst-case ratios have to be calculated via numerical methods [Naroditskiy et al., 2012; Guo, 2016]. As a result, these mechanisms' ratios have only been calculated for at most 10 agents.
• OC We propose a mechanism with better worst-case efficiency ratios than all previous mechanisms. Furthermore, the mechanism's implementation takes O(n3 ) complexity. The worst-case efficiency ratio has been characterized analytically ( n+1 2n ). That is, unlike previous results, our mechanism can also be used for large n values. We present the competitive ratios of different mechanisms in the following table. The column OC contains the efficiency ratios of our mechanisms. The column UB contains the conjectured upper bounds on the efficiency ratios [Naroditskiy et al., 2012].
• OC Lastly, we also proved that if the agents' valuations are drawn from identical and independent distributions, our mechanisms' asymptotic efficiency ratio equals 1 with probability close to 1 (approaching 1 asymptotically). For example, if every agent's valuation is drawn i.i.d. from the uniformU(0, 1) distribution, then with 20 agents, the efficiency ratio is 1 with probability at least 0.954. With 50 agents, the probability becomes at least 0.991.

2 Formal Model Description

For the public project problem, anonymous 2 VCG redistribution mechanisms have the following form [Naroditskiy et al., 2012]:

• Build the public project if and only if ∑ θi ≥ 1.
• If the decision is to build, then agent i receives ∑j̸=i θj - h(θ-i).
• If the decision is not to build, then agent i receives (n1)/n - h(θ-i).
• h is an arbitrary function and θ-i refers to the types from the agents other than i herself.

A VCG redistribution mechanism is characterized by the function h. Not all h functions are valid, since we need to enforce the weakly budget-balanced constraint.

After simplification, we have that the total payment received by the agents is

We note that max{∑i θi, 1} is exactly the first-best total utility. For presentation purposes, we use S(θ) to denote this expression, where θ is the type profile.

Therefore, a VCG redistribution mechanism characterized by h is weakly budget-balanced if and only if

Because all VCG redistribution mechanisms are efficient and strategy-proof, under it, agent i's utility equals ∑i θi - h(θ-i) if the decision is to build, and her utility equals 1 - h(θ-i) if the decision is not to build. That is, agent i's utility equals S(θ) - h(θ-i). The total utility is then

The mechanism has a worst-case efficiency ratio α if

That is,

Combining the above with the weakly budget-balanced constraint, we have

In conclusion, our task is to design h that satisfies Inequality (1) with the aim of maximizing the worst-case efficiency ratio α.

2 For our objective, it is without loss of generality to focus on anonymous mechanisms.

Naroditskiy et al. [2012] derived one optimal h function for the case of 3 agents. Guo and Shen [2017] used Automated Mechanism Design technique and identified another optimal solution for 3 agents. We present the latter solution below as one of our results builds on it:

T(θ-i, b) is defined as the maximum between "the sum of the types from θ-i" and constant b. T(θ1-i , b) is defined as the maximum between "the highest type from θ-i" and b.

Unfortunately, neither of the previous results can be generalized to cases with larger numbers of agents. Naroditskiy et al. [2012]'s manual technique only works for 3 agents. Guo and Shen [2017]'s Automated Mechanism Design technique can handle more than 3 agents, but like many Automated Mechanism Design approaches, it soon reaches its computational limit around 10 agents. Also, the derived mechanisms are not optimal when the number of agents is above 3. One mechanism we propose in this paper is obtained by extending the mechanism described in Equation (2). Our approach can easily handle thousands of agents (it takes O(n3 ) time to calculate the payments) and the achieved worst-case efficiency ratios are also better.

3 Dimension Reduction Technique

The main challenge of designing h is its high dimension when n is large. When n = 100, h is a function with 99 variables, which makes it nearly impossible for manual design and computationally too expensive for techniques like Automated Mechanism Design. We have identified an effective technique for reducing the dimension of h, which leads to easy analysis and great worst-case ratios. We can reduce the dimension of h by focusing on the following family of mechanisms:

• We randomly pick 3 distinct agents i, j and k among the n agents.
• If an agent a is not picked, then her additional payment h(θ-a) is set to 0.
• If agent i is picked together with j and k, then her additional payment is set to

Here, z-ijk represents the sum of the types from the remaining n-3 agents (those that are not i, j, and k). That is, if an agent is picked, then her additional payment depends only on the types of the other two agents who are also picked, and the sum of the types from the remaining n - 3 agents.

By focusing on the above family of mechanisms, we are essentially dealing with g, which has only 3 variables. By focusing on the above family, we expect to lose on worstcase efficiency ratios (as we are imposing constraints). On the other hand, the design problem is now much easier to handle, and our results show that this dimension reduction technique leads to good worst-case efficiency ratios. 3

We average over all the possible random choices to end up with a mechanism that is deterministic and anonymous. For agent i, there is 3/n chance of being picked, we have

For presentation purposes, we introduce function f , which is just g divided by (n - 1). We have ∑i h(θ-i) equals

Recalling Inequality 1, we want the above sum (3) to be at least (n-1)S(θ) and at most (n-α)S(θ). Since we want α to be as large as possible, we basically want the above sum to be at least (n- 1)S(θ) and be as close to (n- 1)S(θ) itself as possible. One way to work toward this goal is to design f so that the following is at least S(θ) and be as close to S(θ) itself as possible.

We start with a trivial scenario. If z-ijk ≥ 1, then obviously the decision is to build (and this signal can be picked up by all of i, j, and k since this signal does not depend on any of their types). In this case, we simply set

As a result, if z-ijk ≥ 1, we have

Recall that our goal is to make the sum (4) to be above S(θ) and be as close to S(θ) as possible. With the setup in (5), we have made the sum exactly S(θ). So when z-ijk ≥ 1, the setup in (5) is optimal. We will stick to this setup in our mechanisms.

3 There are many possible ways to reduce dimensions. For example, we may randomly pick 4 agents and end up dealing with functions with 4 variables. Or we may group the agents in other ways (i.e., three even-sized groups instead of three individuals and a remaining large group). We have tried different dimension reduction methods, some also led to mechanisms with constant worst-case efficiency ratios, but the method we presented here is the one that led to the best results.

If for all i, j, k, we have z-ijk ≥ 1, then by the above setup, we have achieved an efficiency ratio of 1:

Lemma 1. Under the setup specified in (5), the efficiency ratio is 1 when the sum of the types is at least 4.

Proof. If ∑i θi ≥ 4, then z-ijk ≥ 1 for all i, j, k, because each type is at most 1.

4 Asymptotically Optimal Mechanism

Let I(COND) be the characteristic function.

We first introduce a technical assumption that is needed in our proof.

Definition 2 (Bounded Precision Assumption). Under the Bounded Precision Assumption, every agent's type is a rational number where the denominator is bounded above by constant C.

As mentioned earlier, the above assumption is not too restrictive. For example, if the agents' valuations are expressed in terms of real-life currency values, then our technical assumption holds. Or if the agents' valuations are expressed using fixed-precision formats (e.g., byte-sized integers 4 ), then our assumption holds.

Theorem 1. Under the Bounded Precision Assumption, the VCG redistribution mechanism characterized by the following f is asymptotically optimal. Namely, as n goes to infinity, the mechanism's worst-case efficiency ratio approaches 1.

The worst-case efficiency ratio equals

4 Of course, in this case, the project cost should also be expressed as an integer larger than 1.

Before we prove the theorem, we discuss how we derived the proposed mechanism. The high-level process is that we first construct an unanonymous mechanism that has a few properties that we need, and then anonymize it to get the mechanism described in the theorem.

When we randomly pick three agents, we keep track of the pick order. For example, let us say, the pick order is i, then j, then k. We only need to consider cases where z-ijk < 1, due to the setup described in (5).

For agent i, we set fi(θj, θk, z-ijk) to be

This is ensure that if θi = 0, then the above amount is exactly S(θ).

We then move on to agent j, we set fj(θi, θk, z-ijk) to be

The characteristic function ensures that if θi = 0, then the above amount is 0 (i has already figured out the exact value of S(θ), so j should not mess with it). Otherwise, if θj = 0, the sum of fi(θj, θk, z-ijk) and fj(θi, θk, z-ijk) is exactly S(θ).

Finally, for agent k, we set fk(θi, θj, z-ijk) to be

The characteristic function ensures that if either θi or θj equals 0, then the above amount is 0.

If either θi or θj is 0, then the sum (4) is exactly S(θ). If neither θi nor θj is 0, then the sum (4) is between S(θ) and 2S(θ). 5

The mechanism proposed in the theorem is obtained by averaging over the 3! = 6 possible permutations of the three picked agents, in order to make the mechanism anonymous. The anonymized version has two properties that we need: if two or more agents among the three picked agents have type 0, then the sum (4) is exactly S(θ). Otherwise, the sum (4) is between S(θ) and 2S(θ).

Now let us prove Theorem 1.

Proof. First of all, we do not need to consider type profiles where the sum of the types is at least 4 due to Lemma 1.

The Bounded Precision Assumption assumes that an agent's type has the form p/q where p and q are integers, and p ≤ q ≤ C. Therefore, the minimal non-zero type is 1/C. That is, the total number of agents with non-zero types is at most 4C.

Let us recall Equation 3. ∑i h(θ-i) equals

If at least two types among θi, θj, and θk are 0s, we have

5 This can be established via algebraic simplification, so we omit the details due to space constraint.

If at most one type is 0, then we have

is between S(θ) and 2S(θ).

We immediately have that ∑i h(θ-i) is at least (n - 1)S(θ).

For three random picks, the probability of having at most one 0 is at most

Therefore, the worst-case efficiency ratio equals

When n goes to infinity, the worst-case efficiency ratio approaches 1.

Example 1. Let us consider an example where C = 10.

• If C = 10 and n = 10000, then α = 0.553.
• If C = 10 and n = 100000, then α = 0.953.
• If C = 10 and n = 1000000, then α = 0.995.
• If C = 10 and n = 10000000, then α ≈ 1.000.

We conclude this section with another asymptotic result.

Theorem 2. We assume the agents' types are drawn independently and identically from a distribution, with µ and σ being the expectation and the standard deviation, respectively. We assume µ > 0 and σ > 0. If we use the setup introduced in (5) (true for all mechanisms proposed in this paper), then the efficiency ratio is 1 with probability at least

When n goes to infinity, the above probability approaches 1.

Proof. Let us consider the sum of the agents' types, denoted by s. The sum's expectation and standard deviation are µ′ = nµ and σ′ = √nσ. When n is large enough, µ′ = nµ is above 4. The probability that s is less than 4 is at most

This is at most (due to Chebyshev's inequality)

Since µ and σ are constants, when n goes to infinity, the probability of s < 4 approaches 0. When the sum of the types s is at least 4, our mechanism's efficiency ratio is 1 according to Lemma 1. Hence, asymptotically, our mechanism's efficiency ratio is 1 with probability 1.

Example 2. Let us consider an example where the agents' types are drawn independently and identically from a uniform distribution U(0, 1). Here, µ = 1/2 and σ2 = 1/12. According to Equation 7, under our mechanism, the efficiency ratio is 1 with probability at least 1- n 3(n-8)2 .

• If n = 20, the probability is at least 0.954.
• If n = 50, the probability is at least 0.991.
• If n = 100, the probability is at least 0.996.

5 Extending the Optimal Mechanism for Three Agents

In this section, we focus on smaller numbers of agents and derive a mechanism that achieves better worst-case efficiency ratios than previous results.

We extend the optimal mechanism from [Guo and Shen, 2017]. We use h3∗ to denote the optimal h function when n = 3. h3∗ from Equation (2) can be rewritten as h3∗ (a, b) =

Lemma 2. (Due to [Guo and Shen, 2017]): For any 0 ≤ a, b, c ≤ 1, we have

Next, we modify h3∗ slightly into h3∗′ (replacing a, b by min{a, 1} and min{b, 1}, respectively, and then added a - min{a, 1} + b - min{b, 1}):

Lemma 3. For any 0 ≤ a, b, c, we have

The main difference between Lemma 2 and Lemma 3 is that we no longer require that a, b, c ≤ 1.

Finally, for all constant terms mentioned in the description of h3∗′ , we can scale it by a factor of t and maintain a similar inequality to that in Lemma 3. We modify h3∗′ into h3∗′′ by scaling the constants by a factor of t:

Lemma 4. For all 0 ≤ a, b, c and 0 < t, we have

Theorem 3. The VCG redistribution mechanism characterized by the following f has a worst-case efficiency ratio of n+1 2n .

If z < 1, then

Proof. We have that for all 0 ≤ θi, θj , θk and 0 ≤ z-ijk < 1,

Therefore, we have

For the mechanism characterized by the above f function, ∑i h(θ-i) is at least (n-1)S(θ), as required by Inequality 1.

Next we analyze how large ∑i h(θ-i) can be.

We first consider type profiles where the decision is to build. ∑i h(θ-i) is at most

So when the decision is to build, the corresponding worstcase efficiency ratio is n+1 2n . We omit the case where the decision is not to build due to space constraint.

In summary, for the mechanism we introduced in this section, which does not require the Bounded Precision Assumption, the worst-case efficiency ratio is n+1 2n . Asymptotically, this is 0.5. We have included this mechanism in the table in Subsection 1.2. This mechanism outperforms all previously proposed mechanisms in terms of worst-case efficiency ratios (both asymptotically and for smaller number of agents). The mechanism's implementation takes O(n3 ) complexity, as we need to average over all possible draws of three agents.