2012/06/21 by Bach Q. Ha, Ha, Bach Q., Jason D. Hartline +1
Business, Management and Accounting · Computer Science · Decision Sciences · Engineering · Mathematics · #Auction Theory and Applications #Auction theory #Benford’s Law and Fraud Detection #Common value auction #Computer Science and Game Theory (cs.GT) #Computer science #Consumer Market Behavior and Pricing #Economics #Engineering #English auction #Extractor #FOS: Computer and information sciences #Finance #Generalized second-price auction #Mathematical economics #Microeconomics #Profit (economics) #Revenue #Revenue equivalence #Reverse auction #Vickrey auction #cs.GT
paper · pdf · doi:10.48550/arxiv.1206.4955
4 pages
arxiv created 2012/06/21 · openalex publication_date 2012/06/21 · arxiv updated 2012/06/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We give an auction for downward-closed environments that generalizes the random sampling profit extraction auction for digital goods of Fiat et al. (2002). The mechanism divides the agents in to a market and a sample using a biased coin and attempts to extract the optimal revenue from the sample from the market. The latter step is done with the downward-closed profit extractor of Ha and Hartline (2012). The auction is a 11-approximation to the envyfree benchmark in downward-closed permutation environments. This is an improvement on the previously best known results of 12.5 for matroid and 30.4 for downward-closed permutation environments that are due to Devanur et al. (2012) and Ha and Hartline (2012), respectively.