Abstract
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.
Introduction
In multi-agent systems, fairness is often as critical as efficiency. If two users with similar profiles receive vastly different deals, the "envied" user may lose trust in the system. This paper, originally presented at IJCAI 2015, explores the intersection of algorithmic game theory and resource allocation by addressing a fundamental question: How can a seller price identical (homogeneous) resources—such as CPU cycles or cargo space—to maximize revenue while ensuring no buyer envies another?
The authors provide a comprehensive complexity map for revenue-maximizing "envy-free" pricing of homogeneous resources. They demonstrate that while some versions of this problem are solvable in polynomial time, others are NP-hard, requiring the development of sophisticated approximation algorithms with logarithmic guarantees.
Pricing Models and Fairness Constraints
The study focuses on homogeneous resources where a buyer’s value depends solely on the quantity received. Two distinct notions of fairness are investigated:
- Envy-Free (EF): A buyer receives the bundle that maximizes their utility (value minus price) among all possible bundle sizes at the given prices.
- Pair Envy-Free (PEF): A buyer prefers their assigned bundle over the bundle assigned to any other specific buyer.
These constraints are analyzed across two pricing schemes: Item Pricing (a flat rate per unit) and Bundle Pricing (different prices for different quantities, such as bulk discounts).
Methodology
The authors employ a mix of combinatorial optimization and complexity theory to establish their results:
- Dynamic Programming (DP): For general valuations under item pricing, a DP approach finds the optimal price by discretizing the space of "candidate" optimal prices.
- Approximation Schemes (FPTAS): For "single-minded" buyers (who desire exactly $k$ items or nothing), the problem is proven NP-hard, but a Fully Polynomial Time Approximation Scheme is provided.
- The Key Lemma: A central technical contribution is a lemma that transforms a "nearly-feasible" outcome (violating supply constraints) into a feasible, pair envy-free outcome while retaining at least half the revenue. This serves as the foundation for several $O(\log n)$ approximation algorithms.
- Reductions: NP-hardness and inapproximability results are established through reductions from the "Subset Sum" problem and "UDP-MIN" (a known hard pricing problem).
Results
The paper clarifies the hierarchy of fairness concepts, showing that Walrasian Equilibrium $\subset$ Envy-Free $\subset$ Pair Envy-Free. PEF is the most relaxed constraint, allowing for higher potential revenue. A significant finding is that for bundle pricing, EF and PEF are equivalent (Theorem 4).
The core contributions are summarized in the following taxonomy of complexity:
Key insights include:
- Revenue Gap: The gap in potential revenue between EF and PEF item pricing can be unbounded, highlighting the cost of requiring absolute utility maximization.
- Complexity vs. Flexibility: While bundle pricing extracts more revenue, it is significantly harder to compute and approximate than item pricing.
Conclusion
While this work fills significant gaps in the understanding of envy-free pricing for homogeneous resources, several open questions remain. The authors identify gaps in the complexity table, such as tight lower bounds for PEF item pricing with general valuations. Furthermore, the assumption of item homogeneity limits direct application to heterogeneous markets (e.g., ad slots). Future work may also explore the middle ground where market clearance is not strictly required, reflecting the realities of modern digital markets.
Summary updated