Improved two sample revenue guarantees via mixed-integer linear programming

DOI10.1007/978-3-030-85947-3_1MaRDI QIDQ2670901zbMATH OpenOpenAlexFDO

Authors Mete Şeref Ahunbay, Adrian Vetta

Publication date 1 June 2022

Full work available at URL https://arxiv.org/abs/2103.00235

Mathematics Subject Classification ID

Mixed integer programming (90C11) Auctions, bargaining, bidding and selling, and other market models (91B26)

Abstract: We study the performance of the Empirical Revenue Maximizing (ERM) mechanism in a single-item, single-seller, single-buyer setting. We assume the buyer's valuation is drawn from a regular distribution $F$ and that the seller has access to {em two} independently drawn samples from $F$. By solving a family of mixed-integer linear programs (MILPs), the ERM mechanism is proven to guarantee at least $.5914$ times the optimal revenue in expectation. Using solutions to these MILPs, we also show that the worst-case efficiency of the ERM mechanism is at most $.61035$ times the optimal revenue. These guarantees improve upon the best known lower and upper bounds of $.558$ and $.642$, respectively, of [Daskalakis & Zampetakis, '20].

Recommendations

• The sample complexity of revenue maximization
• Sampling and Representation Complexity of Revenue Maximization
• Settling the sample complexity of single-parameter revenue maximization
• The Sample Complexity of Up-to-ε Multi-dimensional Revenue Maximization
• Robust revenue maximization under minimal statistical information
• On the asymptotic optimality of the randomized linear program for network revenue management
• Sample average approximation in a two-stage stochastic linear program with quantile criterion
• Approximating the revenue maximization problem with sharp demands
• Approximating the revenue maximization problem with sharp demands
• A two-dimensional problem of revenue maximization

Cites work

• Efficient empirical revenue maximization in single-parameter auction environments
• Making the Most of Your Samples
• Optimal Auction Design
• Revenue maximization with a single sample
• Settling the sample complexity of single-parameter revenue maximization
• The sample complexity of auctions with side information
• The sample complexity of revenue maximization

Cited in

(2)

• A closer look at two conjectures about irregular marginal revenue
• Sampling and Representation Complexity of Revenue Maximization

This page was built for publication: Improved two sample revenue guarantees via mixed-integer linear programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2670901)