Budget Feasible Mechanisms: A Survey

1 Introduction

Auction theory [Myerson, 1981; Klemperer, 1999], a branch of economic theory that studies different types of auctions and the behavior of auction participants, has guided the development of auctions for buying, selling, and allocating items (e.g., goods or services) in many real-world application domains. These domains include grid computing, edge computing, the World Wide Web, e-commerce, networking, and social choice. Moreover, auctions of various types have received significant attention in the Artificial Intelligence (AI) community due to their inherent relevance and connections to other areas in AI (e.g., autonomous agents [Wellman et al., 2007]).

Generally, auctions can be categorized into two main types: seller-centric auctions or buyer-centric procurement (or reverse) auctions. In a seller-centric auction, sellers design auction mechanisms to determine how to sell a set of items to the auction participants in order to optimize sellers' objectives (e.g., revenue or social welfare). The auction participants submit bids (or willingness to pay) for the items, and the auction mechanisms determine the allocation of items to participants and participants' payments for buying the items. For instance, the first-price auction, the second-price auction, and the Vickrey-Clarke-Groves (VCG) auction mechanisms [Vickrey, 1961; Clarke, 1971; Groves, 1973] are well-known mechanisms for seller-centric auctions.

∗Corresponding author

On the other hand, in a buyer-centric procurement (or reverse) auction, which is the focus of this survey, the buyers design procurement auction mechanisms to determine how to procure items from the participants (or sellers) in order to optimize buyers' utilities for obtaining the items. The participants (or sellers) submit costs for their items, and the procurement auction mechanisms determine items to procure from the participants (or sellers) and participants' (or sellers') payments for selling the items. For instance, in federated learning [Zhang et al., 2021], the training task owner (buyer) procures data services from workers (sellers) who submit costs for training the global model. Additionally, in crowdsensing [Zheng et al., 2020], the requester (buyer) typically aims to engage users (sellers) in providing sensing data through procurement auctions.

Because participants' information (e.g., their values for the items or their true costs of items) is private, a primary design goal for auction or procurement auction mechanisms is to ensure that participants report information truthfully (i.e., report values as bids or costs as prices). That is, the participants will have no incentive to misreport information.

In addition to truthfulness, another crucial goal pertaining to buyer-centric procurement (or reverse) auctions is to ensure buyer budget feasibility in procurement auction settings that are prevalent in many real-world domains. More specifically, the buyers in these settings have budget constraints (e.g., purchasing power). Therefore, procurement auction mechanisms must also be budget feasible, ensuring that the total payment to the sellers is no more than the buyer's budget.

Motivated by several applications in real-world domains, [Singer, 2010; Singer, 2014] initiated the study of budget feasible mechanisms for procurement auction settings when the buyer has the limited budget. The key challenge of designing budget feasible mechanisms is that the budgets limit the total payment to sellers, which depend on sellers' private costs of the items. Thus, designing good budget feasible mechanisms is particularly difficult and different from other auction settings (see, e.g., [Aggarwal and Hartline, 2006]). Since the introduction of budget feasible mechanisms for procurement auction settings with budgeted (or budget constrained) buyers [Singer, 2010], research in this area has experienced significant growth. Moreover, research results have been published in prominent venues such as those in AI and economics.

Furthermore, numerous works have explored various settings and generalizations of the classical setting of [Singer, 2010], with a focus on designing theoretically provable good (approximately optimal) budget feasible mechanisms for increasingly complex buyers' utility or valuation functions for the items satisfying desirable properties (e.g., truthfulness). Apart from the theoretical interests, research efforts have also considered designing budget feasible mechanisms for settings that have real-world applications in domains such as crowdsourcing [Singla and Krause, 2013], crowdsensing [Zheng et al., 2020], participatory sensing [Restuccia et al., 2016], bike sharing [Angelopoulos et al., 2018], recommender system [Dandekar et al., 2014], and federated learning [Zhang et al., 2021].

In this survey, we provide a comprehensive overview of key procurement auction settings and mechanism design results of budget feasible mechanisms from existing literature. We also provide several promising directions for future research. To the best of our knowledge, this is the first survey summarizing the significant contributions of existing literature on budget feasible mechanisms.

Roadmap. In Section 2, we present the classical procurement auction settings with budgeted buyers and the corresponding mechanisms for different buyer valuation functions. In Section 3, we proceed to discuss recent settings and application domains beyond the classical settings. In Section 4, we introduce promising future directions when designing budget feasible mechanisms for general procurement auction settings. Finally, we conclude this survey in Section 5.

2 The Classical Procurement Auction Settings with Budgeted Buyers

In this section, we first present the classical procurement auction settings with budgeted buyers and then review the corresponding existing key mechanisms for different buyer valuation functions.

2.1 The Classical Settings

In the classical procurement auction setting [Singer, 2010], there is a single buyer and n sellers, denoted by A = {1, 2, ..., n}. Each seller has an item for sale. Seller i ∈ [n] has a privately known cost ci ≥ 0, and denote by c = (ci)ni=1 the cost vector of sellers. The buyer wants to procure sellers' items with a budget B. In addition, the buyer has a publicly known valuation function V (S) which evaluates the value of the buyer for the given subset S ⊆ A of items. Due to the revelation principle [Epstein and Peters, 1999], we only consider direct-revelation mechanisms. We use bi to denote the bid (or reported cost) of seller i. Upon receiving bids b = (bi)ni=1 of the reported costs from sellers, a mechanismM determines an allocation W ⊆ A as winning sellers (whose items will be purchased) and the payments p = (pi)ni=1 to the sellers.

More specifically, a deterministic mechanism M = (x, p) determines an allocation function x(b) : Rn+ → {0, 1}n and a payment function p(b) : Rn+ → Rn+. Let xi(b) and pi(b) be the allocation and payment of seller i, respectively. Specifically, if xi(b) = 0, then pi(b) = 0. We use b-i to denote the bid vector of other bids without seller i. Sellers can bid strategically on their costs and would like to maximize their utilities. The utility of seller i is the difference between the obtained payment and the cost, i.e.,

In addition, the proposed budget feasible mechanismM = (x, p) should satisfy the following desired economic properties:

• Individual Rationality: Every seller i ∈ A receives non-negative utility, i.e., ui(ci, b-i) ≥ 0.
• Incentive Compatibility or Truthfulness: Every seller i ∈ A obtains the maximum utility when she bids the true cost ci, i.e., ui(ci, b-i) ≥ ui(bi, b-i) for any ci and b = (bi, b-i).
• Computational Efficiency: The functions x and p can be computed in polynomial time.
• Budget Feasibility: The total payment of the buyer does not exceed the given budget B, i.e., ∑i∈W pi(b) ≤ B.

[Myerson, 1981] provided a characterization of the mechanisms that are truthful in the single parameter domains. Such characterization, shown below, is applicable to designing budget feasible mechanisms.

Theorem 1. In a single parameter domain, a mechanism M= (x, p) guarantees sellers' truthfulness if and only if:

(1) xi(bi, c-i) is monotone: ∀i ∈ W, if bi ≤ ci, then xi(ci, c-i) = 1 implies xi(bi, c-i) = 1 for every c-i; (2) winners are paid threshold payments: the payment to each winning bidder is the critical value inf{ci :

xi(ci, c-i) = 0}.

We denote by ALG(V, b, B) the value V (W) derived from a deterministic mechanism. If the buyer knows the true private costs c, we can directly choose the subset of items with the maximum value of the buyer under the budget constraint and pay each selected seller their true cost. Let OPT(V, c, B) denote the optimal value to this problem, i.e.,

A mechanism achieves an α-approximation against the benchmark OPT(V, c,B), if for any input instance, ALG(V, b,B) is at least a 1α -fraction of the optimal value OPT(V, c,B) where α ≥ 1, i.e.,

We sometimes refer α as the approximation ratio.

In the existing literature, some works designed randomized mechanisms to improve the performance of deterministic mechanisms. Roughly speaking, a randomized mechanism can often be represented as a probability distribution over truthful deterministic mechanisms. As a result, randomized mechanisms will have randomized allocation functions and payment rules. The approximation ratio of a randomized mechanism is defined as the ratio between the optimal value and the expected value obtained from the randomized mechanism.

2.2 The Classical Results

For the classical procurement auction setting with a single budget constrained buyer, existing studies have focused on designing efficient budget feasible mechanisms for different buyer valuation functions. We review these existing budget feasible mechanisms and their theoretical performances (i.e., approximation ratios) in this classical setting.

There are four main valuation functions (i.e., additive, submodular, XOS, and subadditive) that have been investigated previously. We first provide their definitions formally below. For additive valuation functions, we use v = (vi)ni=1 to denote the values of sellers and vi is the value for seller si.

Definition 1 (Additive). A valuation function V : 2n → R+ is additive if V (S) = ∑i∈S vi, ∀S ⊆ A.

Definition 2 (Submodular). A valuation function V : 2n → R+ is submodular if

Specifically, the valuation function V (·) is monotone if V (S) ≤ V (T), ∀S ⊆ T ⊆ A, while it is symmetric if V (S) = V (A \ S) for any S ⊆ A.

Definition 3 (XOS, a.k.a., fractionally subadditive). A valuation function V : 2n →R+ is XOS if there is a set of linear functions f1, . . . , fm such that

for any S ⊆ A. Note that the number of functions m can be exponential in n = |A|.

Definition 4 (Subadditive, a.k.a., complement free). A valuation function V : 2n → R+ is subadditive if V (S)+V (T) ≥ V (S ∪ T ) for any S, T ⊆ A.

It is not hard to see that the valuation function V (·) adheres to the following hierarchical structure,

additive ⊂ submodular ⊂ XOS ⊂ subadditive.

Therefore, a mechanism for a valuation function in a higher hierarchical structure can be applied to those that are lower. Next, we provide existing mechanisms and their approximation ratios for the above-mentioned valuation functions.

If not specifically highlighted, all presented mechanisms in this section satisfies the required properties, i.e., individual rationality, truthfulness, computational efficiency, and budget feasibility.

2.3 Additive Valuation Functions

The classical results for additive valuation functions are summarized in Table 1. For additive valuation functions, recall that vi is the value for seller si. Given the input of the mechanisms, [Singer, 2010] first introduced a mechanism with a 5-approximation by using a greedy strategy to select items/sellers. Such a greedy strategy has been formally proven to be monotonic and is illustrated in GREEDYADDITIVE. Initially, the strategy involves sorting all sellers based on their ascending order of costs relative to values and then identifying the maximum number of winners to be selected sequentially under this order. If there are a total of k chosen sellers in set W, then the threshold payment for unit value of seller i is determined by the minimum value between ck+1 vk+1 , which represents the cost relative to the value of the (k+1)-th seller, and B ∑i∈W vi , which is the average payment for the selected sellers, i.e., pi = vi min{ ck+1 vk+1 , B ∑i∈W vi }.

GREEDY-ADDITIVE

1. Order all items of sellers in A, i.e., c1 v1 ≤ c2 v2 ≤ · · · ≤ cn vn
2. Let k = 1 andW = ∅
3. While k ≤ n and ck/vk ≤ B ∑i∈W∪{k} vi

1. Return winning set W

Subsequently, to improve the approximation ratio, [Chen et al., 2011] introduced a deterministic mechanism that achieves a (2+√2)-approximation. This mechanism leverages the optimal value of the fractional knapsack problem, which is the relaxed version of the optimal problem in (2) and can be computed in polynomial time. Moreover, they proposed a mechanism that randomly combines a deterministic mechanism and the mechanism directly outputting the seller with the highest value within the budget. They proved that this randomized mechanism achieves a 3-approximation. They also provided lower bounds of 1 + √2 and 2 for deterministic and randomized mechanisms, respectively. Later, [Gravin et al., 2020] presented an improved randomized mechanism with an approximation ratio of 2, perfectly matching the lower bound. They also introduced a deterministic mechanism with a 3approximation, improving the previously known the best result of 2 + √2.

Building on the aforementioned theoretical findings, some studies have sought to improve mechanism performance by considering divisible items and the large market assumption. [Anari et al., 2014] proposed an optimal deterministic mechanismwith an approximation ratio of e e-1 for divisible items, incorporating the large market assumption that each seller's cost is significantly smaller compared to the buyer's budget. Moreover, under the same large market assumption, [Anari et al., 2014] demonstrated a randomized mechanism with a e e-1 -approximation when dealing with indivisible items.

[Klumper and Sch¨afer, 2022] took a step further by eliminating the large market assumption and assuming that sellers' costs are bounded by the buyer's budget. They designed a deterministic mechanism for divisible items that has a 2.62approximation and provided a lower bound of 1.25. Additionally, by applying the bounded cost efficiency criterion, i.e., ci vi ≤ θ where θ ≤ 2, they introduced a deterministic mechanism with an approximation ratio of 2 and a lower bound of 1.18.

2.4 Submodular Valuation Functions

Due to its practicality, submodular valuation functions have been extensively studied theoretically and practically in many domains. In this subsection, our main focus is to review relevant theoretical results (i.e., approximation ratios) when the buyer valuation function is submodular. The classical results for submodular valuation functions are summarized in Table 2.

For any given submodular valuation function, we denote the marginal contribution of item i with respect to set S as Vi|S = V (S ∪ {i}) - V (S). We can sort sellers according to their non-decreasing costs relative to their marginal contributions, i.e.,

where Si-1 = {1, 2, · · · , i - 1} and S0 = ∅. Because the function is submodular, we have

Next, we present the proportional share allocation rule which has been extensively applied in designing budget feasible mechanisms for submodular valuation functions 1 .

Definition 5 (Proportional Share Allocation Rule, [Singer, 2010]). For a budget B and set of sellers A with cost vector c, the generalized proportional share allocation rule sorts sellers according to Eq. (6) and allocates to sellers 1, ..., k that respect ci ≤ B · Vi|Si-1 /V (Si). Observe that this condition is met for every 1, · · · , i when i ≤ k.

1 We note that the mechanism design idea for additive valuation functions is an instance of the proportional share allocation rule.

Monotone Submodular Valuation Functions. Given the above proportional share allocation rule, [Singer, 2010] first introduced a randomized mechanism with an 233.83approximation for monotone submodular valuation functions. Soon after, [Chen et al., 2011] proposed a greedy based strategy (see GREEDY-SUBMODULAR) to choose winners. Specially, this strategy only uses half of the budget to compute the average payment for selected values, i.e., B/2 V (Sk-1∪{k}) . Based on the GREEDY-SUBMODULAR strategy, they designed a deterministic mechanism with 8.34approximation and a randomized mechanism with 7.91approximation. They also proved that the lower bounds of the deterministic and randomized mechanism are 1 + √2 and 2, respectively.

GREEDY-SUBMODULAR

1. Let k = 1 andW = ∅
2. While k ≤ n and ck/Vi|Sk-1 ≤ B/2 V (Sk-1∪{k})
3. W ← W ∪ {k}, k ← k + 1
4. Return winning set S

The winner selection process here bears similarity to that in additive functions. However, the threshold payment for each winner is rather different due to the distinctive property of the submodular valuation function. That is, the marginal value of the selected seller will vary depending on the round chosen. The rationale behind the payment characterization for the submodular valuation function can be described as follows. Consider running the proportional share mechanism without seller i. For the first j sellers in the marginal contribution sorting, by using the marginal contribution of i at point j, we can find the maximum cost that seller i can declare to replace the seller in the j-th place in the sorting. Taking the maximum of these costs for all possible point j guarantees payments that ensure truthfulness. Specifically, let k′ denote the index of the last seller j ∈ A\{i} that respects cj ≤ Vj|Sj-1 · B2 /V (Sj). For brevity, we will write

and

Definition 6 (Payment Characterization [Singer, 2010]). The threshold payment for each winner i ∈ W is

Subsequently, [Jalaly and Tardos, 2021] introduced a randomized mechanism achieving 5-approximation, which improved the bound of 7.91 in [Chen et al., 2011]. Additionally, when mechanisms have access to an oracle that computes the true optimal value, [Jalaly and Tardos, 2021] presented deterministic and randomized mechanisms with exponential time complexities that achieve approximation ratios of 4.56 and 4, respectively.

For large markets where the value of each agent is small compared to the optimal value, [Jalaly and Tardos, 2021] gave a deterministic mechanism ensuring a 1 + e ≈ 2.58approximation. Differently, [Anari et al., 2014] used a cost version for defining the largeness of the market (i.e., each seller's cost is significantly smaller compared to the buyer's budget) and proposed deterministic mechanisms with a 2approximation and a 3-approximation, with exponential and polynomial running time, respectively.

As the class of deferred-acceptance (clock) auctions has been proven to be strategy-proof for auction settings, [Balkanski et al., 2022] investigated the design of clock auction mechanisms for procurement auction settings with budgeted buyers. They proposed a deterministic mechanism with a better approximation ratio of 4.75. Considering the idea of clock auctions, [Han et al., 2023] improved the approximation ratios by proposing deterministic and randomized mechanisms with approximation ratios of 4.45 and 4.3, respectively.

Non-monotone and Symmetric Submodular Valuation Functions. For non-monotone submodular valuation functions, [Amanatidis et al., 2019] proposed the first randomized mechanismwith an approximation ratio of 505. [Balkanski et al., 2022] provided a clock-auction based deterministic mechanism with an approximation ratio of 64, improving the best known randomized approximation of 505. Based on this result, [Huang et al., 2023] improved the approximation ratio to 27.4. [Han et al., 2023] further proposed a randomized mechanism with a better approximation ratio of 12. For symmetric submodular valuation functions, a prominent class of nonmonotone submodular functions, [Amanatidis et al., 2017] introduced both deterministic and randomized mechanisms that achieve approximation ratios of 10.9 and 10 respectively, with super-polynomial running time (i.e., any running time faster than polynomial time).

2.5 XOS and Subadditive Valuation Functions

For XOS valuation functions, under the demand oracle model (i.e., for any given price vector p1, ..., pn, it returns a subset T ∈ argmaxS⊆A V (S) - ∑i∈S pi), [Bei et al., 2012] proposed a randomized mechanism with an approximation ratio of 768 by using linear programming that describes some fractional covers of the valuation functions. Building upon this, [Amanatidis et al., 2017] improved the approximation ratio to 244 with super-polynomial running time. They also demonstrated that, for any fixed ϵ > 0, any (randomized) n1-ϵ -approximation mechanism for XOS valuation functions requires exponentially many value queries (i.e., value oracle receives a subset S and returns V (S)) in expectation.

Regarding subadditive functions in the demand oracle model, [Dobzinski et al., 2011] presented a randomized mechanism that achieves an O(log2 n)-approximation and a deterministic mechanism with an O(log3 n)-approximation.

Subsequently, [Bei et al., 2012] improved the approximation ratio to O( logn log logn ). Later, [Balkanski et al., 2022] provided a clock-auction based deterministic mechanism with an approximation ratio of O(log(n)/ log log(n)) that matches the best known randomized mechanisms by [Bei et al., 2012] and improved the best known deterministic mechanism with an approximation ratio of O(log3 (n)) by [Dobzinski et al., 2011].

2.6 Specific Valuation Functions

In addition to the previously discussed standard valuation functions, the related procurement auction literature has explored specific subclasses of classical valuation functions (e.g., additive and submodular valuation functions). For these subclasses of valuation functions, several studies proposed mechanisms that achieve improved approximation ratios. These subclasses of valuation functions include unweighted/weighted cut valuation functions [Dobzinski et al., 2011; Amanatidis et al., 2017], weighted coverage valuation functions [Amanatidis et al., 2016], budgeted matching valuation functions [Amanatidis et al., 2016], concave additive valuation functions [Amanatidis et al., 2023], and linear capped valuation functions [Klumper and Sch¨afer, 2022].

3 Beyond the Classical Settings

In addition to the aforementioned mechanism design results for different buyer valuation functions, extensive research has explored other procurement auction settings of budget feasible mechanisms. These important settings include online, Bayesian, multi-unit, and two-sided auction extensions of the classical settings. Other studies have also examined other practical settings that draw inspiration from real-world application domains such as crowdsourcing and crowdsensing. In this section, our main focus is to review these settings that go beyond the classical settings primarily in game theory or AI communities.

3.1 Online Settings

Different from the classical works that consider offline settings, there exists literature focusing on online settings where sellers may arrive over time 2 . [Singer and Mittal, 2011] first investigated an online procurement auction setting with a single budgeted buyer where sellers arrive in a random order over time and designed mechanisms for additive valuation functions with constant competitive ratios. [Badanidiyuru et al., 2012] presented a posted price mechanism with a constant competitive ratio when the buyer has a symmetric submodular valuation function and sellers arrive in a random order over time. For non-symmetric submodular valuation functions, they provided a posted price mechanism that is O(logn)-competitive. For the non-monotone submodular valuation functions, [Amanatidis et al., 2019] proposed the first O(1)-approximation mechanism (the ratio is 1710).

2 In online settings, it is common to use the concept of competitive ratio [Willey and Rao, 1980] (i.e., the ratio between the performance of the proposed mechanism and that of the optimal offline value) to evaluate the performance of the proposed mechanisms.

Moreover, they provided O(p)-approximation mechanisms for both monotone and non-monotone submodular valuation functions in independence systems with rank quotient at most p.

Apart from the above settings, other studies considered other online procurement auction settings inspired by realworld characteristics and domains, especially in crowdsourcing and crowdsensing. We provide an outline of these studies below by focusing on describing these settings.

Multiple Private Parameter Settings. [Zhao et al., 2014] considered an online procurement auction setting with a budgeted buyer where each arriving seller holds multiple pieces of private information, including arrival time, departure time, and cost. In their setting, the sellers have the ability to misrepresent their multiple private parameters to maximize their utility, which is more challenging than a single private parameter setting. Therefore, Myerson's characterization of singleparameter domains does not apply directly. However, they introduced online mechanisms that can ensure truthfulness on these private parameters.

Heterogeneous Task Assignment Settings. [Zhang et al., 2016] considered online heterogeneous task assignment within crowdsourcing markets, where a budget constrained requester (i.e., the buyer) has a collection of tasks and the workers (sellers) arrive sequentially over time. In their setting, the workers (sellers) declare the sets of tasks they can handle along with their desired payment for each task. The requester faces online decisions in assigning tasks to workers while ensuring budget feasibility.

Time-Discounting Value Settings. In some online crowdsourcing domains, the buyer's values for items may decrease over time (e.g., the value of gathered sensing data might decrease due to its time-sensitivity). [Zheng et al., 2020] designed a mechanism involving the selection of users through a time-dependent threshold for their values, when simultaneously achieving truthfulness and budget feasibility.

Bi-Objective Optimization Settings. Existing studies mostly focus on optimizing one buyer valuation function for the values of selecting workers. However, some works considered optimizing multiple objectives at the same time. For instance, [Zhang et al., 2020] proposed mechanisms that can effectively optimize the buyer valuation function and the diversity of chosen sellers simultaneously.

Unreliable Seller Settings. As sellers can be unreliable when providing services in crowdsourcing (e.g., unable to complete the assigned tasks within the allocated time), [Chandra et al., 2015] presented mechanisms ensuring that the tasks can be reallocated to other sellers to guarantee timely completion of the set of tasks by the deadline.

Settings of Incremental Arrival of Budget. Another scenario that is taken into consideration in terms of budget by [Mukhopadhyay et al., 2022] is that the buyer does not have an entire budget available a priori, but the overall budget comes incrementally in multiple phases. They proposed a mechanism that can guarantee ensure the budget constraint at every phase.

3.2 Bayesian Procurement Auction Settings

Compared with previous works that have no prior knowledge of sellers' private information, some literature considered the Bayesian procurement auction setting with a single budgeted buyer where sellers' costs are drawn from some known distribution. In this setting, [Bei et al., 2012] provided a randomized 512 α approximation (α is a positive constant) mechanism for subadditive valuation functions satisfying the ex-post budget constraint, i.e., the payments to the agents never exceed the budget for any realization of sellers' costs. [Ensthaler and Giebe, 2014] further analyzed the characterization of the optimal mechanism for additive valuation functions that satisfies the ex-ante budget constraint, i.e., in expectation over realizations of sellers' costs and random choices of the mechanism. Subsequently, [Balkanski and Hartline, 2016] considered both ex-ante and ex-post budget constraints and proposed mechanisms for these two constraints with approximation ratios depending on the market size 3 .

The above-mentioned works assume that the distribution of sellers' costs is known. However, in various real-world application domains, the distribution of sellers' costs often remains unknown, posing a challenge for mechanism design. To address this, [Singla and Krause, 2013] focused on a stochastic setting where sellers' costs obey an unknown distribution. They designed an upper confidence bound-based multi-armed bandit mechanism achieving the optimal regret bounds (i.e., the difference from the optimal value with prior information of sellers' costs). In contrast, [Biswas et al., 2015] considered a setting where sellers' values are drawn from an unknown distribution. They proposed a learning-based mechanism that can estimate sellers' values when ensuring truthfulness and obtain a logarithm regret bound with respect to the buyer's budget.

3.3 Multi-unit Settings

While most studies focus on settings where each seller offers only a single unit of an item, other studies have examined the settings where a seller has multiple units of an item and may benefit from selling any number of them. [Chan and Chen, 2014] is the first to study such settings and design mechanisms for such settings. They demonstrated that achieving a mechanism that approximates the buyer's optimal value within lnn for additive valuation functions, where n is the total number of available units, is unattainable. Consequently, they introduced a randomized mechanism achieving a 4(1 + lnn)-approximation for concave additive valuation functions, i.e., the margins for the same item are nonincreasing, including bounded knapsack problems as a special case. Additionally, for subadditive valuation functions, they develop a randomized mechanism capable of providing an O(log2 n/ log log n)-approximation using a demand oracle. [Wu et al., 2019] extended the settings to consider local diminishing return (LDR) valuation functions, which are a class of functions located between concave additivity and submodularity. They introduced both deterministic and randomized mechanisms with approximation ratios of O(lnn), respectively.

3 More detailed approximation results for different valuation functions can be referred to in Fig. 1 [Balkanski and Hartline, 2016].

3.4 Two-sided Auction Settings

In the classical procurement auction settings, there is only a single buyer. Such settings might not be realistic in application domains such as two-sided markets where there are multiple buyers. [Chan and Chen, 2016] considered the problem of designing mechanisms for a dealer, who aims to maximize revenue by buying items from a seller market and selling them to a buyer market. For such settings for subadditive valuation functions, they proposed a randomized O((log2 n)(log2 m))- approximation mechanism for the dealer, where n and m are the number of buyers and sellers, respectively. In another direction, [Liu et al., 2022] considered two-sided markets where multiple buyers want to procure items from sellers. Additionally, the buyers are strategic about their private information on the budgets. For such a setting, they proposed mechanisms that ensure truthfulness on both sellers' and buyers' sides and achieve constant approximations.

3.5 Other Settings

We now highlight additional settings that have been considered in recent years.

Diffusion Settings. Many works in auctions assume that sellers are reachable to the buyer and voluntarily participate in the auctions. However, in many real-world situations, many potential sellers may be unaware of the auctions (e.g., due to the lack of knowledge). Some works make efforts to design diffusion mechanisms to incentivize participants to invite other potential agents to participate in the auctions [Li et al., 2017]. [Liu et al., 2021b] first studied the procurement auction settings with a budgeted buyer and designed diffusion mechanisms based on the seller network. The proposed randomized mechanism has a logarithmic approximation ratio with respect to the network size.

Sybil-proof Settings. In the auction literature, studies have examined false-name manipulation (also known as sybilproofness), where a seller can report more than once by creating and using fake identifiers. [Liu et al., 2023] showed that the sellers can easily obtain higher utility by performing falsename manipulation in existing mechanisms and proposed a sybil-proof mechanism that can deter the false-name attack and ensure truthfulness simultaneously.

Fairness Settings. Fairness has also been considered in procurement auction settings with budgeted buyers. [Liu et al., 2021a] considered the settings that sellers belong to different groups and the buyer wants to select sellers from different groups proportionally. For this setting, they proposed proportion-representative mechanisms with approximation ratios with respect to the group size.

Matroid Settings. [Leonardi et al., 2017] considered the settings that the buyer has additive valuation functions and wants to procure items from sellers that form an independent set in a given matroid structure. They proposed a deterministic mechanism with an approximation ratio of 4. They also demonstrated that, given a polynomial time deterministic blackbox that returns α-approximation solutions to the matroid intersection problem, there exists a deterministic mechanism with (3α + 1)-approximation.

Apart from the above settings, we note that there are some other settings that consider guaranteeing additional properties (e.g., privacy), optimizing different objectives rather than buyer valuation functions (e.g., age of information and costbenefit trade-off objective), investigating mechanisms that perform favorably on realistic instances.

4 Future Research Directions

In previous sections, we provide an overview of key procurement auction settings and existing mechanism design results of budget feasible mechanisms. In this section, we conclude this survey by highlighting several important future research directions for designing budget feasible mechanisms for a wide range of procurement auction settings with budgeted buyers.

Approximate Economic Properties. When designing budget feasible mechanisms, it is often desirable for the mechanisms to satisfy several properties (e.g., truthfulness and individual rationality) as discussed earlier. However, in certain application domains (e.g., crowdsourcing [Hu and Zhang, 2019] and spectrum auction [Zhu and Shin, 2015]), it could be suitable to consider relaxed versions of these properties in order to obtain mechanisms that are more efficient (e.g., obtaining better approximation ratios). For instance, in the settings with XOS and subadditive valuation functions, the best known mechanisms are limited to achieving large approximation ratios. Therefore, a natural direction would be to consider suitable relaxations of various properties and design mechanisms satisfying the relaxed properties. As an example, one can incorporate some notion of ϵ-approximate truthfulness or ϵ-individual rationality that permits slight deviations from these constraints and design mechanisms with better approximation ratios. Furthermore, one can also consider the concept of resource augmentation, which permits the use of additional resources [Phillips et al., 1997], to explore the trade-off between the relaxation of budget constraints and the mechanism's performance. That is, by increasing the budget by a small amount, one can possibly design mechanisms that can lead to a noticeable improvement in the mechanism's efficiency (e.g., approximation ratios).

Non-linear Utility Function. Most of the studies in the budget feasible mechanism design literature assume that the sellers' utilities are quasilinear as in Eq. (1). However, in more general settings, sellers could have non-linear utility functions [Feng et al., 2023], such as the budgeted utility, the risk-averse utility, and the endogenous valuation utility, depending on the sellers' behavior and environments in various economic contexts. For instance, in the case of riskaverse utility, where the utility function ui for seller i is a concave function mapping from the wealth pi(b) - cixi(b) of the seller to their utility. By considering non-linear utility functions in procurement auction settings with budgeted buyers, we can capture other real-world application domains and facilitate decision-making.

Automated Mechanism Design. The standard approach for designing mechanisms is to leverage domain expertise to manually construct mechanisms for specific settings. Differently, [Conitzer and Sandholm, 2002] introduced the automated mechanism design approach to design mechanisms computationally (e.g., using integer or linear programming) for specific settings. In a recent study [D¨utting et al., 2023], machine learning and deep learning techniques were employed to design automated auction mechanisms. These recent directions open the doors to the possibility of designing budget feasible mechanisms through the lens of automated mechanism design. This promising direction could potentially lead to the discovery of better budget feasible mechanisms for specific procurement auction settings with budgeted buyers.

5 Conclusion

In this survey, we present an overview of various procurement auction settings with budgeted buyers and key mechanism design results of budget feasible mechanisms. We provide an in-depth review of the classical procurement settings and their mechanism results. We also provide a review of other settings extending the classical settings and modeling real-world application domains (e.g., in artificial intelligence and machine learning). Finally, we present several promising and exciting future directions for designing budget feasible mechanisms in general settings. This survey aims to serve as a valuable point of reference for researchers, offering insights into existing settings/results and inspiring further explorations on designing budget feasible mechanisms for general procurement settings.

Acknowledgements

Hau Chan is supported by the National Institute of General Medical Sciences of the National Institutes of Health [P20GM130461], the Rural Drug Addiction Research Center at the University of Nebraska-Lincoln, and the National Science Foundation under grant IIS:RI #2302999. Weiwei Wu is supported in part by the National Natural Science Foundation of China under grant 61972086, the Natural Science Foundation of Jiangsu Province under Grant No. BK20230024. The content is solely the responsibility of the authors and does not necessarily represent the official views of the funding agencies.