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[1] 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:[2]

  • 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 2O(√(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.

  • In the rental harmony problem, monetary 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).

References
  1. "On profit-maximizing envy-free pricing | Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms". dl.acm.org. Retrieved 2020-01-16.
  2. Balcan, Maria-Florina; Blum, Avrim; Mansour, Yishay (2008), "Item pricing for revenue maximization", in Fortnow, Lance; Riedl, John; Sandholm, Tuomas (eds.), Proceedings of the 9th ACM Conference on Electronic Commerce (EC-2008), Chicago, IL, USA, June 8-12, 2008, pp. 50–59, doi:10.1145/1386790.1386802
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.