Affordable Access

The Unit-Demand Envy-Free Pricing Problem

  • Fernandes, Cristina G.
  • Ferreira, Carlos E.
  • Franco, Álvaro J. P.
  • Schouery, Rafael C. S.
Publication Date
Sep 30, 2013
Submission Date
Sep 30, 2013
arXiv ID: 1310.0038
External links


We consider the unit-demand envy-free pricing problem, which is a unit-demand auction where each bidder receives an item that maximizes his utility, and the goal is to maximize the auctioneer's profit. This problem is NP-hard and unlikely to be in APX. We present four new MIP formulations for it and experimentally compare them to a previous one due to Shioda, Tun\c{c}el, and Myklebust. We describe three models to generate different random instances for general unit-demand auctions, that we designed for the computational experiments. Each model has a nice economic interpretation. Aiming approximation results, we consider the variant of the problem where the item prices are restricted to be chosen from a geometric series, and prove that an optimal solution for this variant has value that is a fraction (depending on the series used) of the optimal value of the original problem. So this variant is also unlikely to be in APX.

Report this publication


Seen <100 times