Procurement Auctions via Approximately Optimal Submodular Optimization
Authors: Yuan Deng
Amin Karbasi
Vahab Mirrokni
Renato Paes Leme
Grigoris Velegkas
Song Zuo
Venue: ICML 2025 spotlightposter (2025)
Keywords: Auction Design
Submodular Maximization
Primary area: theory->game_theory
TL;DR: We propose a new setting of procurement auctions and we give approximation-preserving black-box reductions from submodular function maximization to  mechanisms.

Abstract: We study the problem of procurement auctions, in which an auctioneer seeks to acquire services from a group of strategic sellers with private costs. The quality of the services is measured through some submodular function that is known to the auctioneer. Our goal is to design computationally efficient procurement auctions that (approximately) maximize the difference between the quality of the acquired services and the total cost of the sellers, in a way that is incentive compatible (IC) and individual rational (IR) for the sellers, and generates non-negative surplus (NAS) for the auctioneer. {Our contribution is twofold: \textbf{i)} we provide an improved analysis of existing algorithms for non-positive submodular function maximization and \textbf{ii)} we design computationally efficient frameworks that transform submodular function optimization algorithms to mechanisms that are IC and IR for the sellers, NAS for the auctioneer, and approximation-preserving.} Our frameworks are general and work both in the offline setting where the auctioneer can observe the bids and the services of all the sellers simultaneously, and in the online setting where the sellers arrive in an adversarial order and the auctioneer has to make an irrevocable decision whether to purchase their service or not. We further investigate whether it is possible to convert state-of-art submodular optimization algorithms into descending auctions. We focus on the adversarial setting, meaning that the schedule of the descending prices is determined by an adversary. We show that a submodular optimization algorithm satisfying bi-criteria $(1/2,1)$-approximation in welfare can be effectively converted to a descending auction in this setting. We further establish a connection between descending auctions and online submodular optimization. Finally, we demonstrate the practical applications of our frameworks by instantiating them with different state-of-the-art submodular optimization algorithms and comparing their welfare performance through empirical experiments on publicly available datasets that consist of thousands of sellers.

Procurement Auctions via Approximately Optimal Submodular Optimization
Yuan Deng' Amin Karbasi²
2 Vahab Mirrokni'
Renato Paes Leme'
Grigoris Velegkas 2* Song Zuo
Abstract
1. Introduction
In this paper, we consider procurement auctions (Dim- itri et al., 2006) in which strategic service sellers with private costs submit bids to an auctioneer, who then de- cides the set of winners based on objective function and purchases their services. Procurement auctions have been adopted in multitude of application domains, includ- ing industrial procurement (Bichler et al., 2006), data shar- ing (Roth & Schoenebeck, 2012; Rasouli & Jordan, 2021; Sim al., 2022; Fallah al., 2023), and crowdsourcing markets (Singer & Mittal, 2013). Additionally, Amazon Business provides government procurement solutions for products ranging from office supplies to first responder equipment (AmazonBusiness, 2024), while the U.S. Govern- ment Publishing Office conducts nationwide procurement for items used in publishing (USGPO, 2024). Each of these markets involve thousands of vendors for ensuring supplier diversity and competitive prices. There is also large body of literature on procurement auction for the sale of data, in- cluding Bayesian mechanism design for one-sided markets, two-sided markets, and their online learning variants (Ghosh & Roth, 2011; I; Roth & Schoenebeck, 2012; Abernethy et al., 2015; Agarwal et al., 2019; Sim et al., 2022; Fallah et al., 2023; Agarwal et al., 2024).
We study procurement auctions where an auction- eer must acquire services from strategic sellers with private costs. The quality of these services is represented by a known submodular function. Our goal is design computationally efficient auctions that approximately maximize the differ- ence between service quality and total seller costs, while remaining incentive compatible (IC), indi- vidually rational (IR), and yielding non-negative surplus (NAS) for the auctioneer. Our contri- bution twofold: (i) we provide an improved analysis of existing algorithms for non-positive submodular function maximization: (ii) we de- velop frameworks that transform submodular op- timization algorithms into mechanisms that are IC, IR, NAS, and preserve approximation guaran- tees. These frameworks apply both in an offline setting-where all bids are simultaneously observ- able-and an online cetting-where sellers arrive adversarially and decisions must be made irrevo- cably. We further investigate whether state-of-the- art submodular algorithms can be converted into descending auctions under adversarially chosen price schedules. We show that any algorithm satis- fying a bi-criteria (5. 1)-approximation in welfare can be adapted into such a descending auction. Finally, we demonstrate the practicality of our frameworks by instantiating them with various submodular optimization algorithms and evalu- ating their performance on datasets containing thousands of sellers
Since procurement auctions were introduced the algorith- mic game theory community in the seminal paper of Nisan & Ronen (1999), many aspects of these auctions have been studied, including frugality in procurement auctions for min- imizing purchasing costs (Archer & Tardos, 2007; Karlin & Kempe, 2005; Talwar, 2003), budget-fcasible procure- ment auctions in which the purchasing cost constrained by a budget (Singer, 2010; Kempe et al., 2010; Chen et al., 2011; Bei et al., 2012; Balkanski et al., 2022), and profit maximization for optimizing the auctioneer's 's surplus (Cary et al., 2008). In this paper, we consider the classic setting of procurement auctions with one auctioneer and a group of sellers, W. Each seller has a private cost C; for providing the service, and for each S C N, the auctioneer has a value function fS) for purchasing services from sellers in S. The social welfare obtained from the procurement auction when the auctioneer purchases from sellers in S is given by the difference between the value obtained by the auctioneer and the total cost of sellers in S, i.c., f(S)- - Etes Co.
Part of the work was done while the author was a student researcher at Google Research. 'Google Research 'Yale Univer- sity. Corresoondence to: Yuan Deng <dengyuan @ google.com>, Grigoris Velegkas <grigoris. <szuo@ gooil@ggogc.comm>>
<grigoris.velegkase velegkas @alaseaaalllu.....ae Song Zuo
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Procurement Auctions via Approximately Optimal Submodular Optimization
We note that our objective differs from the utilitarian objec- tive, which maximizes the sum of all agents' valuations, i.e., f(S) + +())+Cigs Ligs Ci assuming seller i has value c; if the service is not sold. Our objective can be considered a measure simi- lar to the gains-foom-trade in the bilateral trade literature, as it measures the additional total value generated by running the procurement auction. This is further motivated by the fact that, in many domains where procurement auctions can be applied, sellers incur costs only after they have been selected to provide service. For instance, when vendor provides goods or services to a company, it is most often the case that they incur costs only after signing the contract and needing to purchase the required materials. Although maximizing gains-fron too---roomrrddae is equivalent to maximizing the utilitarian objective, providing an approximation to the coins-from-trade is considerably harder than providing an approximation to the utilitarian objective. In particular, non-zero approximation to the utilitarian objective may al- ready be achieved without any trade, which would only result in a zero approximation to gains- from-trade
difference between the value obtained by the auctioneer and the total cost of sellers. Our goal is to design mechanism that: 1) is incentive compatible (IC) and individual rational (IR) for each seller; 2) guarantees non-negative auction- eer surplus (NAS); 3) achieves state-of-the-an bi-criteria welfare guarantees; 4) is computationally efficient.
The interpretation of the desired game-theorrtice theoretical properties, i.c., IC, IR, and NAS, is that IR encourages sellers to partic- ipate in the auction while IC prevents strategic behavior and simplifies the sellers' decision-making process. The surplus of the auctioneer is given by f(S) ([S)-Eies ies p: for purchasing services from sellers in S, where p; is the payment to seller E S. NAS is reminiscent of the weakly budget-balanced property under the interpretation that f(S) captures the po- tential revenue generated for the auctioneer through the services purchased from sellers in S. The NAS property is critical for many applications: if the auctioneer is at risk of having negative revenue, they might be incentivized not to run the auction at all. Thus, it is crucial to ensure that our transformations from algorithms to mechanisms satisfy NAS, which requires subtle technical work.
Another major obstacle to studying our objective is that maximizing for f(S) Eies C2 a computationally chal- lenging optimization problem, even when I is mono- tone submodular function. Submodularity captures broad class of functions with diminishing returns, including gross- substitute functions, budget additive functions, and coverage functions. When f is a monotone submodular function, the aforementioned optimization task is known as regularized submodular maximization, expressed as maximizing the dif- ference between monotone submodular function (S) and modular function Eies G as the regularization term. For the special case where G 0 for all sellers, it is well-known that obtaining an approximation ratio better than (1 1/e) requires exponentially many queries to f (Nemhauser et al., 1978). Before a breakthrough result from Sviridenko et al. (2017), many heuristics had been proposed in the litera- ture (Feige et al., 2008; 2013; Kleinberg et al., 2004), but none of them provided provable guarantees that are uni- versal and unconditional. For example, Feige et al. (2013) design algorithms with parameterized approximation guar- antees, where the parameterization may depend on classes of instances and the properties of their optimal solutions. Svirddekko et al. (2017) show a tight bi-criteria (a. :3)- approximation guarantee of the form f(S) - -ies G. 2 f(OPT) B ExcOPT C2 with a = 1 11--1/ 1/e and 3 = 1, where OPT = arg max [(S)) - Eies G4 which rules out the possibility of constant approximation for the welfare objective. Harshaw et al. (2019) developed simplified and practical algorithm, called the distorted greedy algorithm, that achieves the same optimal approximation guarantee.
1.1. Our Results
In this paper, we make theoretical contributions to the lit- erature of regularized submodular optimizations as well as theoretical and empirical contributions to the literature of procurement auctions.
On the submodular optimization side, Harshaw et al. (2019) show that the distorted greedy algorithm satisfies an (1 1/e, 1) bi-criteria approximation guarantee. In Section 3, we demonstrate that the distorted greedy algorithm also satisfies (1-e-8, (1)) bi-criteria approximation simultaneously for all B E [0, 1], which is also almost tight (Feldman, 2021). Using the framework developed in this work, we obtain mechanisms that satisfy the same approximation guarantees for all 3 E [0, 1]. We also extend the results to a setting with noisy function evaluations.
Moving on to the mechanism design side in Section 4.1, from a theoretical perspective, we first show that VCG mechanisms satisfy IC, IR, and NAS, and they are always welfare-optimal, but it is computationally prohibitive im- plement them for practical applications. We then develop a mechanism design framework that can convert state-of- the-art submodular optimization algorithms to sealed-bid mechanisms that satisfy IC, IR and NAS, preserve the bi- criteria welfare guarantees, and can be computed efficiently. Leveraging online submodular optimization algorithms, we extend our framework to the online setting where the sellers arrive in potentially adversarial order and the auctioneer has to make an irrevocable decision whether to purchase their services.
Inspired by recent progress in regularized submodular maxi- mization, revisit the problem of procurement auctions where our objective is to maximize the welfare, i.e., the
2

---

Procurement Auctions via Approximately Optimal Submodular Optimization
In addition to sealed-bid mechanisms, in Section 5 we ask whether it is possible convert submodular optimization algorithms to descending auctions. These auctions were initially designed under the assumption that f is a gross- substitute function (Kelso Jr & Crawford, 1982), which is a subclass of submodular functions. We focus on the adversar- ial setting where the schedule of descending prices is deter- mined by an adversary. We show that if the demand oracle is based on the cost-scaled greedy algorithm (Nikolakaki et al., 2021), the descending auction always achieves bi-criteria (2. >approoximation in welfare, even in the adversarial set- ting. On the other hand, we show that if the oracle solves the demand problem exactly, the approximation guarantees could be arbitrarily bad. We further establish a connection between descending auctions and online submodular opti- mization algorithms, showing that any online submodular optimization algorithm can be converted to descending auction in an approximation-preet preseervnnneeeiinggggg way. Thus, an im- possibility result, showing there is no descending auction that can achieve bi-criteria (a, 1) >aapproximation in welfare with a > 1. implics an impossibility result on online sub- modular optimization with bi-criteria (a, -paaprooximation guarantees for the same a, which is a long-standing open question in online submodular optimization.
maps sellers' reported bids b to vector of payments to each seller. We assume sellers have quasi-linear utilities such that given bid profile b and mechanism M, seller i's utility is given by u. (b) p(b) design a mechanism M that is incentive compatible, individ- ual rational, and induces non-negative auctioneer surplus: A mechanism is incentive compatible (IC) if it is always an optimal strategy for seller to report their private cost truth- fully, i.e., for any seller i and any b, uy(c,, b-i) 2 un (b()); A mechanism is individual rational (IR) if a seller's utility is al- ways non-negative if they report truthfully, i.e., for any seller and any b_i. (c b-.)= 2 0; A mechanism satisfies the non -on-angte auctioneer surplus (NAS) condition the ac- quired value of the auctioneer is at least the total payment to the sellers, i... f(a(b)) 2 Eier (b)),, for any bid profile b. We will refer to mechanisms that satisfy the IC, IR, and NAS conditions as feasible mechanisms. We measure the perfor- mance of a mechanism by its welfare / (a(c)) - Eieate) Gi and let OPT arg maxg J(S) - Eies Ci when the def- inition of f is clear from context. We may also write c(S) = Eies C-- We say that a mechanism satisfies bi- criteria (a, B) appppooxinitooon to the welfare if fa((c) Eiea(e) C 2 max {0, f(OPT) - 3 EEEOPT 0i
1[i E a(b)]. Our goal is to
In Section 6, we complement our theoretical results with empirical studies evaluating the welfare performance and running time tradc-offs of different mechanisms on a cover- age problem. Due to space constraints, the discussions of further related work are deferred Appendix A.
3. Submodular Optimization Algorithms
We first present several submodular optimization algorithms that will be useful for the derivation of our mechanisms, and provide an improved analysis for the deterministic and stochastic versions of the distorted greedy algorithm (Har- shaw al., 2019). We will demonstrate how to convert all the algorithms from this section to NAS, IC, and IR mech- anisms that maintain the approximation guarantees of the underlying algorithms in Section 4.1.
2. Preliminaries
We consider a setting of procurement auctions with one auctioneer and a set of n sellers with items to sell. The auctioneer has a valuation function f : 2 + R2z that specifies the value that the auctioneer assigns to the items of every set S of sellers, where S C A. Each seller e A has a private cost C 2 0 indicating the minimum acceptable payment for selling to the auctioneer. We focus on functions f that are monotone and submodular with f(0) = 0. A function/ f is monotone if f(S) < f(T) for all S WW, and submodular if satisfies the property of diminishing returns: f(i 5) >= [( | T) for all S _ T N and i & T, where f(i ( = f(S
Recall that in the regularized submodular maximization problem under a cardinality constraint, there is a monotone submodular function f : 2 + R20. a cost G, E Rz0 for each element E N, and cardinality constraint k S n. All the algorithms we touch upon in this section, and subsequently in our mechanism design framework, share the same paradigm (Algorithm 1): the algorithm maintains a candidate solution set initialized as S = 9 and in each round k, it assigns a score to each element E W \ S based on scoring function G, which depends on the cost vector e and possibly the round number k as well random seed (for randomized algorithms). The algorithm then adds the element with the highest non-negative score to S.
- f(S) computes the marginal contribution of seller to f. conditioned on S. Throughout the paper, we use bold symbols æ to represent a vector with n elements (I ) and use (a).)) to represent (za, ..)) As usual, we use i to indicate all the sellers other than seller i.
We next describe each algorithm in detail, focusing on the corresponding scoring function G. The bi-criteria guaran- tees of all the algorithms are deferred to Table 1 in Ap- pendix B. To simplify the notation, when we discuss deter- ministic algorithms, we omit referring to the random seed that G could take as input, and we omit referring to the
Let b; be the reported bid from seller i. A mechanism M (a) consists of an allocation rule a : Ry + 2 that maps sellers' reported bids b to subset of sellers to procure the items, and payment rule p: R% + Rg that
3

---

Procurement Auctions via Approximately Optimal Submodular Optimization
round number k input of G when G does not use the round number information.
fact, the cost-scaled greedy algorithm can also be applied the online and adversarial setting in which the sellers arrive in an online manner (such that any decision is irrevocable) and the sequence of their arrival is determined by an adver- sary. In the online and adversarial setting, the algorithm maintains a tentative solution and adds a newly arrived seller to the solution S if and only if f(i 5) - o > 0.
sreedy-margin (Kleinberg et al., 2004). We start with the simplest algorithm. called the grredy-margin algorithm, which is perhaps the most natural approach. This algorithm simply chooses the seller with the largest difference between their marginal contribution and their cost, i.e. the scoring function is given by G(i, Sc = f(i [) - G.
3.1. Improved Analysis of Distorted Greedy
Greedy-rate (Feige et al., 2013). The greedy-rate algorithm chooses the seller that maximizes the ratio of the difference between their marginal contribution and their cost, over their marginal contribution, i.e., the scoring function is given by (i,,S, c) = /((S))=
We now explain the improved analysis we propose for the distorted greedy algorithm. Recall that the distorted greedy score of every element E N in every round - j S of the execution of the algorithm is (1-1)*-
f(i |
[([SS)
S - c , and the element that maximizes it is added to the current solution, provided that its distorted score is non- negative. Harshaw et al. (2019) showed that both versions of the algorithm enjoy (roughly) a (1 1/e, 1)-bi-criteria approximation guarantee, which is tight. We show that, in fact, these algorithms satisfy an even stronger guarantee: the distorted greedy algorithm enjoys (1 - e 3 + o(1))- bi-criteria guarantee for all 3 E [0, 1]. where the o(1) term is sub-constant in cardinality k. A similar result holds, in expectation, for the stochastic version of the algorithm. The guarantee of the algorithm holds sinultaneously for all B E [0, 1), so it does not require parameterization by B.
Distorted Greedy (Harshaw et al., 2019). The dis- torted greedy algorithm shares a similar flavor to the clas- sical algorithm of Nemhauser et al. (1978), but with a slightly distorted objective with a multiplier (1- =)= on the marginal contribution in round E: G(i,S,c,
(1- f(i S) G. It is worth highlighting that this scoring function does not have the diminishing-retum structure and in particular, it does not stop early even if scores are negative for all remaining candidates.
Stochastic Distorted Greedy (Harshaw et al., 2019). In order to speed up the execution of the distorted greedy algo- rithm, Harshaw et al. (2019) proposed a randomized im- plementation of it that works as follows. It runs for n iterations and in every iteration k it draws a seller uni- formly at random from N. Assume the random seed r encodes the selected seller in iteration E via re). Then, we can define the scoring function as G(i, c, k, E) = 1[i r(O). (11- 4) S(i | 5) 5))c;) ..) Harshaw et al. (2019) showed that, in expectation over the random draws of the sellers, the approximation guarantee of this algorithm does not degrade compared to its deterministic counterpart.
Theorem 3.1. Let N be universe of elements, f 2N + Rz0 be monotone submodular function, and c : N + R20 be a cost function. Let OPT be the optimal solution of the objective max II - -Eies (i). Then, the output of the distorted greedy algorithm satisfies (RR) Σjen 9j 2 (1 - e ") ((OPT) (B + 1/k) E Cj. simultaneously all 3 E [0.
The proof, well as the formal statement for the the algo- rithm, are postponed to Appendix B. Our main technical insight is to perform parameterized analysis of the poten- tial function argument of Harshaw et al. (2019) based on the target value of 33 that we wish to prove the guarantee for. In other words, given some 8 E [0, 1), we lower bound the potential function by a 3-dependent quantity. This allows to obtain the stated guarantees for all B simultaneously. A result of Feldman (2021) (cf. Theorem B. shows that our analysis achieves the Pareto frontier of the bi-criteria guarantees for this problem, up to the o(1) term. Details are deferred to Appendix B.
Inturnn-onIInvesmment (ROI) Greedy (Jin et al., 2021). The ROI greedy algorithm chooses the seller that has the largest marginal contribution per unit of their cost among sellers whose cost not exceeding their marginal contribution, i.e. the scoring function is given by G(i, Observe that, ROI greedy is effectively the same as greedy- rate as both algorithms are effectively ranking the sellers in descending order of f(ils) Feige et al. (2013) provide parameterized approximation guarantee for this algorithm while Jin et al. (2021) demonstrate a unconditional approxi- mation guarantee without paying a linear term on f(PPT), which is desirable when this quantity is large.
= f(AS) - es
ey
In Appendix B we present an adaptation of the distorted greedy algorithm that works even when we only have access to approximate version F 2N + R>o of valuation func- tion ʃ such that (1 (S) < F(S) < (1+e)[(S), VS C N (Horel & Singer, 2016). Gong et al. (2023) propose a slight adaptation of the distorted greedy algorithm that per- forms well when = = O(1kk). However, when we convert their algorithm to a mechanism, it is not immediate how to
Cost-scaled Greedy (Nikolakaki et al., 2021). This algo- rithm chooses the seller with the largest difference between their marginal contribution and twice their cost, i.e., the scor- ing function is given by S.c) = f(i | S) - 2 G. In
4

---

Procurement Auctions via Approximately Optimal Submodular Optimization
prove the NAS property, since F might not be submodular, which was crucial property of the function in our later proof of NAS. Thus, we propose modification of their algorithm to overeome this issue (see Algorithm 7). Our main insight is to have the greedy scores of the elements in round t of the execution depend not only on the current tentative solution S,, but on the whole trajectory .,, St. Essentially, this enforces the structure of diminishing returns without hurting the approximation guarantees.
Algorithm 1 A meta algorithm AA = (G) for submodular
optimization
Data: A set of seller .N, a cost profile c from sellers, and a random seed r
Result:
A subset of sellers purchase services from So 0
for k from 1 to n do 1' = arg max G(i, C,,1,
if G S c,, > 0 then
Sk = Sk-1 }
4. A Mechanism Design Framework
end
else
In this section, we develop a framework that is capable of converting the state-of-the-art submodular optimization algorithms to feasible mechanisms for procurement auctions. end return Sn
Sk = Sk-1
end
We first start with the "offine" setting, where all the sellers report their cost to the mechanism designer simultaneously and then we move on to the "online" setting, where the sellers arrive sequentially.
if 6, > f(i | S). then G(i, k.) < for all b_ k. and r; 3) for all i, S with i & S, is and r. G(i, U.,SS. b, k, is independent of b-j.
4.1. Offline Mechanism Design Framework
As a warm-up, we first show that the classic VCG frame- work (Vickrey, 1961; Clarke, 1971; Groves, 1973) provides mechanisms that are IC, IR, and welfare-efficient. It turns out that the VCG mechanisms also satisfy NAS.
We argue that both (1) and (2) of Assumption 4.2 are mild ones and any reasonable meta-algorithm A should satisfy it. For instance, all the algorithms we present in Table 1 satisfy these assumptions. In particular, Assumption 4.2(1) states that the scoring function G should be non-increasing as the reported bid b; increases, which is a natural requirement as a candidate with smaller reported bid is more favor- able. Assumption 4.2(2) states that the algorithm should not pick a candidate whose marginal contribution is smaller than their reported bid. Under truthful reporting, such candidate has a negative marginal contribution in round k towards the social welfare, and therefore, they should not be included to the solution. Assumption 4.2(3) is a stronger assumption, stating that the score for a seller i should be independent of bids from other sellers, but to the best of our knowledge, almost all state-of-the-art al- gorithms satisfy this assumption. In fact, for mech- anism to satisfy the desired properties we can relax As- sumption 4.2(3) to require: for all i, S with i E S, k, and r, for any b, if i of arg max G(i, S. b, k. r), then for any bn > bi arg maxigs G(E, (b/, b k), arg max G(E, S, r)). In other words, as long as seller does not have the highest score, then the candidate with the highest score remains the same. Such a property is similar to non non-bossiness, studied by Paes Leme et al. (2023).
Proposition 4.1. The VCG mechanism satisfies NAS when is a submodular function.
The proof is postponed to Appendix C. Although VCG mechanisms are IC, IR, NAS, and welfare-efficient, imple- menting them is computationally prohibitive. We now move on to describing the computationally efficient framework that transforms algorithms to mechanisms, which is one of the main contributions of our work.
Algorithm 1 provides a meta-algorithm A = GG) for reg- ularized submodular function optimization specified by a scoring rule G, computing a score for a candidate given a subset S, a vector c, the round number k, and possibly random seed r (for randomized algorithms) as input. The algorithm runs for n rounds' and maintains a tentative so- lution set S₁. at the end of each round k. In each round k it calls G to compute a score for each candidate not in the ten- tative solution set Sk-1, and then it identifies the candidate i" with the highest score (where ties are broken lexicograph- ically). If the highest score is positive, Sg = S U { otherwise S S
Assumption&& 4.2. The meta-algorithm A = (G) satisfies: 1) for all and S with & S, G(i, 5, b, k. r) is non-increasing in by for all b_,, 1o and r; 2) for all i and S with i & S,
Given a meta algorithm A specified by Algorithm 1, Al- gorithm 2 first runs Algorithm with the reported bids as input in order to obtain the set of sellers S whose items will be purchased. Then, the payment for each seller i E S* is computed in the following way: we re-run A by raising the bid from seller to infinity and record the intermediate solutions SS, S,, S.)). For
'Ou framework can be extended to accommodate algorithms that stop early without running all the iterations. To simplify the exposition, we let the algorithm run for longer by adding extra dummy rounds.
5

---

Procurement Auctions via Approximately Optimal Submodular Optimization
each Sk, we compute the supremum of the of bids b, 2 0 satisfying i arg max Sx-, b, k and G(i, 1, b, k, r) > O. If such a non-negative bid does not exist, the sup function takes default value of O. Finally, Pa is computed by taking the max across k E [n]]
algorithm and Onn² log [l) calls the scoring function.
4.2. Online Mechanism Design Framework
In this section we shift our attention to the online setting, where each seller i E N arrives online in an arbitrary order and the auctioneer needs to make an irrevocable decision of whether to buy the item or not. For convenience, assume seller k arrives in round k. A meta-algorithm AA' = (G) for online submodular optimization is provided in Algorithm 3, where the scoring function G in round k computes a score for a seller k given a subset S, a vector C(1.)), and possi- bly a random seed r as input. The algorithm maintains a tentative solution S₁. at the end of each round k. In each round k, seller l is added to the tentative solution if and only if the scoring function returns a positive score. From the taxation principle, we can focus on (possibly random- ized) posted-price mechanisms for designing IC and IR mechanisms, i.e., in each round k. the auctioneer makes a take-it-or-leave-it price pk E R20 for seller k. We provide an approximation-pprssevvei
Algorithm 2 A feasible mechanism construction for a given meta algorithm A
Data: A set of sellers N, a bid profile b from sellers, and a meta algorithm A
Result: A subset of sellers to purchase from and a vector of payment to sellers
Generate random seed r if needed or set r = 0
S A(A,brr)
for i E S* do
Run A((oc, b))),r and record ( -,, S
Ps =0 0
for k E [n] do
p: = max sup [b.]G Sk-1, b, r) > =0}
Pt
transformation from online al- ggortthm to posted-price mechanisms in Algorithm 8, post- poned to Appendix C.I. Our main insight is to map the (online) scores to posted prices in an approximation preserv- ing way. The formal proof is postponed to Appendix C.I. Similarly as in the offine setting, we require that the online submodular optimization algorithm satisfies the following mild assumptions.
max (pt, sup {b.li j arg max G(L,Sx-1,
b, r))
end end
return
5t and p
Theorem 4.3. For a meta-algorithm A (G) satisfying As- sumption 4.2, the mechanism constructed using Algorithm 2 is feasible.
Assumption 4.5. The meta-algorithm AA' = (G) satisfies: 1) for all k. S. b(1,k-1) and r, G(k, S, b(I,)).)) r) is contin- uous and strictly decreasing in by: 2) for all k; S, b(1,k-1) and r. by > f(k| | (),, then G(k, S, ((1,)),) r) < O.
The proof is postponed to Appendix C. To show the IC and the IR properties, we make use of Myerson (1981) together with our carefully designed payment rule with Assump- tion 4.2(1) and 4.2(3). It is more technically difficult is to establish the NAS property, where we make use of the sub- modularity property of f and Assumption 4.2(2). It worth highlighting that Theorem 4.3 does not require the scor- ing function G' to have diminishing- return structure, i.e., Gli, S, b.j.r) 2 Gii, T, b, r) for all S C T and j S k; and the distorted greedy algorithm does not satisfy such a structure. With Theorem 4.3, we establish a framework for converting submodular optimization algorithm to a mech- anism satisfying IC, IR, and NAS. In such a mechanism, the sellers are incentivized submit their true private costs as their bids, and therefore, the mechanism preserves the bi-criteria welfare approximation guarantee, which follows immediately from the fact that under truthful bidding the allocations of Algorithm I and Algorithm 2 coincide.
In particular, we drop the counterpart of Assumption 4.2(3) in the online setting, but we additionally require G to be continuous and strictly decreasing to avoid tie-breaking issues so that the equation G G(k, S, (b(1, r) = 0 has unique solution in terms of 2. Theorem 4.6. For a meta-algorithm A = (G) satisfying Assumption 4.5, the online mechanism constructed using Algorithm 8 is IC, IR, NAS, and outputs the same solution as Algorithm 3 under full knowledge of the cost of the items.
As we alluded to before in Section 3, the cost-scaled greedy algorithm (Nikolakaki et al., 2021) gives a (2. - criteria approximation guarantee in the online setting and fits within the template we have provided. Similarly, an adaptation of this algorithm by Wang et al. (2021) gives (8- (8-0/3, 8-afa), 0 < a S B parameterized bi-criteria guar- antees in the online setting, and, interestingly, can also handle matroid constraints. In addition, Wang et al. (2020) provide parameterized bi-criteria guarantees adapting the algorithm from Nikolakaki et al. (2021). In the case of noisy evaluations of the function f, our framework can be applied
Remark 4.4 (Running Time). In Algorithm we need to make at most O(n) many calls to the optimization algorithm in line to compute A A((x, r), i.e., one call for each seller in the optimal solution. Moreover, for each inner loop starting, we need to make Onn log BB) calls to the scoring function where [B] is the number of possible bids. To sum- marize, Algorithm 2 makes (n) calls to the optimization
6

---

Procurement Auctions via Approximately Optimal Submodular Optimization
Algorithm 3 meta algorithm A = =G) for online sub-
Algorithm 4 Descending auction with demand oracle D and a step size of
modular optimization
Data: A set of sellers arriving online and a random seed r
Data: A set of sellers W and bid profile b from sellers Result: A subset 5 of sellers to purchase from and vector of payment to sellers
Result: subset 5* of sellers to purchase from So = 0, k- =0
while there exists newly arrived seller l + 1 with cost
Set the set of active sellers as S = N
C do
Set initial prices as P. = f(a 0)
h +1
while D(S, p) 5 S do
it G(k, Sk-1, ((1,),,) > 0 then | Sk = Sk-1 U {k}
Select an arbitrary seller E S ((S.p)
P: P;
end else
if P4 < by then
S = S\ {i}
Sk = Sk-1
p; p=
end end
end
end
return Sx
return 5and p
to the noise-robust algorithm from Gong et al. (2023), which builds upon Nikolakaki al. (2021).
Descending auctions were initially designed under the as- sumption that f is a gross-substitute function, subclass of submodular functions. In particular, when f is gross- substitute function, the demand oracle that exactly solves the welfare optimization problem can be computed in polyno- mial time; and with such an oracle, the descending auction returns the optimal subset OPT, even if it is executed in the adversarial setting, i.e., where the selection of seller not in D(S, p) for price decrement is determined by an adversary (Kelso Jr & Crawford, 1982; Paes Leme, 2017).
5. Descending Auctions
The mechanism design framework developed in Section 4.1 has a sealed-bid format. In this section, we investigate another popular class of procurement auctions, called de- scending auctions. A descending auction is parameterized by a demand oracle D, that takes set of sellers S S A and vector of prices p as input and returns a subset of sellers D(S,p) C S. The auction maintains a set of active sellers S, initialized to be N. and a vector of prices p, where p; is initialized to be f(i | 0). the highest possible marginal contribution from seller i. In each iteration, the auction calls D: If D(S, p) S. the descending auction ends and returns the current S as the set of sellers to purchase from and p the vector of payment to sellers; If D(S, p) S S, an active seller not in D(S, p) is chosen and its price is decreased by a small step size e. If p; is smaller than by, seller is removed from the active seller set and p; is set to O.
Descending Auctions in the Adversarial Setting, We first show that when f is a submodular function, in the adversar- ial setting, a descending auction may return an arbitrarily worse solution even with the exact demand oracle satisfying bi-criteria (1, 1>-approximation in welfare. The proof is postponed to Appendix D.
Theorem 5.1. In the adversarial setting, given demand oracle 'D satisfying bi-criteria (1, 1--approximation in wel- fare, for any L E N4, there exists a problem instance with L + 2 sellers and a vector of bids b, such that Algorithm 4 with demand oracle D and E < I returns a subset S* with (f(OPT)-EIGOR))
Algorithm 4 provides a classic paradigm of such auctions. Note that the descending auction is always IR since seller is chosen only if the final price p; is at least b, and IC since the reported bid b, is only used for checking whether the current price p. is smaller than 6;. which also enables the implementation without eliciting sealed bids from sellers in which whenever p& is lowered, the auctioneer asks the seller whether they would like to leave the market. This has the appealing property that for the set of the winning sellers, the auctioneer only learns upper bound on their true valuation, instead of their actual valuation, which is always the case in sealed-bid bid auctions. Another advantage of descending auctions is that they satisfy obviously strate- gyproofness (Li, 2017). Moreover, NAS can be achieved if ((D(S.)) p)) - E EiED(S,,) Pa 2 0 always holds.
f(S*) Eies- bj = O .f(())((()))))))))) - ExEOPT bz).
We complement our negative result by designing a demand oracle based on the cost-scaled greedy algorithm of (Niko- lakaki el., 2021), which leads to a descending auction with (1/2, 1) --approximation guarantees. The proof is postponed to Appendix D.
Theorem 5.2. There exists a demand oracle D satisfying
bi-criteria (2. appprrxiiininio in welfare such that, Algo-
rithm 4 with demand oracle 'D and ε > O always returns a subset S satisfying
- b, Z ( -
ΣISOPT b, - ne in the adversarial setting.
Remark 5.3. We remark that our results show a, perhaps, munter-intuitive phenomenon in the adversarial setting:
7

---

Procurement Auctions via Approximately Optimal Submodular Optimization
there are instances in which if we run the descending auction described in Algorithm 4 with the perfect demand oracle we will end up with welfare that is arbitrarily worse than the execution with the oracle based on Nikolakaki et al. (2021). In particular, the family of problems that witnesses the lower bound in Theorem 5.2 shows that for every L > O, there an instance in which the solution S* that we get through the perfect oracle satisfies f(S*) Eies bj 1, whereas the solution S that we get through the ccaled-greedy oracle satisfies f(S)- - Eies b; 2 1./2-1
problem using mixed integer program (MIP) when is relatively small. Figure 1 shows the running time com- parison of different methods and Figure 2 compares the welfare outcomes. In summary, i) VCG computes both VCG allocation and payment; ii) Optimal Welfare com- putes VCG allocation (i.e., the welfare-optimal allocation) only; ii) For Descending Auction (DA) with an unspecified oracle, we implement it with a demand oracle that com- putes the wellare- allocation. We also experiment with Greedy-margin, Greedy-rate, Distorted Greedy, and Cost-scaled Greedy, introduced in Section 3 and their DA variants, In Appendix E, we use an approach, based on lazy implementations of the greedy algorithm (Minoux, 2005), to speed up the computation for both allocation and payment.
From Online Submodular Optimization to Descending Auctions. We demonstrate a reduction from online submod- ular optimization to descending auctions when the selection of seller i not in D(S. p) for price decrement can be con- trolled by the auctioneer. Recall that we have demonstrated that an online submodular optimization algorithm (Algo- rithm 3) that satisfies Assumption 4.5 can be converted to an (online) posted-price auction that preserves the bi-criteria welfare guarantee. As posted-price auctions can be imple- mented by descending auctions with a tailored schedule of descending prices, an online submodular optimization algo- rithm (Algorithm 3) that satisfies Assumption 4.5 can also be converted to a descending auction that preserves the bi- criteria welfare guarantee (see Algorithm 9 in Appendix D). Thus, an impossibility result, that there is no descending auction that can achieve bi-criteria (a,, 1) -)aaprroximation in welfare with a > 1. directly implies an impossibility result on online submodular optimization with bi-criteria (a. 1) -paapooxxint guarantees for the same a, which is long-standing open question for online submodular opti- mization. We leave this as interesting open question.
Running Time by Mechanism and Sample Size
Dasounding Axdieauddeddd (0k)
Ds facelly rorge
(S tod firely
Bicurde tarely
Runding Time por Instance Grad
Bined rragin
Greedyratt
Eyr We Bae
Somple S1z3 In)
Figure 1. Average running time for different mechanisma sms at differ- ent sample sizes n. Both axes are log-scaled.
Running Time Comparison Figure shows the average rumning time for different mechanisms. VCG, Descend- ing Auction, and Optimal Welfare exhibit super-polynomial complexity due to MIP computations, with Descending Auc- tion being the slowest. Greedy- based algorithms demon- strate polynomial complexity, but Distorted Greedy's 's time grows faster due to the absence of a diminishing-return structure, so the approach from Appendix E does not apply.
6. Experiments
In this section, we empirically evaluate the welfare performance and running time trade-offs of various mechanisms on publicly available coverage prob- lem. Our instances constructed using bipartite graph from SNAP (https: /napp.nap...aaa/// stwnsttaoooooo strr.for.... edu/ data tata/wwike k Vooe. html). The graph consists of ap- proximately 7000 nodes representing sets and 2800 nodes representing vertices to be covered by the sets. We consider the value of covering each vertex and the cost of select- ing each set based on the degrees of the corresponding nodes. We define the value of (S) as the sum of the values from vertices covered by at least one selected set, i.e., [(S = EieU,es Uz. To create instances with vary- ing sizes and value-to-cost ratios, for each pair (n, 8), we randomly sample subsets of the sets of size n and scale their costs using x U[s, s²]. We generate 10000 random instances per (n, Since VCG needs to solve exactly arg maxs (S(S) - (i.
Welfare Comparison Figure 2 compares welfare for sam- plc sizes = 4000. Further comparisons are shown in Figure and 4, Appendix E. Instances are grouped by the fraction of active agents, determined by whether their marginal contribution exceeds their cost. This fraction de- creases as the cost multiplier x increases. When feasible to run, DA with optimal oracle outperforms other auc- tions conns-cottaatting our theoretical result that DA can be much worse than cost-scaled greedy in some cases. Across approximation algorithms, direct implementations outper- form their DA variants, with an ordering of freedy-marger Greedy-rate > Scaled Greedy > Distorted Greedy.
we solve the optimization
8

---

Procurement Auctions via Approximately Optimal Submodular Optimization
Normalized Welfare Fraction Active Agents 4000)
13 tirely
DA Covuteed Guedy
Ditinnl creely
Cnadyrragh
Deveyy ofr
traction of Active Agerts
Figure 2. Welfare function of the fraction of active agents for n 1000. Curves correspond to different mechanisms.
7. Conclusion
In this work propose procurement auction setting inspired by the recent development in regularized submod- ular optimizations. Our results enable computational and welfare efficient transformations from regularized submodu- lar maximization algorithms to various types of mechanisms, including sealed-bid auctions and descending auctions, that satisfy several desirable properties such as NAS, IC, and IR. Moreover, have tested our framework on several large-scale instances which showcases its practical appli- cability. An immediate direction is to close the gap be- tween the (1/2, 1) bound of our descending auction and the (1- 1/e, 1) we get in the sealed-bid auction. Another inter- esting problem would be to replace the cost in the objective of the mechanism designer with the payment, i.e., to study an objective of maximizing the surplus of the mechanism designer. It would also be interesting ing auction get the same performance as VCG, when we disregard computational considerations.
if the descend-
Acknowledgements
Amin Karbasi acknowledges funding in direct support of this work from NSF (11S-1845032), ONR (N00014- 19-1- 2406), and the AI Institute for Learning-Enablee Optimiza- tion at Scale (TILOS). Grigoris Velegkas was supported in part by the AI Institute for Learnin--Enable Enabled Optimization at Scale (TILOS).
Impact Statement
This paper presents work whose goal is advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.

---

Procurement Auctions via Approximately Optimal Submodular Optimization
References
Blumrosen, L. and Dobzinski, S. (almost) efficient mecha-
nisms for bilateral trading. Games and Economic Behav- ior, 130:369-383, 2021.
Abernethy, J., Chen, Y., Ho, C.-J., and Waggoner, B. Low- cost learning via active data procurement. In Proceedings the Sixteenth ACM Conference on Economics and Com- putation, pp. 619-636, 2015.
Blumrosen, L. and Mizrahi, Y. Approximating gains-from- trade in bilateral trading. In Web and Internet Economics: 12th International Conference, WINE 2016, Montreal, Canada, December 11-14, 2016, Proceedings 12, pp. 400 413. Springer, 2016.
Agarwal, A., Dahleh, M., and Sarkar, T. A marketplace for data: An algorithmic solution. In Proceedings of the 2019 ACM Conference on Economics and Computation, pp. 701-726, 2019.
Brustle, J., Cai, Y., Wu, F., and Zhao, M. Approximating gains from trade in two-sided markets via simple mecha- nisms. In Proceedings of the 2017 ACM Conference Economics and Computation, pp. 589-590, 2017.
Agarwal, A., Dahleh, M., Horel, T., and Rui, M. Towards data auctions with externalities. Games and Economic Behavior, 148:323-356, 2024.
Cai, Y., Daskalakis, C., and Weinberg, S. M. An algorithmic characterization of multi-dimennional mechanisms. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pp. 4599 2012a.
Amanatidis, G., Kleer, P., and Schäfer, G. Budget-feasible mechanism design for non-monotone submodular objec- tives: Offline and online. In Proceedings of the 2019 ACM Conference on Economics and Computation, pp-
901-919, 2019.
Cai, Y., Daskalakis, C., and Weinherg, M. Optimal multi-dimensional mechanism design: Reducing revenue to welfare maximization. In 2012 IEEE 53rd Annual Symposium Foundations of Computer Science, pp. 130- 139. IEEE, 2012b.
AmazonBusiness.
Government procurement solutions, amazon. com/
2024. URL en/work-wi baark-wwithh wiwt /ws//vveermeet. Last accessed October 2024.
Anari, N., Goel, G., and Nikzad, A. Mechanism design for crowdsourcing: An optimal 1-1/e competitive budget- feasible mechanism for large markets. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 266-275. IEEE, 2014.
Cai, Y., Daskalakis, C., and Weinberg, M. Reducing revenue welfare maximization: Approximation algo- rithms and other generalizations. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Dis- crete Algorithms, pp. 578-595. SIAM, 2013a.
Archer, A. and Tardos, É. Frugal path mechanisms. ACM Transactions Algorithms (TALG), 3(1):1-22, 2007.
Cai, Y., Daskalakis, C., and Weinberg. S. M. Understanding incentives: Mechanism design becomes algorithm design. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 618-627. IEEE, 2013b.
Balkanski, E., Garimidi, P., Gkatzelis, V., Schoepflin, D., and Tan, X. Deterministic budget-feasible clock auctions. In Proceedings of the 2022 Annual ACM-SIAM Sympo- sium on Discrete Algorithms (SODA), pp. 1940-2963 SIAM, 2022.
Cai, Y., Goldner, K., Ma, S., and Zhao, M. On multi- dimensional gains from trade maximization. In Proceed- ings of the 202 ACM-SIAM Symposium on Discrete Al- gorithms (SODA), pp. 1079-1098. SIAM, 2021.
Bei, X. and Huang, Z. Bayesian Incentive Compatibility via Fractional Assignments. In the Twenty-Secone Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011.
Cary, M., Flaxman, A. D., Hartline, J. D., and Karlin, A. Auctions for structured procurement. In SODA, volume 8, pp. 304-313, 2008
Bei, X., Chen, N., Gravin, N., and Lu, P. Budget feasible mechanism design: from prior-free to bayesian. In Pro- ceedings of the forty-fourth annual ACM symposium on Theory of computing, pp. 449 458,558111 2012.
Chawla, S., Immorlica, N., and Lucier, On the limits of black-box reductions in mechanism design. In Pro- ceedings of the forty-fourth annual ACM symposium on Theory of computing, pp. 435 4454444.44 2012.
Bei, X., Chen, N., Gravin, N., and Lu, P. Worst-case mech- anism design via bayesian analysis. SIAM Journal on Computing, 46(4):1428 1448, 2017.
Chen, N., Gravin, N., and Lu, P. On the approximability of budget feasible mechanisms. In Proceedings of the twenty-second annual ACM-SIAM symposium on Dis- crete Algorithms, pp. 685-699. SIAM, 2011.
Bichler, M., Davenport, A., Hohner, G., and Kalagnanam, Industrial procurement auctions. Combinatorial auctions, 1:593-612, 2006.
Clarke, E. H. Multipart pricing of public goods. Public choice, 11(1):17-33, 1971.
10

---

Procurement Auctions via Approximately Optimal Submodular Optimization
Colini-Baldeschi, R., Keijzer, B. d., Leonardi, S., and Turchetta, S. Approximately efficient double auctions with strong budget balance. In Proceedings of the twenty- seventh anmual ACM-SIAM symposium on Discrete algo- rithms, pp. 1424-1443. SIAM, 2016.
Fu, H., Kleinberg, R., and Lavi, R. Conditional equilibrium outcomes via ascending price processes with applications to combinatorial auctions with item bidding. In EC, pp. 586. Citeseer, 2012.
Geng, M., Gong, S., Liu, B., and Wu, W. Bicriteria al- gorithms for maximizing the difference between sub- modular function and linear function under noise. In International Conference on Algorithmic Applications in Management, pp. 133-143. Springer, 2022.
Colini-Baldeschi, R., Goldberg, P. W., Keijzer, B. d., Leonardi, S., Roughgarden, T., and Turchetta, S. Approx- imately efficient two-sided combinatorial auctions. ACM Transactions on Economics and Computation (TEAC), (1):1-29, 2020.
Ghosh, A. and Roth, A. Selling privacy at auction. In Proceedings of the 12th ACM conference on Electronic commerce, pp. 199-208, 2011.
Deng, Y., Mao, J., Sivan, B., and Wang, K. Approximately efficient bilateral trade. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp- 718-721, 2022.
Gong, Q. Gao, S., Wang, F,, and Yang, R. multi-pass streaming algorithm for regularized submodular max- imization. In Combinatorial Optimization and Appli- cutions: 15th International Conference, COCOA 2021, Tianjin, China, December 17-19, 2021, Proceedings 15, pp. 701-711. Springer, 2021.
Dimitri, N., Piga, G., and Spagnolo, G. Handbook of pro- curement. Cambridge University Press, 2006.
Dobzinski, S., Papadimitriou, C. H., and Singer, Y. Mecha- nisms for complement-free procurement. In Proceedings of the 12th ACM conference on Electronic commerce, pp- 273 282, 2011.
Gong, S., Liu, B., Geng, M., and Fang, Q. Algorithms for maximizing monotone submodular function minus modular function under noise. Journal of Combinatorial Optimization, 45(4):96, 2023.
Dughmi, S., Hartline, J. D., Kleinberg, R., and Niazadeh, R. Bernoulli factories and black-box reductions mech- anism design. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 158- 169. ACM, 2017.
Groves, T. Incentives in teams. Econometrica: Journal of the Econometric Society, pp. 617-631, 1973.
Fallah, A., Makhdoumi, A., Malckian, A., and Ozdaglar, A. Optimal and differentially private data acquisition: Central and local mechanisms. Operations Research, 2023.
Han, K., Wu, Y., Huang, H., and Cui, S. Triple eagle: Simple, fast and practical budget-feasible mechanisms. Advances in Neural Information Processing Systems, 36, 2024.
Fei, Y. Improved approximation to first-best gains- from- trade. In International Conference on Web and Internet Economics, pp. 204-218. Springer, 2022.
Harshaw, C., Feldman, M., Ward, J., and Karbasi, A. Sub- modular maximization beyond non-negativity: Guar- antees, fast algorithms, and applications. In Interna- tional Conference on Machine Learning, pp. 6634-2643. PMLR, 2019.
Feige, U. A threshold of In n for approximating set cover. Journal of the ACM (JACM), 45(4))634 652, 1998.
Hartline, J., Kleinberg, R., and Malekian, A. Bayesian incentive compatibility via matchings. In the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011.
Feige, U., Immorlica, N., Mirrokni, V., and Nazerzadeh, H. A combinatorial allocation mechanism with penalties for banner advertising. In Proceedings of the 17th inter- national conference on World Wide Web, pp. 169-178, 2008
Hartline, J. D. and Lucier, B. Bayesian Algorithmic Mecha- nism Design. In the 42nd ACM Symposium on Theory of Computing (STOC), 2010.
Feige, U., Mirrokni, V. S., and Vondrák, J. Maximizing non-monotone submodular functions. SIAM Journal on Computing, 40(4): 1133 1153, 2011.
Hartline, J. D., Kleinberg, R., and Malekian, A. Bayesian incentive compatibility via matchings. Games and Eco- nomic Behavior, 92:401 4290, 2015.
Feige, U., Immorlica, N., Mirrokni, V. S., and Nazerzadeh, H. Pass approximation: framework for analyzing and designing heuristics. Algorithmica, 66:450-478. 2013.
Horel, and Singer, Y. Maximization of approximately submodular functions. Advances in neural information processing systems, 29, 2016.
Feldman, M. Guess free maximization of submodular and linear sums. Algorithmica, 83(3):853-877 2021.

---

Procurement Auctions via Approximately Optimal Submodular Optimization
Jalaly Khalilabadi, P. and Tardos, É. Simple and efficient budget feasible mechanisms for monotone submodular valuations. In International Conference Web and In- ternet Economics, pp. 246-263. Springer, 2018.
Mitra, S., Feldman, M., and Karbasi, A. Submodular+
concave. Advances in Neural Information Processing Systems, 34:11577-11591, 2021.
Myerson, R. B. Optimal auction design. Mathematics of operations research, 6(1):58-73, 1981.
Jin, T., Yang. Y., Yang, R., Shi, J., Huang, K., and Xiao, X. Unconstrained submodular maximization with modular costs: Tight approximation and application to profit max- imization. Proceedings of the VLDB Endowment, 14(10): 1756-1768, 2021.
Myerson, R. B. and Satterthwaite, M. A. Efficient mecha- nisms for bilateral trading. Journal of economic theory, 29(2):265-22 1983.
Nemhauser, G. L.,, Wolsey, L. A., and Fisher, M. L. An analysis of approximations for maximizing submodular set functions Mathematical programming, 14:265- 294, 1978.
Karlin, A. R. and Kempe, D. Beyond vog: Frugality of truthful mechanisms. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'OS) pp. 615- 624. IEEE, 2005.
Nikolakaki, S. M., Enc, A.. and Terzi, E. An efficient framework for balancing submodularity and cost. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1256-1266, 2021.
Kazemi, E., Minace, S., Feldman, M., and Karbasi, A. Reg- ularized submodular maximization at scale. Interna- tional Conference on Machine Learning. pp. 3356-5366. PMLR, 2021.
Kelso Jr, A. and Crawford, P. Job matching, coalition formation, and gross substitutes. Econometrica: Journal of the Econometric Society, pp. 1483-1504. 1982.
Nisan, N. and Ronen, A. Algorithmic mechanism design. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pp. 129-140, 1999.
Kempe, D., Salek, M., and Moore, C. Frugal and truthful auctions for vertex covers, flows and cuts. In 2010 IEEE 51st Annual Symposium Foundations of Computer Science, pp. 745-754. IEEF, 2010.
Paes Leme, R. Gross substitutability: An algorithmic survey, Games and Economic Behavior, 106:294-316, 2017.
Paes Leme, R., Schneider, J., and Zhang, H. Nonbossy mechanisms: Mechanism design robust secondary goals. arXiv preprint arXiv:2307.11967, 2023.
Kleinberg, J., Papadimitriou, C., and Raghavan, P. Seg- mentation problems. Journal of the ACM (ACM), 263- 280, 2004.
Papadimitriou, C. and Yannakakis, M. Optimization, ap- proximation, and complexity classes. In Proceedings of the twentieth annual ACM symposium on Theory of computing, pp. 229 234, 1988.
Lehmann, B., Lehmann, D., and Nisan, N. Combinatorial auctions with decreasing marginal utilities. In Proceed- ings of the 3rd ACM conference on Electronic Commerce, pp. 18-28, 2001.
Qi, B. On maximizing sums of non-monotone submodular and linear functions. Algorithmica, pp. 1-55, 2023.
Li, S. Obviously strategy-proof mechanisms. American Economic Review, 107(1 (11(11)3257-327, 2017.
Rasouli, M. and Jordan, M. I. Data sharing markets. arXiv preprint arXiv:2107.08630 2021.
Lu, C., Yang. W., and Gao, S. Regularized nonmono- tone submodular maximization. Optimization, pp- 1-27, 2023a.
Roth, A. and Schoenebeck, G. Conducting truthful surveys, cheaply. In Proceedings of the 13th ACM Conference on Electronic Commerce, pp. 826- 843, 2012.
Lu, C., Yang, W., and Gao, S. Streaming algorithms for maximizing the difference of submodular functions and the sum of submodular and supermodular functions. Op- timization Letters, pp. 1-25, 2023b.
Sim, R. H. L., Xu, X., and Low, B. K. H. Data valuation in machine "ingriin"ingreedients strategies, and open challenges. In Proc. IJCAI, pp. 5607-5614, 2022.
McAfee, R. P.A.A A dominant strategy double auction. Journal of economic Theory, 56(2):334450, 1992.
Singer, Y. Budget feasible mechanisms. In 2010 IEEE 51st Annual Symposium on foundations of computer science, pp. 765-774. IEEE, 2010.
Minoux, M. Accelerated greedy algorithms for maximizing submodular set functions. In Optimization Techniques: Proceedings of the Sth IFIP Conference on Optimization Techniques Würzburg, September 5-9, 1977, pp. 234 243. Springer, 2005.
Singer, Y. and Mittal, M. Pricing mechanisms for crowd- sourcing markets. In Proceedings of the 22nd interna- tional conference on World Wide Web, pp. 1157-1166, 2013.
12

---

Procurement Auctions via Approximately Optimal Submodular Optimization
Sviridenko, M., Vondrák, and Ward, J. Optimal approx-
imation for submodular and supermodular optimization with bounded curvature. Mathematics of Operations Re- search, 42(4):1 197-1218, 2017.
Talwar, K.
The price of truth: Frugality in truthful mecha- nisms. In Annual Symposium Theoretical Aspects of Computer Science, pp. 608-619. Springer, 2003.
Tang, S. and Yuan, Adaptive regularized submodular maximization. arXiv preprint arXiv:2103.00384 2021a.
Tang, S. and Yuan, J. Submodular optimization beyond non- negativity: Adaptive seed selection in incentivized social advertising. arXiv preprint urXiv:2109 109. 18180, 2021b.
USGPO. Nationwide procurement, 2024. URL https:
//www gpo /ttp////////pppp.o/////////ttot http:///wwoootttoooo--tttt------
agency/serrvcces-for-- forerrvviieeeeo-----e-eeeeeeeeee
nationwide www.eppeent--oooooooooooo
Last
accessed October 2024.
Vickrey, W. Counterspeculation, auctions, and competitive sealed tenders. The Journal of Finance, 16(1):8-3) 37, 1961.
Wang, Y., Xu, D.. Du, D., and Ma, R. Online bicriteria al- gorithms to balance coverage and cost in team formation. In International Conference on Algorithumic Applications in Management, pp. 25-36. Springer, 2020.
Wang, Y., Xu, Y., and Yang, X. On maximizing the dif- ference between an approximately submodular function and a linear function subject to matroid constraint. In International Conference on Combinatorial Optimization and Applications, pp. 75-85, Springer, 2021.
13

---

Procurement Auctions via Approximately Optimal Submodular Optimization
A. Related Work
Gains From Trades vs. Utilitarian Objectives. The objective we study in this work has connections to gains-from-tradd in two-sided market. The seminal work of Myerson & Satterthwaite (1983) showed that even when there is one seller and one buyer there no mechanism that satisfies IR, Bayesian IC (BIC), Budget-Balance, and can extract the full gains- gains-from-tre from-trade (GFT), i.e., the total value generated by transferring the items from the sellers to the buyers. In light of that result, lot of works have focused on relaxing one of these desiderata. Of particular interest are the works that are seeking an approximately optimal solution to the GFT objective. In the case of one buyer and one seller, McAfee (1992) provided an elegant mechanism that achieves an 1/2-approximation guarantee if the median of the buyer's value is higher than that of the seller's. In a similar spirit, Blumrosen & Mizrahi (2016) proposed a approxxxxinnioo for this problem, when both the buyer and the seller satisfy the wawpottoone-haar--aaaaa (MHR) condition. Recently, Brustle et al. (2017) provided a simple mechanism that gives a 1/2-approximation to GFT under arbitrary distributions. Subsequently, Deng et al. (2022) provided a constant approximation to the first-best objective, i.e., the GFT that can be achieved if the agents are not strategic, resolving long- sang-standing open question; and Fei (2022) improves the approximation factor to 3.15. Cai et al. (2021) moved beyond the setting with one seller, providing approximations algorithms in environments with multiple sellers. A different line of work in the two-sided markets literature has focused on the utilitarian objective, i.e., the total value of the buyers for the items that the purchased and the total cost of the sellers who did not sell their items. Lehmann et al. (2001) gave greedy and Fu et al. (2012) implemented it as an ascending auction that
algorithm for this objective that gives a 1 -1ppappppximmaiioo gives the same approximation, when the buyers are not strategic. More recently, Blumrosen & Dobzinski (2021) designed a simple take-it-or-leave-it mechanism for this objective that achieves a (1 1 approximation. (2016) designed constant-facto approximation mechanism that satisfies the Strongly Budget Balanced condition, meaning that all the payments of the buyers are transferred to the sellers. Subsequently, Colini-Baldesche et al. (2020) developed a constant-factor approximation mechanism in the setting with XOS valuations.
et al.
Budget-feasible Mechanism Design. The study of bedget-feasible mechanism design, with an emphasis on procurement auctions, was put forth by the seminal work on Singer (2010) who provided a prior-free" budget-feasible mechanism that enjoys constant approximation when the objective is a non-negative and monotone submodular function. Since then, a long line of work has studied this problem providing better approximation guarantees, relaxing the monotonicity constraint on the objective function and extending the results to even more general classes of functions including XOS and subadditive functions (Dobzinski et al., 2011 I; Chen et al., 201 I; Anari et al., 2014; Bei et al., 2017; Jalaly Khalilabadi & TTardos, 201 8;; Amanatidis et al., 2019; Balkanski et al., 2022; Han et al., 2024). Currently, the best approximation guarantees for monotone submodular functions are obtained by Han et al. (2024), that achieve an approximation factor of 4.3. is worth highlighting that, to the best of our knowledge, none of these works have studied non- non-positive submodular functions.
Reduction from Algorithm Design to Mechanism Design. Our results contribute to the rich literature of transformations from algorithms that operate on non-strategic data to mechanisms whose input is coming from strategic agents. A striking result by Chawla et al. (2012) showed that there is relfare-preserving black-box reduction when the mechanism is required to be truthful in expectation. Since then, a beautiful line of work initiated by Hartline & Lucier (2010) develops mechanisms that satisfy the weaker Bayesian Incentive Compatibility (BIC) condition, instead of truthfulness in expectation. An important tool that all these works (Hartline& & Lucier, 2010; Bei & Huang, 2011; Hartline et al., 201 1; 2015; Dughmi matching. It is worth highlighting that Dughmi et al. (2017) managed to obtain an exuctly BIC mechanism, by introducing novel constructions in the context of mechanism design, such as various Bernoulli factories. In the context of multidimensional revenue maximization, Cai et al. (2012b;a; 201 20:ba;b) developed black-box transformations from algorithms (approximately) revenue-optimal and (approximately) BIC mechanisms
et al., 2017) utilize to establish the (approximate) BIC property is a applica-to-surrogee
Submodular Optimization. The problem of submodular maximization has received a lot of attention in the opti- mization literature. The seminal work of Nemhauser et al. (1978) shows that the natural greedy algorithm gives an 11/e)- approximation to the optimal solution when the submodular function is monotone and non-negative. Later, Feige et al. (2011) designed algorithms that provide constant approximation guarantees when the underlying function is non-negative, but, potentially, non-monotone. Designing approximation algorithms with constant-factor approximation guarantees for general non non-positive submodular functions is known to be hard (Papadimitriou & Yannakakis, 1988; Feige. 1998). The study of the objective f(S) c(S), where f is non-negative submodular function and is linear function, is
"This means that auctioncer does not have any prior information about the private types of the sellers.
14

---

Procurement Auctions via Approximately Optimal Submodular Optimization
commonly referred as regularized submodular optimiaatiarriiimmittiiiii This line of work was initiated by Sviridenko et al. (2017) who designed algorithm that obtains (1 - 1/e)) c(OPT) and showed that this guarantee is optimal. Later, Feldman (2021) and Harshaw et al. (2019) designed simpler and more computationally efficient algorithms that attain the same approximation guarantees. Since then, there has been long line of work studying that problem and designing algorithms that work in the centralized setting, the distributed setting, the streaming setting, and the online setting (Kazemi et al., 2021; Wang et al., 2020; 2021; Jin et al., 2021; Mitra et al., 2021; Nikolakaki et al., 2021; Gong et al., 2021; Tang Yuan, 2021 a;;; Geng et al., 2022; Lu et al., 2023a; Qi 2023; Lu al., 2023b; Gong et al., 2023). It is worth noting that the design of approximation algorithms for bi-criteria objectives has alson been considered in different contexts the past (Kleinberg al., 2004; Feige et al., 2008; 2013).
B. Omitted Details from Section 3
Table I. Instantiations of Algorithm 2 with different submodular optimization algorithms.
Algorithm
Approximation Guarantee
Greedy-margin
No Worst-Case Guarantee
(Kleinberg et al., 2004)
Greedy-rate
Parametrized Guarantee
(Feige et al., 2013)
Distorted Greedy (Harshaw et al., 2019) & (this paper)
(1- e 8) f(OPT) - (B + ( for all / E [0,
Stochastic Distorted Greedy (Harshaw et al., 2019) & (this paper)
(1- (1)
- (()
for all / E [0, 1] (in expectation)
ROI Greedy (same as Greedy-rate)
f(OPT) (1 + In ((PT)) c(OPT)
(Jin et al., 2021)
Cost-scaled Greedy (Nikolakaki et al., 2021)
1/2 f(OPT) c(QPT) (online and adversarial)
B.1. Deterministic Distorted Greedy Algorithm Analysis
Algorithm 5 Distorted greedy algorithm (Harshaw et al., 2019)
Data: A set of n items N, a monotone submodular function f f: 2 - Rzo. a cost function c: V + Rgo. a capacity
constraint S n Result: subset of the items R C N with |S| S So 0 for j from to k do
C,,
(1 (1-1) f(i Sr-1) G. Vi E S arg G(i,, S1-1 if
-,,",,,-,,,,,,,)
G(i S, = S--1 Uf7)
then
end
else
Sy Sj-1 end end
return S,
In this section we extend the results of (Harshaw et al., 2019) that obtain a (1 - -e-1,1) 1) bi-criteria approximation guarantee (1 e- -,3) guarantee, where 3 E [0, 1]. First, we recall a negative result from (Feldman, 2021).
Theorem B.1 (Feldman,, 2021)). For every 3 e [0, 1], E > 0, no polynomial-tinn time algorithm can guarantee (1 (1-e -1 B)- bi-criteria approximation for the problem max (S)) Eies 0:).
15

---

Procurement Auctions via Approximately Optimal Submodular Optimization
We underline that Feldman (2021) proposes algorithm that achieves an (almost) matching upper bound, however the algorithm works using the continuous multilinear extension of the underlying function, which is quite con-practical and does not fit our mechanism design framework. We propose approach based the distorted greedy algorithm of (Harshaw et al., 2019) that achieves this guarantee for every 8 E [0, 1]. Formally, we prove the result stated in Theorem 3.1.
We reiterate that Theorem 3.1 improves upon the guarantees stated in (Harshaw et al., 2019) since achieves optimal bi-criteria guarantee simulataneously for / E [0, 1]. Following (Harshaw et al., 2019), we define the following functions
k-t
(x(T) = (1
S(T)
Σ cj.
NTNN,
JET
(1
(-++11
V. V. max 0,
1
[(iTT)
VT CNNINN
The next result from (Harshaw et al., 2019) describes the connection between these two quantities. Lemma B.2 ((Hrrhhww et al., 2019)). In each iteration t E {O....,k 1} of Algorithm 5 holds that
k- 1-+++)
P (S41)) -
Vr 4n + 1:
f(S.).
The next result of (Harshaw et al., 2019) relates the marginal gain in each iteration of Algorithm 5 to the function (r 4)) Lemma B.3 (HHarshaw al., 2019)). In each iteration of Algorithm it holds that
1 k (++1)
1 (S(OPT) ((S.)) - (OPT)
i., 2
R:
Finally, we will make use of the following simple technical result. Proposition B.4. For any E N [0, 1] it holds that
1 1
1 3.n
21 -
-
n
Proof. We have that
1 1 (1 1) x-n
F.
1
(Simplify denominator)
n
1
11
1
Zin
(1 1-r5e"
Equipped with the previous results, we are ready to prove Theorem 3.1.
Proof of Theorem 3.1. By definition (n(-), (.(()) we have that
(S,) = (1-2) Tc S(() - c(0) = 0,
and
(S+) 1 f(Sx) c((s)) =((S)) c(Sx).
Notice that (St) ( Σ
k-1 (S+1() (S.).. By Lemma B.2 it follows immediately that P (S++1)
(S.)) 2 0. Moreover, by Lemma B.2 and Lemma B.3 we have that
1 1.
(
1
(1+11
T ( (S.)) - (.(.., +
1
f(S.)
(Lemma B.2)
K
16

---

Procurement Auctions via Approximately Optimal Submodular Optimization
(-(++1
2 k
(S(OPT) - f(S.)
k
(
1 k-((+1
c(OPT) + k
1
f(S))
(Lemma B.3)
k
k-(++)
1
1
S(OPT)
(OPTT
(Rearranging terms)
k k:
First, assume that 3 is multiple of 1/k. We lower bound the first l: B k terms of Ei= 1 - +b,(S)) by 0 and the last 3 & terms by the previous inequality. Thus, we get
- -(((5))
Σ
D1t1 (S(t1)
- (S,
t=
8-k
k-((+1)
1 S(OPT) - (PPT))
1= B-k
k-(++1
Σ K
S(OPT) .....cc000 c(OPT)
k
1= 9-k
1 1 - (1- T.
3.k
f(OPT) 3 ((PTT)
(Sum of geometric series)
k (- k)
2 (1 - e p) - -0(O/)((PP)))) - c(PPT.
(Proposition B.4)
In case 3 is not multiple of 1/k, the same analysis goes through with / being the smallest multiple of 1/k that is greater than B and the guarantee we get (1 0 ,), which at least (1 - e-0, 8
, 1/k).
B.2. Stochastic Distorted Greedy Algorithm Analysis
In this section we shift our attention to the stochastic version of the distorted greedy algorithm (Harshaw et al., 2019), which requires fewer oracle calls to the function f(-) than its deterministic counterpart.
Algorithm 6 Stochastic distorted greedy algorithm (Harshaw et al., 2019)
Data: A set of n items N, monotone submodular function f 2-V - Rzo, a cost function N + Rgo, a capacity constraint S n, an error parameter >
Result: subset of the items R C N with |.S] <
So = 1 [ log 11 for from 1 to le do
By sample elements uniformly and independently from Ω C(i,,)),,,.,,,)) (1- =)²-3, 1(1 ( 1 -c, Vi arg max;es; 1,EB, G(i, S,-1, c,j.r) if G(i (,-(",,)-,,,,,))) > 0 then
B; S, = 5 U(
end
else
S, = S
end
end
return S,
first state some results from Harshaw et al. (2019) that will be useful our analysis.
17

---

Procurement Auctions via Approximately Optimal Submodular Optimization
Lemma B.5 (HHarshaw al., 2019)), In each step of Algorithm 6 it holds that
(1
1 2
1
(++1)
1 k c(OPT)
E +)] (1 E)
1
(S(OPT) - B(((())))
Notice also that have the trivial lower bound (S,, 1n) 2 O. We are now ready state and prove our main result in this subsection.
Theorem B.6. Let Af be a universe of elements, f 2 + Rzo be a monotone submodular function and e: N - Rgn be a cost function. Let OPT be the optimal solution of the objective maxscN.iSIs*([(S)) Eieg Then, the output R of Algorithm 6 satisfies IE [((Rt) ([(R)->EER'' cs| 2 (1- -e () (3 1/k) ΣjEOPT Cj. simultaneously for all 3 E [0,
Proof. By definition of Po(-), (x(+) we have that
E[(o( = (1 -11-1) :1 -f(0) - c(0) = 0,
and
0 . -((S) c(S&) [[(((k)) c(Sx)]
([+) =
K:
Notice that, by linearity of expectation, [Sp) Do(S))] Ei 1l (8(+1) (S)). By definition of W follows immediately that E[ (S++1) - (S.) 2 0. Moreover, by Lemma B.2 and Lemma B.5 we have that
1
1 (1-1)
(e+1)
E| (S.41) +.((s)) = E (r(( ie)
S(S)) (Lemma B.2 and linearity of expectation)
1
1
k-(++1
1 k (f(OPT) - B[f(S))) ((OPT)
2
-1
1
k
k
1-+11
1
1
[[f()))
(Lemma B.3)
k
k
2 (1 (e
1
1
(1
1
1 (-(++)
1 S(OPT) c
Te
K
(--1-1
8
1 1
[[f(S:)
(Rearranging terms)
k
k.
1k (11k)
1
1 k-(++1
1 f(OPT) c(OPT)
2 (1 c)
(Non-negativity of f)
k
First, assume that 3 is a multiple of 1/k. We lower bound the first - B terms of E/= E[ (Se+1) - +.(S)) by 0
and the last B & terms by the previous inequality. Thus, we get
E 21044 - +.((s)) 2
E El0141(S(+1) (S:)) (S.)
t=k B-le
k-1
Σ
(1 (1-6) 5)
1 S(OPT)
T (
k
(++11)
1
2 61
1
S(OPT) 3. c(OPTT
3-
(Non-negativity of c)
ho
Te
IIn fact, holds for the realization the random variables and not just expectation.
18

---

Procurement Auctions via Approximately Optimal Submodular Optimization
1 - 5 1 (1 x)) 3-k
k 1 1- (1- F(OPT) B c(OPT)
(Sum of geometric series)
2 (1 - e) - E - ((OPT) 3
(Proposition B.4)
In case 3 is not a multiple of 1/k, the same analysis goes through with being the smallest multiple of 1/k that is greater than & and the guarantee we get is ((1 c1 - e )))), which is at least ((1 =) e -))), 1/k).
B.3. Noisy Setting
Following the model of Horel & Singer (2016), in this section discuss adaptations of our results to the noisy setting
where we have access to an oracle F 2 + 2z0 that
(1 f)f(5) - F(S) S (1+ (1) C
for some & > O. Our Algorithm 7 is an adaptation of Harshaw et al. (2019) and Gong et al. (2023) with the main difference being that when we evaluate the score of an element we look its minimum marginal contribution across all the sets we have constructed in the history of the execution. This because the function F is not submodular.
Similarly in the noiseless setting, let
(T) (1-1) (1-k) k.
1
F(T) JET
Σen cj+
VT
(T, = max { 0.
(1-
(1-
1
k- (++1)
min F(ilS) - x G ajj
VT
k
SET
Algorithm 7 Noisy distorted greedy algorithm
Data: set items N, a monotone submodular function f 2 + R20. a cost function c: / + R20, a capacity constraint S n, a cost parameter æ Result: subset of the items R [ N with |S| k So 0 0 S. = So for j from 1 to 1 do
G(i,S)-1,
= (1 [1= R-3 minises P(i) S(-1) x c. Vi S i = arg max,gs_-, G(i, S,,,, if
> 0 then S, = S ( = S
end
else
- S S = S
end
end
return S,
The next result describes the connection between क, v. Our proof is an adaptation of Harshaw et al. (2019); Gong et al. (2023). Lemma B.7, In each iteration E (O...... 1} of Algorithm 7 it holds that
1 k-(++)
(S+4)) - - 2 V, 12) + K K
F(S.).
where S, = (So,..... S.).
Proof. By definition we have that
(141(1141) - = (1 (1-1) k.
1 (-(21) F(S.+1) -c(S+t))
(1-1)
1 k-t
F(S.) - c(S.)
k:
19

---

Procurement Auctions via Approximately Optimal Submodular Optimization
k F(S - -c((t1)) - (1 (1- k
k-(++1
1
R- (t+1)
(1 (1- (1-k) k
F(S.) - c(S))
k-(H2]
1 k-(++)
(F(St-1) - F(S.)) - (c(S(+1)- -
+ 1 k
1 (1- k
F(S.).
k
Now we consider two cases. If Sc+1 = St then (SS,, in) - 0 and the inequality holds. Otherwise, we have
(1 (1 k
1 k-(++1
1
k-(++1
+ - c(Sa)) (F(SH+1) - - -
F(S.)= =
K
(-+1+
k-(++1
(1-7)
1
1
F(ig[S;) - cs. +
F(S,) 2
K
k
k
k- (-(+1)
k-(++)
min
F(i (S) - cs2 + k
1
F(Si)= =
k
15/5t
k)
k-
1
1
(,(,,, +
F(SI).
h
ko
The next result relates the marginal gain in each iteration of Algorithm 7 to the function US 4t). It builds upon the approach of Harshaw et al. (2019); Gong et al. (2023). Lemma B.S. In each iteration of Algorithm 7 holds that
1 k-(++)
1) k-(++1
V. 44) 2
1-
((OPP))-(SS.)) -2s (1- k
T f(S))
K: (OPT).
k
K:
Proof. First, notice that
F(S) = F (i)) -
-)
(1)
Let OPT be the optimal solution of maxs(J(S)- c(S)). We have that
1-(++)
b (S,, it) max
{
(1.b
1011-11
1
min F(ir - x C3 SES;
(Definition)
K
2 k (1
(1-
1
k- 1-(11
min SirlS) x Gi
(Restricting max)
1:
SES.
k (1++)
1
k max TEN
1
min Fil()) x {j
(Definition)
Ke
SES:
d- (1+11)
|PPT|
max iEN
min F(i]S) x x4 SES.
(k Z |OPT)
(1+1)
1
OPPT|
max :COPT
1
min F(i(S) - x x.C SES.
(Restricting max)
k
(-+++)
min F(iSS) - x cs
(Averaging argument)
SES,
k-(++)
1
1
F(iSSt) - x.CG. Cs
(8 arg min F(i[S))
PEOP
k
Ses.
k-(++1
1
(1-=)) (T))()) - -2f((")) - x G.
(Equation (1))
k
(COPT
20

---

Procurement Auctions via Approximately Optimal Submodular Optimization
k-(+1)
((--))(i(ss) - -2 - x . cs
(Submodularity of f)
k.
1EOPT
1 k-+11)
(1 (1=s))(((s.) 28 (1- 1 k-((+1 f(Sx) x
(Monotonicity of f)
k
iCOP
We will bound each term of the summation separately. Notice that ΣiEOPT
c(OPT). Similarly,
ExCOPT 2s (1 - 1)²²7)) (++1)) f(Sk) 2s f(s) & fekf(Sk), and by the submodularity and monotonicity of we have
Σ (1- 2 (1 E) (f(S, UOPT) - f(S.) 2 (1 - (f(OP) - f(S)))
SEOPT
Putting everything together, we get
(S,, it) 2 -)
(1-T)
1 (1+11
(S(OPT) ((SP)))-((s))) -2sk (1-
1
k-
-(Ss) - Ic(OPT),
1:
and dividing by k we get
(1 1 1-(++)
(t+11
()) 2 1-E E
(S(OPT) - ((S)) -2s
1
1
f(Sa) (0(OPT).
k
k
k.
We are ready to prove the bi-criteria guarantees of Algorithm 7. Our analysis follows Harshaw et al. (2019); Gong et al. (2023). Theorem B.9. For 1 + 22k Algorithm 7 returns set Sy with
1
f(Sx) - c(St)) 2 1 2ck +
(1 (1-1/0) (1-1/0) - c(Szt)
Proof.
Combining Lemma B.7 and Lemma B.8 we immediately get that
$
(S
(S.)) 2
k-(1+1
U. it)
+
F(S.) Z
1
k- (1+1)
1)
k-(++1
1
1 1)
k-(++)
1
(f(OPT) f(S.))
1
f(St) ((PT)
+
1
F(S:) 2
k
k
k
k.
1-E
1
1
k- (++1)
(F(OPT) f(S.)) 2s
1
1
k-(++1
f(Sa) (OPT)
1
1
1
1
k-
(++1)
f(S.)
k
(-++1)
k-(++1)
1 1-8
1
f(OPT) - 1 1
1
f(Sk)
=((OP).
k
k
Moreover, notice that straightforward bound is
(S 2 0.
By definition of + we have that
1)a K
1
F(0) xc(()
k.
1
(A(a))= =
1
F(St) xc(St).
k.
21

---

Procurement Auctions via Approximately Optimal Submodular Optimization
Combining the previous inequalities we get
F(Sx) xc((s))
(x((k) (So)
Σ (S.) (
(-+++)
k-(++1
1
f(Sa) k d(PPT)
- k
S(OPT) - - 1 (1 k
h
1=1
(++++
1 1 k-(++1)
1
1 1 k.
S(OPT) - 22
Σ
f(Sx) c(OPT)
k
i=1
1-E
k. (1 (1 - 1/4))) S(OPT) - 26h (1 (1 - 1/1b*) f(Sa) - x d(OPT)
h
which implies that
(1 ++)))(()))zo() (0(
(1 E) (1 (1 1/k)²* S(OPT) 2ck (1 (1 1/b)** f(Sx) =c(OPT)
2 (1 - E) (1- - 1/b))* f(OPT) 2ck f(S)) zc(OPT)
and rearranging get
(1 + 2ck eS,(S)) - xx((Sx) 2 (1 E) (1-1/h) S(OPT) - (OPT)
2 (1 ( f(OPT) zc(OPT).
Finally, we can simplify x = 4 2ek: + e and get
1-6
f(Sa) - c(Sa)
2 c((w)
(1 - 1/e) - c(Sa).
1 2sk +
Remark B.10 (IC, IR, NAS in the Noisy Setting). We remark that our modification in Algorithm enforces the diminishing returns property in the scores of the elements that are added to the constructed solutions. Hence, an identical argument to the one we used in the proof of Theorem 4.3 shows that the NAS property is satisfied. The IC, IR properties continue to hold since they are not affected by the submodularity the function.
C. Omitted Details from Section 4.1
Let ObT(b) arg mag f(S) Eies C₁2 i.e., the optimal solution to the optimization problem when sellers report bids b. Given a bid profile b, the VCG mechanism purchases items from the sellers in OPT(b) and the payment p; each d E OBT(b) is given by
)
Pi (F(OPT(G)
)-(((PT(((S,B0))))
Cj )
Σ tj
Σ
JEOPT(O))
JEOPT ((o,b(()))_)))
Proof of Proposition 4.1. We would like to show (OPT(()) 2 EicopT P: when f is a submodular function.
(OPT((o)))
Σ P: = Σ (EOPT(6)
f(OPT(b))
Σ
Σ JEOPT (1o)
Cj
(EOPT(b)
jEOPT(biR(s)
Σ (EOPT(
f(OPT(b))
Σ
F(OPT(() \ (i1)
Σ Cj
C3
SEOPT(O)N
JEOPT(O)
22

---

Procurement Auctions via Approximately Optimal Submodular Optimization
E S(OPT(b)) ((OPT() \ (i))
()))
$ ((OP((b)
where the first inequality uses the fact that OPT((oc, arg sagss f(8) - -jes oj and the second inequality follows the property of submodularity.
be the intermediate tentative solutions of running Proof of Theorem 4.3. Fix b-; and r, and let { { ,.: } A(N, (b;, r)). Moreover, let Pi. maxisisk 83 where
2210= i arg arg max (2, (2,bb.))..r) & G (2, > 0 1457
2j = sup 2
We will show that for any i, b-s, r, and k: (1) b, < <,,, E Sh and if b, Pa i & S (f prove it by induction on k. When & = from Algorithm 1, the definition of pr,,, and Assumption 4.2(1), we have
if & sh S = We
when by P,,,, then S {i) since i arg max, G(C,0, 0, (hi, b,,,
when b; Pi,1, with fj arg max G(e, 0, (b. b-.), 1),, if G(ei, U, (b,, 1.)),,1r) 0, S {(f): otherwise,
shh =
Moreover, notice that whenever i # Lt i's bid becomes irrelevant due to Assumption 4.2(3) so that
arg ? G(e, 0, (o,,b,)),,,))
and therefore, i $ St. Sh = -f. For the inductive step, we assume the previous arguments hold for all rounds up k. Then, for round k + 1, we have
when by < Pt,++, then either we have i E S c shi or we have S = Sg which also implics E S since = arg maxigsy G(e, (b,, b..), le + 1,r) and G(i, St (b,, b i), k + 1.r) > O;
when b, > Pt,k+1, with f+ arg max G G(t, (k, (b,, b d. k+ + 1,r), if G( Sp (b,, i), b) +1,) > 0. $hi = S (l otherwise, sh+1 =
Again, notice that whenever i + l i's bid becomes irrelevant due to Assumption 4.2(3) so that
4+1 arg max G(i, (00, b).), 1,r):
Egst
and therefore, i & St: kk+1 Shi = St+1. which concludes the inductive step. Observe that Algorithm exactly computes the critical bid p; = Pi.n for seller such that if Pi... i S* and if 6; > Pi.. i & S*. From Myerson's 's lemma (Myerson, 1981), the mechanism is IC for seller i. Moreover, the mechanism is IR because i E S" only if c; = b, S Pi.. when seller i reports truthfully.
Finally, to prove the mechanism satisfies NAS, assume seller i is added to the solution in round such that S \ S = {i}. From Assumption 4.2(2), have b, I f() f(st-)) in order to have a positive score for in round k. As have established that if b; < Pi then i E shi we have pi < by < ((S ) - f( For j 2 k; we have
2G & f(i 1)-1 due to the fact that G(i, S,,,,,J111 b, r) < 0 whenever by > f(i s 1) from Assumption 4.2(2). From the previously proved fact that if & Sh: 1 1 S we have Sh: C 5T for k by submodularity of f. As result, for j > k we have that
2 S111
(S 2 f(i = - f($t-1)
23

---

Procurement Auctions via Approximately Optimal Submodular Optimization
which implies that ps max (Pi,--1, max S ((S -(
Thus,
E
f(s)) f($ ).
iES
k=
C.1. Omitted Details from Online Mechanism Design Framework
Algorithm 8 A posted-price mechanism construction for given meta algorithm .
Data: set of sellers arriving online and a meta algorithm AA
Result: subset of sellers to purchase from and vector of payment sellers Generate random seed r if needed
So = 0, =
while there exists newly arrived seller k + do
Let pı be the unique solution of the equation SA-1, Sk-1, (C(1,k-1); 2), = 00 terms of &
Post price P& seller k
if Seller k accepts the posted price then
S Sk-1 1 U [k}
Pk = pk
end
else
S Sk-1
Pk
end
end
return Sy. and p
Proof of Theorem 4.6. The IC and IR properties follow immediately from the fact that the mechanism is posted -asced-price mechanism, such that seller & accepts posted price P& if and only Pk c* 4. From the definition of P& and the monotonicity of G from Assumption 4.5(1), we have S Algorithm 3 return the same solution if sellers always best respond to the posted prices.
if and only if ce Pk. and therefore, Algorithm 8 and
Finally, we prove for NAS. For seller k E S*, from Assumption 4.5(2), we have
p S f(k] Sk-1) f(St) f(Sx-1).
Thus, summing up over all sellers in S", we have
Σ
S Σ - =
KES*
KES-
D. Omitted Details from Section 5
Proof of Theorem 5.1. We construct an instance with L + sellers, indexed L,,,,.,,,,+,,,4 with a submodular function f such that: if [L + 1, L + n = 0, f(S) = JS]; otherwise, f(S) L. Moreover, let b, = -1/L for i < L
and b = b = I 2. We next describe the strategy of the adversary for selecting seller E S (P(Sp)) in line 4 of Algorithm
First, the adversary keeps selecting a seller j {L + 1, 2} until either PL+1 < 1 or PL+2 L This achievable since if (L + 1, L + 2) C D(S, p), the welfare is most L - 2 x (L 1) < 0, so that the approximation
FFor simplicity, we assume that seller does not accept the offer when the cost exactly the same as the posted price.
24

---

Procurement Auctions via Approximately Optimal Submodular Optimization
guarantee is violated. Without loss of generality, assume that PL-+1 < and therefore, the welfare of selecting seller L+1 alone is f([L+ PP++1 > 1.
Next, the adversary iterates over sellers from seller 1 to seller L such that for each seller i, keep selecting the seller i until i leaves the market, i.e., < by. We argue that the above process is achievable as the welfare of selecting any subset containing seller is at most 1.
The final welfare is at most 2 by purchasing items from either seller L + or L + However, the optimal welfare obtained by purchasing from sellers {1.-.., ,.,, which gives welfare -- 1.
Proof of Theorem 5.2. The (3. -aaaprooimetee demand oracle D we construct maintains a tentative solution S initialized at S = 0. For each iteration, let i be the candidate selected by the adversary in the previous iteration. Update S S (i) if f(i I S) > 2p: (otherwise, keep S as it is), and return S. Let S* be the subset returned by the Algorithm 4 with demand oracle D. For each seller i E S", let fs and S; be the price ps and the tentative solution S maintained by the demand oracle right before i is added to the solution, respectively. For seller i & S let P. and S; be the price pj and the tentative solution maintained by the demand oracle when is removed from the descending auction, respectively.
Let g(S) = ((S) - 2. Eies bi, which is also submodular function. For any seller E OPT \5"
gii 5*) f(il (*) - 2- s S() 2
where the first incquality follows b, = S i. b; for i o S and the second inequality follows the fact that f(i S*)) s f(i S.) s 2 (p: + s). As result, we have
29 2 10PT \ 1
Σ
g(i ((|5)) 90 g(5")
1EOPT)S
(J(S UOPT) - f(S*)) -
by i
2 F(OPT) - -(S5) 2- Σ bis
1EOPT
where the second inequality follows submodularity of g. Rearranging, we obtain
f(S") 2 S(OPT) - 2. Σ
4 22 1 8*1 2 S(OPT) - 2. Σ
b. - 2ns.
1EOPT
iCOPT
Observe that we have
S(S") 2. Σ b, Σ
f(i -.
Σ EES-
f(i S.) - 2 po 2 0,
VE
S
where the first inequality follows P.: 2 b, for i S* and the second inequality due to i E 5* and the definition of á. and Sc Therefore, have Eies- b, S [(S*), indicating S(S*) Eies- bi 2 f(S*). Putting everything together, we have
1 S(OPT) Σ b; - ne.
S(S*)
Σ YES
b 2 2
S(S*) 2 2 1EOPT
E. Omitted Details from Section 6
Heuristic Implementation We provide heuristic to optimize the running time of Algorithm 1 if the scoring rule of meta algorithm A = (G') has a diminishing-rrttum structure, i.e., G(i, S, b, j.j.r) r) 2 G(i, T, b, k) for all S C and j < k. In particular, inspired by the lazy implementation of the classical greedy algorithm (Minoux, 2005), we maintain priority queue that records each candidate's 's last-updated score. The priority queue is initialized consisting of elements with key i and value G(i 0, c, 0, r) for each i E N. For each iteration k we repeatedly compare candidate i with the highest score in Q and candidate i with the second-highes score in Q. If G(i,, S, c, k, r) for the tentative solution S is positive and
25

---

Procurement Auctions via Approximately Optimal Submodular Optimization
"wogheaaap Normalized Welfare by Fraction of Active Agents to 100)
Normalized Welfare by Fraction Active Agents in 200)
Greek)
decuute cieadyy
Srunly
Fodtion of As Agents
hacion of Acliec Agort
(a) n2 100
(b) 72 200
ized Fraction Active Agents
Desernt 2MC
an Crempomene wore's
ot Creecyomn
Paction Active Agerts
(c) 500
Figure 3. Welfare function of the fraction of active agents for n 200,,200,
26

---

Procurement Auctions via Approximately Optimal Submodular Optimization
Normalized Welare by Fraction of Active Agents 1000)
Normaized Welfare by Fraction of Active Agents in 2000)
DA Greal)
DK Decuted bieely
fronly
hodton of Act Agents
Nacion of Acliec Agora
(a) 72 1000
(b) n = 2000
Normalized by of Agents
DK Crudwvens
Demy
Actios Agents
(c) 4000
Figure 4. Welfare as function of the fraction of active agents for E (1000, 2000, 4000).
27

---

Procurement Auctions via Approximately Optimal Submodular Optimization
Algorithm 9 Descending auction construction for given meta algorithm A and step size of
Data: set of seller and a bid profile from sellers
Result: subset S of sellers purchase from and a vector p payment sellers
Generate random seed r if needed set 0 Sg 0 Set initial prices p. [(i () for k from 1 to do
Let P& be the unique solution of the equation G k, Sk-1, (C(,A-1);2)) in terms of Update ph pb: if
Pk: > b. then
S = Sk-1 \ {2}
end
else
Sk = Sk-1 Ph =
end
end
return S and
larger than the iz's 's score maintained in Q, then i is guaranteed to have the highest score due to the diminishing-retuus structure; otherwise, update the score for i and repeat (see Algorithm 10 in Appendix). The running time the payment calculation in Algorithm can be optimized in a similar way (see Algorithm 11 in Appendix for details). Note that the scoring rules of all deterministic algorithms presented Table have a aoninishinngreturre structure, except for the distorted greedy algorithm.
F. Faster Implementations of Algorithm 1 and Algorithm 2
We present the algorithmic descriptions of faster implementations of Algorithm and Algorithm 2 when the scoring rule of the meta-algorithm has a diminishing-retur structure.
Algorithm 10 faster implementation of Algorithm 1 when G has diminishing-retun structure Data: A set of seller N, a cost profile c from sellers, and a random seed r Result: subset of sellers to purchase services from So = & Initialize an empty descending-ordes priority queue Q for ifrm 1 to n do
Insert an element to Q with key and value G(i,, 0, c, O,))
end
while k < n do
Pop the highest score candidate i* from Q while True do
Let the highest score from Q be s* (without popping the candidate) if Sk,,,,,, c, + 1,r) max(0, s*) or
8* < 0 then
Break
end
else
Pop the highest score candidate jL from Q Insert an element to Q with key i and value G(i", Se. c, k + 1,r)
end
end
if G(i,, Sz, c, k + 1,r) > then
Sk+1 Sx (i) k= +1
end
else
break
end
end
return S₁
28

---

Procurement Auctions via Approximately Optimal Submodular Optimization
Algorithm 11 faster implementation of Algorithm 2 when G has diminishing- structure
Data: A set of sellers N, bid profile b from sellers, and a meta algorithm AA
Result: subset of sellers to purchase from and vector of payment sellers Generate random seed if needed or set
S A(N, b, r) computed using Algorithm 10 and record the intermediate
solutions {Sa, S, .5} for from K do
i Sx \ 1. To Sg-1, and j 0 Initialize empty descending-order priority queue Q for e E Sg do Insert an element to Q with key and value G(i, Sk C,, r)
end
P: b. while j <
do Pop the highest score candidate e from Q while True do
Let the highest score from Q be s (without popping the candidate) if (G,(",T,,c. k,r) > max(0, s*) or
s* < 0 then
Break
end
else
Pop the highest score candidate E' from Q Insert an element to with key l and value G(t", b.j+k E- l'
end
end
if G(e", TJ, c,j k.r) then
Pr max (pi, sup { (2, +.). G("",TTT,. b..bb,+))r))) T3+1 u j j+1
end
else
break
end
end end
return S* anddn p
29


Reviews:
[{"review_id": "o8fynVpvpq", "reviewer": "Reviewer_zLfD", "summary": "The paper studies a procurement mechanism with objective function f(S) - \\sum_{i \\in S} p(i) that is truthful, individually rational, and has nonnegative surplus, and provide a bi-criteria approximation.\nTo the best of my knowledge, this is the first to study such objective function in the procurement auction literature, largely different from the standard procurement auction setting to minimize cost given a utility constraint or the budget-feasible mechanism design setting to maximize utility given an ex-post budget constraint.\nThe authors provide an improved analysis for the standard Distorted Greedy algorithm for this sake, and design a mechanism based on it.\nThe authors then extend their results to online mechanism and descending auction.\nThey further validate their findings through experiments.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for taking the time to read our paper and for their valuable feedback. We agree with the suggestions and we will do the appropriate reorganization of our content based on their feedback. If our manuscript gets accepted, we will also make sure to utilize the extra space of the camera ready version to enlarge the figures.", "claims_and_evidence": "All the claims sound clear and well-explained.\nOne minor issue I found is that the improved analysis of the Distorted Greedy seems a bit orthogonal to the paper's main contribution, though I appreciate the result itself.\nOne direction might be to make the paper more focused on the mechanism design part, while deferring the improved analysis part to the appendix, but I don't think this to be crucial component to judge the paper's contribution.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I haven't read all the proofs line by line, but the ideas sound reasonable.", "experimental_designs_or_analyses": "I found no issue", "relation_to_broader_scientific_literature": "The paper's topic is significant to mechanism design and submodular maximization.", "essential_references_not_discussed": "I don't find any", "other_strengths_and_weaknesses": "The paper is generally well written, and I don't find specific weakness of the paper.\nOne minor point I'd say is that the paper contains too many results, which are not equally interesting.\nThe authors might want to more strategically present a part of the results they think will be the most significant.", "other_comments_or_suggestions": "Figures are a little hard to parse - legends and titles/axes are not very readable until I enlarge my screen enough.", "questions_for_authors": "Nothing specific.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NLNZszqaSO", "reviewer": "Reviewer_fVpD", "summary": "In this paper, they develop a framework to convert a family of greedy algorithms for submodular maximization to a mechanism for procurement actions.\nMoreover, they provide an improved analysis of the Distorted Greedy algorithm.\nFinally, they consider the case of Descending auctions where they design a mechanism based on an online greedy algorithm for submodular maximization.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for taking the time to read our paper and for their valuable feedback. We respond to each of the points they raised below.\n\n>Information on the specs of the machine and the MIP solver.\n\nThanks for the suggestion, we will add more details about the specs of the machines and the MIP solver in the revision.\n\n>In the description of the Distorted Greedy algorithm (lines 174-180) ...\n\nThanks for the suggestion, we will make the edit.\n\n>VCG in the appendix.\n\nThis is a valid point, we will do that.\n\n>Typo in the definition of $u^M_i(b)$  (line 161). \n\nWe believe that this expression is correct; the seller could potentially get paid even if their service isn’t purchased, but it only incurs a cost if it has to provide the service. However, all the mechanisms discussed in this paper satisfies the property that the payment of a seller would be 0 if their service isn’t purchased. Please let us know if this isn’t clear. \n\n>I think there might be a typo in line 263.\n\nThanks for catching that, this is indeed a typo! It should be $S_{k-1}$.\n\n>Algorithm 2 is difficult to follow.. the variable $i$ is used in the for loop as well as inside the $\\max$  (line 289).\n\nWe will modify the algorithm, importing notation from the appendix to make it easier to follow. To answer your question, $i$ is the same variable as in the for loop, and we compute the appropriate threshold payments for seller $i$ in line 289 with respect to $S_{k-1}$ and take the max with the current p_i.\n\n>In line 175 (second bullet), I think it should be $G(l_1^*,\\emptyset,\\ldots) > 0$  instead of  $G(l,\\emptyset,\\ldots) > 0$.\n\nThanks for catching that, this is indeed a typo in line 1175.\n\n>Are you familiar with any other work converting greedy algorithms to auction mechanisms? Is this a classic approach?\n\nConverting algorithms to mechanisms is in general a classical approach in algorithmic game theory. For instance, VCG transforms an (optimal) algorithm to a welfare-optimal mechanism. If the optimal algorithm for the underlying problem happens to be greedy, then VCG can be viewed as some such transformation. There have been other works studying black-box transformations from algorithms to mechanisms, under various objectives such as welfare or revenue. Some classical works include Lehmann, Lehmann, and Nisan (2001), Archer and Tardos (2001), Mu'alem and Nisan (2002), Babaioff, Lavi, and Pavlov (2009), Dobzinski and Nisan (2010). \n\nHowever, most of these settings handle auctions where the designer is *selling* items, and the conversion may not always work if the algorithm does not give optimal outcome. In our setting, we consider converting approximately optimal algorithms and making sure that the conversion creates a mechanism that satisfies the NAS property adds an additional difficulty. For instance, it was not clear to us whether VCG would satisfy that or not. We will discuss some of these works and the differences to our setting in the next version of our work. \n\n>Can you clarify what is the complexity of Algorithm 2?\n\nIn algorithm 2, we need to make at most $O(n)$ many calls to the optimization algorithm in line 284, i.e., one call for each chosen seller. Moreover, for each inner loop starting in line 286, we need to make $O(n \\log |B|)$ calls to the scoring function where $|B|$ is the number of possible bids. To summarize, Algorithm 2 makes $O(n)$ calls to the optimization algorithm and $O(n^2 \\log |B|)$ calls to the scoring function. We will elaborate on this in the next version of our work. \n\n>Can you formally define $OPT(b)$  in Appendix C?\n\n$OPT(b)$ is the *optimal solution* to the optimization problem when sellers report bids $b$, i.e., $OPT(b) \\in \\argmax_{S \\in 2^N} f(S) - \\sum_{i \\in S} b_i$. We will clarify that in Appendix C.\n\n>When using the lazy greedy variants is there a significant reduction in running time? Did you run the experiments using the lazy variants?\n\nYes, there is a significant reduction and we used the lazy variants for all algorithms, except for the distorted greedy, which doesn’t admit a diminishing return structure in its scoring function so that lazy greedy cannot be applied.\n\n>Are you going to release the code for the experiments?\n\nWe will try to release the code.\n\n>Can you describe potential future research directions?\n\nAn immediate direction is to close the gap between the $(1/2,1)$ bound of our descending auction and the $(1-1/e,1)$ we get in the sealed-bid auction. Another interesting problem would be to replace the cost in the objective of the mechanism designer with the payment, i.e., to study an objective of maximizing the surplus of the mechanism designer. It would also be interesting to see if the descending auction can get the same performance as VCG, when we disregard computational considerations. We will elaborate in the next version.", "claims_and_evidence": "All claims are supported by proofs.", "methods_and_evaluation_criteria": "The proposed algorithms and evaluation criteria make sense.", "theoretical_claims": "I checked the correctness of proposition 4.1 (Appendix C) and theorem 4.3 (Appendix C). I didn't find any errors.", "experimental_designs_or_analyses": "The experimental design is clear and sound.\n\nInformation on the specs of the machine that the experiments where run is missing.\nAlso, the MIP solver that was used is not mentioned.", "relation_to_broader_scientific_literature": "The paper contains a comprehensive review of submodular maximization algorithms.\nThe main idea is to transform greedy algorithms for submodular maximization to a mechanism for procurement auctions thus connecting the domain of submodular maximization to that of algorithmic game theory and mechanism design.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "- In the description of the Distorted Greedy algorithm (lines 174-180) I would suggest using another symbol instead of $k$ in order to avoid confusion with the cardinality constraint.\nThe same holds for Stochastic Distorted Greedy.\n\n- I would suggest adding an appendix briefly describing the VCG mechanism for non expert readers.\n\n- There might be a typo in the definition of $u_i^M(b)$ (line 161). Please check.\n\n- I think there might be a typo in line 263. Is it $S_k$ or $S_{k-1}$? In contrast, in Algorithm 2 line 287 you have $S_{k-1}$.\n\n- Algorithm 2 is difficult to follow. Especially, the for loop in lines 286-290. The definition of $p_i$ in the appendix (proof of theorem 4.3) is much clearer.\nAlso, the variable $i$ is used in the for loop as well as inside the $\\max$ (line 289). Is this the same variable? Again the notation in the appendix is much clearer.\n\n- In line 175 (second bullet), I think it should be $G(l_1^\\star, \\emptyset, ...) > 0$ instead of $G(l, \\emptyset, ...)$", "questions_for_authors": "- Are you familiar with any other work converting greedy algorithms to auction mechanisms? Is this a classic approach?\n- Can you clarify what is the complexity of Algorithm 2? I expected that the algorithm would be impractical for medium size inputs however in the experiments it seems to perform well.\n- Can you formally define $OPT(b)$ in Appendix C?\n- When using the lazy greedy variants is there a significant reduction in running time? Did you run the experiments using the lazy variants?\n- Are you going to release the code for the experiments?\n- Can you describe potential future research directions?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "d8DknyNcAx", "reviewer": "Reviewer_KBrU", "summary": "This paper focuses on procurement auctions where an auctioneer aims to acquire services from strategic sellers with private costs. The quality of services is represented by a submodular function, and the goal is to design efficient mechanisms that maximize the difference between service quality and total seller costs while meeting IC, IR, NAS constraints.\n\nThe authors first review existing research on procurement auctions and regularized submodular maximization. Then they show that for the distorted greedy algorithm, a stronger guarantee holds (stronger than previous results). In the mechanism design aspect, they first show that VCG mechanisms satisfy IC, IR, and NAS but are computationally prohibitive. They then develop a framework that can convert all submodular optimization algorithms into sealed-bid mechanisms that meet the desired properties and preserve approximation guarantees. This framework is also extended to the online setting. Additionally, they establish a connection between online submodular optimization and descending auctions, and prove that in the adversarial setting, a descending auction with an exact demand oracle may return a poor solution, but one based on the cost-scaled greedy algorithm can achieve a good approximation guarantee. Finally, The experimental results show that VCG and descending auctions with optimal oracle have high complexity, while greedy-based algorithms have polynomial complexity. In terms of welfare, the direct implementations of approximation algorithms outperform their descending auction variants.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for taking the time to read our paper and for their valuable feedback. \n\n>I hope the author can analyze the complexity of the algorithm in more detail.\n\nThanks for the comment, notice that all of our algorithms run in polynomial time. For example, in algorithm 2, we need to make at most $O(n)$ many calls to the optimization algorithm in line 284, i.e., one call for each chosen seller. Moreover, for each inner loop starting in line 286, we need to make $O(n \\log |B|)$ calls to the scoring function where $|B|$ is the number of possible bids. To summarize, Algorithm 2 makes $O(n)$ calls to the optimization algorithm and $O(n^2 \\log |B|)$ calls to the scoring function. We will elaborate on this in the next version of our work. Moreover, our experiments show that they can be implemented even in practical applications. In the next version of our work we will explicitly state the number of oracle calls to the submodular optimization algorithm as well as the extra complexity of our operations, for each of the algorithms we use.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes. No issues have been found so far.", "experimental_designs_or_analyses": "Yes. No issues have been found so far.", "relation_to_broader_scientific_literature": "This paper comprehensively studies procurement auctions from multiple aspects.\nThis paper improves the analysis of the distorted greedy algorithm, advancing regularized submodular optimization.\nThis paper develops frameworks to transform submodular optimization algorithms into mechanisms for procurement auctions that satisfy IC, IR and NAS, which is related to the literature on mechanism design in procurement auctions.\nThis paper contributes to the understanding of descending auctions, and makes a bridge between two areas via the reduction from online submodular optimization to descending auctions.", "essential_references_not_discussed": "No, to my knowledge.", "other_strengths_and_weaknesses": "No.", "other_comments_or_suggestions": "I hope the author can analyze the complexity of the algorithm in more detail.", "questions_for_authors": "See suggestions above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mHaHK8cgA7", "reviewer": "Reviewer_PxDv", "summary": "The paper studies the design of procurement auctions with submodular welfare. The problem involves an auctioneer and $n$ sellers, each possessing an item for sale with a private cost $c_i$, representing the minimum price at which they are willing to sell. The auctioneer's valuation over items is given by a monotone submodular function $f$. The mechanism selects a subset $S$ of items based on the sellers' reported costs and determines the payment for each seller. The goal is to design a truthful mechanism that maximizes $f(S) - c(S)$ while ensuring that the total payment does not exceed $f(S)$.\n\nThe main contribution of the paper is establishing useful frameworks that transform a reasonable greedy-like submodular optimization algorithm into a truthful mechanism without losing its approximation/competitive ratio in both offline and online settings.  More specifically, the submodular optimization algorithm can determine the item selection strategy for the auctioneer. Then, the authors design corresponding payment rules to ensure truthfulness. The paper further extends these results to the setting of descending auctions. Finally, the proposed mechanisms are empirically evaluated.\n\n## update after rebuttal\nI appreciate the authors' rebuttal and will keep my original score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for taking the time to read our paper and for their valuable feedback.  We will re-organize section 4 and name the assumptions we use for the submodular optimization algorithm.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes, the proposed mechanisms are evaluated both theoretically and empirically.", "theoretical_claims": "Yes, I reviewed the truthfulness proof of the mechanism.", "experimental_designs_or_analyses": "Yes, the paper evaluates the proposed mechanisms on a real-world dataset (although the scenario differs slightly from actual applications, it is still reasonable).", "relation_to_broader_scientific_literature": "The paper makes contributions to mechanism design with a submodular welfare objective. The proposed payment rule computation may influence future work in this area.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "The structure of Section 4 is a little bit weird. It first presents the mechanism framework for the offline setting, followed by Section 4.1, which covers the online mechanism framework. It might be better to move the offline results to Section 4.1, the online results to Section 4.2, or alternatively, move the online results to the appendix.", "other_comments_or_suggestions": "Section 4 discusses several reasonable assumptions for the meta-algorithm. It might be more readable to assign a name to each assumption.", "questions_for_authors": ".", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This is a strong and broadly-scoped paper addressing a classic problem, mechanism design for procurement auctions, in light of some new results in submodular optimizations.  All reviewers appreciated the exposition, the depth of theoretical results, and the scope of the setting(s) considered.  This AC would encourage the authors to make the edits proposed in response to fVpD's detailed reviews.
Decision: Accept (spotlight poster)