PaperlayerView exact revision on arXiv

Source-linked AI summary

Budget Feasible Mechanisms

Yaron Singer

arXiv:1002.2334v2cs.GT

TL;DR

The paper studies procurement mechanisms where private seller costs and a payment budget jointly constrain which outcomes can be implemented. It develops budget-feasible truthful mechanisms, showing constant-factor approximation for nondecreasing submodular valuations while general functions can yield unbounded approximation. The paper also gives improved results for subclasses and studies further feasibility limits and characterizations.

  • Problem

    The paper asks which mechanism-design problems remain approximable when truthful payments, rather than only costs, must stay within a fixed budget.

  • Method

    It formulates strategic procurement as a single-parameter mechanism-design problem and develops randomized, universally truthful budget-feasible mechanisms for valuation classes including submodular functions.

  • Results

    A randomized constant-factor budget-feasible mechanism exists for nondecreasing submodular functions, while general functions can have an unbounded approximation ratio.

  • Takeaways & Limitations

    Budget feasibility is tractable for important submodular valuation classes, with improved approximations for subclasses such as additive, OXS, and coverage functions.

Abstract

from arXiv · show

We study a novel class of mechanism design problems in which the outcomes are constrained by the payments. This basic class of mechanism design problems captures many common economic situations, and yet it has not been studied, to our knowledge, in the past. We focus on the case of procurement auctions in which sellers have private costs, and the auctioneer aims to maximize a utility function on subsets of items, under the constraint that the sum of the payments provided by the mechanism does not exceed a given budget. Standard mechanism design ideas such as the VCG mechanism and its variants are not applicable here. We show that, for general functions, the budget constraint can render mechanisms arbitrarily bad in terms of the utility of the buyer. However, our main result shows that for the important class of submodular functions, a bounded approximation ratio is achievable. Better approximation results are obtained for subclasses of the submodular functions. We explore the space of budget feasible mechanisms in other domains and give a characterization under more restricted conditions.

I. INTRODUCTION

The paper identifies budget-feasible mechanism design as a setting where payments constrain feasible outcomes, unlike classical mechanism design. It shows that general valuation functions can make approximation impossible, while nondecreasing submodular functions admit constant-factor mechanisms.

  • The problem: Budget-feasible mechanisms must maximize the auctioneer’s value while ensuring total payments never exceed the budget.The constraint applies to payments supporting truthfulness, rather than directly to sellers’ private costs.
  • The problem: Classical mechanism design assumes a publicly known outcome set independent of payments, whereas these problems’ feasible outcomes depend on private information and mechanism payments.This payment-dependent outcome space places the problems outside a standard mechanism-design framework.
  • The difficulties: VCG can select an optimal within-budget allocation while paying (n −1) times the budget in a simple Knapsack instance.The instance has identical values, many small-cost items, and one item whose cost equals the budget.
  • The difficulties: General valuation functions can force any budget-feasible truthful mechanism into an unbounded approximation ratio.A particular item whose inclusion creates value forces the mechanism to surrender its entire budget to that item.
  • Our Results: A randomized constant-factor budget-feasible mechanism exists for nondecreasing submodular functions and is universally truthful.The paper also studies improved approximations for additive, OXS, coverage, and other special cases, plus impossibilities and characterizations under restrictions.
  • Related Work: The paper distinguishes budget feasibility from frugality, which minimizes payments for a feasible solution rather than maximizing buyer demand under a payment cap.It also contrasts its setting with cost sharing, where private valuations are optimized under a public cost function.

II. THE MODEL

The model is a strategic budget-limited reverse auction with private seller costs and a publicly known buyer budget and valuation function. Mechanisms must be truthful, computationally efficient, individually rational, normalized, nonnegative, and budget feasible, with approximation measured against the full-information optimum.

  • The model: Each item is held by a strategic agent with private cost, while the buyer’s budget and demand function are common knowledge.The mechanism outputs both an allocated subset and a payment vector.
  • The model: A mechanism maps bids to an allocated subset and payments, seeking normalized, individually rational, and nonnegative payments.Normalization requires unallocated agents to receive zero payment, while individual rationality requires allocated agents’ payments to cover their costs.
  • Mechanism requirements: Truthfulness requires truthful cost reporting to be a dominant strategy; a randomization over truthful mechanisms is universally truthful.The model is single-parameter because each bidder has one private value.
  • Mechanism requirements: Computational efficiency requires polynomial-time allocation and payment functions, using value queries when the demand function has exponential representation.A value query evaluates the buyer’s demand function on any subset.
  • Approximation: An α-approximate mechanism satisfies OPT(c, N, B) ≤ αV(S), and randomized mechanisms are evaluated by expected constant-factor approximation.The benchmark is the full-information optimal solution under the budget.

III. SYMMETRIC SUBMODULAR FUNCTIONS

The symmetric submodular case simplifies budget-feasible mechanism design. Sorting bids and selecting the largest budget-feasible prefix yields a truthful mechanism with approximation ratio two.

  • Symmetric submodular functions: Symmetric submodular functions depend only on set cardinality and have nonincreasing marginal values.They are represented by values r1 ≥ ... ≥ rn ≥ 0.
  • Allocation rule: The mechanism sorts bids increasingly and selects the largest prefix whose kth bid satisfies ck ≤ B/k.It pays each selected agent θi = min{B/k, ck+1}.
  • Guarantees: The resulting truthful mechanism satisfies the payment budget and approximates the full-information optimum.The budget-feasibility claim concerns the payments supporting truthfulness.
  • Guarantees: 2: The mechanism has approximation ratio two.The proof shows it returns at least half as many items as the greedy optimum.
  • Generalization: For general nondecreasing submodular functions, marginal contributions decrease as the preceding allocated set grows.The mechanism uses marginal contribution normalized by cost for sorting.
  • Generalization: The general case assumes access to a value oracle because submodular functions may require exponential representation.The oracle returns V(S) for queried subsets.

A. The Proportional Share Allocation Rule

The proportional share rule extends the symmetric mechanism using marginal contribution per cost. It works for several submodular subclasses, but Coverage exposes payment and monotonicity difficulties that require further modifications.

  • Allocation rule: The generalized proportional share rule sorts agents by marginal contribution per cost and allocates a prefix satisfying ci ≤ B·Vi/V(Si).The condition holds for every allocated prefix agent.
  • Additive valuations: For additive valuations, each agent’s marginal contribution is fixed at vi, so the rule produces a budget-feasible mechanism.The threshold payments do not exceed proportional shares.
  • Payment properties: The threshold payments are bounded by proportional contributions, supporting budget feasibility and individual rationality.This is the payment property used for additive and related submodular cases.
  • Coverage difficulties: In Coverage, an agent’s marginal contribution depends on the previously allocated subset and therefore on its sorting position.This creates difficulties absent from additive valuations.
  • Coverage difficulties: Coverage payments can depend on an agent’s declared cost, so the proportional share mechanism cannot induce truthfulness.The issue arises because the marginal contribution changes with sorting position.
  • Coverage difficulties: Simple position-independent schemes, including Shapley-value replacements, also fail to provide strong general guarantees.The paper states that the only known route to good general-submodular guarantees retains marginal-contribution sorting.
  • Coverage difficulties: The maximum of a greedy solution and the highest-value item need not preserve monotonicity under marginal-contribution sorting.This blocks a standard approximation step in the general and Coverage cases.

C. Overview of Our Approach

The approach characterizes threshold payments for a modified proportional share rule, establishes budget feasibility using proportional-payment bounds, and partitions agents to obtain approximation guarantees.

  • Overview of Our Approach: The approach begins by deriving an alternative characterization of proportional-share threshold payments.Although the original rule fails in some cases, this characterization is used in the new design.
  • Overview of Our Approach: For nondecreasing submodular functions, modified proportional-share threshold payments remain close to agents’ proportional contributions.Running the modified rule with a constant fraction of the budget makes the payments budget feasible.
  • Overview of Our Approach: The mechanism partitions agents to account for variation in the proportional-share rule over subsets.This partitioning is used to obtain approximation guarantees.
  • Payment characterization: An agent’s marginal contribution at point j is Vi(j) = V(Tj−1 ∪ {i}) − V(Tj−1).Tj is formed by marginal-contribution-per-cost sorting over agents excluding i.
  • Payment characterization: The threshold payment is characterized as the maximum over stages of min{ci(j), ρi(j)}.At each stage, these terms bound the cost i can declare while still being allocated.
  • Payment characterization: The maximizing stage determines the largest declared cost that still places agent i early enough and satisfies the allocation condition.Declaring a higher cost prevents allocation in the cases analyzed.
  • Guarantees: The threshold-payment construction yields individual rationality: ci ≤ θi.The proof compares the truthful cost with a suitable stage-specific threshold.

E. Payment Bounds

The modified proportional share rule uses threshold payments tied to proportional contribution and establishes a constant-factor payment bound. The proof handles the relevant threshold cases using marginal contribution-per-cost ordering and submodularity.

  • Threshold payments are guaranteed to be within a constant factor of agents’ proportional contribution, guiding the mechanism’s design.
  • The modified rule runs over an agent subset using a constant fraction of the budget and extends the payment characterization to include a distinguished agent.
  • The threshold payment bound is θi ≤ Vi · B′/V(W′) in both analyzed cases.
  • The proof derives the bound by considering marginal contribution-per-cost ordering and separate cases for the threshold index.
  • Submodularity supplies an e/(e −1)-approximation for an intermediate solution, while the proof concludes after bounding V(W) relative to V(W′).

F. Approximation Guarantee

The mechanism partitions agents by value and declared cost, discarding sufficiently costly agents while retaining a constant-factor approximation over the remaining set. Feasibility follows from the cost threshold and inclusion of the highest-value agent.

  • The partition selects the highest-value agent, assigns agents with cost at most B/2 to Ns, and places the remaining agents in Nℓ.
  • Because agents in Nℓ have large costs and lower individual value than i∗, feasible solutions include at most one such agent, limiting the loss from discarding them.
  • The modified proportional share allocation rule is feasible when run over Ns with i∗ included and a constant fraction of the budget.
  • The allocation rule achieves a constant-factor approximation over Ns, expressed as V(W) ≥ OPT(c, B, Ns).
  • The proof combines marginal-contribution ordering, submodularity, and the contribution of i∗ to derive the desired approximation bound.

G. Main Result

The main theorem establishes a randomized, universally truthful, budget-feasible constant-factor approximation for submodular maximization, alongside a near-2 lower bound. The stated mechanism ratio is approximately 117.7 in expectation, though tighter analysis may be possible.

  • For any submodular maximization problem, a randomized constant-factor approximation mechanism exists in the value query model that is budget feasible and universally truthful.
  • No budget-feasible mechanism can achieve an approximation better than 2 −ǫ for any fixed ǫ > 0.
  • The mechanism’s expected approximation ratio is approximately 117.7.
  • The analysis may not be tight, since the paper notes that a tighter analysis could show the mechanism performs better.

A Budget Feasible Approximation Mechanism

The mechanism caps payments for non-distinguished agents, uses a reduced internal budget, and combines threshold payments with the highest-value agent’s payment. The construction is truthful and budget feasible, with its approximation ratio derived from the agent partition.

  • For non-distinguished agents, payments are capped at B/2, while the modified proportional share rule uses B′ = B/α with α = (12e−4)/(e−1).
  • The partition is monotone, and the B/2 payment cap prevents agents in Nℓ from benefiting by misreporting their costs.
  • Using B′ = B/α and the payment bound from Lemma 4.6, the mechanism’s payments satisfy the budget constraint.
  • The resulting mechanism is truthful and budget feasible, with individual rationality and monotonicity established separately.
  • The approximation ratio follows by combining Lemma 4.7 with the partition-based comparison between the full optimum and the restricted agent set.

V. THE SPACE OF BUDGET FEASIBLE MECHANISMS

The paper establishes approximation limits and special-case guarantees for deterministic budget feasible mechanisms. Submodular subclasses admit improved mechanisms, but even simple demand valuations impose a factor-two lower bound.

  • 5-approximation mechanisms exist for Knapsack, while Matching admits a budget feasible (5e−1)/(e−1)-approximation mechanism.
  • No budget feasible mechanism can approximate either Knapsack or Matching within a factor better than 2−ǫ for any fixed ǫ > 0.
  • For the demand valuation V(S) = |S|, no budget feasible mechanism can guarantee an approximation of 2−ǫ for any ǫ > 0.
  • The lower-bound construction uses equal costs B/2 + ǫ, forcing any allocated agent’s threshold payment to be at least B/2 + ǫ.Monotonicity and individual rationality then prevent allocating to a second agent, although the full-information optimum allocates to two agents.

B. Lower Bound on Fractionally Subadditive Functions

The paper shows that fractionally subadditive demands are computationally hard to approximate through value queries, even when costs are public. It also proves an unconditional impossibility for nontrivial hiring-team problems.

  • Fractionally subadditive functions: Fractionally subadditive functions are maxima of finite sets of additive valuations and include all submodular functions.They are also subadditive, but the paper shows that value-query access still creates a strong approximation barrier.
  • Fractionally subadditive functions: Approximating fractionally subadditive demands within 2−ǫ requires exponentially many value queries for any fixed ǫ > 0, even with public costs.
  • Fractionally subadditive functions: The hard instance distinguishes valuations that agree on queried behavior but differ on a set T, so better approximation requires distinguishing them.The proof uses exponentially many value queries to separate the two valuations.
  • Hiring a team of agents: A hiring-team problem is nontrivial when every feasible solution contains more than one agent.These problems use V(S) = 1 for feasible outcomes and 0 otherwise.
  • Hiring a team of agents: No budget feasible mechanism has a bounded approximation ratio for any nontrivial hiring-team problem.The proof raises each selected agent’s threshold payment until their combined payments exceed the budget.

D. Characterizing Budget Feasible Mechanisms in Restricted Settings

The paper characterizes budget feasible mechanisms under anonymity and weak stability. In this restricted setting, every selected agent’s bid must not exceed an equal share of the budget, while broader characterization remains open.

  • Restricted conditions: Anonymity requires symmetric treatment of agents under corresponding bid changes, while weak stability constrains allocations when selected agents’ bids change.
  • Restricted conditions: For symmetric submodular functions, the proportional share mechanism satisfies anonymity and weak stability.The paper asks whether all good budget feasible mechanisms in this setting must have this form.
  • Characterization: Every selected agent must bid at most B/|S| when an anonymous, weakly stable budget feasible mechanism selects S.
  • Characterization: The bound follows because anonymity makes selected agents’ threshold prices equal, so any selected bid above B/|S| would force total payments over budget.
  • Open directions: A more general characterization of budget feasible mechanisms and stronger lower bounds remain open directions.
Loading 1002.2334v2…