Triple Eagle: Simple, Fast and Practical Budget-Feasible Mechanisms
Authors: Kai Han
You Wu
He Huang
Shuang Cui
Venue: NeurIPS 2023 poster (2023)
Keywords: mechanism design
budget-feasible
truthful

Abstract: We revisit the classical problem of designing Budget-Feasible Mechanisms (BFMs) for submodular valuation functions, which has been extensively studied since the seminal paper of Singer [FOCS’10] due to its wide applications in crowdsourcing and social marketing. We propose TripleEagle, a novel algorithmic framework for designing BFMs, based on which we present several simple yet effective BFMs that
achieve better approximation ratios than the state-of-the-art work for both monotone and non-monotone submodular valuation functions. Moreover, our BFMs are the first in the literature to achieve linear complexities while ensuring obvious strategyproofness, making them more practical than the previous BFMs. We conduct extensive experiments to evaluate the empirical performance of our BFMs, and the experimental results strongly demonstrate the efficiency and effectiveness of our approach.

Triple Eagle: Simple, Fast and Practical Budget-Feasible Mechanisms
Kai Han"
You Wu
School of Computer Science and Technology Soochow University, P.R.China hanka iasda. edu. cn
School of Computer Science and Technology Soochow University, P.R.China 00136227129ettt suda. edu. cn
He Huang
Shuang Cui
School of Computer Science and Technology Soochow University, RR.China huangh@suda, edu. cn
School of Computer Science and Technology University of Science and Technology of China lakers@ma il ustc. edu. cn.
Abstract
We revisit the classical problem of designing Budget-Feasine Mechanisms (BFMs) for submodular valuation functions, which has been extensively studied since the seminal paper of Singer [FOCS' 10] due to its wide applications in crowdsoureing and social marketing. We propose TripleEagle, novel algorithmic framework for designing BFMs, based on which we present several simple yet effective BFMs that achieve better approximation ratios than the state-of-the of-the-art work for both monotone and non-monotone submodular valuation functions. Moreover, our BFMs are the first in the literature achieve linear complexities while ensuring obvious ptrateyyrooffness, making them more practical than the previous BFMs. We conduct extensive experiments evaluate the empirical performance our BFMs. and the experimental results strongly demonstrate the efficiency and effectiveness of our approach.
Introduction
In the celebrated Influence Maximization (IM) problem (e.g., [19, 21, 27]) an advertiser needs to select "seed users" in social network, such that the influence spread caused by "Word-of- Mouth" propagation is maximized. However, the users may want some rewards for serving as seeds and also behave strategically maximize their utilities. So the advertiser has pay the users under some budget B and ensure their fruthfulness, besides maximizing the influence spread [36]. Another similar problem arises in crowdsourcing markets (e.g., Amazon's 's Mechanical Turk [T]), where crowdsourcing task owner needs to hire some strategic workers to perform a crowdsourcing task and pay them under a budget, with the goal of maximizing the crowdsourcing revenue [4. 25, 37, 38).
Motivated by the above applications, Singer [35] initiates the studies on budger-feasible mechanism design, where buyer needs to select set of strategic sellers with private costs from ground set N with [W] = n and pay them under a budget B, such that the valuation f(S) is maximized while ensuring that the sellers report their private costs truthfully. Singer [35] considers monotone and submodular valuation function f()) and adopts a value oracle model where f(X) can be obtained for all X N. Following Singer [35]'s work, lot of BFMs have been proposed; almost all of the theoretical studies in this line put their emphasis on improving the approximation ratios of the proposed BFMs (as elaborated in Sec. 1.1), and many studies have applied BFMs various
Kai Han is the corresponding author (Email: hankai @ suda.edu.cn).
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

application scenarios such as mobile crowdsensing, federated learning, experimental design, social advertising, vehicle sharing, data pricing, team formation, cellular traffic planning, and so on.
1.1 Main Results of the Related Work
There exist BFMs concentrating on different valuation functions including (monotone or non- monotone) submodular functions, additive, XOS and subadditive functions. We review them sepa- rately in the following.
BFMs for monotone subomdular valuation functions: Singer [35] proposes 1 117.7-a 17.7-approximation
BFM. Chen et al. [13] improve the work of [35] by proposing a 1191-apprxximation BFM, and they also propose a lower bound of (resp. v2 1) for the approximation ratio of any randomized (resp. deterministic) BFM for submodular valuation functions. Jalaly and Tardos [23, 24] further propose an improved 5-approximation BFM. It is noted that all the above mentioned BFMs are randomized and incur a polynomial number (at least )(n²)) of value oracle queries. The studies of [23, 24, 35] also propose BFMs with exponential time complexity. among which the randomized BFM proposed by [23, 24] achieve the best ratio of 4. Recently, Balkanski et al. [9] propose the first deterministic BFM with polynomial running time, which achieves a ratio of 4.75 by using (n log n) value oracle queries, and they also show lower bound of 4.5 for the ratio of their proposed BFM.
Observing the large number of participants in some BFM applications such as crowdsoureing, some studies [4, 23, 24] have also considered a "large market" model where the additional assumptions Fmaz 0 are made, with Cmaz (resp. Umar) denoting the maximum cost (resp. valuation) of any single element. Under these assumptions, Anari et al. [4] and Jalaly and Tardos [23, 24] show that there exist 3-approximation and 2.58-approximation BFMs using O(n²) and Onn)) value oracle queries, respectively. However, their time complexity still can be too high for large markets, and the additional assumptions mentioned above may not always hold. For example, in the influence maximization problem, the advertiser's budget could be relatively small even though the social network has billion-scale, so Sag x 0 may not be truc. Therefore, in this work we will consider the original BFM model of [35].
of Cmox or OPT
B3
BFMs for non-monotone subomdular valuation functions: When the valuation function is non- monotone and submodular, Amanatidis et al. [2, 3] propose 505-approximation BFM leveraging the continuous greedy algorithm [28], while Balkanski et al. [9] achieve 64-approximation under Onn log n) time complexity. Very recently, Huang et al. [22] propose randomized BFM with an improved approximation ratio of (3 + v5)² Rs 27.4 under (n logn) time complexity.
BFMs for other valuation functions: There also exist BFMs for additive valuation functions [4, 13, 18, 35], among which Gravin et al. [18] achieve the best-known approximation ratios of 2 and 3 for randomized and deterministic BFMs, respectively. For subaddtive and XOS valuation functions, the work of [9, 10] proposes BFMs using demand oracle queries, as it is known that no BFMs with polynomial number of value oracle queries can achieve any ratio better than n 0.5-e for these valuation functions [35].
1.2 Limitations of Prior Art and Our Contributions
Despite the great progress on BFM design in dozen years described above, the existing BFMs for submodular valuations still suffer from several major deficiencies. First, all of them have at least M(n²) query complexity, which can be impractical for large markets. Second, it is unclear whether their approximation ratios can be further improved (both for randomized and deterministic BFMs). Third, from practical point of view, their algorithmic frameworks for achieving truthfulness still have some serious drawbacks. To understand these, we explain their techniques in the following.
The BFMs in [4, 10, 13, 23, 24, 35] have used sealed- bid auctions roughly described as follows: the sellers first report their costs and then are sorted according to the non-increasing order of their densities (i.e., the ratios of their marginal gains to costs), and finally the mechanism selects some winners with the largest densities and ensures truthfulness using Myerson's 's lemma [32]. However, sealed-bid bid auctions have been criticized for lacking practicability [6, 9, 26, 30], because it is hard for the players to verify truthfulness and to trust the auctioneer, resulting in strategic behaviours.
To address the issues of sealed-bid auctions, there is growing interest in designing "simple mecha- nisms" (e-g., [7, 15, 30, 31, 33)). The seminal work of Milgrom and Segal [31] proposes a new class of auctions dubbed clock auctions, where each player can be offered by multiple descending prices

---

and remains active only if the player accepts the last offered price, and eventually the mechanism selects some active players as the winners and pay them the last offered prices. Milgrom and Segal [31] indicate that clock auctions satisfy obvious strategyproofness and several other properties (e.g.. group strategyproofness
transparency, and unconditional winner privacy) not possessed by sealed-bid auctions. Inspired by [31], Balkanski et al. [9] propose a BFM using clock auction with the following design: they make (logg rı) guesses on OPT using a "doubling trick" similar to that in online learning theory [34], and create (logg r1) candidate solutions without violating B by offering each active seller a new price for each guessed OPT, and the final winners are selected from the best candidate solutions. The clock auction BFM in [22] adopts similar framework [9], but uses random sampling to handle non-monotone submodular valuation functions.
Although clock auctions are considered to be more practical than sealed- bid auctions [9], we argue that they sometimes still lack practicability, as enquiring a player with too many descending prices may be time-consuming and cause the effect that the player loses patience and quits the auction early. We hereby propose the concept of pricing complexity of clock auctions:
Definition 1 The (worst-case) pricing complexity of a clock auction is the maximum number of prices it offers to any player participating in the auction.
can be seen from above that the BFMs in [9] have (log, n) pricing complexity, which could still be large for impatient sellers. In fact, Balkanski al. [9] raise an open question of "whether there exist even simpler families of budget feasible mechanisms with which one can obtain constant approximations mechanisms", and prove that posted-price mechanisms are insufficient for deriving a constant ratio. Note that posted-price mechanisms (e.g.. [12]) are perhaps the simplest form of truthful mechanisms; these mechanisms show each player one "lake-it-orleeav-it" price and hence have ((1) pricing complexity. The main difference between posted-price mechanisms and clock auctions is about how they deal with any seller u who accept the offered price: it is mandatory to select such a seller u as a winner in posted-pricing mechanisms, while clock auctions may not follow this rule (this implies that clock auctions have the additional power of use "side observations" on the other sellers' behavior to decide whether u should be a winner). However, from a practical perspective, clock auctions with low pricing complexities are almost as simple as posted-pricing mechanisms. because both of them can be efficiently implemented and can be easily understood by the players for ensuring truthfulness.
In this paper, we address all the deficiencies of the existing BFMs mentioned above by presenting TripleEagle, a novel clock auction framework that brings us several simple, fast, effective, and practical BFMs. Specifically, we show that:
For monotone submodular functions, there exist randomized BFM and deterministic BFM with the approximation ratios of 3/3++ xy 4.3 and 2 + v6 4.45, respectively; both of them use at most (n)) value oracle queries. This improves the best-known ratio of 4.75 in [9] (using On2 log n) value oracle queries) for this long-standing problem.
For non-monotone submodular functions, there exists randomized BFM with an approxi- mation ratio of 12, using at most (nn) value oracle queries. This improves the best-known ratio of (3 + v5)²² xs 27.4 of the randomized BFM proposed in [22] using (n log n) value oracle queries.
Under the assumption of [9, 13] that each seller's cost is no more than B, our TripleEagle BFMs offer each seller only one price; without this assumption, most one additional price query is needed in total. Therefore, our BFMs only have (()) pricing complexity, which provides confirmative answer to the open question of Balkanski et al. [9] mentioned above, because TripleEagle is virtually as simple as posted-pricing mechanism.
We conduct extensive experiments using the applications of influence maximization and crowdsourcing. The experimental results show that, compared to the state-of-the of-thhe-rtt-tttt art BFMs proposed in [9. 22-24], our BFMs are faster in orders of magnitude, while achieving significantly better valuations of the winning sellers
Compared to [9], our TripleEagle framework has an essentially different design roughly explained as follows. Instead of offering multiple descending prices to each seller through blindly guessing OPT as in [9], we adopt a pricing rule inspired by the simple yet fundamental law of supply and demand in economics [17]. Specifically, TripleEagle processes the sellers in an arbitrary order and calculates the
3

---

price offered to new "supplier" (i.e., an unprocessed seller) based on the "current supply" (i.e., the valuation of already processed sellers who accepted the offered prices). Therefore, the offered prices in TripleEagle tend to decrease when there are more sellers. Finally, TripleEagle tries to return set of sellers with the maximum ratios of marginal gains to prices under the budget B. Due to this novel design, TripleEagle only needs one scan over the sellers and offer one price to each seller, while still achieving a better approximation ratio than [9].
As far as we know, our work is the first attempt on reducing both the time complexity and pricing complexity of BFMs. We analogize low pricing complexity to the "Triple Eagle" hole score in golf", and believe that our ideas have the potential to be applied to other clock auction problems.
2 Preliminaries
Following [35], we assume that each seller in ground set V has a private cost c(u) 2 0 and there is a submodular valuation function defined on the power set of N satisfying VX C f(x) 2 0 and
VX,Y N f(x) + f(Y) 2 f(XUY) + f(XnY)
(1)
We say that f()) is monotone if VX C C f()) < f(Y), otherwise it is non-monotone.
For simplicity. we call f(X Y) & f(XU)) - f(Y) as the marginal gain of X with respect to Y for all X,Y E N, and we use e(X) and p(X) (AX C shorthand for Luex c(u) and Enex p(u), respectively. We will consider clock auctions where each seller E NN can be offered by descending prices that are computed using public information, and we use p(u) to denote the last price offered to u at any time. When a clock auction terminates, a set S S N can be selected as winners only if P(S) < B and each seller E S has never rejected any price offered to u. The approximation ratio of to the problem max (Xx)
defined as OPT/ where OPT = f(O) and is an optimal solution
X S N A (X) < B). We will also consider randomized clock auctions: such an auction is a deterministic clock auction for every realization of all its internal random choices, and it clearly satisfies universal truthfulness [22]. For the simplicity of description, we adopt the assumption made in [9. 13] that Vu E N : c(t) I B, and we will show how to remove this assumption later. In our algorithms, if the elements in set X are sequentially inserted into X, listed as fu1.... Ugg according to the order that they are inserted, then we call the subset Y {u,, ,u) S X t :
< t q) as a regular subset of A, and also call Y a suffix (resp. prefix) of X if = (resp. s = 1). Throughout the paper, we use u" to denote a seller in N who has the maximum valuation, i.e., u² arg maxueN (u))
3 Randomized BFM for Monotone Submodular Valuations
In this section, we consider a monotone submodular valuation function f(-) and provide a randomized BFM using the TripleEagle framework, as shown by Algorithm (i.e., the TripleEagleRan algorithm). Algorithm 1 takes as input a parameter a > for setting a "reserve price" that will be explained shortly. In Line 1, Algorithm calls the LSDPricing procedure (i.e., Algorithm 2) to process all sellers in N except u"; each of these sellers is offered one price by Algorithm 2 and then Algorithm returns set A containing the sellers who accept their prices. After that, if f(A) 2 f(u"), then Algorithm calls Algorithm 2 again to process u² and finally returns a suffix of A respecting the budget constraint (Lines 3-4). Otherwise, Algorithm 1 makes random decision of returning either u" or T (Lines 6- 1-13,, where T is superset of A and is got by trying to include u² by offering u* a "best effort" price of B- p(A).
can be seen that Algorithm 2 offers each seller u price Bf(u(A) f())+a This pricing rule is inspired by the fundamental Law of Supply and Demand (LSD) in economics [17], as intuitively explained in the following. First, note that A contains all the processed sellers who accept the offered prices, so fAA) can be regarded as the current "supply" in the market, thus the price offered to a new "supplier" (i.e., an unprocessed user u) should decrease with the increment of (A). Second, the marginal gain [u (A) represents how much value the user u can contribute given the current supply f(A), so the price offered to should increase with f(u A). Third, the factor of("") guarantees that user can be paid a price larger than B/a, a, which can be regarded as a "reserve price" of the buyer. Without this reserve price, the winner set could have poor value due the overpayment to some sellers.
Pe.g.. a "hole-in-one" par- five, see https:://e..iiipppppps www.kpedia.rg/wwik/Peee... (score)

---

Algorithm 1: TripleEagleRan(()
A f- LSDPricing(0.W. (u")
(AA) 2 f(u") then A + LSDPricing(A4
af)(()))
< the largest suffix of satisfying Enesp(ut B:
else
Sample random number Z from the uniform distribution [4 1]; if 2
then
0
p(u B:S {u'}
else
Set Setp(u") =B -B- p(u) and show u' the price p(u");
if u accepts p(u") then T AU {u²}
12
else T + A; S T:
return S
Algorithm 2: LSDPricing A, C.n)
foreach do p(u) t- B-f(u) Show the price p(u); ](A]+q
if u accepts p(u) then A + Aufu);
return A
3.1 Performance Analysis of TripleEagleRan
is evident that Algorithm 1 provides each seller only one price and incurs 2n value oracle queries (n queries for finding u*). So we only analyze its approximation ratio. Let us consider the set the moment that Algorithm 1 finishes. For convenience, we use A,, to denote the set of elements already in A the moment right before u (Vu ./) is processed. We first introduce Lemmas 1-2, which can be proved based on submodularity and the observation that each seller who accepts the offered price must have a sufficiently large density (and vice versa) due to the pricing rule of Algorithm
Lemma For any regular subset X [!us ..e of A returned by Algorithm 2, we have
f(x) N Evex f(v) Av) 2 p(X) f(Au,) + af(u")
Lemma 2 After Line of Algoritlum I is executed, we have OPT - 2f((A) af(u").
With Lemmas 1-2,
bound the approximation ratio of Algorithm if is generated by Line 4, as shown by Lemma 3. Intuitively, if p(A) B, then we have f(A) > f(u") due to Line 3 and hence we can use Lemma 2 to get OPT < (2 + (S) directly; if p(A) B, then p(S) is also sufficiently large, which implies f(S) is large, because
a suffix A and hence contains the sellers in A with the largest ratios of marginal gains to prices due the pricing rule of Algorithm 2.
Lemma 3 For any E (2, /3 + 1), the set S generated by Line 4 of Algorithm I satisfies
OPT S max (3+ 2a
a² 2 2+
S(S)
Proof: Due to Line 2, we must have f(u") < f(A) when Line 4 of Algorithm is executed.
Therefore, if p(A) < B, then we have S A and hence
OPT < (A( + +af(u") < x2+
(2)
5

---

due to Lemma 2. In the following, we consider the case of p(A) > B. Let H be the smallest suffix of A satisfying p(H) > B, so H S contains exactly one element (denoted by w) which added into A before the elements in S. Using Lemma 2 and submodularity, we get
OPT
S (A) + af((")) S U (w)) + + H) + +af("*)
V 2/(S) + 2 H) + (2+a)
Suppose that f(A) H) = =f("r, p(w)= = eB (and hence p(5) > (1 - () for certain o > 0 and E [0, 1J. According to Lemma I, we have
f(u)) 2 f(w A H) 2 oB f(A) H) + af(u")
2 2 - +a]((u)
(4)
B
f(S) 2 (1 B) f(A H) + f(w
A (AAH) + +af("))
2 (1 g²) + aa) (5)
B
Let x = a + a. We have 0 0 1 and f(S) 2 x² f(u") due to Eqns. (4)-(5). Combining these with
Eqn. (3), we get
OPT S 25(5) + (2 (2+20 20 + a) a)) 25( + 2 2x S(S)
x 1/2
4+ a
f(S)
(6)
x 0-1/x
Note that x = o + a 2. The R.H.S. of Equ (6) is no more than 4f(5) when 2 2 or 2- When < - (i.e.. a + 1) and x E (a, a²z): the R.H.S. of Eqn (6) is maximized when x = a. Therefore, for any E (2, + 1) we have
OPT < 4 + 2a - a² +2
2a + 1)
ʃ(S) = 3+ a² S(S)
a²
Combining Eqn. (2) and Eqn. (7) completes the proof.
Next, we bound the approximation ratio of Algorithm when S is generated by Lines 6-13 (using randomization), as shown by Lemma 4:
Lemma 4 For any > 2, if Algorithm returns S that is generated by Lines 6-13, then we have
S [[S(S)]
In this case, we must have f(A) < f(u)) after Line 1 is executed. This implies p(A) < B because otherwise we have f(A) 2 af("") due Lemma 1, contradicting f(A) f(u") when > 1. We prove that the set T generated by Lines 10-13 of Algorithm must satisfy OPT < (T( + of (u*) according to the following discussion:
Proof:
1. & O: In this case, we can use similar reasoning as Lemma get
OPT < 2/(A) + ax (u(""" < 25()) + aa(""" where the second inequality is due to C according to Lines 11-12.
2. O and accepts the price in Line 11: In this case, have T AU {u*} and hence can also use similar reasoning as Lemma 2 to get
OPT f(T) S Emco, f(u A) f(A) +af(")) af(
which yields OPT < 2f(T) + +f("").
3. E O and and u" rejects the price in Line 11: In this case, we must have T A. clu") > B - p(A) and hence
f(0) + af(u)) < BS(A)
B. S(A)
c0 (u*)) S p(A) <
(8)
af((rt

---

where the second inequality is due to Lemma 1. Note that all the sellers in O {u*} has been processed by Line and each seller u E O \ {u" \ A must reject the offered price and hence satisfy c(u) > p(u). So we can use this and Eqn. (8) to get
S(ul Au) Encortor)) p(u)- f(An) taf(")
1(0) ((0)(u)))- ((A)) - Eueouuu HA
> <Encorern c(u). f(A) + +af(u*)
B
B
1 S S(A) (f(A) + +zf(( af(w*)
- ((A) + f(n")
(9)
Therefore, when 2, have
OPT S f()) \ {u*)) + f(u)) s (1 - + ( 22((T) + aff("))
(10)
According to Lines 6-13, the algorithm returns T or {u*) with probability of 2 or z+a respectively. So we get
24a
E[((S)
- ((T) Pr(S {u')] ".
(11)
= 2f(T) af(u*) OPT
(12)
2+a 2+a
2+a
which completes the proof.
Combining Lemmas 3-4, we immediately get:
Theorem With a VI3+1 = 2.3, the TripleEagleRan mechanism can return set S satisfying ([))) by offering one price to each seller in N and incurring at most ((n) value 2
OPT <
2
oracle queries.
Remark: As mentioned in Sec. 2, we have adopted the assumption made in [9, 13] that Vu e W clv) B for the simplicity of description. This assumption can be easily removed according to the following discussion. Note that each buyer is guaranteed to be offered price no more than B in TripleEagleRan. Therefore, before running TripleEagleRan, we only need identify valid " = arg N f(v). This can be done by first sorting all the sellers according to the non-increasing order of their values, and then offer B to them one by one until seeing the first seller accepting B and then that seller is clearly valid u". After that, we can delete all the sellers rejecting B and then run TripleEagleRan. Clearly, using such method, the complexity of our mechanism on the number of value oracle queries is still Onn), while only one additional price query (for u is incurred. This method can also be used for all our mechanisms described the sequel.
Deterministic BFM for Monotone Submodular Valuations
If directly the LSDPricing algorithm to process all the sellers in M, it is possible that the valuation of the sellers who accept the offered prices is no more than f(u"), while u" rejects its price and hence cannot be selected as winner, resulting in poor approximation ratio (especially when f(u") is large). To address this issue, we have used randomization in TripleEagleRan. In this section, we introduce TripleEagleDet (i.e., Algoirthm 3), deterministic BFM that circumvents the aforementioned issue using an idea of "two-phase pricing", as elaborated the following.
In the first pricing phase (Lines 2-6), Algorithm 3 constructs set K by using the pricing rule in Line 3 to processes the sellers in N {u"), }; this pricing rule a relaxation of the pricing rule in the LSDPricing algorithm, because the valuation of the already processed sellers is not used to lower the price for the next seller to be processed.
The first pricing phase stops as soon as f(K) 2 f(u") (Line 6). If f(K) is still less than f(u") when all the sellers A {u*) have been processed in the first pricing phase, then Algoirthm 3 sets winner set S = {u²) (Line 8). In the case that the first pricing phase generates set K satisfying J(K) 2 f(u"), ), Algorithm 3 enters the second pricing phase in Line 10, where we use LSDPricing to process all the sellers not processed in the first phase (including u²). Intuitively, since f(K) > f(u")
7

---

Algorithm 3: TripleEagleDet(a)
K + O'C'+ N;;; foreach E N {u"} do
p(u) +- of(a)) Show u the price p(u);
u accepts p(u) then k K- {u};
C C.CCA.A {u])
f(K) 2 f((x) then break;
7 if f(K) < f("") then
p(u")= + B; S {u"}:
else
10
LSDPricing( K; C, C,af(u")):
$ + the largest suffix of A satisfying Enes p(u) S B:
12 return 5
and K is prefix of A in the second pricing phase (Line 10), we can regard K as a substitute of u² and hence no longer need worry about the issue explained in the beginning of this section.
We analyze the approximation ratio of Algorithm by considering two cases. In the first case, we have f (K) f(u") p(A) s B. which implies that {u" } S A due Line 8 and Line 11. In this case, we can directly use the two-phase pricing rules to bound the total valuation the sellers in O who rejected the offered prices and hence get Lemma 5:
Lemma When Algorithm 3 finishes, if f(K) < f(u") or p(A) & B, then we have OPT < (2 (S))
In the second case (i.e. [(K) 2 f(u") and p(A) > B), we must have that S is generated by Line 11 and S A. In this case, bounding the performance of Algorithm 3 more complicated and is given by Lemma 6:
Lemma 6 Suppose that E (2,
xTZ+1).
When Algorithm 3 finishes, if f(K) 2 f(u") and p(A) >
B, then we have
3a +
a(2 + a)
a(4+a) a²+a-2) f(S)
OPT < max
3+
2+ a² -a a² + 2 a²
2
(13)
We roughly explain the idea for proving Lemma 6 as follows. Consider the set A generated by Line 10 (recall that K is prefix of A). the smallest suffix H of A satisfying p(H) > does not intersect
K, then
similar reasoning Lemma 3 to prove OPT (3
3a+44
f(S). Under the
a²+2a
other case (i..,, H O K * 0), H must have prefix generated using the relaxed pricing rule of Line 3, which possibly degrades the valuation of and hence S (note that S is a suffix of Ht), Fortunately, since f(K) is at most 2f("") due to Line 6, we can prove that the approximation ratio of f(S) is only
slightly weaker than that in the case of H n K = 0. i.e., OPT S max 2 a²4a-4:
a(2-a) 2 + a(1+a)
o²+a-2
(S)) Combining Lemmas 5-6, we can immediately get the performance bounds of TripleEagleDet, shown by Theorem 2, which reveals that TripleEagleDet has better approximation ratio than the deterministic BFM with a provable ratio of 4.75 in [9]. Note that Balkanski et al. [9] show that their BFM cannot achieve ratio better than 4.5 even if their analysis for the 4.75-ratio is tight.
Theorem With a = Vo R 2.45, the TripleEagleDet mechanism can return a set S satisfying OPT < (2 + (S) by offering one price to each seller in and incurring 2n value oracle queries.
5 BFM for Non-Monotone Submodular Valuations
In this section, we extend our TripleEagleRan algorithm to handle a non-monotone submodular valuation function f(-), as shown by the TripleEagleNm algorithm (i.c., Algorithm 4).

---

Algorithm 4: TripleEagleNm(a)
Ai f 0; A2 f 0;
foreach N {ur} do
jt arg (1.2) f(u A.):
p(u)+ + B.f(ulAg)
f(A))+o((u>) Show a the price p(u);
u accepts p(u) then
L A2 + A3 U {u);
7
(max (ma))
2 f((") then Let n² and process using Lines 3-6;
A + arg (A) f(X);
10
S - the largest suffix of A satisfying Enes p(u) S B;
11 else
12
Sample random number Z from the uniform distribution (1 1];
13
S 3+a then
14
p(u ) + B: S {u'}:
15
else
16
9 arg maxie (1,2) f(u") A.):
17
pl (A,) and show u" the price p(u"); if f("" A4) and u² accepts p(u") then Ag Ag U {
Set
18
19
T + arg ( f(X); +
20
return S
The TripleEagleNm algorithm is similar in spirit to the TripleEagleRan algorithm execept that it maintains two sets of candidate winners: A₁ and Ag. Lines 1-6 of Algorithm 4, each seller A {u"} is greedily routed A₁ {1,2]) such that f(u A,) maximized, and then u is offered price generated using the same rule as Line 2 of Algorithm 2. After all the sellers in N \ {u") } are processed, Lines 12-19 of Algorithm 4 adopt the operations similar those in Lines 6-13 of Algorithm 1, except that u* is offered a "best-effort" price of B p( (Ag) after it is greedily routed to Ag by Line 16. We show the performance bounds of Algorithm in Theorem 3:
Theorem With 3. the TripleEagleNm mechanism return set S satisfying OPT < [S)] by offering one price to each seller in N and incurring at most 3n value oracle queries.
Performance Evaluation
We use the influence maximization application mentioned in Sec. to compare the following BFMs: (I) Our TripleEagleRan (TER) and TripleEagleDet (TED) algorithms, (2) The fierativePrrninng (IP) algorithm in [9] with a ratio of 4.75, and (3) The Random-TM TM (RTM) algorithm in [24] with a ratio of 5. All the algorithms are implemented using C++ and are run on a Linux server with Intel Xeon Gold 6126 @ 2.60GHz CPU and 128GB memory. Each implemented randomized algorithm is independently executed 50 times. and the average result is reported. We use three real social network datasets: (1) Flixster [5] with 28,843 nodes and 272,786 edges; (2) Epinions [29] with 75,879 nodes and 508,837 edges; and (3) Slashdot [29] with 82, 168 nodes 948,464 edges. We adopt the well-known Independence Cascude (IC) model [27] for the influence spread function f(-), and follow [14] to set the activation probability Pu.; cach edge (u, v) 1/N where (o) denotes the set of in-neighbors of v. The cost c(u) of each node is generated uniformly at random from the interval [0, 1]. Since evaluating f-) is known to be #P-hard [14], we adopt the approach in [11] to generate one million random reverse-reachable sets for approximately evaluating f-)). It is known that the influence spread function through such an approximation is still monotone and submodular [11].
The experimental results in Fig. reveal that, for all three datasets, our BFMs outperform the baselines on utility (i.e., the valuation of returned solution). Specifically, TER and TED have similar utilities that outperform RTM (resp. IP) with the performance gain ranging from 55%-1122% (resp. 1%-14.). Moreover, TER and TED incur much fewer value oracle queries than RTM (resp. IP) in more than one (resp. three to four) orders of magnitude. It can also be seen that, although TER and RTM are

---

RTM
TER
TED
RTMM
-TER
-EEED
1e10
4000
Oracle Querles
168
Utility
104
Budget
Budget
Flixster
Flixster
8000
1c10
6000
Orade Querles
168
Utility
4000
166
2000
Budget
Budget
10
(c) Epinions
Epinions
10000
7500
Orade Querles
166
Utility
5000
166
2500
Budget
Budget
10
(6) Slashdot
Slashdot
Figure 1: Comparing the BFMs for the influence maximization application
both randomized mechanisms, RTM incurs large variations while TER is almost deterministic in Fig. This can explained by the fact that RTM always returns random solution by its design, while the randomization of TER is only triggered in some special cases (see Sec. 3). Finally, we have also compared our BFMs with the existing ones using a crowdsourcing application similar to that in [8, 16, 20, 22], where non non-monotone submodular valuations are also considered. The experimental results are qualitatively similar to Fig. and can be found the Appendix due to the page limits.
7 Conclusion
We have proposed TripleEagle, a novel algorithmic framework for designing budget feasible mecha- nisms with submodular valuations, based which have presented several simple, fast, effective and practical BFMs that achieve obvious strategyprooffess, low complexity, and better approximation ratios than the-state-of-the. studies. The efficiency and effectiveness of our approach has been strongly comroborated by our experiments on influence maximization and crowdsourcing.
Acknowledgements
Kai Han's 's work is partially supported by the National Natural Science Foundation of China (NSFC) under Grant No. 62172384.
References
[1] Amazon Mechanical Turk. http://vwww.muurk.com
[2] Georgios Amanatidis, Pieter Kleer, and Guido Schäfer. Budget-feasible mechanism design for non non-monotone submodular objectives: Offline and online. In ACM Conference on Economics and Computation (EC), pages 901-919, 2019.
[3] Georgios Amanatidis, Pieter Kleer, and Guido Schäfer. Budget-feasible mechanism design for non-monotone submodular objectives: Offline and online. Mathematics of Operations Research, (733):286-2309 2022.
10

---

[4] Nima Anari, Gagan Goel, and Afshin Nikzad. Mechanism design for crowdsoureing: An optimal 1-1/e competitive budget-feasible mechanism for large markets. In IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 266-275, 2014.
[5] Cigdem Aslay, Francesco Bonchi, Laks S. Lakshmanan, and Wei Lu. Revenue maximization in incentivized social advertising. Proceedings of the VLDB Endowment (PVLDB), 10(11):
1249, 2017.
[6] Lawrence M Ausubel, Paul Milgrom, et al. The lovely but lonely vickrey auction. Combinatorial auctions, 17:22-26, 2006.
[7] Moshe Babaioff, Nicole Immorlica, Brendan Lucier, and S Matthew Weinberg. A simple and approximately optimal mechanism for an additive buyer. Journal of the ACM (JACM), 67)4):
1-40, 2020.
[8] Eric Balkanski, Adam Breuer, and Yaron Singer. Non-monotone submodular maximization in exponentially fewer iterations. In Advances in Neural Information Processing Systems (NeurIPS), pages 2359-2370, 2018.
[9] Eric Balkanski, Pranav Garimidi, Vasilis Gkatzelis, Daniel Schoepflin, and Xizhi Tan, Deter- ministic budget-feasible clock auctions. In ACM-SIAM Symposium on Discrete Algorithmss (SODA), pages 2940-2963, 2022.
[10] Xiaohui Bei, Ning Chen, Nick Gravin, and Pinyan Lu. Budget feasible mechanism design: from prior-free to bayesian. In ACM Symposium on the Theory of Computing (STOC), pages 449-458, 2012.
[11] Christian Borgs, Michael Brautbar, Jennifer Chayes, and Brendan Lucier. Maximizing social influence nearly optimal time. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 946-957, 2014.
[12] Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. Multi- parameter mechanism design and sequential posted pricing. In ACM Symposium Theory of Computing (STOC), pages 311-320, 2010.
[13] Ning Chen, Nick Gravin, and Pinyan Lu. On the approximability of budget feasible mechanisms.
In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 685-699, 2011.
[14] Wei Chen, Chi Wang, and Yajun Wang. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 1029-1038, 2010.
[15] Xi Chen, George Matikas, Dimitris Paparas, and Mihalis Yannakakis. On the complexity of simple and optimal deterministic mechanisms for an additive buyer. In ACM-SIAAM Symposium on Discrete Algorithms (SODA), pages 2036-2049, 2018.
[16] Matthew Fahrbach, Vahab Mirrokni, and Morteza Zadimoghaddam. Non-monotone submodular maximization with nearly optimal adaptivity and query complexity. In International Conference on Machine Learning (ICML), pages 1833-1842, 2019.
[17] David Gale. The law of supply and demand. Mathematica Scandinavica, 3()) 1955.
[18] Nick Gravin, Yaonan Jin, Pinyan Lu, and Chenhao Zhang. Optimal budget-feasible mechanisms for additive valuations. ACM Transactions on Economics and Computation, 8(4):21:1-21:15. 2020.
[19] Kai Han, Keke Huang, Xiaokui Xiao, Jing Tang, Aixin Sun, and Xueyan Tang. Efficient algorithms for adaptive influence maximization. Proceedings of the VLDB Endowment, 11(9): 1029-1040, 2018
[20] Kai Han, Shuang Cui, Tianshuai Zhu, Empei Zhang, Benwei Wu, Zhizhuo Yin, Tong Xu, Shaojie Tang, and He Huang. Approximation algorithms for submodular data summarization with a knapsack constraint. Proceedings of the ACM on Measurement and Analysis of Computing Systems (POMACS), 5(1):1-31, 2021.
[21] Kai Han, Benwei Wu, Jing Tang, Shuang Cui, Cigdem Aslay, and Laks VS Lakshmanan. Efficient and effective algorithms for revenue maximization in social advertising. In ACM Conference on Management of Data (SIGMOD), pages 671-684. 2021.
[22] He Huang. Kai Han, Shuang Cui, and Jing Tang. Randomized pricing with deferred acceptance for revenue maximization with submodular objectives. In International World Wide Web Conference (WWW), pages 3530-3540, 2023.

---

[23] Pooya Jalaly and Éva Tardos. Simple and efficient budget feasible mechanisms for monotone submodular valuations. In The 14th International Conference on Web and Internet Economics (WINE), pages 246-2632 2018.
[24] Pooya Jalaly and Éva Tardos. Simple and efficient budget feasible mechanisms for monotone submodular valuations. ACM Transactions on Economics and Computation (TEAC), 9(1):1-20, 2021.
[25] Radu Jurca and Boi Faltings. Mechanisms for making crowds truthful. Jourmal of Artificial Intelligence Research (JAIR), 34:209-253, 2009.
[26] John H Kagel, Ronald M Harstad, and Dan Levin. Information impact and allocation rules in auctions with affiliated private values: A laboratory study. Econometrica: Journal of the Econometric Sociery, pages 1275-1300 1304, 1987.
[27] David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In ACM SIGKDD International Conference Knowledge Discovery and Data Mining (KDD), pages 137-146, 2003.
[28] Ariel Kulik, Hadas Shachnai, and Tami Tamir. Approximations for monotone and nommonotone submodular maximization with knapsack constraints. Mathematics of Operations Research, 38 (4):729-739, 2013.
[29] Jure Leskovec and Andrej Krevl. Snap datasets: Stanford large network dataset collection. URL: http://snap.stanfore edu/, 2014.
[30] Shengwu Li. Obviously strategy-proot mechanisms. American Economic Review, 107(11): 3257-3283 2017.
[31] Paul Milgrom and Ilya Segal. Clock auctions and radio spectrum reallocation. Journal of Political Economy, 128(1):1 31, 2020.
[32] Roger B. Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58-73, 1981.
[33] Aviad Rubinstein. On the computational complexity of optimal simple mechanisms, In Innovations in Theoretical Computer Science (ITCS), pages 21-28, 2016.
[34] Shai Shalev-Shwartz al. Online learning and online convex optimization. Foundations and Trends@ Machine Learning, 4(2):077-194, 2012.
[35] Yaron Singer. Budget feasible mechanisms. In IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 765-774, 2010.
[36] Yaron Singer. How to win friends and influence people, truthfully: influence maximization mechanisms for social networks. In ACM International Conference Web Search and Data
Mining ( (WSDM), pages 733-742, 2012.
[37] Yaron Singer and Manas Mittal. Pricing mechanisms for crowdsourcing markets. In Interna- lional World Wide Web Conferences (WWW), pages 1157-1166, 2013.
[38] Jennifer Wortman Vaughan. Making better use of the crowd: How crowdsourcing can advance machine learning research. Journal of Machine Learning Research (JMLR), 18(1) 18(1):7026-700 2017.
12

---

Appendix
A Proof of Lemma 1
Proof: is evident that f(X) 2 Evex f(v An) f(A,, - f((,) due to submodularity,
Besides, for each e E X, we have f(A,) 2 (Au,)) and c(() S p(u) (because accepts the offered price), so we get
Bf( Aoo) c(v) s(u)) I(A,) + +as("*) I(Au,) ) + af(u*)
Bf(c Av)
and hence
EvEx f( A.) 2 Emex p(u) [(Au.) of(("))
= =p(X) [(Au,) of("")
B
B
which completes the proof.
B Proof of Lemma 2
Proof: After Line is executed, all the elements in / must have been processed by the LSDPricing algorithm. As each element in O \ A rejects the offered price, we have
Bf(u Au) E \ A c(u) p(u) f(An) + aaf(")) J(A)+
Bf(u Au) N
(14)
Using this and submodularity, we get
((A)
E S(u |A)s Σ f(u Au)
((A)+af(u))
Σ du)
S f(A + af(l")
(15)
B
KEOVA
The lemma then follows by re-arranging the above inequality.
C Proof of Lemma 5
Let O1, O2 the set of sellers O who reject the offered prices in Line of Algorithm and in the LSDPricing procedure (Line 10 of Algorithm 3), respectively. Let K,, denotes the set of elements already in when u is offered a price in Line 3. Under the case of f(K) < f(u"), we
Proof:
must have S {u') (due to Line 8), O₁ O \ {u*) } K and
f(o \ (u²)) - ((K) S Σ f(u K.) = Σ p(u) af(u") nEO
as(u")
Σ c(u)
I af("")
B
B
mEO:
MEO:
and hence
OPT S ((K) + af(u")++ + f(u')((())))))"")) (x))
(16)
On the other hand, if f(K) 2 f(u") and ((A) S B, then we have A = O₂ U UO.. Note that K is prefix of A under this case. So can use submodularity to get
OPT <
Σ
f(u K.)+ + Σ f(u Aw)
nEO;
mEOz
c(uu af(u")
(An) + af(u")
<
Σ
Σ
c(u)
B
B
wEO
uEDs
c00 af("*)
f(A) + af(
+c(02)
B
B
c0) f(A) +(A)+)
B
< f(A) +afu"),
(17)
which yields S(A) < 2f(A) + af((")) S (2 + (A) by using ((A) 2 S(K) 2 f(1²). Note that
S A under this case (due to Line 11), so the lemma follows.
D
13

---

D Proof of Lemma 6
Proof: By similar reasoning with Lemma 5, we have
OPT < 2f(A) +af("")
(18)
Let H be the smallest suffix of A satisfying p( > B, so H \ S contains exactly one element (denoted by w) which is added into A right before the elements in S. For convenience, we define
5(X) = _mex f(u Aa) for any regular subset X of A. Suppose that f(A \ H) = =f(="),
f(K)= = Af((") ). 6(KH)) = ff(")) and p(KNH) = pB. Clearly, we have p H K) 2 (1-p)B, A and
2. We consider the following cases:
1. KnH = 0: In this case, all the sellers in H are selected using the pricing rule of Algorithm 2.
So we can use similar reasoning Lemma 3 to get
2 a 2/20)
OPT - 4+ x-1/x
f(5)
(19)
where x j + a. Note that fKK f(u") and K C AA\ H. s0 2 and 2 + 1. The R.H.S. of Eqn (19) is no more than 4f(S) when x 2 a-2 or a + a-2' When
a+1 < a-2 (i.c., < ( and E [a+ 1, 2 ) the R.H.S. of Eqn (19) is maximized
2
when x = a + 1. Therefore, for any E (2, 1T7+1
we have
2
OPT S ( a- 44 4
a² a2 + 2xx
3a +
f(5) 3
f(S)
(20)
a² 20
2. K n H| > 1: According the construction of K, this implies f(K) \, 5) f(u*) and hence
In this case, we must have |K n S) 2 1 because |H S = 1 by definition.
f(A) < f(K \ 5)+ f(S) - (u") + f(S)
(21)
Note that each seller u E K satisfies c(u) S p(u) = Bf(u[Au)
aflw') so we have
af("')
Tf(x") = 5(K H) 2 p K H)
2 pa:((u))
(22)
B
This implies p S T/a and hence p(H K) z (1 - B/ By similar reasoning as Lemma 1, we have
8(H \ K) 2 21 (1- f(u') 2 - (A)
(23)
and hence
8(H) + K)
> (1 f(u²) =
w (a+>~X/a)f(uu)
(24)
where the last inequality is due to J S A. Recall that 1 < X S 2 and a E (2, vTZ+1). So the R.H.S. of Eqn. (24) is minimized when X = 2. Therefore, we get
S(S) 2 (HH f(u²) 2 (a + 4/a)s(u)) Combining Eqn. (18), Eqn. (21) and Eqn. (25), we get
(25)
2+ a
OPT 2f(()) + (2 + a)f(w") < 2+ a a+ 1-1a
f(S)
(26)
3. K KNH = 1: In this case, we must have A= KUS, Kns = and H K = S according
the definition of HI. Moreover, due Eqn. (22) we have f(u*) > 8(K n H1 > pa f(" and hence p < 1/a. Note that all the elements in S is selected using the pricing rule of Algorithm 2. Therefore, using similar reasoning as Lemma 1, we get
f(S) 2 (1 p) (f(K) + a- f(u)) 2 (1 1/a)(A aof((()
(27)
14

---

Recall that A and A = K U S. Combining this with Eqn. (18) and Eqn. (27), we get
OPT I 2f(A) + +ff(") 1 2f(K) + 2f()) + af(u")
2f(S) (2)+ a2)+
2A +
2+ (1 (1- 11-a/aa(A + S(S)
2 - 1/a
2
(1 (1- [1-1/a](++o) 1(5)
a
< 2 4+a
S(S)
(28)
2/0
The lemma then follows according to the above discussion.
E Proof of Theorem 3
can be easily seen that Algorithm offers one price each seller and incurs most 3n value oracle queries (n queries for finding u' and 2n queries for building A and A2). The approximation ratio Algorithm
be proved by directly combining Lemma and Lemma 8:
Lemma If Line 10 of Algorithm 4 is executed, then we have OPT S 12f(S) when a 3.
Proof: In this case, all the elements in O must have been processed by Lines 3-6. Let O1 (resp- O2) denote the sellers in O who reject the offered prices that are calculated using A (resp. A2) in Line 4. For convenience, we define 6, (w)
f(u Ai..) for any E A, where Ai, denotes the set of elements already in A; at the moment that u is processed by Algorithm 4. It can be seen that, for each B8,(w)
E A.(i E {1, we have (u) 2 O, because otherwise we have p(u) ta < 0 and hence p(u) should be rejected by u due to e(u) 2 0, which implies that u not A, a contradiction. So have f(X) f(A,) for any prefix X of A4.
In the following, we consider the sets A,, Ag, A after Line 10 of Algorithm 4 executed. For each i {1,2} and each u E Oi, we can use similar reasoning as Lemma 1 to get
[(u Ax) cuu)
(u( c(u)
[(Ai.)) + tas("))
[(A.) + af(())
< S(A)) + af(("))
(29)
B
B
B
Moreover, according to submodularity and the greedy rule of Line 3, for all i,j E {1,2] and i i we have
Σ (())
Σ 65(1)
Σ di(w) S Σ d((1) s f(A.) S f(A"),
(30)
BEANO
HEAnO
ueA:
where the third inequality is due to (x) 2 0 for all u E A, Using the above inequalities and submodularity, we get
f(OUA)) $(A))
Σ f(u (1)
Σ f(u A1)
uEOnAz
aEO,U0,
f(A'+ Σ 81(2) +
Σ
(1(1) < f(A)+
Σ
51(u) + Σ 82(u)
nEO
#EDg
mEO
nEO2
S(A") +af(u*) < 2f((A") + a=()")
S f(A*)+ (c(Or) + c(O2))
(31)
where the third inequality due to the greedy rule Line Similarly, we get Combining Eqns. (31)-(32) gives
S(OU A²) f(A2) +
(32)
OPT < Σ S(OU A,) & <T(A)) + 2a/(n"),
(33)
(E(1,2)
15

---

where the first inequality is due to submodularity and A n A2 0. Therefore, if p(A") S B, then
we have S A". ((S) 2 f(u") and hence
OPT < 6f(() + 2af(u") - (6 + 2a)
(34)
p(A)) > B, then let H be the smallest suffix of A" satisfying p(H) > B, and we can use similar reasoning as Lemma to get
[(5) + f(u²) 2 S(H) 2 S(A H) + af(
(35)
Combining Eqn. (33) and Eqn. (35), we get
OPT I ( + 6f(A \ + 2af(u")
< 6(f(5) 6( + f(""(((()))))))))))) aff("") + 2af(u²)
< 12 + (12-4a)f(u")
(36)
The lemma then follows by combining Eqn. (34) and Eqn. (36).
Lemma 8 If Lines 12-19 of Algorithm 4 are executed, then we have OPT < 121][((8) when a
Proof: For clarity, we use J1 (resp. J2) to denote the set Ai (resp. A2) at the moment that Algorithm 4 executes Line 12, and define J = arg ( f(X). So we have f(J*) < f(u") due to Line 7. It can be seen from Line 18 that u" is added into A, only if (1) max)e(1.2) f(u" J+) 2 0 and (2) u² accepts the price of B p(Jg). Note that the set T generated by Line 19 must
satisfy f(T) 2 f(J*). In the sequel, we prove that OPT < 6f(T) + 2a.(u") by discussion:
1. u² $ O: In this case, we can use similar reasoning as Lemma 7 to get OPT f(O) \ (w²))
S 6f(J*) + fa"( S (f( + 2af(u²) 2. u² E O and u² is added into A, in Line 18; or u²
(37)
and ma. f(u" | J+) < 0: In
these situations, after Line 19 is executed, we can use similar reasoning as Lemma 7 to get
Vi E {1,2} : : U A.) f(A)) s 2f(() +af(""
(38)
Note that f(A.) - f(T) due to Line 19. So we get
OPT <
Σ f(OUA) s 6f(T) + 2af(u") (E(1,2)
(39)
3. u" E O and max,e(1.2) f(u" J:) 2 0 and {u*) rejects the price in Line 18: In this case,
we must have c(u*) > B p())) and hence
BS(J)) BJ()) B c(O) ((O)(u))) S p())) < f(0) + +af(u*) af(u*) af(w*) a
B S(J))
< B
(40)
where the second inequality is got by Lemma 1. Note that all the elements in 0 \ {u²}
has been processed by Lines 3-6. Let O₂ (resp. O2) denote the set of sellers in 0 {u*)
who reject the offered prices that are calculated using A1 (resp. A2) in Line 4. By similar reasoning with Lemma 7, we get
f(u J.)
8,(u)
f(J)) +af(u*)
Wi E (1,2), Vu E E0;
(41)
du)
c(u)
B
Vi,j E (1,2) Aitj:
Σ
s(u) Jj) < S(J"):
(42)
(EOV(r)))
where 6c(u) is defined in the same way as that in the proof of Lemma 7. Therefore, we can use Eqns. (40)-(42) to get
1o ((J1) 5
Σ
f(u J1)
Σ flul Ji)
REOLU02
< f(J)+ + Σ 81(1) + -E 82(u)
(43)
MEO:
uεO,
$ 1(J)+ + cc(0 [(J) +af(1")
B
< [+ = f(J²) + {(J") f(u"),
(44)
16

---

where Eqn. (43) is due to submodularity and the greedy rule in Line 4. Similarly, we get
f(0) ( (O) f(J2) = (1+ ((J) +(5))((00) f(u")
(45)
Combining the above equations, we get
2
S(O) (u) 52 2 2 ((J") +
Ι(O 10rku")) ))
(46)
and hence
OPT < S(O))))))))) (u)]) [(u")( 22 (2 2++2 a 2)
[(J) + +35(n"),
(47)
Therefore, when 2 1.5, we have OPT 6f( + 2af S 6f((T) + 2a f(f(").
According to Lines 12-19 of Algorithm 4, the algorithm returns or {u²} with probability of 340 or a 3+a respectively. So we get
[[[(S)] Pr(S=
((T)) = T)
Pr(S {u") f(u))
= ( af(u") OPT
3 a 3+a 2 12
(48)
when a = 3. This completes the proof.
F Additional Experiments
In this section, conduct experiments using crowdsourcing application similar to that in [8, 16, 20, 22], where each worker (seller) in N owns an image, and a buyer with a budget B needs to crowdsource a set S of representative images from the workers. Following [8, 16, 20, 22], we the CIFAR-10 dataset [8, 16, 20, 22] containing ten thousands 32 x 32 color images, where each image associated with label denoting its category such as "Airplane", and the valuation (utility) of $ is calculated as
max SU. f(S) - = WEN
WES
I
E EuES
WES WES Su,v:
E
(49)
where Su.u denotes the similarity between any two images u and v and measured by the cosine similarity of the second additive factors in Eqn. (49) represent the "coverage" and "diversity" of S, respectively, and it is known that such a valuation function f(-) is non-monotone and submodular [16]. We assume that each worker has a private cost c(u) for providing its image, and set c(u) to be proportional to the standard deviation of its pixel intensities. Following the same setting as that in [22], the costs of all images are normalized with the average value of 0.1, and the images with labels in (Airplane, Automobile, B are considered. The other experimental settings are the same with those in Fig. 1.
pixel vectors of image and image v. Intuitively, the first and
SIP
RBC
CO TENM
SIP
RCA
TENN
2730
1e9
Oracle Querles
167
Utility
2720
2710
163
Budget
Budget
3
Figure 2: Comparing the BFMs for the crowdsoureing application
In Fig. 2, we compare our TripleEagleNN (TENM) algorithm with two state-of-the-art BFMs for non-monotone submodular valuations: (1) the -teratvvvee---rteeeeeeeeeeeeee (SIP) algorithm in
17

---

[9] with an approximation ratio of 64; and (2) the RandomClockAuction (RCA) algorithm in [22] with an approximation ratio of (3 + v5)². The experimental results in Fig. show that, our TENM algorithm consistently outperforms the other orders of magnitude fewer value oracle queries than the SIP algorithm. It is also noted that TENM and RCA perform similarly on the number of value oracle queries; this can be explained by the fact that RCA has nearly-linaar query complexity of (n log n.) and hence is also efficient for this problem instance (but with poorer performance on utility than TENM). These experimental results demonstrate the superiorities of our approach once again for non-monotone submodular valuations.
baselines on utility, while incurring about three
The code of paper can be found
https: / //a////moooouuu../////// attpeacccccennee////ppllelgggggo 4D1B/README,
README mdd
18


Reviews:
[{"review_id": "hCK9GyHbxn", "reviewer": "Reviewer_Mo9x", "summary": "This paper studies the budget feasible mecchanism design, where a buyer needs to select a subset from strategic sellers with private costs , and pays them under a budget $B$. The goal is to maximize the valuation of the subset $S$ defined as $f(S)$. This paper gives both deterministic and randomized solutions for this problem, with improved approximation ratio and pricing complexity(defined as the maximum number of prices offered in the clock auction in the worst case), for monotone and non-monotone submodular functions, respectively. Finally, the paper provides an experimental evaluation of their methods against SOTA, and showed that the utility and the number of queries are better than the iterative-pruning(IP) and Random-TM(RTM) algorithm. ", "questions": "Is there any concrete example of practical applications of this method. ", "limitations": "The reviewer personally believes that the studied problem might be a little inappropriate for machine learning conferences. Theory conferences might be a better fit. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The studied problem is well-motivated, and the theoretical results are solid. \n- The paper has experimental results to show empirically their advantage over existing methods. \n- The literature review is informative and pointed out some drawbacks of the existing works they mentioned. ", "weaknesses": "- There is no formal problem setting, so it might be hard for reviewers from outside AGT community to understand this problem at the first sight. \n\nSome minor comments for this paper:\n- The reviewer strongly suggest to replace $f(O)$ by $\\text{OPT}$.\n- line 138, $2^{\\mathcal{N}}$ should be $2^{|\\mathcal{N}|}$.\n- The description and the presentation of this algorithm is hard to understand. The reviewer suggests to add a line input with descriptions, e.g., the candidate set $C$, the accepted set $A$.\n- $v^*$ can be replaced by $u^*$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment: There is no formal problem setting, so it might be hard for reviewers from outside AGT community to understand this problem at the first sight.**\n\nResponse: Thanks a lot for your comment! We have provided the formal problem setting in Section 2, including the formal problem formulations, the definitions of clock auctions and submodular functions, as well as the assumptions and notation descriptions.\n\nFor a reader outside of the AGT community, our problem could also be understood as a simple pricing problem under incomplete information: we need to offer a proper price to each user with an unknown cost and finally select a group of users who accept the prices under the budget, such that the revenue of the selected users (cast by a submodular function) is maximized. Clearly, each user must behave truthfully on whether accepting the offered price or not for her/his own benefit (i.e.,truthfulness is guaranteed). By addressing this simple pricing problem, we have avoided using the other more complex forms of auctions (e.g., the sealed-bid auctions in prior studies \\[4, 10, 12, 21, 22, 35]) that are harder for a reader outside the AGT community to understand.\n\nWe will follow your comments to make further efforts to help the readers outside the AGT community to understand our problem.\n\n**Question: Is there any concrete example of practical applications of this method.**\n\n\nResponse: Thanks a lot for your question! We have provided two concrete examples of practical applications including crowdsourcing and influence maximization in the first paragraph of Section 1, Section 6 and Appendix F of the supplementary file. These applications have also been used as representative applications of budget-feasible mechanisms in prior studies(e.g., \\[4, 21, 22, 36, 37]). Specifically:&#x20;\n\n(1) In the influence maximization application shown in Section 1 and Section 6, there is a set of users (i.e.,sellers) in a social network and each of them has a cost for being selected as a \"seed user\".  After some users are selected as \"seed users\" by an advertiser with a budget for compensating the seed users, they will advertise the product to their friends and then the influence will propagate in the social network through the \"word of mouth\" effect. The goal of the advertiser is to select a proper set of seed users under the budget to maximize the \"influence spread\", i.e., the expectation of the number of users who are activated in the influence propagation, which is cast by a submodular function. This influence maximization problem was originally proposed by the celebrated paper \\[25] (with 9900+ citations) and has aroused great attention during the past two decades (e.g., see \\[5,15,31,32]). However, in practice the users may not report their true costs, so the advertiser is faced with the additional challenge of ensuring the truthfulness of the users, which turns the problem into an instance of the BFM problem studied in our paper.&#x20;\n\n(2) The crowdsourcing application is similar to the influence maximization application explained above, only with the difference that the \"advertiser\" and \"seed users\" in the influence maximization application are changed to the \"crowdsourcing task owner\" and \"workers\" in the crowdsourcing application, respectively, and that the target function is re-defined. In Appendix F of the supplementary file, we have elaborated on a concrete crowdsourcing example similar to that in \\[4, 19, 21, 22, 37].\n\nPlease note that our problem model is exactly the same as that proposed in the seminal paper \\[35] and is very general (one can regard it as essentially a submodular knapsack problem plus the truthfulness requirement), so there also exist many other applications in various fields such as mobile crowdsensing,federated learning, experimental design, social advertising, vehicle sharing,data pricing, team formation, cellular traffic planning, and so on. This can be verified by checking the 300+ citations of the seminal paper of \\[35] published in FOCS’10.&#x20;\n\nIf given a chance, we will follow your comments to further clarify the applications of our method.\n\n**Comment: The reviewer strongly suggest to replace f(O) by OPT.**\n\nResponse: Thanks. We will do as you suggested.\n\n**Comment: Line 138, $2^{\\mathcal{N}}$ should be $2^{|\\mathcal{N}|}$.**\n\nResponse: Thanks. We use $2^{\\mathcal{N}}$ to denote the power set of $\\mathcal{N}$. Such a notation for power set has also been used in many other proposals (e.g., \\[2]\\[3]\\[4]\\[8]\\[9]\\[16]\\[19]\\[20]\\[35]). We will revise to make it clearer.\n\n**Comment: The description and the presentation of this algorithm is hard to understand. The reviewer suggests to add a line input with descriptions, e.g., the candidate set C, the accepted set A.  $v^\\star$ can be placed by $u^\\star$**\n\nResponse: Thanks. We will do as you suggested.\n\n**Comment: The reviewer personally believes that the studied problem might be a little inappropriate for machine learning conferences. Theory conferences might be a better fit.**\n\nResponse: Thanks a lot for your comment! We agree on that our paper may also fit some theory conferences. However, the scope listed in the CFP of NeurIPS’23 includes “algorithm game theory”, which perfectly fits our paper. Moreover, since the representative applications of our paper include two social computing applications, i.e., influence maximization and crowdsourcing, which both have aroused great interests in the machine learning conferences/journals such as NeurIPS/JMLR/JAIR (e.g., \\[15, 23,31, 32, 38]), we think that our paper also fits well to another scope listed in the CFP of NeurIPS’23, i.e., “Social and economic aspects of machine learning”.\n\n"}, {"review_id": "J8CnB96zGD", "reviewer": "Reviewer_kDRB", "summary": "The paper considers the problem of designing budget feasible mechanisms, in which the designer has a budget B, agents have private costs, and to each subset S of agents is associated a reward. The goal is to design a mechanism that incentives agents to truthfully reveal their privare costs and allows the designer to choose a subset S of agents whose total cost is at most B, and that maximizes the optimal reward of the designer.\n\nThe paper provides both deterministic and randomized mechanisms for this setting both for monotone and submodular reward functions and for non monotone and submodular reward functions. All these mechanisms improves the approximation of the chosen subset S with respect to the optimal choice. Not only, they achieve these results with a faster and \"simpler to understand\" algorithm, in which agent are posted a price, they may accept or refuse the price, but the actual set of selected agents will be computed only at the end among the agents that did not refuse a price.", "questions": "Can you stress the difference and similarities between your mechanisms and sequential posted-price mechanisms by Chawla et al., 2010?\n\nDo you believe that a specific order of processing in algorithm 3 may help the performances of the mechanism? E.g., since f(u) are known (from the computation of v*), you may use thus information to discard the \"worse\" agents.", "limitations": "None", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The problem is interesting and received a lot of attention recently in our community.\n\nThe proposed algorithms improves over the previous ones.", "weaknesses": "None", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Question: Can you stress the difference and similarities between your mechanisms and sequential posted-price mechanisms by Chawla et al., 2010?**\n\nResponse: Thanks a lot. Nice question! We guess that \\[Chawla et al., 2010] refers to the STOC’10 paper “Multi-parameter Mechanism Design and Sequential Posted Pricing”. We think that this is an excellent paper, but it has studied a totally different problem. First, \\[Chawla et al., 2010] considers a “forward auction” problem where a seller (without a budget) needs to maximize the revenue by selling a product to a group of buyers, while we consider a “reverse auction” problem where a buyer (with a budget) needs to buy some products from a group of sellers. Please note that forward auctions and reverse auctions are two separated lines of research in auction theory and that’s why our problem is raised in FOCS’10 \\[35] after \\[Chawla et al., 2010]. Second, a major difference is that \\[Chawla et al., 2010] considers a “Bayesian setting” where the distributions of the preferences of the players are known, while we consider a “Prior-free” setting where there is no prior knowledge about the players. The only similarity between \\[Chawla et al., 2010] and our work is that some prices are offered to players, but \\[Chawla et al., 2010] use the “posted-pricing” scheme where each seller who accepts the offered price must be immediately selected as a winner, while we consider “clock auctions” where a seller is not mandatory to be selected as a winner if she/he accepts the offered price. Such a difference on pricing rule would lead to very different algorithm design and performance analysis even under the same problem.  \n\nIn summary, although \\[Chawla et al., 2010] is a great paper, it belongs to a different line of research and their techniques cannot be applied to our problem. We will cite \\[Chawla et al., 2010] and discuss about it.\n\n**Question: Do you believe that a specific order of processing in algorithm 3 may help the performances of the mechanism?E.g., since f(u) are known (from the computation of v\\*), you may use thus information to discard the “worse” agents.**\n\nResponse: Great question! Choosing order sounds a good idea. In fact, we had carefully thought about it before our submission,but it seemed that this idea can hardly help due to the following observations. In the traditional problem of submodular maximization with a knapsack constraint, good performance relies on selecting the elements strictly according to the non-increasing order of the ratios of marginal value to cost (e.g., see \\[Maxim Sviridenko 2004] “A note on maximizing a submodular set function subject to a knapsack constraint”). However, in our setting the costs of the sellers are unknown and even can be falsely reported due to the sellers’ strategic behaviors, so the strict order mentioned above cannot be ensured no matter how we order the elements based on their values. Even if we use a sealed-bid auction and solicit the cost information from the sellers to achieve the strict order mentioned above (as done in \\[12,21,22,35]), we have to trade off the approximation ratio for ensuring that the sellers report their true costs, and that’s why the sealed-bid auction approaches in \\[12,21,22,35] all have worse approximation ratios than ours. Moreover, choosing order results in super linear complexities which could be unsuitable for large markets. Due to the above considerations, we had abandoned the ordering idea to ensure linear time complexity while still achieving better performance ratios than SOTA.\n\n\n"}, {"review_id": "NIbCLRda65", "reviewer": "Reviewer_QWwV", "summary": "This paper proposes a novel technique in designing budget-feasible mechanisms (BFMs), which improves the state of the art results on approximation guarantees and query complexity simultaneously. In particular:\n\n* With monotone submodular functions, the newly proposed mechanisms improve the approximation from 4.75 to $\\frac{\\sqrt{13}+5}2$ (randomized BFM) and $2+\\sqrt{6}$ (deterministic BFM) and improve the query complexity from $O(n^2 \\log n)$ to $O(n)$;\n* With non-monotone submodular functions, the newly proposed mechanisms improve the approximation from $14+6\\sqrt{5}$ to 12 and improve the query complexity from $O(n \\log n)$ to $O(n)$.\n\nThe key innovation of the technique is to set query prices as a decreasing function of the value of the set of sellers accepted the offered prices so far. \n$$\\mathsf{price}(u) = \\mathsf{budget} \\cdot \\frac{\\mathsf{marginal ~ value}(u | \\mathsf{accepted ~ sellers})}{\\mathsf{value}(\\mathsf{accepted ~ sellers}) + \\alpha \\cdot \\max_{s}\\mathsf{value}(s)}.$$\n\nWith such adaptive price queries, each seller is queried with a price at most once. The final winners are then a subset of the sellers who accept the offers. One key advantage of this approach is that the query complexity becomes $O(n)$, and in the meanwhile the approximation guarantees are also improved with careful analysis and proper optimization of the parameter $\\alpha$.\n\nFinally, the empirical evaluation shows that the actual performance of the newly proposed mechanisms indeed dominates the benchmarks on both optimality and the number of queries.", "questions": "1. Is the current pricing formulation optimized? \n2. Will querying the sellers in the order of their values be helpful?", "limitations": "No specific limitation.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "* A significant improvement with a novel technique on a widely studied problem.\n* Simultaneously improvements on both approximation guarantee and query complexity.\n* Solid analysis on proving the approximation ratios.", "weaknesses": "* No empirical evaluation for the non-monotone submodular function case. (Addressed after author response)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment: No empirical evaluation for the non-monotone submodular function case.**\n\nResponse: Thanks a lot for your comment! Due to the page limits, the empirical evaluation for non-monotone submodular objectives is provided in the supplemental file (Appendix F), and we have mentioned about this in Lines 312-315 in Section 6 of the main file.\n\n**Question: Is the current pricing formulation optimized?**\n\nResponse: Thanks a lot for your question! We have carefully optimized the performance of our pricing method by adjusting the parameter \\alpha (e.g., see Lemma 3, Lemma 6, and Theorems 1-3) to get better ratios than the existing studies. We have also listed in Lines 34-36 the currently best-known lower bounds for BFMs with submodular objectives (which were proposed by Chen et al. \\[12]), i.e., 2 for randomized BFMs and $1+\\sqrt{2}$ for deterministic ones. To the best of knowledge, since the work of Chen et al. \\[12] in SODA’11, no other papers have provided any further lower bounds for BFMs with submodular objectives. It is interesting to make further optimizations for our algorithms to narrow the gaps between our performance ratios and the lower bounds in \\[12] (or provide tighter lower bounds than \\[12]), which will be our future work. We will follow your comments to provide more discussions about this.\n\n**Question: Will querying the sellers in the order of their values be helpful?**\n\nResponse: Great question! Choosing order sounds a good idea. In fact, we had carefully thought about it before our submission,but it seemed that this idea can hardly help due to the following observations.In the traditional problem of submodular maximization with a knapsack constraint, good performance relies on selecting the elements strictly according to the non-increasing order of the ratios of marginal value to cost (e.g., see \\[Maxim Sviridenko 2004] “A note on maximizing a submodular set function subject to a knapsack constraint”). However, in our setting the costs of the sellers are unknown and even can be falsely reported due to the sellers’ strategic behaviors, so the strict order mentioned above cannot be ensured no matter how we order the elements based on their values. Even if we use a sealed-bid auction and solicit the cost information from the sellers to achieve the strict order mentioned above (as done in \\[12,21,22,35]), we have to trade off the approximation ratio for ensuring that the sellers report their true costs, and that’s why the sealed-bid auction approaches in \\[12,21,22,35] all have worse approximation ratios than ours. Moreover, choosing order results in super linear complexities which could be unsuitable for large markets. Due to the above considerations, we had abandoned the ordering idea to ensure linear time complexity while still achieving better performance ratios than SOTA.\n\n"}, {"review_id": "M9Vbq3KPB4", "reviewer": "Reviewer_LiBq", "summary": "The paper studies the design of budget-feasible mechanisms: a buyer wants to purchase from a set of potential sellers with different production costs which are private information, and the goal is to maximize the total value subject to a budget constraint.  The main result is a new framework that achieves (1) good approximation to the first-best and (2) low pricing complexity, roughly measured by the number of questions each seller has to answer.  The authors conduct experiments that show the new methods outperform existing methods on influence maximization tasks.", "questions": "(also including detailed comments here)\n\nLine 117, \"... as simple as a posted-pricing mechanism ...\": maybe this will become clear later, but do you mean you offer a single price to each seller, and the seller can possibly be selected only if they accept the price?  It might help to be explicit about the connection to and difference from posted pricing early on.\n\nLine 150, \"... because otherwise we can ...\": I guess this would add another pricing query to each seller?  Is this why you keep writing O(1) rather than 1?\n\nLast paragraph in Section 6: it would be nice to explicitly comment on the tradeoff between queries and quality of solution for all 3 (families) of methods.  The impression I got is RTM makes much fewer queries at the cost of worse quality of solution, while IP returns decent solutions at the cost of much more queries.  (And then of course TER / TED has the best performance in terms of both.)", "limitations": "n/a", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The problem is very well established and practically relevant.  The paper is well written and technical ideas are clearly explained.  The paper makes solid progress for the problem by proposing a new design framework, which might trigger further progress.  The technical contribution appears to be nontrivial.", "weaknesses": "While I like the paper overall, one minor complaint is it doesn't say much about lower bounds.  Of course this is largely due to the intrinsic complexity of the BFM problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\n**Comment\\:While I like the paper overall, one minor complaint is it doesn't say much about lower bounds. Of course this is largely due to the intrinsic complexity of the BFM problem.**\n\nResponse: Thanks a lot for your comments! For BFMs with additive valuation functions, Singer \\[35] has proposed a lower bound of 2, and Chen et al. \\[12] have proposed two improved lower bounds of 2 (for randomized BFMs) and $1+\\sqrt{2}$ (for deterministic BFMs). Since submodular functions generalize additive functions, these lower bounds also apply to BFMs with submodular objectives. In Lines 34-36 of Section 1.1, we have listed the lower bounds of Chen et al. \\[12]. To the best of knowledge, since the work of Chen et al. \\[12] in SODA’11, no other papers have provided any further lower bounds for BFMs with submodular objectives, which remains as an interesting open problem and we will study it in future. We will add more discussions about this.\n\n**Question: Line 117, \"... as simple as a posted-pricing mechanism ...\": maybe this will become clear later, but do you mean you offer a single price to each seller, and the seller can possibly be selected only if they accept the price? It might help to be explicit about the connection to and difference from posted pricing early on.**\n\nResponse: Nice question! You are correct. We have tried to briefly explain the differences between posted pricing and clock auctions in Lines 100-102 due to the space constraints, and we will follow your suggestion to revise these lines to make the differences clearer. Here is a detailed explanation:\n\nSuppose that each user is offered one price in a clock auction. Then the only difference between this clock auction and any posted-pricing mechanism is about how they treat any seller u who accepts the offered price: it is mandatory to select u as a winner in the posted-pricing mechanism, while u can be either a winner or a loser in the clock auction (this implies that the clock auction is allowed to use the observation of all the sellers’ behaviors in the end of the auction to decide whether u should be selected as a winner). However, from the perspective of pricing complexity, these two mechanisms are the same. That’s why we say “…virtually as simple as…”.\n\n**Question: Line 150, \"... because otherwise we can ...\": I guess this would add another pricing query to each seller? Is this why you keep writing O(1) rather than 1?**\n\nResponse: Thanks a lot! You are right. As claimed in Lines 149-151, we have adopted the assumption made in \\[9, 12] that no user’s cost is larger than B (our mechanism offers only one price to each user under this assumption). As you see, Lines 149-151 also suggest a simple method to remove this assumption by using an additional query to each seller. So we write O(1) instead of 1 for rigorousness.\n\nActually, there is another simple method to remove the assumption in Lines 149-151 by using at most 1 additional query in total. Specifically, since each user is guaranteed to be offered a price no more than B in our main algorithm (which rules out every seller with a cost larger than B), we only need to identify a valid $v^*$ before running our algorithm. This can be done by first sorting all the sellers according to the non-increasing order of their values, and then offer B to them one by one until seeing the first seller accepting B and then that seller is clearly a valid $v^*$. After that, we delete all the sellers rejecting B and run our algorithm. Clearly,using such a method, eventually $v^*$ is queried for at most 2 times and any other seller is queried once. We have omitted this method for conciseness and would add a discussion on it if needed.\n\n**Question: Last paragraph in Section 6: it would be nice to explicitly comment on the tradeoff between queries and quality of solution for all 3 (families) of methods. The impression I got is RTM makes much fewer queries at the cost of worse quality of solution, while IP returns decent solutions at the cost of much more queries. (And then of course TER /TED has the best performance in terms of both.)**\n\nResponse: Thanks a lot! You are correct. We will fully follow your suggestions to add these comments."}]

Author rebuttal:

Meta-review: I am recommending this paper for acceptance. All four reviewers support acceptance (7,7,7,7). There was broad consensus that this paper advances the theoretical state-of-the-art, and that the experiments demonstrate that the gains are not just of theoretical nature.
Decision: Accept (poster)