Abstract: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...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, Tuncel, 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.Read More
Publication Year: 2013
Publication Date: 2013-09-30
Language: en
Type: preprint
Access and Citation
Cited By Count: 1
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot