Revenue Maximization Envy-Free Pricing for Homogeneous Resources / 90
Gianpiero Monaco, Piotr Sankowski, Qiang Zhang
PDF

Pricing-based mechanisms have been widely studied and developed for resource allocation in multi-agent systems. One of the main goals in such studies is to avoid envy between the agents, i.e., guarantee fair allocation. However, even the simplest combinatorial cases of this problem is not well understood. Here, we try to fill these gaps and design polynomial revenue maximizing pricing mechanisms to allocate homogeneous resources among buyers in envy-free manner. In particular, we consider envy-free outcomes in which all buyers' utilities are maximized. We also consider pair envy-free outcomes in which all buyers prefer their allocations to the allocations obtained by other agents. For both notions of envy-freeness, we consider item and bundle pricing schemes. Our results clearly demonstrate the limitations and advantages in terms of revenue between these two different notions of envy-freeness.