Introduction
In algorithmic game theory, pricing and allocation problems typically assume unit demand (a buyer wants one item) or relaxed multi-unit demand (a buyer wants up to $k$ items). However, many real-world markets, such as television advertising slots, exhibit "sharp" multi-unit demand. In these scenarios, a buyer requires exactly a specific number of items to derive any utility; receiving fewer results in zero value. This "all-or-nothing" constraint significantly complicates market clearing and revenue maximization.
Problem Formulation
The paper investigates two primary solution concepts for setting prices and allocations under sharp multi-unit demand:
- Competitive Equilibrium (CE): A state where every buyer receives their preferred bundle at current prices, and all unsold items are priced at zero.
- Envy-Free (EF) Pricing: A more flexible concept where no buyer prefers another's bundle, but unsold items can maintain high prices to prevent envy.
While standard economic tools like the "distributive lattice" property of equilibrium prices work for unit demand, they fail under sharp demand. To make the problem tractable, the authors focus on a correlated values model, where the value buyer $i$ has for item $j$ is $v_{ij} = v_i \cdot q_j$, where $v_i$ represents the buyer's valuation and $q_j$ represents the item's quality.
Methodology
The authors propose several algorithms to address the computational challenges of these pricing models:
- Max-CE Algorithm: For revenue-maximizing competitive equilibrium, a two-stage approach is used. Dynamic programming identifies candidate winners, followed by a Linear Program (LP) to determine optimal prices. Due to an exponential number of constraints, the Ellipsoid Method with a custom separation oracle is employed.
- Max-EF Algorithm: While EF pricing is generally NP-hard for arbitrary demands, the authors develop a polynomial-time algorithm for cases where buyer demand is bounded by a constant. This utilizes a specialized dynamic programming technique (Solve-DLP) to navigate the allocation search space.
Key Results
The research establishes a clear boundary between tractable and intractable pricing problems. The correlated values assumption (effectively a rank-1 valuation matrix) is the key driver for polynomial-time solutions in scenarios that are otherwise NP-hard.
As summarized in the table above, the paper proves that for correlated values:
- Competitive Equilibrium: Determining existence and finding the revenue-maximizing CE is possible in polynomial time. This contrasts with general valuations, where even checking for the existence of a CE is NP-complete.
- Envy-Free Pricing: Revenue maximization is solvable in polynomial time if demands are bounded by a constant, but remains NP-hard for arbitrary demands, even with as few as three buyers.
Insights and Future Directions
A notable finding is the "over-priced" phenomenon: in sharp demand markets, an item can be priced higher than its individual value to a buyer ($p_j > v_{ij}$), provided the buyer's total bundle profit remains positive. This behavior is absent in simpler unit-demand models and adds significant complexity to finding optimal prices.
Future research may explore approximation algorithms for the NP-hard general demand cases, more complex valuation structures beyond rank-1 models, and the integration of adjacency constraints (e.g., requiring consecutive time slots), which are common in practical advertising markets.
Summary updated