Incentive-Compatible Diffusion Combinatorial Auctions

1 Introduction

Diffusion auctions are an emerging class of auctions that aim to incentivize information sharing through social networks. In the seminal work of [Li et al., 2017], the authors modeled all bidders as nodes in a social network, each of which has access to and possesses a segment of network information-namely, their neighbors. The authors proposed a novel mechanism called the information diffusion mechanism, which incentivizes information propagation and increases both the seller's revenue and the allocation efficiency compared to the traditional Vickrey auction [Vickrey, 1961]. After this work, there are many follow-up papers that study diffusion mechanisms from different perspectives. For example, Zhao et al. [Zhao et al., 2018] and Kawasaki et al. [Kawasaki et al., 2020] extended diffusion auctions to the multi-unit unit-demand setting and Li et al. [Li et al., 2019;

∗Corresponding Author.

Li et al., 2018; Li et al., 2023] studied diffusion auction design with transaction costs. Besides the above extensions, several studies have investigated other aspects of diffusion auctions, including theoretical characterizations [Li et al., 2020], fairness [Zhang et al., 2020b; Zhang et al., 2020a], collusion [Jeong and Lee, 2024], and privacy preservation [Hu et al., 2021]. For an overview, see [Zhao, 2021; Guo and Hao, 2021].

In diffusion auction models, buyers can influence the final outcome by strategically disclosing their private information, including their values and neighbors. Prior research on diffusion auctions has predominantly concentrated on the simple single-parameter domain [Archer and Tardos, 2001; Li et al., 2020], where each buyer's valuation function can be fully characterized by a single private parameter. Both singleitem diffusion auctions and multi-unit unit-demand diffusion auctions fall into this domain. In contrast to the extensive studies on the single-parameter domain, the combinatorial auction domain [Bikhchandani et al., 2006; Lavi et al., 2003], where buyers can assign different values to different bundles of items, has received considerably less attention in the diffusion auction literature. The complex interdependencies between allocations and network structures render the analysis of diffusion combinatorial auctions highly challenging. In particular, in diffusion combinatorial auctions, bidders can engage in both competitive and cooperative behaviors over different bundles through strategic information disclosure, a phenomenon that does not arise in the single-parameter domain. To date, the only work on diffusion combinatorial auctions is [Fang et al., 2024], which introduces a framework for extending traditional combinatorial auctions to the diffusion auction setting. However, a general theoretical foundation for diffusion combinatorial auctions remains largely unexplored.

In this paper, we provide a complete characterization of implementable diffusion auctions within the combinatorial domain. Building on the characterization, we introduce a novel concept, termed invitation-critical monotonicity, and further identify a family of implementable allocation policies for which the corresponding optimal payment policies, namely those maximizing the seller's revenue, can be derived in closed form. As a by-product, we demonstrate that the VCG payment policy is optimal within the combinatorial auction domain. This is not the case for the single-parameter domain, as discussed in [Guo et al., 2025]. In addition, we leverage the established theory to design a practical diffusion combinatorial auction, called the Exhausted-Reference Pricing Mechanism, which can elicit buyers' true information and guarantee the seller's revenue.

The remainder of the paper is organized as follows. Section 2 formulates the basic model of diffusion combinatorial auctions. Section 3 provides a complete characterization of diffusion combinatorial auctions. In Section 4, we introduce a class of implementable allocation policies and derive the optimal payment policies for such allocations. Section 5 demonstrates a practical combinatorial auction mechanism, and the last section summarizes this work.

2 Preliminaries

We begin with a formal definition of the diffusion combinatorial auction model. Consider that a seller s sells a set M of items in a social network G = (N ∪ s, E), where N ∪ s is the node set and E is the edge set. Besides the seller s, G consists of a set of buyers N = {1, 2, · · · , n}. For each agent i ∈ N ∪ s, she has a set of neighbors ri ⊆ N \ {i}, to whom i can share the sale information. For each item bundle a ⊆ M and buyer i, we use vi(a) to denote i's valuation for receiving a. In this work, we focus on the combinatorial auction domain [Lavi et al., 2003], in which i's valuation function vi satisfies normalization (vi(∅) = 0) and free disposal (vi(a) ≤ vi(b) for any a ⊆ b ⊆ M). In our model, both ri and vi are private information of buyer i.

For convenience, let θi = (vi, ri) be i's private type and θ = (θi)i∈N be the type profile of all buyers. In addition, we use θ-i = θ \ {θi} to denote the type profile without i, i.e., θ = (θi, θ-i). The auction mechanism asks each buyer i to report her true type θi. Accordingly, let θ′i = (v′i , r′i ) be i's report, where v′i represents the valuation function she submits and r′i denotes the neighbor set she shares the auction information to. In a social network setting, buyer i is not aware of other buyers who are not her neighbors, and thereby the misreport space of r′i is limited to P(ri), where P(ri) is the power set of ri. In a similar way, let θ′ = (θ′i )i∈N be the reported type profile of all buyers, θ′-i be the reported type profile of all buyers except i, and we also use θ′ = (θ′i , θ′-i).

One key feature of diffusion auctions is that only buyers receiving the sale information can participate in and further share the sale. Although the set of actual bidders would change with the reported type profile, previous works [Kawasaki et al., 2020; Li et al., 2022] proved that the revelation principle holds in diffusion auctions. Therefore, we can focus on direct auction mechanisms. Before defining the direct version of diffusion combinatorial auctions, we next introduce a crucial concept called valid buyers.

Definition 1. Given a reported type profile θ′ , we say i is a valid buyer if there exists a set of buyers {aj}kj=1 with a1 ∈ rs, aj ∈ r′aj-1 for 1 < j ≤ k, and i ∈ r′ak .

That is, buyer i is valid if there is an "invitation chain" from the seller to i in the reported type profile, and i is invalid if such a chain does not exist. Given a reported type profile θ′ , let F(θ′ ) denote all valid buyers. We next formally define diffusion combinatorial auctions based on valid buyers.

Definition 2. A (direct) diffusion combinatorial auction mechanism M = (f, p) consists of an allocation policy f = {fi : Θ → P(M)}i∈N and a payment policy p = {pi : Θ→R}i∈N, and for all reported type profile θ′ , f and p satisfy the following constraints:

1) fi(θ′ ) = ∅, pi(θ′ ) = 0, ∀i /∈ F(θ′ ); 2) f(θ′ ) and p(θ′ ) are independent of (θ′i )N\F(θ′ ); 3) fi(θ′ ) ∩ fj(θ′ ) = ∅, ∀i ̸= j ∈ F(θ′ ).

In a (direct) diffusion combinatorial auction, we ask all buyers to directly submit their types to the seller; after receiving all reports, the seller executes a mechanism based on all valid buyers' reports. We emphasize that 1) an invalid buyer cannot become valid by misreporting, and 2) the auction is defined on all valid buyers' reports. Therefore, even if all buyers reported in the model, only the valid buyers are activated, and only their reports determine the auction outcome.

Given buyer i with type θi = (vi, ri), a reported type profile θ′ and an auctionM = (f, p), the utility of i is quasilinear and defined by ui(θi, θ′ ,M) = vi(fi(θ′ )) - pi(θ′ ). Next, we introduce two properties that a mechanism should possess. The first property is individual rationality, which requires the utility of any buyer to be non-negative when truthfully reporting her valuation function.

Definition 3 (Individual Rationality). An auctionM is individually rational (IR) if ui(θi, ((vi, r′i ), θ′-i ),M) ≥ 0 for all buyer i ∈ N, all θ′-i , and all r′i ⊆ ri.

The IR property ensures that buyers have no incentive to withdraw from the auction. Another desired property is incentive compatibility.

Definition 4 (Incentive Compatibility). An auction M is incentive compatible (IC) if ui(θi, (θi, θ′-i ),M) ≥ ui(θi, (θ′i , θ′-i ),M) for all buyer i, all θ′i , and all θ′-i .

In other words, IC requires that truthfully reporting the valuation function and sharing the sale information to all neighbors is a dominant strategy for all buyers. As the revelation principle holds in diffusion auctions, we can restrict our attention to IC and IR auctions w.l.o.g.

Next, we present two properties that M should satisfy from the perspective of the seller. Given a type profile θ, the social welfare achieved inM= (f, p), denoted by SW f (θ), is defined by the total utilities of all participants (including the seller), which can be simplified as ∑i∈N vi (fi(θ)) in the auction realm. We sayM is efficient if it maximizes the social welfare for all type profiles, and we call the associated allocation policy the efficient allocation policy.

Definition 5 (Efficiency). An auctionM is efficient if M ∈ argmaxM′=(f ′ ,p′ ) SW f ′ (θ) for all θ.

Besides the allocation efficiency, another desiderata of the seller is revenue. Given a type profile θ and an auctionM, the seller's revenue, denoted by RevM(θ), is the total payments of all buyers ∑i∈N pi(θ). The least requirement for revenue is weak budget balance which asks that RevM(θ) ≥ 0 for all θ. An auction that is weak budget balance does not require an injection of funds from the seller.

Definition 6 (Weak Budget Balance). An auction M is weakly budget balanced (WBB) if RevM(θ) ≥ 0 for all θ.

Previous research on diffusion auctions has focused primarily on the single-parameter domain. In particular, Li et al. [Li et al., 2020] provided a characterization of IC and IR diffusion auctions for this domain. This characterization, however, does not extend directly to the combinatorial auction domain, due to the substantially more complex structure of bidders' valuation functions. In the subsequent sections, we introduce new techniques to bridge this theoretical gap.

3 Characterizations of IC and IRDiffusion Combinatorial Auctions

This section explores the theoretical foundations of diffusion combinatorial auctions. We begin by identifying several necessary conditions that an IC diffusion combinatorial auction should satisfy. Then, we show that these conditions are also sufficient for an auction to be IC.

In single-parameter auction domains, value monotonicity is a necessary condition for an auction to be IC, both in traditional auctions [Archer and Tardos, 2001] and in diffusion auctions [Li et al., 2020]. This condition requires that with others' bids fixed, the allocation to any buyer weakly improves with her own bid. The condition is well-defined in single-parameter domains because the set of feasible allocations for each buyer can be partitioned into two linearly ordered classes. In contrast, in combinatorial auction domains, buyers may assign heterogeneous values over different item bundles, leading to a rich set of allocations that are generally not comparable in a total order. To deal with this issue, a more general condition, termed weak monotonicity, is proposed [Bikhchandani et al., 2006]. Next, we present the weak monotonicity within the diffusion auction environment and demonstrate that the allocation policy of any IC diffusion combinatorial auction should be weakly monotonic.

Definition 7 (Weak Monotonicity). An allocation policy f is weakly monotonic if v′′ i (b) - v′′ i (a) ≥ v′i (b) - v′i (a) for all buyer i, all θ′-i , and any i's two reports (v′i , r′i ), (v′′ i , r′i ) such that fi((v′i , r′i ), θ′-i ) = a and fi((v′′ i , r′i ), θ′-i ) = b.

Intuitively, the weak monotonicity condition requires that, for a fixed invitation set, if a buyer modifies her valuation report to shift the allocation to her from bundle a to b, then the incremental valuation of bundle b relative to bundle a must weakly increase. To distinguish this concept in diffusion combinatorial auctions from its classical counterpart, we adopt the shorthand notation WMon-D to denote it in the diffusion auction environment. Lemma 1 shows that WMon-D is necessary for any IC diffusion combinatorial auction.

Lemma 1. If an auction (f, p) is IC, then f is WMon-D.

Proof. Fix a buyer i and θ-i. Let θ1 i = (v1 i , ri) and θ2 i = (v2 i , ri) be two types of i such that fi(θ1 i , θ-i) = a and fi(θ2 i , θ-i) = b respectively. IC requires that v1 i (a) - pi(θ1 i , θ-i) ≥ v1 i (b) - pi(θ2 i , θ-i) and v2 i (b) - pi(θ2 i , θ-i) ≥ v2 i (a) - pi(θ1 i , θ-i). Adding these inequalities and rearranging the terms yields v2 i (b) - v2 i (a) ≥ v1 i (b) - v1 i (a), which completes the proof.

An allocation policy f is said to be implementable if there exists a payment policy p such that the induced mechanism (f, p) is incentive compatible. Previous work [Lavi et al., 2003] proved that weak monotonicity is sufficient for any (non-diffusion) combinatorial auction to be implemented. However, in diffusion auction settings, buyers are able to manipulate their invitations so as to include or exclude other buyers from the valid buyer set. This feature implies that the weak monotonicity condition alone is insufficient to characterize the implementability-a similar phenomenon has been observed in single-parameter diffusion auction domains [Li et al., 2020]. Consequently, additional restrictions on the payment policy are required to achieve incentive compatibility. In what follows, we identify three fundamental properties of the payment policy, beginning with bid-independence.

Definition 8 (Bid-Independence). A payment policy p is bidindependent if pi((v′i , r′i ), θ′-i ) = pi((v′′ i , r′i ), θ′-i ) for all buyer i, all θ′-i , and any i's two reports (v′i , r′i ), (v′′ i , r′i ) such that fi((v′i , r′i ), θ′-i ) = fi((v′′ i , r′i ), θ′-i ).

The bid-independence property requires that each buyer's payment is determined exclusively by the allocation she receives and the invitation set she reports. That is, there exists a unique payment associated with each allocation, with r′i and others' reports θ′-i fixed. In subsequent sections, we will demonstrate that any IC diffusion combinatorial auction must be bid-independent.

Another desirable property of the payment policy is bidcriticality, which imposes a bound on the payment differentials over any two allocations. Given a buyer i and θ′-i , the critical valuation difference between two allocations a, b, denoted by δab(r′i , θ′-i ), is defined by infv′i {v′i (a) - v′i (b) | fi((v′i , r′i ), θ′-i ) = a}. Note that δaa(r′i , θ′-i ) = 0 for all allocations a. With a slight abuse of notation, we use δab(r′i ) to denote the critical valuation difference between a and b, and pi(a, r′i ) to denote the payment of buyer i, where θ′-i is omitted whenever it is clear from the context. The bid-criticality property requires that for a fixed invitation set, the differences of i's payment over any two allocations is bounded by the corresponding critical valuation difference.

Definition 9 (Bid-Criticality). A payment policy p is bidcritical if pi(a, r′i ) - pi(b, r′i ) ≤ δab(r′i ) for all buyer i, all θ′-i , all r′i , and any two allocations a, b.

In order to incentivize information diffusion, each buyer's utility should be non-increasing with the number of neighbors she shares the sale information to. Equivalently, for any fixed allocation a to buyer i, her payment is non-increasing with r′i . We formalize this requirement via the notion of invitational-monotonicity, which constitutes the last desired property of the payment policy.

Definition 10 (Invitational-Monotonicity). A payment policy p is invitational-monotonic if pi(a, r′′ i ) ≥ pi(a, r′i ) for all buyer i, all θ′-i , all allocation a, and any r′′ i ⊆ r′i ⊆ ri.

Next, we prove that the above three properties imposed on the payment policy above are necessary for any IC diffusion combinatorial auction.

Lemma 2. If an auction (f, p) is IC, then p is bidindependent, bid-critical, and invitational-monotonic.

Proof. Fixing a buyer i and θ-i, we verify the three properties sequentially.

Bid-independence: Let θ1 i = (v1 i , ri) and θ2 i = (v2 i , ri) be any two types with fi(θ1 i , θ-i) = fi(θ2 i , θ-i) = a. IC requires that v1 i (a) - pi(θ1 i , θ-i) ≥ v1 i (a) - pi(θ2 i , θ-i) and v2 i (a)-pi(θ2 i , θ-i) ≥ v2 i (a)-pi(θ1 i , θ-i), which simplify to pi(θ1 i , θ-i) = pi(θ2 i , θ-i). For notational convenience, in the following proofs we denote buyer i's payment under allocation a and ri by pi(a, ri).

Bid-criticality: Let a = fi((v1 i , ri), θ-i) and b be any allocation that buyer i may achieve via misreporting. By IC, for all possible v1 i with a = fi((v1 i , ri), θ-i), we have v1 i (a) - pi(a, ri) ≥ v1 i (b) - pi(b, ri), yielding pi(a, ri) - pi(b, ri) ≤ v1 i (a) - v1 i (b) ⇒ pi(a, ri) - pi(b, ri) ≤ inf v1 i {v1 i (a) - v1 i (b)} = δab(ri). Hence, the inequality pi(a, ri) - pi(b, ri) ≤ δab(ri) must hold for all IC auctions. Invitational-monotonicity: Take any two types θ1 i , θ2 i with r1 i ⊆ r2 i and fi(θ1 i , θ-i) = fi(θ2 i , θ-i) = a. Suppose, for contradiction, that pi(a, r1 i ) < pi(a, r2 i ). Then, for a buyer whose true type is θ2 i , reporting θ1 i yields a strictly higher payoff since v2 i (a) - pi(a, r2 i ) < v2 i (a) - pi(a, r1 i ), which violates the IC condition. Hence, any IC diffusion auction must satisfy pi(a, r1 i ) ≥ pi(a, r2 i ) whenever r1 i ⊆ r2 i and the allocation is the same a.

Lemma 1 and Lemma 2 specify the necessary properties that an IC auction must satisfy. The following theorem demonstrates that these properties together are also sufficient for an auction to be IC.

Theorem 1. An auction (f, p) is IC if and only if 1) f is weakly monotonic; and 2) p is bid-independent, bid-critical and invitational-monotonic.

Proof. In light of Lemma 1 and Lemma 2, we only need to establish the sufficiency. Fix any θ′-i and any buyer i whose true type is θi. Suppose fi(θi, θ′-i ) = a. We first show that any deviation that changes the allocation to i is unprofitable. Consider a misreport θ′i such that fi(θ′i , θ′-i ) = b, then by bid-independence and invitational-monotonicity, we have pi(b, ri) ≤ pi(b, r′i ). Consequently, pi(a, ri) - pi(b, r′i ) ≤ pi(a, ri) - pi(b, ri). By weak monotonicity and bid-criticality, pi(a, ri) - pi(b, ri) ≤ δab(ri) ≤ vi(a) - vi(b) where the last inequality follows from the definition of δab. Therefore, pi(a, ri) - pi(b, r′i ) ≤ vi(a) - vi(b), which is equivalent to vi(a) - pi(a, ri) ≥ vi(b) - pi(b, r′i ). Thus, the deviation does not increase the buyer's payoff. Now, for any fixed allocation a, the invitational-monotonicity implies that buyer i maximizes her utility by reporting truthfully. This completes the proof.

In addition to incentive compatibility, a practical auction should also satisfy individual rationality. This property requires the utility of any buyer be non-negative when reporting her true valuation function. The following result demonstrates that individual rationality can be achieved by imposing an additional constraint on the payment policy.

Theorem 2. An IC auction (f, p) is IR if and only if pi(∅, ∅) ≤ 0 for all i and all type profile θ.

Proof. Given an IC auction (f, p), the utility of any buyer i can be denoted by vi(a) - pi(a, ri). By Definition 3, IR

is equivalent to mina,ri {vi(a) - pi(a, ri)} ≥ 0. By bidcriticality, pi(a, ri) - pi(∅, ri) ≤ δa∅(ri) ≤ vi(a) - 0, which rearranges to vi(a) - pi(a, ri) ≥ -pi(∅, ri). By invitational-monotonicity, -pi(∅, ri) ≥ -pi(∅, ∅). Consequently, vi(a) - pi(a, ri) ≥ -pi(∅, ∅), where the equity is achieved for buyers of type (null, ∅). Therefore, the IR condition is equivalent to pi(∅, ∅) ≤ 0 for all i and θ.

Theorems 1 and 2 fully characterize IC and IR diffusion combinatorial auctions, extending the single-parameter characterization of [Li et al., 2020]. Nevertheless, these results are conceptual and do not provide explicit allocation or payment policies. Next, we introduce a class of allocations that admit a closed-form revenue-maximizing payment policy.

4 Invitation-Critical Monotonicity

For single-parameter domains, prior work has identified two classes of implementable allocation policies, i.e., the invitation-depressed monotonic (ID-Mon) allocations [Li et al., 2020] and the invitation-promoted monotonic (IP-Mon) allocations [Guo et al., 2025]. A natural question is whether these results extend directly to diffusion combinatorial auctions. Unfortunately, they do not, owing to the complexity of valuation functions and their interplay with network topologies. In this section, we first demonstrate the key limitations of existing work and then introduce a novel class of allocation policies tailored for diffusion combinatorial auctions, whose revenue-optimal payment policies can be achieved in closed form. As a by-product, we show that the VCG payment policy is optimal within the combinatorial auction domain. In contrast, this is not the case for the single-parameter domain, as discussed in [Guo et al., 2025].

4.1 Why Existing Results Fail in Our Setting

In a single-parameter domain, each bidder has a private value that fully describes her preference over auction outcomes. Typically, she either wins the item and receives her value, or loses and gets nothing. Let f sp be an allocation policy within the single-parameter domain and f sp i (θ) = 1 denote the winning case. Then f sp is ID-Mon if f sp i ((v′i , r′i ), θ′-i ) = 1 ⇒ f sp i ((v′i , r′′ i ), θ′-i ) = 1 for all i, θ′-i , r′′ i ⊆ r′i , and is IP-Mon if f sp i ((v′i , r′′ i ), θ′-i ) = 1 ⇒ f sp i ((v′′ i , r′i ), θ′-i ) = 1 for all i, θ′-i , r′′ i ⊆ r′i .

In other words, ID-Mon means that a buyer does not lose allocation by inviting fewer neighbors, whereas IP-Mon means that a buyer does not lose allocation by inviting more neighbors. All existing allocation policies for single-parameter domains can be explained by ID-Mon or IPMon [Guo et al., 2025]. Although ID-Mon and IP-Mon are well-defined and well-studied in single-parameter domains, they do not extend to diffusion combinatorial auctions, as illustrated by the following example.

Consider a scenario with a seller auctioning two items {α, β} to four potential bidders whose social relationships are depicted in Figure 1. Each bidder's valuation function is represented by a triple, indicating the values for α alone, β alone, and the bundle of both items. Consider the common efficient allocation policy, where the seller allocates the items to maximize the social welfare. If buyer A invites only C, she is allocated α alone. However, if she invites no neighbors, or invites both C and D, she obtains nothing. Hence, monotonicity is violated in both directions with respect to invitation strategies. This failure arises because buyers in diffusion combinatorial auctions not only compete with each other for the same item but also cooperate to obtain different items. To address this issue, the next section introduces a class of implementable allocation policies for diffusion combinatorial auctions, where the optimal payment policies can be given in closed form.

4.2 IC-Mon Allocations and Optimal Payments

Recall that WMon-D alone is insufficient to characterize implementability. The key reason is that it captures only a necessary condition on valuation functions while ignoring the influences of the invitation structure. To address this shortcoming, we next introduce a complementary property called invitation-critical monotonicity (IC-Mon for short), which is formally defined below.

Definition 11 (Invitation-Critical Monotonicity). Given f , let Afi (θ′-i ) = {fi(θ′i , θ′-i ) | ∀θ′i } be the set of possible allocations for i under θ′-i . We say f is invitation-critical monotonic if for a predetermined item bundle d ⊆ M, for all i, θ′-i , 1). for all r′′ i , r′i with r′′ i ⊂ r′i , and all a ∈ Afi (θ′-i ), there exists v′i such that fi((v′i , r′i ), θ′-i ) = a and fi((v′i , r′′ i ), θ′-i ) = d.

2). for all r′i and all a ∈ Afi (θ′-i ), there exists v′i , v′′ i such that fi((v′i , r′i ), θ′-i ) = a, fi((v′′ i , r′i ), θ′-i ) = d and v′i (d) - v′i (a) = v′′ i (d) - v′′ i (a).

Intuitively, IC-Mon implies that, given f and θ′-i , for any feasible allocation a for i, she can report a valuation function that still secures a. Moreover, if she invites fewer buyers, she receives a predetermined bundle d (specified ex ante). We illustrate this using Figure 1. Let f be the efficient allocation policy, and let the grand bundle M be the predetermined bundle. Given the reported types of others as in Figure 1, it is clear that α ∈ AfA(θ′-A). For r′A = {C}, r′′A = ∅ and a = α, there exists a valuation function v′A = (6, 0, 15) such that fA((v′A, r′A), θ-A) = α and fA((v′A, r′′A), θ-A) = M. We will formally prove later that the efficient allocation policy is indeed invitation-critical monotonic.

We call an allocation policy f satisfying both WMonD and IC-Mon a weak-and-invitation-critical monotonic

(WIC-Mon) allocation policy. Next, we prove that any WIC-Mon allocation policy is implementable. Before presenting our main results, we first introduce two lemmas.

Lemma 3. If f is WMon-D, then 1). δab(r′i ) ≥ -δba(r′i ), and 2). -δba(r′i ) ≤ δMb(r′i ) - δMa(r′i ) ≤ δab(r′i ) hold for all buyer i, θ′-i , r′i , and any two allocations a, b.

Proof. We begin by proving the first part. For any v′i , v′′ i satisfying fi((v′i , r′i ), θ-i) = a, fi((v′′ i , r′i ), θ-i) = b, we have v′i (a) - v′i (b) ≥ v′′ i (a)-v′′ i (b) by WMon-D. Therefore, δab(r′i ) = infv′i {v′i (a) - v′i (b)} ≥ supv′′ i {v′′ i (a) - v′′ i (b)} = -δba(r′i )

We now prove the second part. If a = M or b = M, this lemma is obvious. Otherwise, supposing δMb(r′i ) - δMa(r′i ) > δab(r′i ), we can find v′i such that fi((v′i , r′i ), θ′-i ) = a and δMb(r′i ) - δMa(r′i ) > v′i (a) - v′i (b). By WMon-D, δMa(r′i ) ≥ v′i (M) - v′i (a). Hence, v′i (M) ≤ v′i (a) + δMa(r′i ) < v′i (b) + δMb(r′i ). Choose some small enough ϵ > 0 and some ξ > 0 such that v′i (a) + ϵ + δMa(r′i ) < v′i (M) + ξ < v′i (b) + δMb(r′i ). Define Ti = {d | a ⊆ d and v′i (a) = v′i (d)}. Then we can build v′′ i : v′′ i (x) = v′i (a) + ϵ if x ∈ Ti and x ̸= M; v′′ i (x) = v′i (M) + ξ if x = M; v′′ i (x) = v′i (x) otherwise. Due to a ⊆ d, δMd(r′i ) - δMa(r′i ) ≤ 0 = v′i (a) - v′i (d), yielding b ̸∈ Ti. And we also have v′′ i (d) + δMd(r′i ) ≤ v′′ i (a) + δMa(r′i ) < v′′ i (M) < v′′ i (b) + δMb(r′i ). Hence, for any d ∈ Ti, v′′ i (d) - v′′ i (M) < -δMd(r′i ) ≤ δdM(r′i ); and v′′ i (M)-v′′ i (b) < δMb(r′i ). By the definition of δdM(r′i ) and δMb(r′i ), fi((v′′ i , r′i ), θ-i) ̸= d or M. But by WMonD, since fi((v′i , r′i ), θ-i) = a, it must be the case that fi((v′′ i , r′i ), θ-i) ∈ Ti ∪ {M}, contradiction. Therefore, δMb(r′i ) - δMa(r′i ) ≤ δab(r′i ). If we switch a and b, we have δMb(r′i ) - δMa(r′i ) ≥ -δba(r′i ).

Lemma 4. If f is WIC-Mon, then 1). δda(r′i ) = -δad(r′i ), and 2). δda(r′i ) ≥ δda(r′′ i ) for all buyer i, θ′-i , a, and r′′ i ⊆ r′i .

Proof. By Lemma 3, δda(r′i ) ≥ -δad(r′i ). Now suppose, for contradiction, that δda(r′i ) > -δad(r′i ). Consider any two valuation reports v′i , v′′ i such that satisfying fi((v′i , r′i ), θ-i) = a, fi((v′′ i , r′i ), θ-i) = d. Then by the definition of δda(r′i ) and δad(r′i ), we obtain v′′ i (d) - v′′ i (a) ≥ δda(r′i ) > -δad(r′i ) ≥ v′i (d) - v′i (a), which contradicts IC-Mon. Thus, δda(r′i ) = -δad(r′i ).

We now turn to the proof of part two. Fix a buyer i, θ′-i , and r′′ i ⊆ r′i ⊆ ri. By IC-Mon, there exists v′i such that fi((v′i , r′i ), θ-i) = a and fi((v′i , r′′ i ), θ-i) = d. By WMonD, δda(r′i ) ≥ v′i (d) - v′i (a); by the definition of δda(r′′ i ), v′i (d) - v′i (a) ≥ δda(r′′ i ). Therefore, δda(r′i ) ≥ δda(r′′ i ).

Based on Lemma 3 and Lemma 4, we now prove that any WIC-Mon allocation policy is implementable.

Theorem 3. An auction (f, p) is IC if 1). f is WIC-Mon, and 2). p = (pi(a, ri) = -δda(ri) + h1(ri) + h2(θ-i))i∈N for all allocation a, where h1(ri) is non-increasing in ri.

Proof. Given that the allocation policy f is WIC-Mon and the constructed payment policy is bid-independent, to prove IC, it suffices to show that p is bid-critical and invitationalmonotonic.

Bid-criticality: for any two allocations a, b and invitation set r′i , pi(a, r′i )-pi(b, r′i ) = δdb(r′i )-δda(r′i ). By Lemma 3, -δba(r′i ) ≤ δMb(r′i ) - δMa(r′i ) ≤ δab(r′i ). Note that, when a = d, we have -δbd(r′i ) ≤ δMb(r′i ) - δMd(r′i ) ≤ δdb(r′i ). By Lemma 4, -δbd(r′i ) = δMb(r′i ) - δMd(r′i ) = δdb(r′i ). Similarly, δMa(r′i ) - δMd(r′i ) = δda(r′i ). Thus, δdb(r′i ) - δda(r′i ) = δMb(r′i )-δMa(r′i ). In summary, we have δdb(r′i )- δda(r′i ) ≤ δab(r′i ).

Invitational-monotonicity: for any allocation a and any r′′ i ⊆ r′i , we have δda(r′i ) ≥ δda(r′′ i ) by Lemma 4. Therefore, pi(a, r′i ) ≤ pi(a, r′′ i ).

Theorem 3 identifies a class of IC diffusion combinatorial auctions. However, even when given a WIC-Mon allocation policy, the space of proper payment policies are still be very large due to h1 and h2. Given any two payment polices p1 and p2 , we say p1 dominates p2 in the revenue if for any type profile θ, Rev(f,p1 ) (θ) ≥ Rev(f,p2 ) (θ). If there exists a payment policy p∗ that dominates all the other payment policies under IR and IC conditions, then p∗ is optimal with respect to f. Our next result shows that for any WIC-Mon allocation policy, the optimal payment policy exists.

Theorem 4. If f is WIC-Mon, the optimal payment policy p takes the form (pi(a, ri) = δd∅(∅) - δda(ri))i∈N .

Proof. By Lemma 2, we have pi(d, ri) -pi(a, ri) ≤ δda(ri) and pi(a, ri) - pi(d, ri) ≤ δad(ri), yielding -δad(ri) ≤ pi(d, ri) - pi(a, ri) ≤ δda(ri). Then by Lemma 4, pi(d, ri) - pi(a, ri) = δda(ri) for any allocation a. Hence, pi(d, ri) = δda(ri) + pi(a, ri) = δd∅(ri) + pi(∅, ri). Fixed θ, let W be the set of winners and ai be i's allocation for every i ∈ W. Then we have Rev(f,p) (θ) = ∑i∈W pi(ai, ri) + ∑i∈N\W pi(∅, ri) = ∑i∈W (pi(d, ri) - δdai (ri))+∑i∈N\W (pi(d, ri)-δd∅(ri)) = ∑i∈N pi(d, ri)- (∑i∈W δdai (ri) + ∑i∈N\W δd∅(ri))

For a fixed θ, (∑i∈W δdai (ri) + ∑i∈N\W δd∅(ri)) is also fixed. So we only consider maximizing pi(d, ri).

By Lemma 2 and Theorem 2, pi(d, ri) ≤ pi(d, ∅) = δd∅(∅)+pi(∅, ∅) ≤ δd∅(∅). Therefore, the optimal pi(d, ri) = δd∅(∅), and the optimal pi(a, ri) = δd∅(∅) - δda(ri).

The following corollary follows straightforwardly from the definitions of δ and WBB.

Corollary 1. If f is WIC-Mon with d = ∅, and p = (pi(a, ri) = -δ∅a(ri))i∈N, then (f, p) is IC, IR, and WBB.

As a canonical example illustrating the developed theory, we next show that the allocation policy of the VCG mechanism is WIC-Mon, and that its associated payment policy is optimal with respect to the combinatorial auction domain.

4.3 The Optimality of the VCGMechanism

The VCG mechanism [Vickrey, 1961; Clarke, 1971; Groves, 1973] is a cornerstone of auction theory and has been widely studied across a range of applications, from spectrum auctions to public project procurement. Li et al. [Li et al., 2017; Li et al., 2020] show that VCG extends naturally to the diffusion auction setting, and that its payment policy is optimal for single-item diffusion auctions. However, subsequent work [Guo et al., 2025] shows that VCG payments are no longer optimal in multi-unit single-demand diffusion auctions. Interestingly, we prove that in diffusion combinatorial auction settings, the VCG payment policy is restored to optimality.

We begin by formally defining the VCG mechanism in the context of diffusion auctions. Given any θ′ , apply the efficient allocation policy f ∗ , break tie randomly. Each i's payment pvcg i (θ′ ) is SW f ∗ (θ′-i ) - (SW f ∗ (θ′ ) - vi(f ∗ (θ′ )).

In other words, the VCG mechanism adopts an efficient allocation policy and charges each participant the externality she imposes on others (i.e., the resulting decrease in social welfare of the other bidders). Next, we prove that f ∗ is WIC-Mon, and that the payment pvcg i coincides with the payment defined in Theorem 4.

Theorem 5. The efficient allocation policy f ∗ is WIC-Mon.

Proof. For notational convenience, given a reported type profile θ′-i and buyer i's invitation set r′i , let SW f ∗ -i (a, r′i ) denote the maximum social welfare achievable when the set of items a is allocated among all buyers except i.

Fix a buyer i and θ′-i . The predetermined item bundle is M, and we proceed to verify the three properties sequentially. WMon-D: let (v′i , r′i ) and (v′′ i , r′i ) satisfy f ∗ i ((v′i , r′i ), θ′-i ) = a and f ∗ i ((v′′ i , r′i ), θ′-i ) = b respectively. We have v′i (a)+SW f ∗ -i (M\a, r′i ) ≥ v′i (b)+SW f ∗ -i (M\b, r′i ) and v′′ i (b)+SW f ∗ -i (M \ b, r′i ) ≥ v′′ i (a)+SW f ∗ -i (M \ a, r′i ). Therefore, v′′ i (b) - v′′ i (a) ≥ v′i (b) - v′i (a).

IC-Mon: 1) for any allocation a and r′′ i ⊂ r′i ⊆ ri, we can build a critical v′i : v′i (x) = SW f ∗ -i (M, r′i )-SW f ∗ -i (M \a, r′i ) if a ⊆ x ⊂ M; v′i (x) = max{SW f ∗ -i (M, r′′ i ), v′i (a) + SW f ∗ -i (M \ a, r′′ i )} if x = M; v′i (x) = 0 otherwise. For any allocation b, we have v′i (a) + SW f ∗ -i (M \ a, r′i ) ≥ v′i (b) + SW f ∗ -i (M \ b, r′i ) under r′i , and v′i (M) ≥ v′i (b) + SW f ∗ -i (M \ b, r′′ i ) under r′′ i . Therefore, f ∗ i ((v′i , r′i ), θ′-i ) = a and f ∗ i ((v′i , r′′ i ), θ′-i ) =M.

2) for any allocation a and r′i ⊆ ri, we can build v′i and v′′ i : v′i (x) = SW f ∗ -i (M, r′i ) - SW f ∗ -i (M \ a, r′i ) if a ⊆ x ⊂ M; v′i (x) = SW f ∗ -i (M, r′i ) if x = M; v′i (x) = 0 otherwise. v′′ i (x) = v′i (x) if x = a or M; v′′ i (x) ≤ SW f ∗ -i (M, r′i ) - SW f ∗ -i (M \ x, r′i ) otherwise. For any allocation b, we have v′i (a) + SW f ∗ -i (M \ a, r′i ) ≥ v′i (b) + SW f ∗ -i (M \ b, r′i ), and v′′ i (M) ≥ v′′ i (b) +SW f ∗ -i (M \ b, r′i ). Therefore, f ∗ i ((v′i , r′i ), θ′-i ) = a, f ∗ i ((v′′ i , r′i ), θ′-i ) =M, and v′′ i (M) - v′′ i (a) = v′i (M) - v′i (a)

We now prove that the VCG payment policy is optimal in the diffusion combinatorial auction domain.

Theorem 6. The VCG's payment policy pvcg is optimal with respect to f ∗ .

Proof. By Theorem 4 and Theorem 5, the optimal p∗ is (pi(a, ri) = δM∅(∅) - δMa(ri))i∈N. For any v′i satisfying f ∗ i ((v′i , ri), θ′-i ) = M, we have v′i (M) ≥ v′i (a) +

Algorithm 1 Exhausted-Reference Pricing Mechanism

• 1: Find i∗ = argmini∈rs |R(i)|, where R(i) = {j | there exists an invitation chain from s to j passing through i};
• 2: Initialize the exhausted agent set E = {i∗ } ∪R(i∗ ) and the remaining allocable items M ′ = M;
• 3: Set fi(θ′ ) = ∅, pi(θ′ ) = 0 for each i ∈ E;
• 4: Sort N \ E by BFS, and let O be the resulting order;
• 5: while M ′ ̸= ∅ do
• 6: Iterate over the bidders i in O;
• 7: Compute g(x) =maxj∈E{vj(x)} for each x ⊆M ′ ;
• 8: Set fi(θ′ ) = argmaxx⊆M ′{vi(x) - g(x)};
• 9: Set pi(θ′ ) = g(fi(θ′ ));
• 10: Update M ′ =M ′ \ fi(θ′ ), E = E ∪ {i};

SW f ∗ -i (M \ a, ri) for any allocation a. Hence, v′i (M) - v′i (a) ≥ SW f ∗ -i (M \ a, ri). Then we build v′i that is similar to v′′ i in the proof of Theorem 5, and we have v′i (M) - v′i (a) = SW f ∗ -i (M \ a, ri). So δMa(ri) = inf{v′i (M) - v′i (a)} = SW f ∗ -i (M \ a, ri). Similarly, δM∅(∅) = SW f ∗ -i (M, ∅). Therefore, the optimal p∗ is (pi(a, ri) = SW f ∗ -i (M, ∅) - SW f ∗ -i (M \ a, ri))i∈N. Notice that the implications of SW f ∗ -i (M, ∅) and SW f ∗ (θ′-i ), as well as those of SW f ∗ -i (M \ f ∗ (θ′ ), ri) and SW f ∗ (θ′ ) - vi(f ∗ (θ′ )), are identical. Therefore, pvcg is optimal.

Although the VCG mechanism is efficient and its payment policy is optimal, it does not guarantee WBB. Consider the example in Figure 1. If we run the VCG mechanism, buyer D wins both items and pays 17, while buyer A receives a reward of 20; all other buyers pay nothing. As a result, the seller's revenue is -3. The potential deficit of the VCG mechanism renders it impractical for real-world applications. In the next section, we present a novel diffusion auction, called the Exhausted-Reference Pricing (ERP) mechanism, which we prove to be IC, IR, and WBB.

5 Exhausted-Reference PricingMechanism

The ERP mechanism maintains a dynamic set of "exhausted buyers" who serve as reference price providers. To incentivize diffusion, the process begins by excluding from the allocation the seller's neighbor with the smallest reachable set, along with that neighbor's successors. Thereafter, the remaining buyers sequentially maximize their utility against the prices set by the exhausted group and are then added to the exhausted set. Consequently, a buyer who reduces her invitation set risks being identified as the minimal contributor and thus faces immediate exclusion from the allocation. The details of the ERP mechanism are given in Alg. 1.

We apply the ERP to Figure 1. Initially, R(A) = {C,D}, R(B) = ∅, so E = {B} and B gets and pays nothing. The BFS order of the remaining agents is A, C,D. For A, g takes 1, 2, 15 on α, β, {α, β}, respectively. Thus A wins α and pays 1, and E updates to {A, B}. Then C wins β and pays 2, while D gets and pays nothing. Finally, the seller's revenue is 3.

Based on Theorem 4 and Corollary 1, we now prove that the ERP mechanism satisfies all desired properties.

Theorem 7. The ERP mechanism is IC, IR and WBB.

Proof. First, we show that the ERP allocation policy f is WIC-Mon. Based on whether buyers are in E during the initialization phase, they are divided into two categories: exhausted buyers and non-exhausted buyers. For exhausted buyers, their allocation will only be ∅ regardless of their report type, and thus f obviously satisfies WIC-Mon. Next, we only consider non-exhausted buyers and proceed to verify the three properties sequentially.

WMon-D: Fix a buyer i, θ′-i , and r′i . The order in which i is added to E is fixed, and i cannot change the set E and M ′ when determining her allocation. We only consider the situation when i receives the items. Let (v′i , r′i ) and (v′′ i , r′i ) satisfy fi((v′i , r′i ), θ′-i ) = a and fi((v′′ i , r′i ), θ′-i ) = b respectively. We have v′i (a) - g(a) ≥ v′i (b) - g(b) and v′′ i (b) - g(b) ≥ v′′

i (a) - g(a). Therefore, v′i (a) - v′i (b) ≥ v′′ i (a) - v′′ i (b). IC-Mon: 1) Fix buyer i, θ′-i and r′′ i ⊂ r′i ⊆ ri. For any

feasible allocation a, we can build v′i : v′i (x) = g(a) if a ⊆ x; v′i (x) = 0 otherwise. When i invites r′i , we have v′i (a) - g(a) ≥ v′i (b) - g(b) for any b. Thus fi((v′i , r′i ), θ′-i ) = a. When i invites r′′ i , she may become an exhausted buyer, and fi((v′i , r′′ i ), θ′-i ) = ∅. Otherwise, v′i (∅) - 0 ≥ v′i (b) - g(b) for any b. Thus fi((v′i , r′′ i ), θ′-i ) = ∅.

2) Fix buyer i, θ′-i and r′i ⊆ ri. For any feasible allocation a, we build the same v′i as in 1) and v′′ i : v′′ i (x) = v′i (x) if x = ∅ or a; v′′ i (x) ≤ g(x) otherwise. For any b, we have v′′ i (∅) - 0 ≥ v′′ i (b) - g(b). Thus fi((v′′ i , r′i ), θ′-i ) = ∅ and v′i (a) - v′i (∅) = v′′ i (a) - v′′ i (∅). Therefore, f is WIC-Mon.

Then we show that the ERP payment policy can be implicitly expressed as -δ∅a(ri). For exhausted buyers, their allocations will only be ∅ regardless of their report type, and thus their payments pi(∅, ri) = 0 = -δ∅∅(ri). For a non-exhausted buyer i, if fi((v′i , ri), θ′-i ) = ∅, we have 0 ≥ v′i (a)-g(a) for any allocation a. So 0-v′i (a) ≥ -g(a). And we also use the v′′ i in 2) to show 0 - v′′ i (a) = -g(a). So δ∅a(ri) = -g(a). Therefore, the optimal payment is pi(a, ri) = g(a) = -δ∅a(ri).

6 Conclusions

In this paper, we establish a general theoretical foundation for diffusion combinatorial auctions. Specifically, we provide a complete characterization of implementable diffusion auctions in the combinatorial domain, extending prior results for the single-parameter setting [Li et al., 2020; Guo et al., 2025]. Moreover, we identify a family of implementable allocation policies whose revenue-optimal payment policies can be derived in closed form. Leveraging this theory, we prove that the VCG payment policy is optimal within the combinatorial auction domain. We further design a diffusion combinatorial auction that is guaranteed to be incentive-compatible, individually rational, and weakly budget-balanced. While our primary focus is on theoretical foundations, the developed framework is readily applicable to real-world scenarios, including Internet auctions [Galgana and Golrezaei, 2024] and decentralized ad exchanges [Nassirzadeh et al., 2024].

Acknowledgments

This research was supported by the Shanghai Frontiers Science Center of Human-centered Artificial Intelligence (ShangHAI). Bin Li is supported by the Fundamental Research Funds for the Central Universities (No.30925010514), and the National Natural Science Foundation of China (No. 62202229).