On Approximate Welfare- and Revenue-Maximizing Equilibria for Size-Interchangeable Bidders

This paper introduces a novel relaxation of Walrasian equilibrium (WE) which we call Restricted Envy-Free Pricing (REFP), an algorithm to compute this outcome for the case of size-interchangeable bidders (a generalization of singleminded bidders introduced in this paper), and a heuristic for searching among these outcomes for one that maximizes revenue. We provide theoretical bounds for our algorithms where possible, and run extensive experiments to evaluate their performance on both a synthetic distribution, and one obtained from real-world web-usage data. Compared to other benchmarks in the literature, our algorithms perform well on the metrics of revenue and efficiency, without incurring too many violations of the true WE conditions.