Near-Optimal Approximation Mechanisms for Multi-Unit Combinatorial Auctions

1 Introduction

We present truthful mechanisms for multi-unit combinatorial auctions, involving constant number of distinct goods, each in limited supply. A widespread modern application of this general setting is the allocation of radio spectrum licences [Milgrom, 2004]; each such license is for the use of a specific frequency band of electromagnetic spectrum, within a certain geographic area. In the design of such "Spectrum Auctions", licenses for the same area are considered as identical units of a single good (the area), while the number of distinct geographic areas is, of course, bounded by a constant.

More formally, we consider the problem of auctioning "in one go" multiple units of each out of a constant number of distinct goods, to prospective buyers with private multi-demand combinatorial valuation functions, so as to maximize the social welfare. A multi-demand buyer may have distinct positive values for distinct multisets of goods, that specify his demand for (potentially) more than one unit per good. We discuss deterministic truthful auction mechanisms, wherein every bidder finds it to his best interest to reveal his value truthfully for each multiset of items (i.e., truthful report of valuation functions is a dominant strategy). Additionally, we are interested in mechanisms that can compute an approximately efficient allocation in polynomial time. This problem generalizes simultaneously combinatorial auctions of multiple goods and multi-unit auctions of a single good to the multi-unit and combinatorial settings respectively.

∗This paper was invited for submission to the Best Papers From Sister Conferences Track, based on a paper that appeared in the 12th International Conference AAMAS (2013).

†Work supported by EPSRC grants EP/K01000X/1 and EP/M018113/1.

Mechanism Design for combinatorial auctions of multiple heterogeneous goods (each in unit supply) has received significant attention in recent years, since the work of [Lehmann et al., 1999; 2002], due to their various applications, especially in online trading systems over the Internet. Research in Algorithmic Mechanism Design was initialized by [Nisan and Ronen, 1999]. A mechanism elicits bids from buyers, so as to determine an assignment of bundles to them and payments in such a manner, so that it is to each buyer's best interest to reveal his valuation function truthfully to the mechanism. The related problem of auctioning multiple units of a single good to multi-demand bidders was considered already by [Vickrey, 1961], through a (multiunit) extension of his celebrated single-item Second-Price mechanism. This extension, however, is not polynomialtime for an arbitrary number of units. Polynomial-time approximation mechanisms for multi-unit auctions were designed relatively recently [Mu'alem and Nisan, 2002; 2008; Dobzinski and Nisan, 2010; V¨ocking, 2012; Nisan, 2014]. In particular, [Nisan, 2014] devised a welfare-optimal deterministic polynomial-time auction mechanism, for the multi-unit setting with submodular bidders first considered by [Vickrey, 1961]. [V¨ocking, 2012] designed and analyzed a randomized universally truthful polynomial-time approximation scheme, for bidders with unrestricted valuation functions.

Results for the more general setting of multi-unit combinatorial auctions are much scarcer [Bartal et al., 2003; Grandoni et al., 2014]. Here, we consider exactly this setting, with a constant number of distinct goods, as in [Grandoni et al., 2014]; for a number of cases of such auctions we analyze Maximum-in-Range (MIR) allocation algorithms [Nisan and Ronen, 2007] (see definition 2 in Section 2), that can be paired with the Vickrey-Clarke-Groves payment rule, so as to yield truthful mechanisms.

1.1 Overview

We discuss truthful mechanisms for multi-unit combinatorial auctions with a constant number of goods developed recently in [Krysta et al., 2013], for two broad classes of the bidders' valuation functions.

Multi-Minded Bidders Each bidder has positive value for every distinct multiset belonging to a specific demand set of alternatives associated with him (and at least as much for the value of every superset of this multiset). His value is zero elsewhere. For this class of valuation functions we describe in Section 3 a truthful FPTAS 1 , that fully optimizes the social welfare in polynomial time, while violating the supply constraints on the goods by a factor at most (1+ϵ), for any fixed ϵ > 0. A relaxation of the supply constraints is necessary for obtaining an FPTAS, as the problem is otherwise strongly NP-hard, for m ≥ 2 goods (see the related discussion in Section 3). In certain environments, a slight augmentation of supply can be economically viable, for the sake of better solutions (e.g., auctioneers with well supplied stocks can easily handle occurrences of modest overselling). This result improves upon an FPTAS by [Grandoni et al., 2014], which approximates the social welfare and the supplies within factor 2 (1 + ϵ), and only when bidders are single-parameter (i.e., associate the same positive value with each multiset from their demand set) and do not overbid their demands.

Submodular Bidders The value of each bidder for a multiset of items is given by a submodular valuation function. Thus, each bidder's marginal value for each additional item allocated to him (a unit of any good) is non-increasing. For this setting we develop a PTAS 1 , that approximates the optimum social welfare within factor (1+ϵ), for any fixed ϵ > 0, without violating the supply constraints. To this end, we revisit a technique introduced by [Dobzinski and Nisan, 2010], for multi-unit auction Mechanism Design, and generalize it for multiple distinct goods, each in limited supply. We describe how this generalization works and also how to use it to obtain a truthful PTAS for multi-minded bidders, that does not violate the supply constraints. This latter result is best possible; a hardness result from [Dobzinski and Nisan, 2010] rules out the possibility of a truthful FPTAS via their technique, for multi-minded bidders and a single good, unless P = NP.

The assumption of m = O(1) distinct goods is important, for otherwise our two problem cases become hard to approximate in polynomial time, within factor less than O(√m) [Lehmann et al., 2002] and e e-1 [Khot et al., 2008; Mirrokni et al., 2008] respectively. Also, our techniques cannot yield truthful polynomial-time mechanisms with approximation factors less than O(m) and O(√m) respectively [Daniely et al., 2014]. We omit from our presentation a truthful constant-approximation mechanism from [Krysta et al., 2013], for bidders with unrestricted valuation functions.

1 (F)PTAS stands for (Fully) Polynomial Time Approximation Scheme, see chapter 8 in [Vazirani, 2003] for a formal definition.

2 In the context of social welfare maximization, by "approximation within factor ρ ≥ 1" we mean recovering at least a fraction ρ-1 of the welfare of an optimum allocation.

1.2 RelatedWork

Mechanism Design for multi-unit auctions was initiated already by the celebrated work of [Vickrey, 1961], where the well-known single-item Second-Price auction is extended for the case of multiple units and bidders with symmetric submodular valuation functions [Lehmann et al., 2006]. This mechanism is however not computationally efficient with respect to the number of available units. A polynomial-time truthful mechanism for this case was analyzed in [Nisan, 2014]. The design of multi-unit mechanisms with polynomially bounded running time in log s, s denoting the number of units, was first considered by [Mu'alem and Nisan, 2008]. The authors analyzed a truthful 2-approximation mechanism for a multi-unit setting with multiple distinct goods (in limited supply), and single-minded bidders, each valuing positively a particular subset of goods (and its supersets). [Archer et al., 2003] improved on this approximation ratio for a similar setting, but their mechanism was based on randomized rounding and was truthful only in expectation. Furthermore, an FPTAS was designed and analyzed in [Briest et al., 2005] for singleminded bidders, in the multi-unit combinatorial setting.

[Dobzinski and Nisan, 2007; 2010] analyzed a general scheme for designing MIR polynomial-time truthful approximation mechanisms, for single-good multi-unit auctions. This resulted in a PTAS for the case of k-minded bidders, a 2-approximation for general valuation functions that are accessed (by the allocation algorithm) through value queries, and a 4 3 -approximation for symmetric subadditive valuation functions. Moreoever, the authors applied their scheme to a class of piecewise linear (multi-unit) valuation functions over the number of units of a single good, to obtain a truthful PTAS mechanism. For a special case of this class, [Kothari et al., 2005] had designed earlier an FPTAS mechanism that was, however, only approximately truthful. [Dobzinski and Dughmi, 2009] gave a truthful in expectation FPTAS for multi-minded bidders. A universally truthful randomized PTAS for general valuation functions accessed by value queries was developed in [V¨ocking, 2012] (in contrast, all of our mechanisms are deterministic). For the multiunit combinatorial setting (i.e., with more than one distinct goods) the known results concern mainly bidders demanding at most one unit per good (e.g. [Lehmann et al., 2002; Briest et al., 2005]). In contrast, we consider a constant number of goods, but multi-demand bidders. [Bartal et al., 2003] proved approximation results for multi-unit combinatorial auctions with multi-demand bidders, where the bidders' demands on numbers of units are upper and lower bounded. The approximation guarantees depend on these bounds.

The study of mechanisms for a constant number of distinct goods, each in limited supply, was initialized by [Grandoni et al., 2014]. The authors utilized methods from multi-objective optimization, to obtain truthful polynomial-time approximation schemes for problems including: multi-unit auctions, minimum spanning tree, shortest path, maximum (perfect) matching and matroid intersection. They devised truthful FPTASes that approximate the objective function (social welfare or cost) of multi-capacitated versions of these problems within factor (1+ϵ), while exceeding the capacities by a factor (1 + ϵ) (capacities here correspond to limited supplies).

2 Preliminaries

We consider a set [m], of m = O(1) goods, [m] = {1, . . . , m}. Each good ℓ ∈ [m] is available in limited suppply (number of units) sℓ ∈ N. A multiset of goods is denoted by a vector x = (x(1), x(2), . . . , x(m)), where x(ℓ) is the number of units of good ℓ ∈ [m], ℓ = 1, . . . ,m. The set of all multisets is denoted by U = ×mℓ=1{0, 1, . . . , sℓ}. Let [n] = {1, . . . , n} be the set of n bidders (prospective buyers). Every bidder i ∈ [n] has a private valuation function vi : U ↦→ R+, so that vi(x) for any x ∈ U denotes the maximum monetary amount that i is willing to pay for x ∈ U, referred to as his value for x. The valuation functions are normalized, i.e., vi(0, . . . , 0) = 0 and monotone non-decreasing: for any two multisets x ≤ y - where "≤" holds componentwise - we have vi(x) ≤ vi(y).

A mechanism consists of an allocation method (algorithm), A, and a payment rule, p. The allocation algorithm, A, elicits from the bidders bids b = ( b1, b2, . . . , bn ) that, presumably, describe their valuation functions, and determines an allocation A(b) = (x1, x2, . . . , xn ), where xi ∈ U is the multiset of goods allocated to bidder i. For the current Section we deliberately ignore the fact that the bidders' valuation functions may not have a succinct representation that will facilitate their efficient communication to the allocation algorithm; recall that the bidders' valuation functions are - generally - defined over U = ×mℓ=1{0, 1, . . . , sℓ}. When they do not have a succinct representation indeed, the allocation algorithms that we discuss in our work access the bidders' valuation functions iteratively, through polynomially many value queries; that is, the algorithm in each iteration asks every bidder for a bid on a specific multiset of items.

The payment rule determines a vector p(b) = ( p1(b), p2(b), . . . , pn(b) ), where pi(b) is the payment of bidder i. Every bidder i bids so as to maximize his quasilinear utility, defined as:

where the second equality stems from a standard assumption of no externalities, i.e., that the value of any bidder for A(b) depends only on his own individual allocation.

We study truthful mechanisms (A, p) wherein each bidder i maximizes his utility by reporting his valuation function truthfully, i.e., by bidding bi = vi, independently of the other bidders' reports, b-i = (b1, . . . , bi-1, bi+1, . . . , bn):

Definition 1 A mechanism (A, p) is truthful if, for every bidder i and bidding profile b-i, it satisfies ui(vi, b-i) ≥ ui(v′i , b-i), for every v′i .

Under this definition, the outcome b = v is a dominant strategy equilibrium. We are interested in designing and analyzing truthful mechanisms (A, p), that render truthful reporting of the bidders' valuation functions a dominant strategy equilibrium, wherein, the social welfare of the resulting allocation, SW(A(b) ) = SW(A(v) ) is (approximately) optimized. The social welfare of an allocation, X = (x1, x2, . . . , xn) is defined as: SW(X) = ∑ni=1 vi(xi). In the sequel we will use simply X, for an allocation output by A, without a specific reference to b, since we analyze truthful mechanisms, that dictate b = v.

The only well understood general method for the design of truthful mechanisms is the Vickrey-Clarke-Groves (VCG) auction mechanism [Vickrey, 1961; Clarke, 1971; Groves, 1973], a generalization of Vickrey's single-item Second-Price and multi-unit auctions [Vickrey, 1961]. Deployment of the VCG auction, however, requires allocation algorithms A that output welfare-maximizing allocations, for the underlying setting; it rarely constitutes a computationally efficient alternative for combinatorial settings, as the underlying optimization problem is NP-hard. As the problems that we consider are indeed NP-hard, our mechanisms use Maximum-in-Range (MIR) [Nisan and Ronen, 2007] allocation algorithms, that maximize the social welfare approximately.

Definition 2 [Nisan and Ronen, 2007] An algorithm choosing its output from the set A of all possible allocations is MIR, if it fully optimizes the social welfare over a subset R ⊆ A of allocations.

Note that the subset R, also called a range, is defined independently from the bidders' declarations. Nisan and Ronen [Nisan and Ronen, 2007] identified MIR allocation algorithms as the sole device that, along with VCG payments, yields truthful mechanisms for combinatorial auctions. That is, any MIR allocation algorithm, A, can be "turned" into a truthful mechanism, if the payment for each bidder i is computed according to the VCG payments scheme, as follows:

This payment scheme coincides with the VCG payment scheme, if A is replaced by the optimal allocation algorithm.

3 Multi-Minded Bidders

In this section we consider multi-minded bidders; every such bidder i ∈ [n] is associated with a collection of multisets Di ⊆ U, referred to as his demand set. We assume that each i ∈ [n] values each multiset d = (d(1), . . . , d(m)) ∈ Di by an amount vi(d) > 0. For every e ∈ U \ Di we define:

Naturally, vi(0) = 0. In this setting, the valuation function of a bidder i can be expressed compactly, as the collection (vi(d), d)d∈Di . As in related literature, we assume therefore that an algorithm expects in input bids of this form, rather than (an oracle representing) the entire valuation function. A bidder i is a winner of the auction, if he is assigned exactly one - or a superset of one - of his alternatives from Di.

The allocation algorithm of our mechanism will be an FPTAS, that maximizes the social welfare and may violate the supply constraints on goods by a factor at most (1 + ε), for any fixed ϵ > 0. The algorithm is reminiscent of the FPTAS for the well-known one-dimensional knapsack problem (see e.g., chapter 8 in [Vazirani, 2003]). For any chosen fixed ε > 0, first it discards any alternative from the bidders' demand sets, that violates any of the supply constraints. Subsequently, the quantities of goods in the remaining multisets are rounded appropriately; the supplies are also adjusted. Thus we obtain a rounded instance. Then, we search for a welfare maximizing allocation of the rounded instance, by usage of dynamic programming. This allocation is shown to be optimal for the initial instance as well, and violates the (initial) supplies by a factor at most (1+ϵ). In light of turning this algorithm into a truthful mechanism, we use notation of actual valuation functions in its description below.

Rounding Fix any constant ε > 0. First, for any i ∈ [n], remove all the alternatives d ∈ Di such that d(ℓ) > sℓ for any ℓ = 1, . . . ,m (if all alternatives of some bidder i are removed, remove i). Henceforth, we use the same notation, U, [n], Di, etc., for the remaining alternatives and bidders. The demands of the alternatives d ∈ Di of each i ∈ [n] are rounded as follows. For every i ∈ [n] and for every d ∈ Di, we produce a multiset d′ = ( d′ (1), . . . , d′ (m) ) so that, for each good ℓ ∈ [m], we have d′ (ℓ) = ⌊ n·d(ℓ) εsℓ ⌋. Then we adapt the supply of each good appropriately, to s′ℓ = ⌈ nε ⌉. Given this rounded version of the problem instance, we will use dynamic programming to produce an allocation for it; this will directly translate into an allocation for the original problem instance, that is welfare-optimal and violates the (original) supply constraints by a factor at most (1 + ϵ). In the sequel, for any multiset d in the demand set Di of some bidder i, we use d′ to refer to the rounded multiset as described above.

Dynamic Programming We use two tables, V and A, for storing respectively social welfare values and allocations. Each cell of each table is indexed by the tuple (i, q1, . . . , qm), for i = 1, . . . , n, where qℓ ∈ {0, 1, 2, . . . , ⌈n/ϵ⌉}, for ℓ = 1, . . . ,m. Notice that there are n(1 + ⌈n/ϵ⌉)m such cells in each table, which is a polynomially bounded number for m = O(1) and any fixed ϵ > 0. To simplify notation, in the sequel we use q for (q1, . . . , qm). V(i, q) stores the maximum welfare of an allocation X, i.e., ∑j vj(xj), whose rounded version X′ = (⌊ n·xj(ℓ) εsℓ ⌋)j,ℓ:

1. uses only multisets that are in the demand sets of the bidders in {1, 2, . . . , i},
2. has total demand w.r.t. good ℓ = 1, . . . ,mwhich is precisely yℓ, i.e., ∑i x′i (ℓ) = qℓ.

The corresponding cell A[i, q] holds this allocation X.

Let us explain how we compute the cells V(1, q) and A[1, q] first, for every q ∈ {0, 1, . . . , ⌈n/ϵ⌉}m. For each vector q: we identify a multiset d ∈ D1 with d′ = q, that maximizes the value of bidder 1, if such a multiset exists. If it does exist, we store the value in V(1, q) and a partial allocation { (1, d) } in A[1, q]. Otherwise, we set V(1, q) = 0 and A[1, q] = { (1, ∅) }. This procedure is described on the left of Figure 1. On the right of the figure, a generalization of this computation is described for bidder i + 1, once the values V(i, q) and A[i, q] are known for all q ∈ {0, 1, . . . , ⌈n/ϵ⌉}m.

The size of each table is n(⌈ nε ⌉ + 1)m and we need time roughly O(maxi |Di| +m) to compute one entry of the table, so the overall time of the algorithm leads to an FPTAS. For its optimality, we argue that the algorithm optimizes the welfare over a superset of feasible solutions X = (x1, x2, . . . , xn) for the initial problem instance; indeed, for every good ℓ = 1, . . . , m we have: ∑i xi(ℓ) ≤ sℓ, or, equivalently, ∑i xi(ℓ)·n ε·sℓ ≤ nε , thus ∑i ⌊ xi(ℓ)·n ε·sℓ ⌋ ≤ ⌈ nε ⌉ = s′ℓ . Thus, X is also feasible for the rounded problem instance and inspected by the dynamic programming algorithm.

For the approximate violation of the supply constraints, let X be an output allocation, for the original problem instance. For any good ℓ = 1, . . . , m we have: ∑i n·xi(ℓ) ε·sℓ ≤

Note that the algorithm is exact, in that it grants every bidder a multiset from his demand set (or none). This feature is essential in proving that the algorithm is MIR and, thus, that it yields a truthful mechanism:

Theorem 1 Multi-unit combinatorial auctions with multiminded bidders and a constant number of distinct goods admit a truthful FPTAS, that optimizes the social welfare fully, while violating the supplies of goods at most by a factor (1 + ϵ), for any fixed ϵ > 0.

Computational Hardness Note that this problem is strongly NP-hard, when we do not allow violation of supply constraints and m ≥ 2 [Chekuri and Khanna, 2000]. It is well known that if a problem is strongly NP-hard, it does not admit an FPTAS, unless P=NP, see, e.g., [Vazirani, 2003]. Also the assumption that m is a fixed constant is necessary. Otherwise the problem is hard to approximate in polynomial time within m1/2-ϵ , for any ϵ > 0 [Lehmann et al., 2002]. By applying a simple reduction from [Lehmann et al., 2002], from the MAXIMUM INDEPENDENT SET PROBLEM [Hastad, 1996], we can establish the same approximation hardness, even if we allow supply violation, when m is non-constant.

An Application: Multi-Dimensional Knapsack Our FPTAS can be applied to the Multi-dimensional Knapsack Problem [Chekuri and Khanna, 2000] (MDKP), where the knapsack has a constant number m = O(1) of distinct compartments, each of capacity sℓ, ℓ ∈ [m]. The problem asks to fit in the knapsack a subset out of a universe U of n given m-dimensional objects, so that the sum of the collected objects' sizes in each dimension ℓ does not exceed sℓ, and the total value of all collected objects is maximized. Each object i ∈ [n] is represented by a vector di = (di(1), . . . , di(m)) and has a value vi. Thus, each such object corresponds exactly to a single-parameter bidder with valuation function vi(d) ≡ vi, if d ≥ di, and vi(d) = 0 otherwise. Our FPTAS is applicable to the MDKP because, as mentioned, it is exact in that it allocates every bidder (i.e., "fits in the knapsack") either an exact alternative from his demand set, Di, or none. We can generalize the MDKP setting further, by handling any mix of packing and covering constraints (i.e., of any of the forms {≥, ≤}), for m = O(1) dimensions and one covering or packing constraint per dimension.

for every q ∈ { 0, 1, . . . , ⌈n/ϵ⌉ }m do: 1. D′1 ←- {d ∈ D1 | d′ = q} 2. if D′1 ̸= ∅ then 1. d←- argmaxa∈D′1 v1(a) 2. V(1, q) ←- v1(d) 3. A[1, q] ←- { (1, d) } 3. else 1. V(1, q) ←- 0. 2. A[1, q] ←- { (1, 0) } for every q ∈ { 0, 1, . . . , ⌈n/ϵ⌉ }m do: 1. D′i+1 ←- { d ∈ Di+1 | d′ ≤ q } 2. if D′i+1 ̸= ∅ then 1. d←- arg max a∈D′i+1 [ vi+1(a) + V(i, q - a′ ) ] 2. νi+1 ←- vi+1(d) +V(i, q-d′ ) 3. if νi+1 > V(i, q) then 1. V(i +1, q) ←- νi+1 2. A[i +1, q] ←- A[i, q-d′ ] ∪ { (i +1, d) } 4. else 1. V(i +1, q) ←- V(i, q) 2. A[i +1, q] ←- A[i, q] ∪ { (i +1, 0) } 3. else 1. V(i +1, q) ←- V(i, q) 2. A[i +1, q] ←- A[i, q] ∪ { (i +1, 0) }

4 The Generalized Dobzinski-NisanMethod

We discuss here a direct generalization of a method designed by [Dobzinski and Nisan, 2010], for truthful single-good multi-unit auction mechanisms. The method's generalization for multiple goods yields a truthful PTAS for bidders with submodular valuation functions over multisets. The method requires as subroutine a MIR α-approximation algorithm A, that, for an instance of the problem involving a constant number t = O(1) of bidders and m = O(1) goods, approximates the optimum welfare within factor α. Moreover, A is MIR with range RA. The method executes iteratively this algorithm A for appropriately chosen combinations of a subset of at most t bidders and a subset of at most m distinct goods. In each iteration, it completes appropriately the partial allocation output by A and, in the very end, returns the best found complete allocation for the whole instance of n bidders and m = O(1) goods. If A is MIR, the method can be shown to be MIR as well; moreover, it recovers a fraction at least (α-1 - m t+1 ) of the optimum welfare of the whole instance.

Let us explain first how the Dobzinski-Nisan method completes a partial allocation output by the presumed algorithm A described above. Subsequently, we will describe such an algorithm A for the case of bidders with submodular valuation functions. The method is described in detail in Figure 2. It determines first a set Pℓ of possible supplies for each good ℓ = 1, . . . , m; these are powers of (1 + 1/(2n)) no larger than sℓ - and rounded downwards to the largest integer - inclusively of 0, as described in lines 1.1 and 1.2 of Figure 2. Subsequently, for every possible subset T of at most t = O(1) bidders and for every combination of supplies of goods (χ1, . . . , χm) ∈ (×mℓ=1Pℓ ), the method:

1. first executes the algorithm A for the bidders in T and for all m goods, each good with the "remaining" supply sℓ -χℓ, to obtain a partial allocation.
2. Then, it splits the other part of each good's supply, χℓ, into at most 2n2 multi-unit bundles, of βℓ = max{⌊χℓ/(2n2 )⌋, 1} units per such bundle. It finds the optimum allocation of these bundles to the remaining [n] \ T bidders.

The (optimal) allocation of the splitted multi-unit bundles of goods to bidders in [n] \ T is carried out by dynamic programming. By re-indexing the bidders appropriately, assume that T = {n - t + 1, . . . , n}, thus [n] \ T = {1, . . . , n - t}. For every i = 1, . . . , n - t and for every q = (q1, . . . , qm) ∈ (×mi=1 [2n2 ]), define V(i, q) = V( i, (q1, . . . , qm) ) to be the maximum value of welfare that can be obtained by allocating at most qℓ multi-unit bundles from each good ℓ = 1, . . . ,m, to bidders 1, . . . , i. Each entry V(i, q) of the dynamic programming table can be computed using:

where q′ ≤ q is taken component-wise; i.e., maximization occurs over all q′ with q′ (ℓ) ≤ q(ℓ) for each ℓ = 1, . . . ,m.

The following result quantifies the performance of the Dobzinski-Nisan method for multiple goods; its proof is a direct extension of a related result from [Dobzinski and Nisan, 2010], for the case of a single good.

Theorem 2 Let A be a MIR algorithm, with time complexity TA(t, (s1, . . . , sm)) for t bidders and at most sℓ units from each good ℓ = 1, . . . ,m. There exists a range of allocations, R, such that the Dobzinski-Nisan Method runs in time polynomial in log s1, . . . , log sm, n, TA(t, (s1, . . . , sm)), for every t = O(1), and outputs an allocation with value at least a fraction (α-1 - m t+1 ) of the optimum social welfare.

The Method's Range The (generalized) Dobzinski-Nisan method optimizes over a range of possible allocations, that can be described independently of the bidders' declarations. This range depends on the range of the algorithm A used within the method. Following [Dobzinski and Nisan, 2010] we describe the method's range as a set of (RA, τ, χ1, . . . , χm)-round allocations. Let us first describe the notion of a round allocation, for any τ ≤ t, for some fixed t = O(1). An allocation X is (RA, τ, χ1, . . . , χm)-round if:

1. There exists a subset T ⊆ [n] of τ = |T| bidders, such that the (partial) allocation X[T ] is optimum in the range

1. for ℓ = 1, . . . ,mdo: 1. define uℓ := (1+ 1 2n ) 2. define Pℓ := {0, 1, ⌊uℓ⌋, ⌊u2ℓ ⌋, . . . , ⌊u⌊loguℓ sℓ⌋ ℓ ⌋ , sℓ} 2. for every subset T ⊆ [n] of bidders, |T| ≤ t, do: 1. for every (χ1, . . . , χm) ∈ (×mℓ=1Pℓ) do: 1. Run A with sℓ - χℓ units from each good ℓ ∈ [m] and bidders in T . 2. Split the remaining χℓ units from each good ℓ ∈ [m] into ≤ 2n2 bundles (per good), each of max {⌊ χℓ 2n2 ⌋, 1} units. 3. Find the optimal allocation of the multi-unit bundles among bidders [n] \ T . 3. return the best allocation found.

Figure 2: The Dobzinski-Nisan Method for multiple goods.

RA of algorithm A, for the sub-instance involving bidders in T and sℓ-χℓ units from each good ℓ = 1, . . . , m.

1. Each bidder i ∈ [n] \ T obtains an exact multiple of max {⌊ χℓ 2n2 ⌋, 1} units from good ℓ and: ∑i∈[n]\T xi(ℓ) ≤ n·max {⌊ χℓ 2n2 ⌋, 1}, for ℓ = 1, . . . , m.

Then, for any fixed t = O(1) and for a MIR algorithm A with range RA as discussed above, the range of the generalized Dobzinski-Nisan method contains all the possible (RA, τ, χ1, . . . , χm)-round allocations, for any τ ≤ t and (χ1, . . . , χm) ∈ (×mℓ=1Pℓ), where Pℓ is defined as in step 1.2 of the method, in Figure 2. Quite elaborate as this description may be, it prescribes exactly the set of allocations that the Dobzinski-Nisan method optimizes upon. By the results of [Nisan and Ronen, 2007], we can obtain a truthful mechanism simply by pairing it with VCG payments.

A PTAS for Multi-Minded Bidders The generalized Dobzinski-Nisan method for multiple distinct goods can be applied directly in the setting of (multi-parameter) multiminded bidders, that we studied in Section 3, to give us a PTAS that respects the supply constraints of the goods. A result of [Dobzinski and Nisan, 2010] rules out the possibility of FPTAS, when the supply constraints are fully respected, thus, the PTAS is best possible in this setting. Let k = maxi |Di| denote the maximum size of any bidder's demand set. For m = O(1) goods and for any number t = O(1) bidders, the optimum assignment can be found exhaustively in time polynomial in log sℓ, ℓ = 1, . . . , s, and m: there are exactly O(kt ) cases to be examined exhaustively, so that the optimum is found. Then, by fixing any ϵ > 0, we can use this (trivially MIR) algorithm A within the procedure of Figure 2, for t =m· 1+ϵ ϵ -1 and α = 1. By Theorem 2, we thus obtain a PTAS that, complementarily to the developments of Section 3, approximates the optimum social welfare within factor (1 + ϵ) and respects the supply constraints.

A PTAS for Submodular Bidders We consider bidders with submodular valuation functions over multisets in U:

Definition 3 For any ℓ = 1, . . . , m let eℓ be the unary vector with eℓ(ℓ) = 1 and eℓ(j) = 0, for j ̸= ℓ. Let x and y denote two multisets from U, so that x ≤ y, where "≤" holds component-wise. Then, a non-decreasing function v : U ↦→ R+ is submodular if v(x + eℓ) - v(x) ≥ v(y + eℓ) - v(y).

These valuation functions, being exponentially large to describe compactly, are accessed by the algorithm through value queries; i.e., the algorithm asks the bidders for their value, for each particular multiset that it needs to process.

The MIR algorithm A needed by the Dobzinski-Nisan method optimizes over a range of allocations, defined as follows. For any ϵ > 0, define δ = 1+ϵ; the range of A contains all allocations that assign bidders multi-unit bundles of each good ℓ ∈ [m], where each bundle has cardinality equal to an integral power of δ. The specified range can be examined exhaustively in polynomial time; to find a welfare-maximizing allocation, we can try O(logδ sℓ) cases per good, for each of t - 1 bidders, given a fixed bidder for assigning the remaining units. Trying all possible multi-unit bundle assignments of a specific good ℓ - and for all possible choices of a "remainders" bidder - is O (t(logδ sℓ)t-1 ). Because for every allocation of a specific good we need to examine all possible allocations for the remaining m- 1 goods, the overall complexity is O (tm(logδ maxℓ sℓ)(t-1)m), which is polynomially bounded for t = O(1) and m = (1). We show in [Krysta et al., 2013] that - for a constant number of bidders and goods - this algorithmA is in fact an FPTAS, w.r.t. welfare; it yields a truthful PTAS when used within the Dobzinski-Nisan method.

Theorem 3 Multi-unit combinatorial auctions with a constant number of distinct goods and bidders with submodular valuation functions admit a truthful PTAS.

5 Conclusions

We elaborated on MIR polynomial-time deterministic mechanisms, for approximate social welfare maximization in multi-unit combinatorial auctions. The main results include (i) a truthful FPTAS for multi-minded bidders, that approximates the supply constraints within factor (1 + ϵ) and optimizes the social welfare; (ii) a deterministic truthful PTAS for submodular bidders, that approximates the social welfare within factor (1+ϵ) without violating the supply constraints. For (ii) we used a generalization of a single-good multi-unit allocation method proposed in [Dobzinski and Nisan, 2010]. Our developments are best possible in terms of time-efficient approximation, as follows by relevant hardness results.