An official website of the United States government
We revisit the well-studied problem of budget-feasible procurement, where a buyer with a strict budget constraint seeks to acquire services from a group of strategic providers (the sellers). During the last decade, several strategyproof budget-feasible procurement auctions have been proposed, aiming to maximize the value of the buyer, while eliciting each seller’s true cost for providing their service. These solutions predominantly take the form of randomized sealed-bid auctions: they ask the sellers to report their private costs and then use randomization to determine which subset of services will be procured and how much each of the chosen providers will be paid, ensuring that the total payment does not exceed the buyer’s budget. Our main result in this paper is a novel method for designing budget-feasible auctions, leading to solutions that outperform the previously proposed auctions in multiple ways. First, our solutions take the form of descending clock auctions, and thus satisfy a list of very appealing properties, such as obvious strategyproofness, group strategyproofness, transparency, and unconditional winner privacy; this makes these auctions much more likely to be used in practice. Second, in contrast to previous results that heavily depend on randomization, our auctions are deterministic. As a result, we provide an affirmative answer to one of the main open questions in this literature, asking whether a deterministic strategyproof auction can achieve a constant approximation when the buyer’s valuation function is submodular over the set of services. In addition to this, we also provide the first deterministic budget-feasible auction that matches the approximation bound of the best-known randomized auction for the class of subadditive valuations. Finally, using our method, we improve the best-known approximation factor for monotone submodular valuations, which has been the focus of most of the prior work
more »
« less
Budget Feasible Mechanisms: A Survey
In recent decades, the design of budget feasible mechanisms for a wide range of procurement auction settings has received significant attention in the Artificial Intelligence (AI) community. These procurement auction settings have practical applications in various domains such as federated learning, crowdsensing, edge computing, and resource allocation. In a basic procurement auction setting of these domains, a buyer with a limited budget is tasked with procuring items (\eg, goods or services) from strategic sellers, who have private information on the true costs of their items and incentives to misrepresent their items' true costs. The primary goal of budget feasible mechanisms is to elicit the true costs from sellers and determine items to procure from sellers to maximize the buyer valuation function for the items and ensure that the total payment to the sellers is no more than the budget. In this survey, we provide a comprehensive overview of key procurement auction settings and results of budget feasible mechanisms. We provide several promising future research directions.
more »
« less
- PAR ID:
- 10632705
- Publisher / Repository:
- International Joint Conferences on Artificial Intelligence Organization
- Date Published:
- ISBN:
- 978-1-956792-04-1
- Page Range / eLocation ID:
- 8132 to 8141
- Format(s):
- Medium: X
- Location:
- Jeju, South Korea
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We consider a general non-stochastic online pricing bandit setting in a procurement scenario where a buyer with a budget wants to procure items from a fixed set of sellers to maximize the buyer's reward by dynamically offering purchasing prices to the sellers, where the sellers' costs and values at each time period can change arbitrarily and the sellers determine whether to accept the offered prices to sell the items. This setting models online pricing scenarios of procuring resources or services in multi-agent systems. We first consider the offline setting when sellers' costs and values are known in advance and investigate the best fixed-price policy in hindsight. We show that it has a tight approximation guarantee with respect to the offline optimal solutions. In the general online setting, we propose an online pricing policy, Granularity-based Pricing (GAP), which exploits underlying side-information from the feedback graph when the budget is given as the input. We show that GAP achieves an upper bound of O(n{v_{max}}{c_{min}}sqrt{B/c_{min}}ln B) on the alpha-regret where n, v_{max}, c_{min}, and B are the number, the maximum value, the minimum cost of sellers, and the budget, respectively. We then extend it to the unknown budget case by developing a variant of GAP, namely Doubling-GAP, and show its alpha-regret is at most O(n{v_{max}}{c_{min}}sqrt{B/c_{min}}ln2 B). We also provide an alpha-regret lower bound Omega(v_{max}sqrt{Bn/c_{min}}) of any online policy that is tight up to sub-linear terms. We conduct simulation experiments to show that the proposed policy outperforms the baseline algorithms.more » « less
-
Deligkas, Argyrios; Filos-Ratsikas, Aris (Ed.)We study a dynamic model of procurement auctions in which the agents (sellers) will abandon the auction if their utility does not satisfy their private target, in any given round. We call this “abandonment” and analyze its consequences on the overall cost to the mechanism designer (buyer), as it reduces competition in future rounds of the auction and drives up the price. We show that in order to maintain competition and minimize the overall cost, the mechanism designer has to adopt an inefficient (per-round) allocation, namely to assign the demand to multiple agents in a single round. We focus on threshold mechanisms as a simple way to achieve ex-post incentive compatibility, akin to reserves in revenue-maximizing forward auctions. We then consider the optimization problem of finding the optimal thresholds. We show that even though our objective function does not have the optimal substructure property in general, if the underlying distributions satisfy some regularity properties, the global optimal solution lies within a region where the optimal thresholds are monotone and can be calculated with a greedy approach, or even more simply in a parallel fashion.more » « less
-
Abstract Biological market theory can be used to explain intraspecific cooperation, interspecific mutualism, and sexual selection through models of game theory. These models describe the interactions between organisms as two classes of traders (buyers/sellers) exchanging commodities in the form of goods (e.g. food, shelter, matings) and services (e.g. warning calls, protection). Here, we expand biological market theory to include auction theory where bidding serves to match buyers and sellers.In a reverse auction, the seller increases the value of the item or decreases the cost until a buyer steps forward. We provide several examples of ecological systems that may have reverse auctions as underlying mechanisms to form mutualistic relationships.We focus on the yellow baboon (Papio cynocephalus) mating system as a case study to propose how the mechanisms of a reverse auction, which have the unintended but emergent consequence of producing a mutually beneficial outcome that improves collective reproductive benefits of the troop in this multi‐female multi‐male polygynandrous social system. For the yellow baboon, we posit that the “seller” is the reproductively cycling female, and the “buyer” is a male looking to mate with a cycling female. To the male, the “item for the sale” is the opportunity to sire an offspring, the price is providing safety and foraging time (via consortship) to the female. The “increasing value of the item for sale” is the chance of conception, which increases with each cycle since a female has resumed cycling post‐partum. The female's sexual swelling is an honest indicator of that cycle's probability of conception, and since resident males can track a female's cycle since resumption, there is transparency. The males presumably know the chance of conception when choosing to bid by offering consortship.Across nature, this reverse auction game likely exists in other inter‐ and intraspecific social relationships. Considering an ecological system as a reverse auction broadens our view of social evolution and adaptations through the lens of human economic structures.more » « less
-
We study gains from trade in multi-dimensional two-sided markets. Specifically, we focus on a setting with n heterogeneous items, where each item is owned by a different seller i, and there is a constrained-additive buyer with feasibility constraint ℱ. Multi-dimensional settings in one-sided markets, e.g. where a seller owns multiple heterogeneous items but also is the mechanism designer, are well-understood. In addition, single-dimensional settings in two-sided markets, e.g. where a buyer and seller each seek or own a single item, are also well-understood. Multi-dimensional two-sided markets, however, encapsulate the major challenges of both lines of work: optimizing the sale of heterogeneous items, ensuring incentive-compatibility among both sides of the market, and enforcing budget balance. We present, to the best of our knowledge, the first worst-case approximation guarantee for gains from trade in a multi-dimensional two-sided market. Our first result provides an O(log(1/r))-approximation to the first-best gains from trade for a broad class of downward-closed feasibility constraints (such as matroid, matching, knapsack, or the intersection of these). Here r is the minimum probability over all items that a buyer's value for the item exceeds the seller's cost. Our second result removes the dependence on r and provides an unconditional O(log n)-approximation to the second-best gains from trade. We extend both results for a general constrained-additive buyer, losing another O(log n)-factor en-route. The first result is achieved using a fixed posted price mechanism, and the analysis involves a novel application of the prophet inequality or a new concentration inequality. Our second result follows from a stitching lemma that allows us to upper bound the second-best gains from trade by the first-best gains from trade from the “likely to trade” items (items with trade probability at least 1/n) and the optimal profit from selling the “unlikely to trade” items. We can obtain an O(log n)-approximation to the first term by invoking our O(log(1/r))-approximation on the “likely to trade” items. We introduce a generalization of the fixed posted price mechanism—seller adjusted posted price—to obtain an O(log n)-approximation to the optimal profit for the “unlikely to trade” items. Unlike fixed posted price mechanisms, not all seller adjusted posted price mechanisms are incentive compatible and budget balanced. We develop a new argument based on “allocation coupling” to show the seller adjusted posted price mechanism used in our approximation is indeed budget balanced and incentive-compatible.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.24963/ijcai.2024/899
