Incentive-Compatible Diffusion Auctions

1 Introduction

In traditional auctions, the bidders are given no incentives to spread the sale information to others since they are in perfect competition. This not only ends the sale with a low revenue, and even worse, may lead to an inefficient allocation. For instance, suppose a seller is selling an item on eBay. Visitors who browse the sale may join in the sale and put their bids. The strike price of the item depends on the number of bidders and their posted bids. In order to involve more participants in an auction, the seller can advertise the sale via sponsored search or social media, etc. However, if the advertisements do not bring any buyers valuable enough, the investment on the advertisements could probably be wasted.

∗Corresponding author.

To tackle this problem, a new thread in auction design which is called diffusion auction comes to the fore. This kind of auction mechanisms can incentivize the early joined participants to share the sale information to the uninformed individuals via, for example, online social networks. [Li et al., 2017] initiated this problem in the scope of social networks. They showed that the classic VCG mechanism [Vickrey, 1961; Clarke, 1971; Groves, 1973] can be directly extended to the social network setting, but the seller may suffer a loss by implementing this mechanism. To overcome the low revenue problem, they proposed the information diffusion mechanism (IDM) which is not efficient but guarantees the seller's revenue. In some particular economic networks, efficiency and revenue could both be guaranteed by a natural market model called customer sharing mechanism [Li et al., 2018]. [Li et al., 2019] further identified a class of diffusion mechanisms for any unweighted graphs, and IDM is a special case in this class with the lowest revenue. They also established a mechanism for weighted graphs.

All of the above-mentioned auctions are specific cases of incentive-compatible (IC) diffusion auctions. Nevertheless, general characterizations of incentive-compatible diffusion auctions are still missing in the literature. The most obvious advantage of incentive-compatible mechanisms is that they are easy for the participants to play and easy for the designer to predict the outcome. Moreover, according to the revelation principle [Myerson, 1979], although honest reporting may not be the only Nash equilibrium, it is without loss of generality to focus on incentive-compatible mechanisms. For diffusion auction design, since each buyer can only share the auction information to some subset of her neighbors, the argument form that is used to prove the revelation principle also holds. In this work, we characterize a sufficient and necessary condition for incentive-compatible diffusion auctions. We prove that natural monotonic allocation policies can be implemented in dominant-strategy incentive-compatibility (DSIC). Moreover, given any monotonic allocation policy, we also obtain the optimal payment policy, i.e., the one that maximizes the seller's revenue.

The characterization of incentive-compatibility can be traced back to value monotonicity [Myerson, 1981] and is later rediscovered by [Archer and Tardos, 2001]. Value monotonicity has been widely used to obtain incentivecompatible mechanisms for single-parameter domains where each agent's preference over outcomes can be captured by a single parameter [Archer and Tardos, 2001; Briest et al., 2005; Auletta et al., 2004; Andelman et al., 2007; Kov´acs, 2005]. A generalization of value monotonicity into arbitrary domains is cycle monotonicity [Rochet, 1987]. However, cycle monotonicity is overly complicated and is rarely applied to argue incentive-compatibility. It is known that for convex domains, cycle monotonicity can be replaced by a simpler condition, called weak monotonicity [Lavi et al., 2003; Bikhchandani et al., 2006; Shmoys and Tardos, 1993]. But even this simpler condition does not have much application in mechanism design for multidimensional problems. When the domain of preferences is unrestricted and there are at least three possible outcomes, [Roberts, 1979] shows that the only incentive-compatible mechanisms are variations of the VCG mechanism. In the diffusion auction scenario, besides posting in a bid, each bidder is allowed to strategically diffuse the sale information to others. Therefore, this is a nontypical multidimensional problem where one domain is the bid and the other domain could be any subset (even an empty set) of edges of a graph. As we will show in the following parts, value monotonicity is not suffice to incorporate diffusion incentives and we develop new techniques for analyzing the incentive-compatibility of diffusion auctions.

Section 2 formulates the basic model of diffusion auction. Section 3 provides a general characterization of incentivecompatible diffusion auctions. In Section 4, we elaborate on a class of natural allocation policies and derive the optimal payment policies for such allocations.

2 Preliminaries

Consider a digraph G = (N,E), where N is the node set and E is the edge set, assume there is a seller s ∈ N who wants to sell an indivisible item. Each node i ∈ N \ {s} refers to a potential buyer and each pair of nodes can communicate through an edge in E. The most typical examples of such graphs are social networks where each person can only directly communicate with her neighbors, e.g., friends, relatives. Initially, only the seller's neighbors are informed of the sale. A node can participate in the sale if and only if one of her neighbors is aware of the sale and further invites her to join the sale. The seller wants to incentivize the early participants to share the sale information to the uninformed nodes, whereby all nodes in the graph can join the sale. This can not only increase the seller's revenue, but also improve the allocation efficiency. For convenience, we define N-s as N \ {s} and call a node in N-s a buyer.

The above problem can be modeled as an auction. Formally, denote buyer i's privately known type by ti = (vi, ri), where vi is her valuation of the item and ri is the set of all her direct neighbors. Let t = (t1, · · · , tn) denote the type profile of all buyers and t-i = (t1, t2, · · · , ti-1, ti+1, · · · , tn) denote the type profile of all buyers except i, i.e., t = (ti, t-i). Let T = ×Ti∈N-s be the type profile space of all buyers, where Ti = R≥0 ×P(N) is buyer i's type space and P(N) is the power set of N. Since ti is private information, i can strategically misreport to affect the outcome. Let t′i =

(v′i , r′i ) ∈ Ti be the reported type of buyer i where r′i ⊆ ri means that i diffuses the sale information to a subset r′i of her neighbors. Since buyers can not diffuse information to a non-existing neighbor, we have r′i ∈ P(ri). Denote a feasible reported type profile of all buyers by t′ = (t′1 , · · · , t′n ), where feasibility requires that t′i = nil if i has never been informed of the sale or she decides not to join the sale. We only consider feasible reported type profiles.

Definition 1. A diffusion auction mechanism M = (π, x) on graph G consists of two components: an allocation policy π = {πi}i∈N-s and a payment policy x = {xi}i∈N-s , where πi : T → {0, 1} and xi : T → R are the allocation and payment functions for i, respectively.

Given buyers' reported type profile t′ , πi(t′ ) = 1 means that i gets the item, while i does not get the item if πi(t′ ) = 0. xi(t′ ) ≥ 0 indicates that i pays the seller xi(t′ ), and i receives |xi(t′ )| from the seller if xi(t′ ) < 0. We say an allocation policy π is feasible if for all t′ ∈ T, ∑i∈N-s πi(t′ ) ≤ 1, and if πi(t′ ) = 1, then t′i ̸= nil. That is, a feasible allocation can only allocate the item to at most one participant. Let Π be the set of all feasible allocations. In what follows, we only consider feasible allocations. Given an allocation policy π and a type profile t, the social welfare is define as W(π, t) = ∑i∈N-s πi(t)vi. An allocation policy π∗ is efficient if for all t ∈ T it always maximizes W(π∗ , t).

Definition 2. An allocation π∗ is efficient if for all t ∈ T, π∗ ∈ argmaxπ′∈ΠW(π′ , t).

Given buyer i with truthful type ti = (vi, ri), a reported type profile t′ and a mechanism (π, x), the quasilinear utility of i is defined as: ui(ti, t′ , (π, x)) = πi(t′ )vi-xi(t′ ). We say a diffusion auction is individually rational if for each buyer, her utility is non-negative when she truthfully reports her valuation, no matter to which subset of neighours she diffuses the auction information and what the others do.

Definition 3. A diffusion auction mechanism (π, x) is individually rational (IR) if ui(ti, ((vi, r′i ), t′-i ), (π, x)) ≥ 0 for all i ∈ N-s, all r′i ∈ P(ri), and all t′-i ∈ T-i.

In diffusion auctions, IR ensures that no matter how a buyer diffuses the information, as long as she honestly reports her value, she will not suffer loss. Besides IR, now we define the incentive-compatibility (IC) as: for each buyer, reporting her true valuation and, meanwhile, fully diffusing the sale information to all her neighbors is always a dominant strategy, no matter what the others do.

Definition 4. A diffusion auction mechanism (π, x) is incentive-compatible (IC) if ui(ti, (ti, t′-i ), (π, x)) ≥ ui(ti, (t′i , t′′-i ), (π, x)) for all i ∈ N-s, all t′i ∈ Ti, and all t′-i ∈ T-i.

Note that on the right-hand side of the inequality, (ti, t′-i ) is replaced by (t′i , t′′-i ). This is because if i does not spread the auction information to all her neighbors, then some buyers who can receive the information under ti, may no longer be able to receive it. Thus under t′i , the feasible type profile of buyers except i is changed from t′-i to t′′-i .

Now we formulate the diffusion auctions' criteria with respect to the seller. Given a reported type profile t′ and a diffusion auction mechanism M = (π, x), the seller's revenue generated by M is defined as the sum of all buyers' payments RevM(t′ ) = ∑i∈N-s xi(t′ ).

Definition 5. A diffusion auction mechanismM = (π, x) is (weakly) budget balanced if for all t′ ∈ T , RevM(t′ ) ≥ 0.

Over the past few years, following similar models as the above, several diffusion auction mechanisms have been proposed, while a general theory for diffusion auctions is missing. In the following sections, we will establish such a theory to fill the gap.

3 Incentive-Compatible Diffusion Auctions

We say an allocation policy π is implementable if there is a payment policy x such that the mechanism (π, x) is IR and IC, and say it is value-monotonic if a winner cannot become a loser by increasing her bid. Given a value-monotonic allocation policy, there exists a critical bid for buyer i, above/below which i wins/loses the item, i.e., each buyer's critical bid is the minimum bid that makes her win.

The most simple scenario is that seller s connects to all buyers in N-s. Since the seller knows all buyers in advance, it reduces to the traditional single-item auction design. General theories for this case have been well developed. Many well-known works [Myerson, 1981; Lehmann et al., 2002; Archer and Tardos, 2001; Mu'Alem and Nisan, 2008] show that a normalized mechanism (i.e., losers always pay zero) for single-parameter domains is IC if and only if its allocation policy is value-monotonic, and the winner pays exactly her critical bid. The most well-know theory for this case is Myerson's Lemma [Myerson, 1981].

Theorem 1 (Myerson's Lemma). Fix a single-item auction environment without information diffusion.

• (a) An allocation policy π is implementable if and only if it is value-monotonic.
• (b) If π is value-monotonic, then there is a unique payment policy x for which (π, x) is IR and IC and the winner pays her critical bid and the losers pay zero.

However, Myerson's Lemma does not apply in our general setting. First of all, although critical bid is a powerful tool of characterizing the payment policy in traditional auctions, the characterization of it is not straightforward in diffusion auctions. In single-parameter domains, critical bid is well defined which depends only on other bidders' bids. For example, in the second price auction, each bidder's critical bid equals the highest bid of the other buyers which is not affected by herself. Unfortunately, this argument is no longer valid in diffusion auctions, since any buyer i now can affect others' report t′-i through strategic diffusion. Secondly, the losers' payoffs in a diffusion auction can be positive and can vary from one bidder to another [Li et al., 2019].

In diffusion auctions, any buyer i's diffusion strategy can affect the allocations. Given any r′i ⊆ ri there is a minimum winning bid for buyer i. That is, each buyer i's critical bid should be a function of her diffusion strategy r′i . Define the critical bid in diffusion auctions as follows.

Definition 6. Given an allocation policy π and other buyers' reports t′-i , buyer i's critical bid with respect to r′i ⊆ ri is v∗ i (r′i ) = arg minb′i∈R≥0 {πi((b′i , r′i ), t′-i ) = 1}.

Note that under some special allocation policies, a buyer cannot win no matter what she does. An immediate evidence is the 'unlucky buyers' identified in [Li et al., 2017]. It is a special class of buyers who cannot affect the allocations no matter how high they bid and which subset of neighbors they diffuse the sale information to. Whenever in these cases, set v∗ i (r′i ) = ∞ for all r′i ⊆ ri. Whether such buyers exist is jointly determined by the structure of the graph and the designed allocation policy.

For single-item auctions, a buyer either wins the item or not. Hence, a buyer's payment policy xi(t′ ) can be decoupled into two components: the payment for winning the item xi(t′ |πi(t′ ) = 1) and the payment for losing it xi(t′ |πi(t′ ) = 0). Let ˜xi(t′i , t′-i ) = xi(t′ |πi(t′ ) = 1) and xi(t′i , t′-i ) = xi(t′ |πi(t′ ) = 0), respectively. The following proposition is straightforward from this definition and will be very useful to explore the underlying structures of diffusion auction design.

Proposition 1 (Payment Decoupling). Given a mechanism (π, x), for all i and all t′-i , the payment for i can be decoupled as xi(t′ ) = πi(t′ )˜xi(t′i , t′-i ) + (1 - πi(t′ ))xi(t′i , t′-i ).

We call ˜x and x the decoupled-payments from x. To simplify the notations, the term t-i, t′-i will be omitted when analyzing a specific buyer i. In the following definitions and lemmas, we will characterize several properties that any IC diffusion auction should possess, and then in Theorem 2 we will further prove that these properties are also sufficient for any diffusion auction to be IC. We first extend the traditional value-monotonicity into diffusion auctions.

Definition 7 (Value-Monotonic Allocation). An allocation policy π for a diffusion auction is value-monotonic if for any t′ and any buyer i with πi((v′i , r′i ), t′-i ) = 1, we have πi((v′′ i , r′i ), t′-i ) = 1 when v′′ i ≥ v′i .

It means that for any buyer i, once her diffusion action is fixed as r′i and all the other buyers' reports are fixed as t′-i , then her allocation is monotonically increasing over her bid v′i . In other words, given t′-i and r′i , i wins the item if and only if v′i ≥ v∗ i (r′i ). We now prove that any IC diffusion auction should have value-monotonic allocation.

Lemma 1. If a diffusion auction (π, x) is incentivecompatible, then π is value-monotonic.

Proof. Proof by contradiction: assume there exists an IC diffusion auction and π is not value-monotonic. This means there are two values v2 i > v1 i such that πi((v1 i , ri), t-i) = 1 but πi((v2 i , ri), t-i) = 0. Denote the payments for buyer i with types t1i = (v1 i , ri) and t2i = (v2 i , ri) by ˜xi(t1i ) and xi(t2i ), respectively. Recall that ˜xi is i's payment for winning and xi is her payment for losing. If v1 i - ˜xi(t1i ) ≥ -xi(t2i ), then buyer i with losing type t2i should misreport t1i since v2 i - ˜xi(t1i ) > v1 i - ˜xi(t1i ) ≥ -xi(t2i ); similarly, if v1 i - ˜xi(t1i ) < -xi(t2i ), then buyer i with winning type t1i should misreport t2i to lose. Since there always exists a beneficial deviation, then the diffusion auction cannot be IC and the assumption is false.

We next extend the traditional value-independent payment into diffusion auctions based on the payment-decoupling in Proposition 1.

Definition 8 (Bid-Independent Decoupled-Payments). The two decoupled-payments from x are bid-independent if for all t′-i , all i and i's two different reports (v′i , r′i ) and (v′′ i , r′i ), we have ˜xi(v′i , r′i ) = ˜xi(v′′ i , r′i ) and xi(v′i , r′i ) = xi(v′′ i , r′i ).

The payment for i consists of the two decoupled-payments, thus if both of them are bid-independent, then the payment for i is also bid-independent. This covers the property of payment in traditional single-item auctions. We now prove that any incentive-compatible diffusion auction should have bid-independent decoupled-payments.

Lemma 2. If a diffusion auction (π, x) is incentivecompatible, then the decoupled-payments of x are bidindependent.

Proof. Given a buyer i and t-i, for any two winning types t1i = (v1 i , ri) and t2i = (v2 i , ri) where min{v1 i , v2 i } ≥ v∗ i (ri), assume for a contradiction that ˜xi(v1 i , ri) ̸= ˜xi(v2 i , ri), then buyer i with t1i would misreport t2i when ˜xi(v1 i , ri) > ˜xi(v2 i , ri), and buyer i with t2i should misreport t1i when ˜xi(v1 i , ri) < ˜xi(v2 i , ri). Therefore, for the winning buyer, her payment ˜xi should be independent of her bid. The same argument is also true for the losers. If max{v1 i , v2 i } < v∗ i (ri) and xi(v1 i , ri) ̸= xi(v2 i , ri), then loser i with higher payment may misreport. Hence, ˜xi and xi should be independent of buyer's bid in any IC diffusion auction.

Since ˜xi and xi are independent of v′i in any IC diffusion auction, we replace ˜xi(v′i , ri) and xi(v′i , ri) with ˜xi(ri) and xi(ri) for expression convenience. The following lemma further deduces that if a diffusion auction is IC, then for every buyer, her critical payment should be a binding constraint for her decoupled-payments.

Lemma 3. If a diffusion auction (π, x) is incentivecompatible, then for any t and all i, the equation ˜xi(ri) - xi(ri) = v∗ i (ri) holds.

Proof. Assume there is an IC diffusion auction and ˜xi(ri) - xi(ri) ̸= v∗ i (ri). Then either ˜xi(ri) - xi(ri) > v∗ i (ri) or ˜xi(ri) - xi(ri) < v∗ i (ri). For the former case, the winning buyer with ti = (v∗ i (ri), ri) will try to lose by lowering her bid, since her utility will be increased from v∗ i (ri)-˜xi(ri) to -xi(ri). Similarly, for the latter case, a losing buyer i with ti = (vi, ri), where ˜xi(ri) - xi(ri) < vi < v∗ i (ri), will misreport to win since her utility of winning vi - ˜xi(ri) is larger than that of losing-xi(ri). In either case, it contradicts the assumption.

The last property we want to present is that in an IC diffusion auction, a buyer's payment should be minimized by diffusing the sale information to all her neighbors.

Definition 9 (Diffusion-Monotonic Decoupled-Payments). The two decoupled-payments from x are diffusion-monotonic if for all i and all t′-i , when r′′ i ⊆ r′i , we have ˜xi(v′i , r′′ i ) ≥ ˜xi(v′i , r′i ) and xi(v′i , r′′ i ) ≥ xi(v′i , r′i ).

The following lemma guarantees that all IC diffusion auctions possess this diffusion-monotonicity property.

Lemma 4. If a diffusion auction (π, x) is incentivecompatible, then the decoupled-payments from x are diffusion-monotonic.

Proof. Consider an IC diffusion auction and two diffusion sets r2 i ⊆ r1 i . If ˜xi(r2 i ) < ˜xi(r1 i ), then a winning buyer with (vi, r1 i ), where vi ≥ max{v∗ i (r1 i ), v∗ i (r2 i )}, would misreport (vi, r2 i ) since vi - v∗ i (r2 i ) > vi - v∗ i (r1 i ). This contradicts IC, thus ˜xi(r2 i ) < ˜xi(r1 i ) is false. Similar argument shows xi(r2 i ) < xi(r1 i ) is also false.

Next, we prove that the above properties together also serve as a sufficient condition for IC diffusion auctions.

Theorem 2. A diffusion auction (π, x) is incentivecompatible if and only if for all type profile t and all i, P1-P4 are satisfied, where

P1 : π is value-monotonic,

P2 : ˜xi and xi are bid-independent,

P3 : ˜xi(ri) -xi(ri) = v∗ i (ri),

P4 : ˜xi and xi are diffusion-monotonic.

Proof. Lemma 1-4 proved the necessity of these four properties in any IC diffusion auction. Next we prove that if a mechanism satisfies P1-P4, then it is IC. The proof includes two steps. The first step shows that the winner has no incentives to deliberately become a loser and vise versa. The second step shows once a buyer's allocation is determined, truthfully reporting maximizes her utility .

According to P2, the bids in all ˜xi and xi are omitted. If i is the winner by truthfully reporting, when she misreports to lose, her utility changes from vi - ˜xi(ri) to -xi(r′i ), where r′i ⊆ ri. We have vi - ˜xi(ri) ≥ v∗ i (ri)- ˜xi(ri) = -xi(ri) ≥ -xi(r′i ), where the left inequality comes from that i wins by truthfully reporting, the inner equation comes from P3 and the right inequality comes from P4. Therefore, a winner has no incentive to misreport to become a loser. If i is a loser by truthfully reporting, when she misreports to win, her utility changes from -xi(ri) to vi - ˜xi(r′i ). We have vi - ˜xi(r′i ) ≤ v∗ i (ri) - ˜xi(r′i ) ≤ v∗ i (ri) - ˜xi(ri) = -xi(ri) where the first inequality comes from P1, the second inequality comes from P4 and the equation is from P3. Therefore a loser has no incentive to misreport to win.

Now we prove that each kind of buyers maximize their utilities by truthfully reporting. A winner's utility is vi - ˜xi(ri). If she misreports t′i and still wins, her utility becomes vi - ˜xi(r′i ) which is no more than vi - ˜xi(ri) according to P2 and P4. Also, reporting t′i has a risk of becoming a loser, which is not beneficial. Therefore it is always an optimal strategy for the winner to be truthful. Similar arguments also hold for the losers. In a word, either a buyer wins or loses, being truthful is always a dominant strategy. That is, P1-P4 is a sufficient condition for a mechanism to be IC.

Besides IC, as we mentioned earlier in Definition 3, a diffusion auction should also be individually rational (IR) which guarantees that each buyer's utility is nonnegative when bidding truthfully.

Theorem 3. An incentive-compatible diffusion auction is individually rational if and only if for all buyer i and all type profile t, property P5: xi(∅) ≤ 0 is satisfied.

Proof. Fix t-i, then i's utility is ui(vi, ri) = πi(vi, ri)(vi - ˜xi(ri))+(1-πi(vi, ri))(-xi(ri)) = πi(vi, ri)(vi-v∗ (ri))- xi(ri), where the last equation comes from P3. IR means that for any true type (v′i , r′i ) ∈ R≥0 ×P(ri), the inequality πi(v′i , r′i )(v′i - v∗ (r′i )) - xi(r′i ) ≥ 0 must hold. This can be guaranteed when minv′i∈R≥0,r′i⊆ri πi(v′i , r′i )(v′i - v∗ (r′i )) - xi(r′i ) ≥ 0 holds. By P1, πi(v′i , r′i ) = 1 when v′i ≥ v∗ (r′i ) and πi(v′i , r′i ) = 0 when v′i < v∗ (r′i ), therefore the minimization requires the bid v′i < v∗ (r′i ). Then the minimization function becomes -xi(r′i ). According to P4, -xi(r′i ) is minimized by choosing r′i = ∅. Hence, the minimum of ui is -xi(∅), where ti = (v′i < v∗ i (∅), r′i = ∅). Therefore, IR is equivalent to the property that for each i and each t, xi(∅) ≤ 0 must hold.

We emphasize that Theorem 2 and 3 imply Myerson's Lemma, but not vice versa. Given any classic valuemonotonic allocation policy, it is not guaranteed that a mechanism will have diffusion incentives. This is why we must have properties P3-P5 hold. The above results present the IC and IR diffusion auctions in a high-level view, while no details are given for the allocation and payment policies. Since a diffusion auction can be very complex, even when the allocation is value-monotonic, it could be very difficult to obtain the corresponding payment policy. In the next section, we present a class of more operational and natural allocation policies, for which an elegant form of the payment policies can be achieved.

4 Monotonic Allocation and Optimal Payment

Our design of natural allocation policies is inspired by the following intuition: in the real world, if a person wins in a sale, she can still win by posting a higher bid; a person who diffuses the sale information to less friends has a better chance of winning the sale, since some high-bid competitors might be excluded from the sale. We focus on such allocations.

Formally, given a buyer i, define a partial order ⪰ti on types: (v1 i , r1 i ) ⪰ (v2 i , r2 i ) if and only if v1 i ≥ v2 i ∧ r1 i ⊆ r2 i . Definition 10. An allocation policy π for a diffusion auction is monotonic if for every type ti with πi(ti, t-i) = 1, we have

that πi(t′i , t′-i ) = 1 for any t′i ⪰ ti.

This definition is an extension of value-monotonicity in Definition 7. The following lemma presents a nice property of monotonic allocation policies, it is a key component of the results in this section.

Lemma 5. If an allocation policy π is monotonic, then for all i and all r′i ⊆ ri, v∗ i (r′i ) ≤ v∗ i (ri).

Proof. Assume there is a monotonic π such that for two reports t′i = (v∗ i (ri), r′i ) and ti = (v∗ i (ri), ri), where r′i ⊆ ri, it has v∗ i (r′i ) > v∗ i (ri). In this case, we have t′i ≻ ti, however, πi(t′i ) = 0 and πi(ti) = 1, which contradicts the monotonicity. Thus the assumption is false.

The key observation from Lemma 5 is that under any monotonic allocation policy, buyer i's critical bid function v∗ i (ri) is nondecreasing in ri. Recall that in characterizations of incentive-compatibility, P4 shows both ˜xi and xi are nonincreasing in ri. Moreover, P3 shows ˜xi(ri) - xi(ri) = v∗ i (ri). Based on Lemma 5 and the above observations, we show that any monotonic allocation policy is implementable.

Proposition 2. In diffusion auctions, any monotonic allocation policy is implementable.

Proof. Remind that a diffusion auction is IR and IC if and only if for any type profile t-i and any buyer i with (vi, ri), P1-P5 hold. Given any monotonic allocation policy, P1 is directly met according to the definitions. Construct two decoupled-payments as ˜xi(ri) = ˜ fi(v∗ i (ri)) + hi(t-i) and xi(ri) = f i(v∗ i (ri))+hi(t-i), where hi(t-i) is independent of i's report, and ˜ fi(v∗ i (ri)) and fi(v∗ i (ri)) are nonincreasing in v∗ i (ri), and ˜ fi(v∗ i (ri)) - fi(v∗ i (ri)) = v∗ i (ri). This construction for ˜x and x satisfies P2-P4. A possible choice is ˜ fi(v∗ i (ri)) = -αv∗ i (ri) and fi(v∗ i (ri)) = -(1 + α)v∗ i (ri), where α could be any nonnegative value. Setting hi(t-i) = (1 + α)v∗ i (∅), P5 is also satisfied. Therefore, for any monotonic allocation, there is a payment such that the mechanism is IR and IC. This completes the proof.

From the proof of Proposition 2, we can see that even when given a monotonic allocation policy, the space of proper payment policies could still be very large. For example, ˜ fi and fi need not be linear in v∗ i (ri), they can be any polynomials with negative coefficients. In the following we select payment policies with respect to the seller's revenue.

Definition 11. Given a monotonic allocation policy π and two payment policies x1 , x2 satisfying IR and IC, we say x1 dominates x2 in the revenue if for any type profile t, Rev(π,x1 ) (t) ≥ Rev(π,x2 ) (t).

If there exists a payment policy x∗ such that for any type profile t ∈ T, it dominates all the other payment policies under IR and IC conditions, then x∗ is optimal with respect to π. Our next result shows that for any monotonic allocation policy, the optimal payment policy exists.

Theorem 4. Given any monotonic allocation policy π, the payment policy x∗ = {x∗i = v∗ i (∅)-v∗ i (ri)(1-πi(t))}i∈N-s is optimal.

Proof. Given any type report profile t and a monotonic allocation policy π, the seller's revenue can be expressed as

where w is the winner and i ̸= w are the losers. The optimal payment policy x∗ should maximize Rev(t) and (π, x∗ ) should be IR and IC. For all IR and IC mechanisms, P1-P5 should hold. P1 is met by the monotonic allocation. According to P3, ˜xw(rw) = xw(rw) + v∗w (rw). Substituting this equation into Rev(t), we get v∗w (rw) + ∑i∈N-s xi(ri). Since the allocation policy is already given, v∗w (rw) is a constant for any t ∈ T. Hence, the objective now is to find x∗ = arg maxx ∑i∈N-s xi(ri) where P2-P5 hold for all i. Furthermore, since each buyer's payment policy (˜xi, xi) is independent of the others' payment policies, the problem of searching for argmaxx=(˜xi,xi) ∑i∈N-s xi(ri) becomes solving |N| - 1 independent maximization subproblems:

max

(˜xi,xi)

xi(ri)

Since v∗ i (ri) is independent of i's bid, constraints (1) and (2) are equivalent to P2. Constraints (2) and (3) together with Lemma 5 ensure that ˜xi and xi are diffusion-monotonic. Constraint (4) is from P5. Hence, constraints (1)-(4) are equivalent to P2-P5, provided that π is monotonic. This means a solution to the above system is an implementable allocation that maximizes the seller's revenue.

According to constraint (3), we must have xi(ri) + v∗ i (ri) ≤ xi(∅) + v∗ i (∅). Rearranging the order, we have

Note that the left side of this inequality is just one of our maximization subproblems. Since xi(∅) ≤ 0 according to constraint (4), we know that xi(ri) is bounded by v∗ i (∅) - v∗ i (ri) which is a constant with respect to an allocation policy π and t. Our finding is that

and

is a feasible solution and hence the optimal one. To see this, notice that xi(∅) is always 0 when xi(ri) = v∗ i (∅) - v∗ i (ri). Therefore constraint (4) is satisfied. Since v∗ i (ri) is independent of v′i and is also nondecreasing in ri, constraints (1) and (3) are satisfied. Finally, the maximized value of xi(ri) and the corresponding value of ˜xi(ri) are xi(ri) = v∗ i (∅) - v∗ i (ri) and ˜xi(ri) = v∗ i (∅), respectively. That is, charging the winner v∗ i (∅) and the losers v∗ i (∅) - v∗ i (ri) will maximize the seller's revenue. Based on Proposition 1, we have x∗i = ˜xi(ri)πi(t) + xi(ri)(1 - πi(t)) = v∗ i (∅) - v∗ i (ri)(1 - πi(t)). Now we complete the proof.

Under the above framework, it is not difficult to verify that the allocation policies of the recently proposed diffusion auction mechanisms [Li et al., 2017; Li et al., 2018; Li et al., 2019] are all monotonic and their payment policies implicitly satisfy the form in Theorem 4. Especially, the classic VCG mechanism uses an efficient allocation that is monotonic. [Li et al., 2017] proved that under the diffusion auction scenario, the VCG mechanism is not budget-balanced, meaning that the seller may have a large deficit. We emphasize that the payment policy in the VCG mechanism also satisfies the optimality in Theorem 4. Then we know that if the allocation policy is efficient, then any IR, IC diffusion auction is not weakly budget-balanced.

Proposition 3. There exists no IR and IC diffusion auction which is efficient and (weakly) budget-balanced.

Before proving this proposition, we first show that the payment policy of the VCG mechanism follows Theorem 4.

Lemma 6. In the VCG mechanism, each buyer's payment satisfies the form in Theorem 4.

Proof. In the VCG mechanism, the highest bidder wins the item. Clearly, this allocation policy is monotonic. Each buyer i in the VCG mechanism pays

which is interpreted as the social welfare decrease of others caused by i's participation. Since there is only one item for sale, then W(π∗ , t \ {ti}) is the highest bid without i's participation and it exactly equals v∗ i (∅). If i does not win, then the second term W(π∗ , t) - π∗ i (t)vi = W(π∗ , t) = v∗ i (ri). Otherwise, the second term is 0. Hence, for any buyer i,

Such a payment policy matches the form in Theorem 4.

Proof of Proposition 3. According to Lemma 6 and Theorem 4, we know that the payment policy in the VCG mechanism maximizes the seller's revenue. Since the allocation policy is efficient and [Li et al., 2017] shows that the VCGmechanism is not budget balanced, Proposition 3 is true.

5 Conclusions

In this paper, we characterize a sufficient and necessary condition for all incentive-compatible and individually rational diffusion auctions. We also propose a class of natural monotonic allocation policies, for which we obtain the corresponding optimal payment policy that maximizes the seller's revenue. In practice, diffusion auctions can be applied in a recursive way: any new comer will be treated as a bidder if she submits a two-dimensional type. This recursion is terminated if there is no new submission. Based on the reports by all participants, the seller can build the social network and determines the allocation and the payments.

An immediate extension of this work is IC in diffusion auctions where the seller has multiple homogeneous items [Zhao et al., 2018; Kawasaki et al., 2020]. It is also important to investigate how the relaxation of IC constraints can improve the efficiency in diffusion auctions [Jeong and Lee, 2020]. Beyond the scope of diffusion auctions, our results could also be applied to general mechanisms with the following format: each agent i is defined by two parameters vi and zi. vi is i's valuation function which is privately determined by a single parameter and zi is an environmentspecific type which is independent of vi and ∅ ⪯ z′i ⪯ zi for any z′i ∈ Zi, where Zi is the misreport space of zi and ⪯ represents a partial order. For example, the wellknown online mechanism design with no-early arrivals and no-late departures [Nisan et al., 2007] essentially has similar underlying structures as diffusion auctions.