The Price of a Budget in Tiered Procurement

A platform buys one contract per period from providers that each offer several service tiers. A tier's quality and its cost multiplier are public, the provider's base cost is private, and the platform pays at most a budget $B$. Without the budget the answer is classical: the welfare-optimal allocation is truthful under threshold payments. With it, the truthful payment for a high tier carries the option value of the tiers below the one awarded, so it can exceed $B$ even when the awarded tier's own threshold does not, and fixing the tier before seeing the report gives up the choice of tier that welfare optimality needs. Clipping the payment at the budget keeps that choice, and what the budget then costs is the quality it cannot certify. Three results follow. First, with two tiers the best worst-case ratio ${\rho }^{\star }(q,\lambda ,B)$ of any deterministic truthful budget-feasible mechanism is exact, a budget-clipped VCG menu attains it, and the ratio is $1$ exactly when the budget stops binding on the two tiers, falling to zero as it approaches that threshold from below. Second, when each tier's cost is a separate private number, no truthful budget-feasible mechanism has a positive worst-case ratio as soon as $B$ separates two tier qualities, while the same clipped menu still guarantees welfare at least the offline optimum minus the part of the best tier's quality the budget cannot cover; the public multiplier is what turns an additive guarantee into a multiplicative one. Third, when qualities must be learned, running the clipped menu on lower confidence bounds keeps every incentive property at every round and across rounds, never buys below true value, and has regret $\tilde{O}(\sqrt{T})$ against the offline clipped menu. Exact enumeration on 2955 discrete instances, 300 continuous instances and 600 online runs confirms the bounds, shows that the tie-broken threshold rule that looks optimal on a coarse grid drops to a median worst-case ratio of $0.12$ on continuous instances, and that the learning layer's regret stays sublinear where the rule it replaces is linear. A budget costs a platform exactly the quality it cannot certify.