# incentivecompatible_diffusion_auctions__2c79ac87.pdf

Incentive-Compatible Diffusion Auctions

Bin Li1 , Dong Hao1 , Dengji Zhao2

1School of Computer Science & Engineering, University of Electronic Science and Technology of China 2Shanghai Engineering Research Center of Intelligent Vision and Imaging, Shanghai Tech University {libin@std.uestc, haodong@uestc, zhaodj@shanghaitech}.edu.cn

Diffusion auction is a new model in auction design. It can incentivize the buyers who have already joined in the auction to further diffuse the sale information to others via social relations, whereby both the seller s revenue and the social welfare can be improved. Diffusion auctions are essentially nontypical multidimensional mechanism design problems and agents social relations are complicatedly involved with their bids. In such auctions, incentive-compatibility (IC) means it is best for every agent to honestly report her valuation and fully diffuse the sale information to all her neighbors. Existing work identiﬁed some speciﬁc mechanisms for diffusion auctions, while a general theory characterizing all incentive-compatible diffusion auctions is still missing. In this work, we identify a sufﬁcient and necessary condition for all dominant-strategy incentive-compatible (DSIC) diffusion auctions. We formulate the monotonic allocation policies in such multidimensional problems and show that any monotonic allocation policy can be implemented in a DSIC diffusion auction mechanism. Moreover, given any monotonic allocation policy, we obtain the optimal payment policy to maximize the seller s revenue.

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 inefﬁcient allocation. For instance, suppose a seller is selling an item on e Bay. 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 efﬁcient but guarantees the seller s revenue. In some particular economic networks, efﬁciency and revenue could both be guaranteed by a natural market model called customer sharing mechanism [Li et al., 2018]. [Li et al., 2019] further identiﬁed 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 speciﬁc 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 sufﬁcient 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

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

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 sufﬁce 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 efﬁciency. For convenience, we deﬁne 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 proﬁle of all buyers and t i = (t1, t2, , ti 1, ti+1, , tn) denote the type proﬁle of all buyers except i, i.e., t = (ti, t i). Let T = Ti N s be the type proﬁle 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 proﬁle 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 proﬁles. Deﬁnition 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 proﬁle 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, P 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 proﬁle t, the social welfare is deﬁne as W(π, t) = P i N s πi(t)vi. An allocation policy π is efﬁcient if for all t T it always maximizes W(π , t). Deﬁnition 2. An allocation π is efﬁcient if for all t T, π arg maxπ ΠW(π , t). Given buyer i with truthful type ti = (vi, ri), a reported type proﬁle t and a mechanism (π, x), the quasilinear utility of i is deﬁned 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. Deﬁnition 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 deﬁne 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. Deﬁnition 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 proﬁle 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 proﬁle t and

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

a diffusion auction mechanism M = (π, x), the seller s revenue generated by M is deﬁned as the sum of all buyers payments Rev M(t ) = P i N s xi(t ).

Deﬁnition 5. A diffusion auction mechanism M = (π, x) is (weakly) budget balanced if for all t T, Rev M(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 ﬁll 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 deﬁned 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. Deﬁne the critical bid in diffusion auctions as follows.

Deﬁnition 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 identiﬁed 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 deﬁnition 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 speciﬁc buyer i. In the following deﬁnitions 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 sufﬁcient for any diffusion auction to be IC. We ﬁrst extend the traditional value-monotonicity into diffusion auctions. Deﬁnition 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 ﬁxed as r i and all the other buyers reports are ﬁxed 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 t1 i = (v1 i , ri) and t2 i = (v2 i , ri) by xi(t1 i ) and xi(t2 i ), respectively. Recall that xi is i s payment for winning and xi is her payment for losing. If v1 i xi(t1 i ) xi(t2 i ), then buyer i with losing type t2 i should misreport t1 i since v2 i xi(t1 i ) > v1 i xi(t1 i ) xi(t2 i ); similarly, if v1 i xi(t1 i ) < xi(t2 i ), then buyer i with winning type t1 i should misreport t2 i to lose. Since there always exists a beneﬁcial deviation, then the diffusion auction cannot be IC and the assumption is false.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

We next extend the traditional value-independent payment into diffusion auctions based on the payment-decoupling in Proposition 1. Deﬁnition 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 t1 i = (v1 i , ri) and t2 i = (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 t1 i would misreport t2 i when xi(v1 i , ri) > xi(v2 i , ri), and buyer i with t2 i should misreport t1 i 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. Deﬁnition 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 sufﬁcient condition for IC diffusion auctions.

Theorem 2. A diffusion auction (π, x) is incentivecompatible if and only if for all type proﬁle t and all i, P1-P4 are satisﬁed, 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 satisﬁes P1-P4, then it is IC. The proof includes two steps. The ﬁrst 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 ﬁrst 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 beneﬁcial. 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 sufﬁcient condition for a mechanism to be IC.

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

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

Theorem 3. An incentive-compatible diffusion auction is individually rational if and only if for all buyer i and all type proﬁle t, property P5: xi( ) 0 is satisﬁed.

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 difﬁcult 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, deﬁne 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 . Deﬁnition 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 deﬁnition is an extension of value-monotonicity in Deﬁnition 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 proﬁle t i and any buyer i with (vi, ri), P1-P5 hold. Given any monotonic allocation policy, P1 is directly met according to the deﬁnitions. 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 f i(v i (ri)) are nonincreasing in v i (ri), and fi(v i (ri)) f i(v i (ri)) = v i (ri). This construction for x and x satisﬁes P2-P4. A possible choice is fi(v i (ri)) = αv i (ri) and f i(v i (ri)) = (1 + α)v i (ri), where α could be any nonnegative value. Setting hi(t i) = (1 + α)v i ( ), P5 is also satisﬁed. 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 f i need not be linear in v i (ri), they can be any polynomials with negative coefﬁcients. In the following we select payment policies with respect to the seller s revenue. Deﬁnition 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 proﬁle t, Rev(π,x1)(t) Rev(π,x2)(t). If there exists a payment policy x such that for any type proﬁle 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 proﬁle t and a monotonic allocation policy π, the seller s revenue can be expressed as

Rev(t) = xw(rw) + X

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) + P 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

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

ﬁnd x = arg maxx P 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) P i N s xi(ri) becomes solving |N| 1 independent maximization subproblems:

max ( xi,xi) xi(ri)

s.t. v i = v i , r i ri,

xi(v i, ri) = xi(v i , ri), (1) xi(ri) = xi(ri) + v i (ri), (2)

xi(ri) + v i (ri) xi(r i) + v i (r i), (3) xi( ) 0. (4)

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

xi(ri) xi( ) + v i ( ) v i (ri).

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 ﬁnding is that

xi(ri) = v i ( ) v i (ri)

and xi(ri) = xi(ri) + v i (ri) = v i ( ) 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 satisﬁed. Since v i (ri) is independent of v i and is also nondecreasing in ri, constraints (1) and (3) are satisﬁed. 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 difﬁcult 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 efﬁcient 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 deﬁcit. We emphasize that the payment policy in the VCG mechanism also satisﬁes the optimality in Theorem 4. Then we know that if the allocation policy is efﬁcient, then any IR, IC diffusion auction is not weakly budget-balanced.

Proposition 3. There exists no IR and IC diffusion auction which is efﬁcient and (weakly) budget-balanced. Before proving this proposition, we ﬁrst show that the payment policy of the VCG mechanism follows Theorem 4. Lemma 6. In the VCG mechanism, each buyer s payment satisﬁes 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

xvcg i (t) = W(π , t \ {ti}) (W(π , t) π i (t)vi),

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, xvcg i = W(π , t \ {ti}) = v i ( ) and

xvcg i = W(π , t \ {ti}) W(π , t) = v i ( ) v i (ri).

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 efﬁcient and [Li et al., 2017] shows that the VCG mechanism is not budget balanced, Proposition 3 is true.

5 Conclusions In this paper, we characterize a sufﬁcient 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 efﬁciency 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 deﬁned by two parameters vi and zi. vi is i s valuation function which is privately determined by a single parameter and zi is an environmentspeciﬁc 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.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

[Andelman et al., 2007] Nir Andelman, Yossi Azar, and Motti Sorani. Truthful approximation mechanisms for scheduling selﬁsh related machines. Theory of Computing Systems, 40(4):423 436, 2007.

[Archer and Tardos, 2001] Aaron Archer and Eva Tardos. Truthful mechanisms for one-parameter agents. In FOCS, pages 482 491, 2001.

[Auletta et al., 2004] Vincenzo Auletta, Roberto De Prisco, Paolo Penna, and Giuseppe Persiano. Deterministic truthful approximation mechanisms for scheduling related machines. In STACS, pages 608 619, 2004.

[Bikhchandani et al., 2006] Sushil Bikhchandani, Shurojit Chatterji, Ron Lavi, Ahuva Mu alem, Noam Nisan, and Arunava Sen. Weak monotonicity characterizes deterministic dominant-strategy implementation. Econometrica, 74(4):1109 1132, 2006.

[Briest et al., 2005] Patrick Briest, Piotr Krysta, and Berthold V ocking. Approximation techniques for utilitarian mechanism design. In STOC, pages 39 48, 2005.

[Clarke, 1971] Edward H. Clarke. Multipart pricing of public goods. Public Choice, 11(1):17 33, 1971.

[Groves, 1973] Theodore Groves. Incentives in teams. Econometrica, 41(4):617 631, 1973.

[Jeong and Lee, 2020] Seungwon Eugene Jeong and Joosung Lee. The groupwise-pivotal referral mechanism: Core-selecting referral strategy-proof mechanism. SSRN preprint, 2020.

[Kawasaki et al., 2020] Takehiro Kawasaki, Nathanael Barrot, Seiji Takanashi, Taiki Todo, and Makoto Yokoo. Strategy-proof and non-wasteful multi-unit auction via social network. In AAAI, 2020.

[Kov acs, 2005] Annam aria Kov acs. Fast monotone 3approximation algorithm for scheduling related machines. In ESA, pages 616 627, 2005.

[Lavi et al., 2003] Ron Lavi, Ahuva Mu Alem, and Noam Nisan. Towards a characterization of truthful combinatorial auctions. In FOCS, pages 574 583, 2003.

[Lehmann et al., 2002] Daniel Lehmann, Liadan Ita O callaghan, and Yoav Shoham. Truth revelation in approximately efﬁcient combinatorial auctions. Journal of the ACM, 49(5):577 602, 2002.

[Li et al., 2017] Bin Li, Dong Hao, Dengji Zhao, and Tao Zhou. Mechanism design in social networks. In AAAI, pages 586 592, 2017.

[Li et al., 2018] Bin Li, Dong Hao, Dengji Zhao, and Tao Zhou. Customer sharing in economic networks with costs. In IJCAI, pages 368 374, 2018.

[Li et al., 2019] Bin Li, Dong Hao, Dengji Zhao, and Makoto Yokoo. Diffusion and auction on graphs. In IJCAI, pages 435 441, 2019.

[Mu Alem and Nisan, 2008] Ahuva Mu Alem and Noam Nisan. Truthful approximation mechanisms for restricted combinatorial auctions. Games and Economic Behavior, 64(2):612 631, 2008. [Myerson, 1979] Roger B. Myerson. Incentive compatibility and the bargaining problem. Econometrica, 47(1):61 73, 1979. [Myerson, 1981] Roger B. Myerson. Optimal auction design. Mathematics of Operations Research, 6:58 73, 1981. [Nisan et al., 2007] Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V Vazirani. Algorithmic game theory, volume 16. Cambridge University Press, 2007. [Roberts, 1979] Kevin Roberts. The characterization of implementable choice rules. Aggregation and Revelation of Preferences, 12(2):321 348, 1979. [Rochet, 1987] Jean-Charles Rochet. A necessary and sufﬁcient condition for rationalizability in a quasi-linear context. Journal of Mathematical Economics, 16(2):191 200, 1987. [Shmoys and Tardos, 1993] David B Shmoys and Eva Tardos. An approximation algorithm for the generalized assignment problem. Mathematical Programming, 62(3):461 474, 1993. [Vickrey, 1961] William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of Finance, 16(1):8 37, 1961. [Zhao et al., 2018] Dengji Zhao, Bin Li, Junping Xu, Dong Hao, and Nicholas R. Jennings. Selling multiple items via social networks. In AAMAS, pages 68 76, 2018.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)