2014/07/31 by Pinyan Lu, Tao Xiao, Lu, Pinyan +1
Decision Sciences · Economics, Econometrics and Finance · Social Sciences · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Experimental Behavioral Economics Studies #FOS: Computer and information sciences #Law, Economics, and Judicial Systems
paper · pdf · doi:10.48550/arxiv.1407.8325
openalex publication_date 2014/07/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the efficiency guarantees in the simple auction environment where the auctioneer has one unit of divisible good to be distributed among a number of budget constrained agents. With budget constraints, the social welfare cannot be approximated by a better factor than the number of agents by any truthful mechanism. Thus, we follow a recent work by Dobzinski and Leme (ICALP 2014) to approximate the liquid welfare, which is the welfare of the agents each capped by her/his own budget. We design a new truthful auction with an approximation ratio of (√(5)+1)/(2) ≈ 1.618, improving the best previous ratio of 2 when the budgets for agents are public knowledge and their valuation is linear (additive). In private budget setting, we propose the first constant approximation auction with approximation ratio of 34. Moreover, this auction works for any valuation function. Previously, only O(log n) approximation was known for linear and decreasing marginal (concave) valuations, and O(log2 n) approximation was known for sub-additive valuations.