An O ⁡ ( log ⁡ log ⁡ n ) O(\log\log n) -approximate budget feasible mechanism for subadditive valuations

Rian Neogi, Kanstantsin Pashkovich, Chaitanya Swamy · 2025

Read An O ⁡ ( log ⁡ log ⁡ n ) O(\log\log n) -approximate budget feasible mechanism for subadditive valuations by Rian Neogi, Kanstantsin Pashkovich, Chaitanya Swamy (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-04665.txt.

Introduction

Neogi, Pashkovich, and Swamy designed a better buying rule in twenty twenty-five for a buyer with a fixed purse. Each good is held by a seller who hides her true cost. The buyer wants the most worth for the purse, and the rule must coax true costs out.

Past rules for broad worth types could only promise a weak share of the best buy. Their new rule uses chance and a type of demand check to do far better. Its promised share grows much more slow as the count of goods grows. The rule still runs in a fair amount of time.

Catalog record

CREATORRian Neogi, Kanstantsin Pashkovich, Chaitanya Swamy
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE71 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-04665

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An O ⁡ ( log ⁡ log ⁡ n ) O(\log\log n) -approximate budget feasible mechanism for subadditive valuations Thanks: An extended abstract is to appear in the Proceedings of the 26th ACM Conference on Economics and Computation (EC) 2025. Rian Neogi, Kanstantsin Pashkovich, Chaitanya Swamy Abstract In budget-feasible mechanism design , there is a set of items U U , each owned by a distinct seller. The seller of item e e incurs a private cost c ¯ e \overline{c}_{e} for supplying her item. A buyer wishes to procure a set of items from the sellers of maximum value, where the value of a set S ⊆ U S\subseteq U of items is given by a valuation function v : 2 U → ℝ + v:2^{U}\to\mathbb{R}_{+} . The buyer has a budget of B ∈ ℝ + B\in\mathbb{R}_{+} for the total payments made to the sellers. We wish to design a mechanism that is truthful , that is, sellers are incentivized to report their true costs, budget-feasible , that is, the sum of the payments made to the sellers is at most the budget B B , and that outputs a set whose value is large compared to OPT := max { v ( S ) : c ¯ ( S ) ≤ B , S ⊆ U } \text{OPT}:=\max\{v(S):\overline{c}(S)\leq B,S\subseteq U\} . Budget-feasible mechanism design has been extensively studied, with the literature focusing on (classes of) subadditive (or complement-free) valuation functions, and various polytime, budget-feasible mechanisms, achieving constant-factor approximation to OPT , have been devised for the special cases of additive, submodular, and XOS (or fractionally subadditive) valuations. However, for general subadditive valuations, the best-known approximation factor achievable by a polytime budget-feasible mechanism (given access to demand oracles) was only O ⁡ ( log ⁡ n / log ⁡ log ​ n ) O(\log n/\log\log n) , where n = | U | n=|U| is the number of items. We improve this state-of-the-art significantly by designing a randomized budget-feasible mechanism for subadditive valuations that achieves a substantially-improved approximation factor of O ⁡ ( log ⁡ log ⁡ n ) O(\log\log n) and runs in polynomial time, given access to demand oracles. Our chief technical contribution is to show that, given any set S ⊆ U S\subseteq U , one can construct in polynomial time a distribution 𝒟 \mathcal{D} over posted-payment vectors d ∈ ℝ + S d\in\mathbb{R}_{+}^{S} satisfying d ⁡ ( S ) ≤ B d(S)\leq B (where d ⁡ ( S ) = ∑ e ∈ S d e d(S)=\sum_{e\in S}d_{e} ) such that, 𝔼 d ∼ 𝒟 ​ [ v ⁡ ( { e ∈ S : c e ≤ d e } ) ] ≥ 1 O ⁡ ( log ⁡ log ⁡ n ) ⋅ v ⁡ ( S ) \mathbb{E}_{d\sim\mathcal{D}}[v(\{e\in S:c_{e}\leq d_{e}\})]\geq\frac{1}{O(\log\log n)}\cdot v(S) for every cost-vector c ∈ ℝ + S c\in\mathbb{R}^{S}_{+} satisfying c ⁡ ( S ) ≤ B / O ⁡ ( log ⁡ log ⁡ n ) c(S)\leq B/O(\log\log n) . Using this distribution, we show how to construct a budget feasible mechanism for subadditive valuations that achieves an approximation factor of O ⁡ ( log ⁡ log ⁡ n ) O(\log\log n) . 1 Introduction In budget-feasible mechanism design , there is a ground set U of n elements or items, and a valuation function v:2^{U}\to\mathbb{R}_{+} , where v(S) specifies the value of a subset S\subseteq U . We are also given a budget B\in\mathbb{R}_{+} . The mechanism designer (or buyer) seeks to procure a set of elements of maximum value. Each element e is held by a strategic seller who incurs a private cost \overline{c}_{e}\geq 0 for supplying item e ; we will often identify sellers with the items they hold. The central difficulty here is that the private costs \{\overline{c}_{e}\} are known only to the sellers, and not to the mechanism designer. Each seller e reports a cost c_{e} to the mechanism, which may not be equal to her true cost. In order to incentivize sellers to reveal their true costs, the mechanism designer makes payments to the sellers. The utility of a seller is equal to the payment it receives minus the cost incurred by potentially supplying the item. Our goal is to design a truthful mechanism, where each seller maximizes their utility by reporting her true cost. Additionally, the mechanism designer also has a budget B and we need to ensure that the sum of the payments given out to the sellers do not exceed this budget. We want to design a mechanism that outputs a set that is a good approximation to the best set one can get subject to the budget constraint. That is to say, we compare the value of our solution to the benchmark \operatorname{OPT}:=\max\{v(S):c(S)\leq B\} . Note that for a truthful mechanism, it does not matter whether we consider the true costs or the reported costs for the budget constraint. For general valuation functions as input, the work of [ Sin10 ] shows that no non-trivial approximation is possible for any budget feasible mechanism. Hence work has been focussed on special classes of valuation functions, such as, typically (in increasing order of generality) additive, submodular, XOS, or subadditive valuations. For subadditive valuations, [ BCGL17 ] made an important contribution showing that the problem admits a randomized O(\log n/\log\log n) -approximate budget feasible mechanism. (Recall that n=|U| ). They also provide an O(1) -factor approximate mechanism in the Bayesian setting, where costs are sampled from a prior distribution that is known to the mechanism designer. They use Yao’s minimax principle to show that their O(1) -approximate Bayesian mechanism implies the existence of an O(1) -factor approximate mechanism in the prior-free setting. This work was later improved in two ways: [ BGG+22 ] achieved a deterministic O(\log n/\log\log n) approximation, and [ NPS24 ] provide a constructive O(1) -factor approximate mechanism in the prior-free setting, that runs in exponential time. 1.1 Our contributions We design a budget-feasible mechanism for subadditive valuations that achieves an O(\log\log n) -approximation, and runs in polynomial time given access to demand oracles . This is a substantial improvement over the previous-best approximation factor of O(\log n/\log\log n) achievable in polytime (also given demand oracle) [ BCGL17 , BGG+22 ] . Theorem 1.1 . There is a truthful budget feasible mechanism for subadditive valuations that achieves an approximation factor of O(\log\log n) , and runs in polynomial time given a demand oracle for the valuation v . Our mechanism is randomized: it satisfies truthfulness and the budget constraint with probability 1, and obtains expected value at least \operatorname{OPT}/O(\log\log n) . To state our key technical contribution, it will be useful to discuss some snippets from prior work on budget-feasible mechanism design for subadditive valuations. An important insight to emerge from the work of [ BCGL17 , NPS24 ] is the following structural property of subadditive functions, stated explicitly in [ NPS24 ] . (This is quite implicit in [ BCGL17 ] hiding behind their use of Yao’s principle.) Theorem 1.2 ( [ NPS24 ] ) . Let v:2^{U}\to\mathbb{R}_{+} be a subadditive function and S^{*}\subseteq U . Let K\subseteq\mathbb{R}^{S^{*}}_{+} be a finite set. There exists a distribution \mathcal{D}^{*}

Read the complete text