Envy-free pricing

• 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.
• It is allowed to leave some items unallocated. However, it is required to maximize the social welfare and/or the seller's revenue.

• 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.

• 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. In particular, for a single agent, the revenue is at least 4 log of the maximum welfare, and for n agents, it is at least O + log ) of the maximum welfare.
• With limited supply, for subadditive valuations, a random single price achieves revenue within a factor of 2^O of the total social welfare.
• A lower bound showing a sequence of subadditive agents for which any single price has approximation ratio 2^Ω
• 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 factor of the maximum social welfare.

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.
• A Walrasian equilibrium is like envy-free pricing, with the additional requirement that all objects with a positive price must be allocated.