Strategyproofness and Monotone Allocation of Auction in Social Networks

1 Introduction

In recent years, auction design in social networks has received emerging attention from the computer science and artificial intelligence community [Guo and Hao, 2021; Li et al., 2022]. In contrast to canonical auction theory, which concentrates solely on bidders directly reachable by the seller, network auction characterizes the auction environment as large and unfixed, providing the potential to recruit additional participants. Existing works on network auctions mostly focus on devising mechanisms that motivate agents to actively disseminate auction information to their neighbors and invite their neighbours into the auction, thereby expanding the market, improving allocation efficiency, and simultaneously increasing the seller's revenue [Li et al., 2017; Zhao et al., 2018; Kawasaki et al., 2020; Li et al., 2022].

∗Corresponding Author.

Monotone allocation combined with critical value payment capture truthful mechanisms in classic auctions. For onedimensional types, Myerson's lemma [Myerson, 1981] is the guiding principle. Archer and Tardos [2001] further developed a concrete characterization of truthful single-parameter mechanisms based on Myerson's Lemma. Regarding multidimensional bidder types, incentive compatibility becomes more complex. For dominant strategy incentive-compatible (DSIC) and deterministic mechanisms, Robert [1979] proposed the monotonicity termed "Positive Association of Differences" (PAD) and showed that all the DSIC mechanisms are varieties of VCG mechanism [Vickrey, 1961; Clarke, 1971; Groves, 1973] in unrestricted domain with at least three possible outcomes. Rochet [1987] introduced cycle monotonicity in unrestricted domains, which is necessary and sufficient for DSIC. Weak-Monotonicity (W-MON), weaker than cycle monotonicity, was proposed in restricted domains [Lavi et al., 2003; Bikhchandani et al., 2006].

For network auctions, the aforementioned monotonicity concepts are too general and impractical for strategyproofness. This is because the private types of bidders are shaped not only by their valuations but also by their social connections. Agents must take into account invitation behaviors when formulating their bids, and vice versa. The mechanism has to consider the complex preferences of agents over all combinations of bids and network structures, which seems implausible. To date, no principle for allocation rules in strategyproof network auctions has been established. In sharp contrast to single-parameterized canonical auctions, where the value-monotonic allocation in Myerson's Lemma serves as a cornerstone, existing network auction mechanisms can only rely on loosely designed allocation rules based on trial and error. Even extensions to multi-unit network auctions with single-unit demands pose unexpected difficulties. In the following sections, we show that the existing key mechanisms for multi-unit network auctions are not strategyproof.

Although Li et al. [2020] presented an elegant theorem to characterize all strategyproof network auctions, a characterization of monotone allocation in network auction and the effect of monotone allocation on payment and strategyproofness is still missing, which has been a major obstacle for network auctions design. Currently, researchers are extending network auction designs to multi-unit scenarios [Zhao et al., 2018; Kawasaki et al., 2020; Liu et al., 2023; Fang et al., 2023]. Unfortunately, even seemingly straightforward extensions to multi-unit network auctions with singleunit demands present unexpected difficulties, and all existing mechanisms turn out to be non-truthful or inefficient. For example, the first efforts of this line by Zhao et al. [2018] and Kawasaki et al. [2020] are not strategyproof, allowing certain agents to gain by inviting fewer neighbours or even by not inviting at all. LDM [Liu et al., 2023] and MUDAN [Fang et al., 2023] use complex rules to localize bidders' competition to ensure truthfulness, harming efficiency and revenue as side effect. Please refer to Appendix A for detailed related work.

1.1 Our Contributions

We study the theory of strategyproof network auctions, which provides a concise approach to achieving truthfulness and revenue optimization in network auctions. In particularly it is helpful for multi-unit or combinatorial network auctions, where most existing mechanisms fall short.

1. We begin by examining why the Distance-based Network Auction with Multi-Unit (DNA-MU) mechanism [Kawasaki et al., 2020] fails to achieve strategyproofness. We identify the underlying causes of this failure and propose a revised mechanism that restores strategyproofness. Our analysis reveals that merely enforcing value-monotonicity in allocation can complicate or even hinder the payment design.
2. Given any value-monotone allocation, we identify a sufficient condition for the payment rule to be strategyproof in network auctions. We further characterize two categories of monotone allocation rules: Invitation-Depressed Monotonicity (ID-MON) and Invitation-Promoted Monotonicity (IP-MON). Each is grounded in different partial orderings in the bidders' multi-dimensional type space. Both ID-MON and IP-MON are not only value-monotone but also monotone with respect to network structure. Consequently, all existing strategyproof mechanisms with various allocation rules in network auctions can be explained by ID-MON or IP-MON.
3. Building on ID-MON and IP-MON, we formally characterize the revenue-maximizing payment rules that satisfy individual rationality and strategyproofness. These payment rules establish the upper bound on the seller's revenue achievable under any given ID-MON/IP-MON allocation rule.

(4) In sharp contrast to existing multi-unit network auctions, which are burdened by complex payment reasoning, our principles of ID-MON and IP-MON implementability greatly simplify the design of strategyproof network auction. To our knowledge, this is the first work to study a simple and principled framework for designing network combinatorial auction with single-minded bidders.

Results lacking full proofs are proven in the appendix 1 .

2 Preliminaries

2.1 Network AuctionModel

Consider a social network G = (N ∪{s}, E), where N ∪{s} is the set of nodes while E is the set of edges. s is the seller node while agents in N are potential bidders in the network. Denote each agent i's neighbor set by N(i) = {j | (i, j) ∈ E}. Assume that the seller s has a collection of items K (either homogeneous or heterogeneous) to be sold and initially she can only call together her direct neighbors N(s) by herself. In order to expand the market, she can incentivize her neighbors to invite their own friends to join the market. Figure 1 is a social network G = (N ∪ {s},E) where s is the seller and N = {A, B, C, F, D, H} are potential bidders.

1 Full version is available at: https://drive.google.com/file/d/ 1F82cDn2si-cQqorwVMQdOtsiKGGjlPjC/view?usp=drive link

Figure 2 shows an instance of auction information diffusion. It starts from seller s, who invites bidders A and B into the market. After that, bidder B further invites neighbors C and F, then C invites D. Later, bidder D does not invite H, thus H cannot enter the market. Finally, {A, B, C, D, F} are the bidders. We denote G = (N ∪ {s}, E) as a digraph depicting the market with information diffusion.

Each bidder i has private information θi = (vi, ri), where vi is her valuation, consistent with the classical singleparameter environment (e.g., single-item, k-unit with unitdemand, or knapsack auctions, etc), and ri = N(i) is the set of neighbors she can invite to participate in the auction.

Let θ = (θ1, . . . , θn) be the type profile of the bidder set N, and θ-i = (θ1, . . . , θi-1, θi+1, . . . , θn) be the type profile of the other bidders N \ {i}. Define Θ = ×i∈NΘi as the space of the joint type of bidders N, where Θi = R≥0×P(ri) is the type space of bidder i, and P(ri) is the power set of ri. Each bidder i could strategically misreport. Let θ′i = (v′i , r′i ) be the reported type of bidder i, where v′i ∈ R≥0 and r′i ∈ P(ri).

Definition 2.1. A mechanism M = (f, p). Here f is the allocation rule f = (f1, · · · , fn) and p is the payment rule p = (p1, · · · , pn), where fi : Θ→ {0, 1} and pi : Θ→R.

Given any type profile θ′ , we say f is feasible if, for all θ′ ∈ Θ, it holds that the seller s can sell at most |K| items. Let F be the set of all feasible allocations. For a given θ′ ∈ Θ and a mechanismM = (f, p), the social welfare is SW(f, θ′ ) = ∑i∈N fi(θ′ )vi. An allocation f ∗ is efficient if it always allocate goods to bidders who value them the most.

Definition 2.2 (Efficiency (EF)). A network auction mechanism M = (f ∗ , p) is efficient if for all θ′ ∈ Θ, f ∗ = arg maxf∈F SW(f, θ′ ).

For any θ′ ∈ Θ and a mechanismM = (f, p), the seller's revenue is RevM(θ′ ) = ∑i∈N pi(θ′ ). Accordingly, we say that the mechanism M is (weakly) budget balanced if the seller never incurs negative revenue from the auction.

Definition 2.3 (Weakly Budget Balance (WBB)). A network auction mechanismM= (f, p) is (weakly) budget balanced if ∀θ′ ∈ Θ, RevM(θ′ ) ≥ 0.

Given profile θ′ , each bidder i's quasi-linear utility function is ui(θ′ , (f, p)) = fi(θ′ )vi - pi(θ′ ). We simplify it as ui((v′i , r′i ), θ′-i ). Next, we formulate individual rationality and strategyproofness.

Definition 2.4 (Individual Rationality (IR)). A network auction mechanismM= (f, p) is individual rational (IR) if for all θ′ ∈ Θ, for all i ∈ N, r′i ∈ P(ri), ui((vi, r′i ), θ′-i )) ≥ 0.

In network auction scenarios, given any mechanism M, if for each bidder, truthfully disclosing her valuation brings non-negative utility, we call this mechanism satisfies IR. It does not place requirements on bidders' invitation behaviors.

Definition 2.5 (Strategyproofness (SP)). A network auction mechanismM= (f, p) is strategyproof if for all θ′ ∈ Θ, for all i ∈ N, ui((vi, ri), θ′-i ) ≥ ui((v′i , r′i ), θ′-i ).

In network auctions, strategyproofnes requires that, for any buyer, truthfully reporting her valuation and inviting all the neighbors around is the dominant strategy.

Definition 2.6 (Network-Implementable). A network auction's allocation f is network-implementable if there exists a payment p such that M= (f, p) is strategyproof.

Notably, network-implementable allocation is different from implementable allocation in classic auctions. The mapping from allocation to payment takes network structure (i.e., invitational incentive) into consideration.

Definition 2.7 (Degenerated). A network auction mechanism M = (f, p) is degenerated if for any profile θ ∈ Θ, for any bidder i ∈ N, and any invitation strategy r′i ⊆ ri, ui((vi, r′i ), θ′-i ) = ui((vi, ri), θ′-i ).

Intuitively, a network auction mechanism is degenerated if each agent's utility is independent of her invitation actions.

2.2 Strategyproof Network Auctions

In classic auction theory, Myerson's Lemma [Myerson, 1981] presents the formulations for all individual rationality (IR) and strategyproof (SP) mechanisms under single-parameter domains. A normalized mechanism (where losers always pay zero) is considered SP if and only if the allocation is valuemonotone and winners always pay the critical winning bid.

Definition 2.8 (Value-Monotonicity). Given a network auction mechanism M = (f, p) and profile θ′ , for every bidder i, if allocation fi((v′i , r′i ), θ′-i ) = 1 implies that fi((v′′ i , r′i ), θ′-i ) = 1 for any v′′ ≥ v′ , then we say the allocation rule f is value-monotone.

Value-monotonicity depicts that given any r′i and θ′-i , for any bidder i, increasing her bid v′i will never turn herself from a winner to a loser. The characterization of IR and SP in the context of network auctions was initially proposed by Li et al. [2020]. They established a sufficient and necessary conditions for IR and SP in network auctions. Before introducing the theorem, we first provide some essential definitions.

Definition 2.9 (Payment Decomposition). Given a network auction mechanism M = (f, p) and any profile θ′ for any bidder i, her payment pi can be decomposed into the winning payment ˜ pi and the losing payment ¯ pi, such that pi(θ′ ) = fi(θ′ )˜ pi + (1 - fi(θ′ ))¯ pi .

Definition 2.10 (Bid-Independent). Given a network auction mechanismM = (f, p) and profile θ′ , ∀ i ∈ N, v′i ̸= v′′ i , ˜ pi((v′i , r′i ), θ-i) = ˜ pi((v′′ i , r′i ), θ-i) and ¯ pi((v′i , r′i ), θ-i) = ¯ pi((v′′ i , r′i ), θ-i).

Definition 2.11 (Invitational Monotonicity). Given a network auction mechanism M = (f, p), for each bidder i, fixing all other bidders' profile θ′-i and bid vi, if her decomposed winning and losing payments satisfy that for all r′i ⊆ ri, ˜ pi(vi, r′i ) ≥ ˜ pi(vi, ri) ∧ ¯ pi(vi, r′i ) ≥ ¯ pi(vi, ri), then we say payment rule p is invitational-monotone.

Intuitively, invitational-monotonicity of the payment represents that, regardless of being a winner or loser, when fixing a bidder's bid, inviting all the neighbors always minimizes their payment. This property directly incentivizes bidders to truthfully disclose their invitation sets.

Definition 2.12 (Critical Winning Bid). Given M = (f, p), for any bidder i, fixing others' θ′-i , denote v∗ i (r′i ) as the critical winning bid for bidder i when her invitation action is r′i :

The critical winning bid v∗ i (r′i ) is the minimum bid that makes bidder i a winner, given all other bidders' strategies θ′-i and assuming bidder i takes the invitation action r′i .

With the above definitions and decomposition, Li et al. [2020] proved a basic sufficient and necessary condition for all IR & SP network auctions.

Theorem 2.1 (IR & SP Network Auction [Li et al., 2020]). A network single-item auction mechanism M = (f, p) is IR and SP if and only if, for all profiles θ ∈ Θ and all bidders i ∈ N, conditions (1)-(4) are satisfied:

1. The allocation rule f is value-monotone.
2. ˜ pi and ¯ pi are bid-independent and invitational-monotone.

Conditions (1) to (3) are for strategyproofness, while condition (4) is for IR. However, Theorem 2.1 only gives an abstract condition of the payment, it doesn't provide details regarding how to devise the allocation function f or what the explicit form of the payment should be. To address this gap, a more fine-grained and operational characterization of strategyproofness is needed for network auction design.

3 Multi-unit Network Auction

The Vickrey auction [Vickrey, 1961] can be naturally extended to the multi-unit setting with unit-demand bidders in classical auction theory by allocating each unit to the top-k highest bidders and charging each winner the (k+1)-st highest bid. However, this extension becomes substantially more complex in network auctions, which has sparked significant controversy and discussion in the community.

The very first work GIDM by Zhao et al. [2018] tried to extend IDM [Li et al., 2017] into k-unit settings. However, it is not strategyproof under some counterexamples constructed in [Takanashi et al., 2019]. Kawasaki et al. [2020] proposed a new mechanism called DNA-MU to deal with k-unit network auctions with unit demand. Unfortunately, Guo et al. [2024] proved that DNA-MU also fails to be strategyproof for the same example in [Takanashi et al., 2019]. It is surprising that two totally different mechanisms fail to be strategyproof for the same counterexample. Upon encountering these difficulties, subsequent works on multi-unit network auctions either make strong assumptions about agents' information [Liu et al., 2023] or greatly compromise on their design objectives [Fang et al., 2023]. In this section, we will unveil the underlying reason of this failure and fix the DNA-MU mechanism.

3.1 Counterexample of DNA-MUMechanism

We revisit DNA-MU in Algorithm 1. It is based on a key notion, invitational-domination, which is widely used in network auctions.

Definition 3.1 (Invitational-Domination). Given a digraph G = (N ∪ {s},E), for any two bidders i, j ∈ N, i invitationally-dominates j if and only if all the paths from seller s to j must include i.

Intuitively, if bidder A dominates B, then without A's invitation, it is impossible for B to enter the auction market. Merging the invitational-domination relations between every pair of nodes, one can create the invitational-domination tree (IDT) for all informed bidders in G. IDT is a partial ordering of agents regarding their topological importance.

Based on these concepts, we introduce the DNA-MU mechanism, which initially determines a distance-based priority ordering using the classic Breadth-First Search (BFS) algorithm. In this priority ordering, it has been proved that no bidder can improve her priority by misreporting her type. Next, it decides whether to allocate one item to each bidder via a threshold bid vk (N\(Ti∪W)) 2 where k is dynamically updated, Ti is the sub-tree rooted at i in the IDT, containing all the bidders who are invitationally dominated by i, and W is the winner set. See Algorithm 1 for details of DNA-MU.

However, DNA-MU fails to be strategyproof in cases where some losers can invite fewer neighbors to gain an extra benefit. We run DNA-MU for the social network in Figure 1 with two invitation profiles: one where all the bidders fully invite their neighbors (truthful behavior) and the other where bidder D does not invite H (false behavior), as shown in Figure 2. Section 3.1 shows that bidder D is profitable by exhibiting false behavior, making DNA-MU fail to be strategyproof.

Proposition 3.1. In K-unit network auctions, DNA-MU mechanism is not SP when |K| ≥ 3.

Please refer to the appendix for more detailed running procedures and a general proof of Proposition 3.1.

2 vk (N \ (Ti ∪W)) is the k-th bid in bidder set N \ (Ti ∪W).

Algorithm 1 DNA-MU Mechanism

1: Initialize ordering O← BFS(G, s); 2: Create Invitational-Domination Tree (IDT) T; 3: Initialize k ← |K|,W ← ∅; 4: for i in O do 5: Ti ←Sub-Tree rooted by i in T; 6: if vi ≥ vk (N \ (Ti ∪W)) then 7: fi ← 1, pi ← vk (N \ (Ti ∪ W)); 8: Update k ← k -1,W ←W ∪ {i}; 9: end if

Input: G = (N ∪ {s}, E), θ, K; Output: Allocation f, payment p; 10: end for 11: Return f, p.

3.2 Reason and a Correction

The direct reason why DNA-MU fails to be strategyproof is that its payment rule is not invitationally-monotone, contradicting condition (2) in Theorem 2.1. This is easily proved in the following Proposition 3.2.

Proposition 3.2. The payment rule of mechanism DNA-MU is not invitationally-monotone.

Proof. Consider the counterexample in Figure 2. Bidder D has two possible invitation strategies r1D = ∅ and r2D = {H}. Notice that ˜ pD(r1D ) = 6 while ˜ pD(r2D ) = v∗D (r2D ) = +∞ > ˜ pD(r1D ). However, invitational-monotonicity (Definition 2.11) requires ˜ pD(r2D ) ≤ ˜ pD(r1D ) as r1D ⊆ r2D , implying DNA-MU payment fails invitational monotonicity.

We revise both the allocation and payment rules of DNAMU to design a new mechanism, termed DNA-MU-Refined (DNA-MU-R), which restores strategyproofness. Specifically, in line 8, we adjust the threshold condition from vi ≥ vk (N\(Ti∪W)) to vi ≥ vk (N\Ti). In lines 9-10, we update the payment rule from pi ← vk (N\(Ti∪W)) to pi ← v∗ i (ri) and remove the decrement of the parameter k (k ← k - 1). The formal algorithm for the DNA-MU-R mechanism is deferred to the appendix.

Lemma 3.1. DNA-MU-R Mechanism is IR, SP, and WBB.

Section 3.2 presents the results of DNA-MU-R in the counterexample. We defer the proof of Lemma 3.1 and the detailed execution steps of DNA-MU-R to the appendix.

Regarding DNA-MU-R mechanism, we have revised both the allocation (line 8 and line 10) and the payment rules (line 9 and line 10). Is is possible to only revise the payment (line 9)? The answer is unknown yet. Technically, the losing payment ¯ pi(ri) is always zero. Thus to satisfy condition (3) in Theorem 2.1, the winning payment ˜ pi(ri) must be equal to the critical winning bid v∗ i (ri). However, the allocation rule of DNA-MU leads to a bad consequence that, bidder D's critical winning bid, which is determined by allocation, v∗D (rD) is not invitationally-monotone. It is worth noting that GIDM [Zhao et al., 2018] also fails to be invitationally-monotone.

Remark 1. Merely ensuring value-monotonicity for the allocation can complicate or even fail the payment design.

Then what kind of allocation rules in network auctions can ensure network-implementability? In the following section, we will reveal, from a high-level perspective, the characteristics of allocation rules that are considered "good" in the context of network auction design.

4 Monotonicity and Implementability

In classic auction theory, value-monotone allocation with critical payment play the vital role for strategyproofness. In this section, we first propose general payment functions satisfying strategyproofness for any given value-monotone allocation rule, based on the fundamental principles in Theorem 2.1. We then identify two classes of network-implementable allocation rules: Invitation-Depressed Monotonicity (ID-MON) and Invitation-Promoted Monotonicity (IP-MON).

Technically, we will unveil the fundamental reason why these seemingly opposite allocations can both be implemented in strategyproof network auctions, despite their significantly different performances. Furthermore, we derive the revenue-maximizing payment rule for both ID-MON and IPMON allocations. Specifically, given any ID-MON or IPMON allocation, our payment schemes achieve the upper bound of the seller's revenue within the strategyproof domain.

4.1 Value-Monotone Allocation

Based on Theorem 2.1, given any value-monotone allocation f , we characterize a general class of payment schemes p such that if such a p exists, then f is network-implementable.

Corollary 4.1. Given any value-monotone allocation f and profile θ, for each bidder i with θi = (vi, ri), if there exists some payment function ˜ p(ri) = ˜ g(ri) + h(θ-i) and ¯ p(ri) = ¯ g(ri) + h(θ-i) such that the following conditions hold for functions ˜ g(·), ¯ g(·),

then f is network-implementable.

Corollary 4.1 provides a basic guideline for designing strategyproof payments when a value-monotone allocation function is given. The critical winning bid v∗ i (ri) in the first constraint is determined by the allocation rule. This raises an immediate question: can we leverage the monotonicity over ri to develop network-implementable allocation rules?

Another significant observation is that given any valuemonotone allocation, when fixing all other bidders' reporting type, the critical winning bid for each bidder i across two different invitation strategies r1 i , r2 i ⊆ ri is comparable.

Lemma 4.1. Given any value-monotone allocation rule f, for any bidder i, fixing all other bidders' profile θ-i, for two different invitation strategies r1 i ⊆ ri, r2 i ⊆ ri, v∗ i (r1 i ) ≤ v∗ i (r2 i ) if and only if ∀vi ∈ R≥0, f(vi, r1 i ) ≥ f(vi, r2 i ).

Next, we specify two different types of value-monotone allocation functions: Invitational-DepressedMonotonicity (IDMON) and Invitational-Promoted Monotonicity (IP-MON). With these allocation functions, a strategyproof payment scheme always exists, meaning that the ID-MON and IPMON allocation rules are always network-implementable.

4.2 Invitation-DepressedMonotone Allocation

Invitation-Depressed Monotone (ID-MON) allocation was initially defined in [Li et al., 2020]. ID-MON allocations are based on the economic intuition that invitations can attract more bidders, thereby intensifying competition in the market and making it harder for each bidder to win. Although IDMON favors bidders who invite fewer neighbors, it does not inherently incentivize invitations. Therefore, during the payment design, the auctioneer should compensate the bidders to encourage more invitations.

Technically, ID-MON allocation is based on a partial ordering ⪰D over bidders' type profile θ.

Definition 4.1. For any bidder i and two types θ1 i = (v1 i , r1 i ) and θ2 i = (v2 i , r2 i ), denote the invitation-depressed partial order by ⪰D: if v1 i ≥ v2 i and r1 i ⊆ r2 i , then θ1 i ⪰D θ2 i .

By leveraging this invitational-depressed partial ordering, the definition of ID-MON is as follows.

Definition 4.2 (Invitation-Depressed Monotonicity (IDMON)). Given an allocation rule f and all other bidders' profile θ-i, If, for every bidder i, the allocation fi(θi, θ-i) = 1 implies that for all θ′i ⪰D θi, fi(θ′i , θ-i) = 1, then we say the allocation f is invitation-depressed monotone.

Lemma 4.2. Given an ID-MON allocation f , for each bidder i ∈ N and two type profiles θ1 i = (vi, r1 i ) and θ2 i = (vi, r2 i ), where r1 i ⊆ r2 i , it always holds that v∗ i (r1 i ) ≤ v∗ i (r2 i ).

The following theorem shows that for any ID-MON allocation rule f, there always exists a payment scheme p such that (f, p) is strategyproof.

Theorem 4.1. Every ID-MON allocation f is networkimplementable.

With regard to the implementation of a strategyproof mechanism, by leveraging the features of ID-MON, we present the following theorem to demonstrate how to construct the optimal payment p∗ such that (f, p∗ ) is strategyproof and maximizes the seller's revenue. Please refer to the appendix for detail proof of Theorem 4.2.

Theorem 4.2. Given an ID-MON allocation f and profile θ, for each bidder i, let ˜ pi = v∗ i (∅), ¯ pi = v∗ i (∅) - v∗ i (ri), and p∗ = {fi(θ)˜ pi + (1 - fi(θ))¯ pi}i∈N, then M∗ = (f, p∗ ) is IR and SP, and for any other IR and SP M′ = (f, p′ ), RevM∗ (θ) ≥ RevM′ (θ).

It is not hard to see that the social welfare maximizing (efficient) allocation rule satisfies ID-MON. Therefore, although directly extending VCG into network does not maximize the seller's revenue [Li et al., 2017; Li et al., 2022], we can obtain the maximum revenue by utilizing the payment in Theorem 4.2:

1. Allocate items to bidders with top-k highest bids.
2. Create the Invitational-Domination Tree (IDT) T.
3. Each winner i pays vk (N \Ti) while each loser j "pays" vk (N \ Tj) - vk (N).

Call this mechanism VCG-Revenue-Maximizing (VCG-RM) mechanism. We can obtain the following statement.

Corollary 4.2. In k-unit network auction with single-unit demand bidders, given profile θ, VCG-RM mechanism is EF, IR, SP, and RevVCG-RM(θ) ≥ RevVCG(θ).

4.3 Invitation-PromotedMonotone Allocation

In contrast to ID-MON allocations, we now characterize another class of monotone allocations that allocate items in the opposite manner. The intuition is rather straightforward: the more neighbors that bidders introduce into the auction, the higher their contribution. Therefore, the allocation rule should favor bidders who have more neighbors. We refer to this class of allocation as Invitation-Promoted Monotone (IPMON) allocation. They are based on an opposite partial ordering of bidders' types.

Definition 4.3. For any bidder i and two types θ1 i = (v1 i , r1 i ) and θ2 i = (v2 i , r2 i ), denote the invitation-promoted partial ordering by ⪰P: if v1 i ≥ v2 i and r2 i ⊆ r1 i , then θ1 i ⪰D θ2 i .

The difference from this partial ordering with that for IDMON is the ordering on ri is totally converse. Given partial order ⪰P, we propose the following monotonicity.

Definition 4.4 (Invitation-Promoted Monotonicity (IPMON)). Given an allocation rule f and all other bidders' profile θ-i, if for every bidder i, the allocation fi(θi, θ-i) = 1 implies that for all θ′i ⪰P θi, fi(θ′i , θ-i) = 1, then we say allocation f is invitation-promoted monotone.

Similarly, we introduce the monotonicity of critical winning bid for IP-MON allocation rules.

Lemma 4.3. Given an IP-MON allocation f , for each bidder i ∈ N, for any two type profile θ1 i = (vi, r1 i ) and θ2 i (vi, r2 i ) where r2 i ⊆ r1 i , it always holds that v∗ i (r1 i ) ≤ v∗ i (r2 i ).

Theorem 4.3. Every IP-MON allocation rule f is networkimplementable.

Following the idea in ID-MON subsection, we can derive the revenue-maximizing payment for any IP-MON allocations. See the appendix for detailed proof of Theorem 4.4.

Theorem 4.4. Given an IP-MON allocation f and profile θ, for each bidder i, let ˜ pi = v∗ i (ri), ¯ pi = 0, and p∗ = {fi(θ)˜ pi + (1 - fi(θ))¯ pi}i∈N, thenM∗ = (f, p∗ ) is IR and SP, and for any other IR and SP mechanismM′ = (f, p′ ), RevM∗ (θ) ≥ RevM′ (θ).

It is worth noting that the DNA-MU-Refined mechanism we proposed in the last section satisfy IP-MON and the payment rule has maximized the seller's revenue.

Proposition 4.1. The allocation of DNA-MU-R is IP-MON.

4.4 Insights and Implementation Complexity

The mechanism design space in the network auction scenario is extremely large. Given one value-monotone allocation rule, there could be various payment rules that make the mechanism strategyproof. We summarize our results in the previous subsections in Figure 3, which shows the relations between each category of strategyproof mechanisms.

( Yellow ) In Theorem 2.1, value-monotonicity is sufficient and necessary to guarantee truthfulness.

• ( Orange ) In Corollary 4.1, functions ˜ g(·) and ¯ g(·) are introduced to specify SP network auctions.

( Pink / Blue ) Since bidders' type is two-dimensional, only considering value-monotone allocation while ignoring the monotonicity in the invitation dimension makes devising the SP payment, i.e., the ˜ g(·) and ¯ g(·) functions be much more complicated. Therefore, we identify ID-MON and IP-MON and proved both of these two monotone allocations can be sufficient to achieve strategyproofness.

( Green ) IP-MON and ID-MON can be considered as two special classes within the design paradigm in Lemma 4.1. By instantiating the partial order in the invitation ri dimension, ˜ g(·) and ¯ g(·) are constructed. There exists a class of strategyproof mechanisms at the intersection of these two classes, which is degenerated in the sense of Definition 2.7.

Proposition 4.2. Given any mechanism M = (f, p) where f satisfies both ID-MON and IP-MON, and p satisfies the revenue-maximizing payment schemes in Theorem 4.2 and Theorem 4.4. Then M is degenerated.

Corollary 4.3. ID-MON and IP-MON allocations with payment scheme in Theorem 4.2 and Theorem 4.4 are special cases in Corollary 4.1.

The ideas of SP auction design for these two monotonicities are entirely different. ID-MON-based mechanisms should follow the principle that losers could get potential benefits on payoffs to incentivize more invitations, even though ID-MON allocation itself discourages invitations. On the other hand, IP-MON-based mechanisms are more straightforward in incentivizing invitations since the allocation itself already guarantees that. These two allocation rules achieve distinct trade-offs between social welfare and revenue.

Proposition 4.3. Under IR and SP constraint, there exists an instance such that no IP-MON allocation is EF. Mechanism under ID-MON may fail WBB.

Another positive result is that both ID-MON and IP-MON mechanisms are computationally feasible.

Proposition 4.4. If an ID-MONor IP-MONallocation f runs in polynomial time O(T), then the revenue-maximizing payment p∗ is computed in O(N · T log(maxi∈N vi)).

Furthermore, it is interesting to note that the allocation rules in all existing network auction mechanisms are either ID-MON, IP-MON, or fall within their intersection. We categorize the existing mechanisms into three groups, as presented in Appendix C.16. Based on the above analysis, especially Theorem 4.1 to Proposition 4.3 and Proposition 4.4, we emphasize the following major result.

Remark 2. Designing strategyproof network auctions can boil down to finding ID-MON and IP-MON allocations and applying the corresponding revenue-maximizing payments in Theorem 4.2 and Theorem 4.4.

The above characterization can guide the design of strategyproof mechanisms for network auctions with complex tasks. Given an ID-MON or IP-MON allocation, we can design an appropriate payment in a simple manner. For example, guided by Theorem 4.2, we easily proposed revisions to VCG and DNA-MU, which are called VCG-RM and DNAMU-R, respectively. We showcase that the VCG-RM and DNA-MU-R mechanisms significantly outperform the only two existing strategyproof mechanisms LDM-Tree [Liu et al., 2023] and MUDAN [Fang et al., 2023] regarding social welfare and revenue in the appendix.

5 Combinatorial Network Auction

Regarding combinatorial network auctions with singleminded bidders, Fang et al. [2024] recently proposed the LOS-SN mechanism, inspired by the MUDAN mechanism [Fang et al., 2023], introducing a novel approach to establishing the priority order. Notably, we observe that the LOSSN mechanism satisfies the IP-MON condition, bringing it within the framework of Theorem 4.3. Building on this, we revisit the problem by naturally extending the classic results from combinatorial auctions with single-minded bidders to network auction settings, addressing both ID-MON and IPMON allocations in a more accessible manner.

The scenario is specified as follows: seller s possesses a set K of k heterogeneous items. For each bidder i ∈ N, she is single-minded if and only if there exists a unique bundle of goods S∗ i ⊆ K that bidder i favors. Formally, each bidder's valuation can be represented by vi(S) = vi if and only if S = S∗ i , and for all other bundlesS′ ̸= S, v(S′ ) = 0. For all bidders, their favorite bundles are public information, while their private information is two-dimensional: the bid vi for S∗ i and the invitation set ri. It is well-established that finding an efficient allocation for this problem is NP-hard [Lehmann et al., 2002]. This complexity extends to network auctions, where each classical scenario can be interpreted as a networked case in which all the bidders are directly connected to the seller. Furthermore, it has been shown that there exists no polynomial time algorithm for optimal allocation with an approximation ratio better than k1/2-ϵ . The well-known nearoptimal approximation scheme is presented in Algorithm 2 [Lehmann et al., 2002].

Algorithm 2 √k-approximation for Combinatorial Auction with Single-minded Bidders

Input: θ = {(vi, S∗

i )}i∈N , W = ∅;

Output: Allocation f;

• 1: Reorder all bids in N by v1 √|S∗ 1 | ≥ v2 √|S∗ 2 | ≥ · · · vn √|S∗n | ;
• 2: for i from 1 to n do
• 3: if S∗ i ∩ (⋃j∈W S∗ j ) = ∅ then
• 4: Update W ←W ∪ {i};
• 5: end if
• 6: end for
• 7: Return the winner set W.
• Algorithm 3 Allocation Rule of NSA Mechanism Input: G = (N ∪ {s}, E), θ, K; Output: Allocation f; 1: Initialize the global winner set W; 2: O ← BFS(G, s); Create the IDT T ; 3: for Bidder i in O do 4: N-Ti ←N \ Ti ∪ {i}; 5: θ-Ti ← {(vj, S∗ j )}j∈N-Ti , ¯Wi ←W; 6: ¯Wi ←Algorithm 2(θ-Ti , ¯Wi); 7: if i in ¯Wi then 8: Update W ←W ∪ {i}; 9: end if 10: end for 11: Return f which gives S∗ i to i if and only if i ∈W.

According to Remark 2, a straightforward way to finding a monotone allocation is to apply Algorithm 2 to all the bidders in N, in conjunction with the revenue-maximizing payment scheme described in Theorem 4.2. We term this mechanism "Network-√k-Approximation Mechanism (Net-√k-APM)".

Regarding IP-MON allocation, we propose the Network Single-minded Auction (NSA) mechanism, which combines a non-trivial extension of Algorithm 2, presented in Algorithm 3, along with the payment scheme introduced in Theorem 4.4.

Theorem 5.2. NSA mechanism satisfies IR, SP, and WBB.

6 Discussion

With the characterization in the above sections, the combinatorial network auction with single-minded bidders (including the multi-unit network auctions with single-unit demand), which has been a major obstacle in the field of network auctions since 2018, is now solved in principle. Building on these insights, this work pioneers the investigation into combinatorial network auctions with single-minded bidders. A significant open question is whether, given any value-monotone allocation rule, there always exists a computationally tractable payment rule that ensures the mechanism is strategyproof. Other intriguing questions include characterizing Bayesian truthful mechanisms, extending the deterministic 0-1 allocation in a more general context, and more.

Acknowledgments

The authors are sincerely grateful to the reviewers for their valuable comments throughout every stage of this paper. This research is supported by the National Natural Science Foundation of China under Nos. 71601029, 62202229, 62372095, 62172077, and 62350710215. Dong Hao, Mingyu Xiao, and Bakh Khoussainov are supported by the Sichuan Science and Technology Program (2025HJPJ0006). Yuhang Guo is supported by the TFS Scholarship (RSRE7059 and RSRE7092) at UNSW Sydney. This work was completed during Yuhang Guo's master's studies at the University of Electronic Science and Technology of China.