Envy-free pricing

Envy-free pricing is an approach for fair allocation of discrete objects among people with different preferences. It is a special case of the problem of fair item allocation, with the following distinguishing properties:

• Monetary payments are allowed. In particular, it is allowed to assign a price to each object, and charge each person the total price of objects allocated to him.
• The people are assumed to be quasilinear in money. This means that the utility an agent gains from a bundle of objects equals the agent's value for the bundle minus the total price of items in the bundle.
• The allocation should be envy-free: for each agent, his utility from his own bundle is at least as large as the utility he could gain from any other possible bundle (in particular, from the bundles given to the other agents).
• It is allowed to leave some items unallocated. However, it is required to maximize the social welfare and/or the seller's revenue (subject to envy-freeness).

The term was invented by Guruswami, Hartline, Karlin, Kempe, Kenyon and McSherry. They focused on maximizing the seller's revenue. For two classes of utility functions: unit demand and single-minded, they showed:

• Computing envy-free prices to maximize the seller's revenue is APX-hard in both cases.
• A logarithmic approximation algorithm for the revenue in both cases.
• Polynomial-time algorithms for some special cases.

The results were later extended by Maria-Florina Balcan, Avrim Blum and Yishay Mansour. They showed that:

• With an unlimited number of units per item, a random single price achieves expected revenue within a logarithmic factor of the total social welfare, even for agents with general valuation functions (not even monotone). In particular, for a single agent, the revenue is at least 4 log (2m) of the maximum welfare (where m is the number of item-types), and for n agents, it is at least O (log (n) + log (m)) of the maximum welfare.
• With limited supply, for subadditive valuations, a random single price achieves revenue within a factor of 2^{O(√(log n loglog n)} of the total social welfare.
• A lower bound showing a sequence of subadditive (and even fractionally subadditive) agents for which any single price has approximation ratio 2^Ω(log1/4n)
• For the multi-unit case, as long as no buyer requires more than a 1-ε fraction of the items, a random single price achieves revenue within an O(log n) factor of the maximum social welfare.

Since then, the problem has been studied in various variants by various papers.

Comparison to related problems

• In envy-free item allocation, monetary payments are not allowed.

• In the rental harmony problem, monetaray payments are allowed, but all objects should be allocated (and each agent should get exactly one object).

• A Walrasian equilibrium is like envy-free pricing, with the additional requirement that all objects with a positive price must be allocated (all unallocated objects must have a zero price).