Jump to content

Envy-free pricing: Difference between revisions

Add links
From Wikipedia, the free encyclopedia
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
No edit summary
Tags: Reverted Visual edit
Tags: Reverted nowiki added Visual edit
Line 17: Line 17:


== Results ==
== Results ==
A [[Walrasian equilibrium|'''Walrasian equilibrium''']] is an market-envy-free pricing with the additional requirement that all items with a positive price must be allocated (all unallocated items must have a zero price). It maximizes the social welfare. However, a Walrasian equilibrium might not exist (it is guaranteed to exist only when agents have [[Gross substitutes (indivisible items)|gross substitute valuations]]). Moreover, even when it exists, the sellers' revenue might be low. {{Note|A Fisher market equilibrium is similar to Walrasian equilibrium, but the agents are not quasilinear in money (money is used only inside the market, and has no intrinsic value).}}
A [[Walrasian equilibrium|'''Walrasian equilibrium''']] is an market-envy-free pricing with the additional requirement that all items with a positive price must be allocated (all unallocated items must have a zero price). It maximizes the social welfare.{{Note|A Fisher market equilibrium is similar to Walrasian equilibrium, but the agents are not quasilinear in money (money is used only inside the market, and has no intrinsic value).}}However, a Walrasian equilibrium might not exist (it is guaranteed to exist only when agents have [[Gross substitutes (indivisible items)|gross substitute valuations]]). Moreover, even when it exists, the sellers' revenue might be low. This motivates the relaxation to envy-free pricing, in which the seller may use reserve prices to increase the revenue.


'''Guruswami, Hartline, Karlin, Kempe, Kenyon and McSherry<ref name=":0" />''' introduced the term ''envy-free pricing'' to indicate that they require only envy-freeness - they do not require that all items be allocated. They focused on market envy-freeness, and maximizing the seller's revenue. For two classes of utility functions: ''[[unit demand]]'' and ''single-minded'', they showed:
'''Guruswami, Hartline, Karlin, Kempe, Kenyon and McSherry<ref name=":0" />''' (who introduced the term ''envy-free pricing'') focused on maximizing the seller's revenue subject to market-envy-freeness. For two classes of utility functions: ''[[unit demand]]'' and ''single-minded'', they showed:
* Computing market-envy-free prices to maximize the seller's revenue is [[APX-hard]] in both cases.
* Computing market-envy-free prices to maximize the seller's revenue is [[APX-hard]] in both cases.
* There is a logarithmic approximation algorithm for the revenue in both cases.
* There is a logarithmic approximation algorithm for the revenue in both cases.
* There are polynomial-time algorithms for some special cases.
* There are polynomial-time algorithms for some special cases.


'''[[Maria-Florina Balcan|Balcan]], [[Avrim Blum|Blum]] and [[Yishay Mansour|Mansour]]''' showed that:<ref>{{citation|last1=Balcan|first1=Maria-Florina|last2=Blum|first2=Avrim|last3=Mansour|first3=Yishay|editor1-last=Fortnow|editor1-first=Lance|editor2-last=Riedl|editor2-first=John|editor3-last=Sandholm|editor3-first=Tuomas|contribution=Item pricing for revenue maximization|doi=10.1145/1386790.1386802|pages=50–59|title=Proceedings of the 9th ACM Conference on Electronic Commerce (EC-2008), Chicago, IL, USA, June 8-12, 2008|year=2008}}</ref>
'''[[Maria-Florina Balcan|Balcan]], [[Avrim Blum|Blum]] and [[Yishay Mansour|Mansour]]''' also studied maximizing the seller's revenue subject to market-envy-freeness. They showed that:<ref>{{citation|last1=Balcan|first1=Maria-Florina|last2=Blum|first2=Avrim|last3=Mansour|first3=Yishay|editor1-last=Fortnow|editor1-first=Lance|editor2-last=Riedl|editor2-first=John|editor3-last=Sandholm|editor3-first=Tuomas|contribution=Item pricing for revenue maximization|doi=10.1145/1386790.1386802|pages=50–59|title=Proceedings of the 9th ACM Conference on Electronic Commerce (EC-2008), Chicago, IL, USA, June 8-12, 2008|year=2008}}</ref>


* 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 (2''m'') 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 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 (2''m'') 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.
Line 30: Line 30:
* A lower bound showing a sequence of subadditive (and even [[fractionally subadditive]]) agents for which any single price has approximation ratio 2<sup>Ω(log<sup>1/4</sup>''n'')</sup>
* A lower bound showing a sequence of subadditive (and even [[fractionally subadditive]]) agents for which any single price has approximation ratio 2<sup>Ω(log<sup>1/4</sup>''n'')</sup>
* 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.
* 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.
'''Briest and Krysta'''<ref>{{Cite journal|last=Briest|first=Patrick|last2=Krysta|first2=Piotr|date=2006-01-22|title=Single-minded unlimited supply pricing on sparse instances|url=https://dl.acm.org/doi/abs/10.5555/1109557.1109678|journal=Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm|series=SODA '06|location=Miami, Florida|publisher=Society for Industrial and Applied Mathematics|pages=1093–1102|doi=|isbn=978-0-89871-605-4}}</ref> also studied maximizing the seller's revenue subject to market-envy-freeness, when the supply is unlimited (i.e., [[Digital goods|digital good]]<nowiki/>s), and the buyers are ''single-minded'' - each buyer wants only a single subset of goods. They showed that:


* The problem is weakly NP-hard even in the restricted case in which the requested subsets are nested, i.e., contained inside each other or non-intersecting.
Since then, the problem has been studied in various variants by various papers.
* The problem is APX-hard even for very sparse instances defined on general graphs, where the number of requests per edge is bounded by a constant ''B'' and no path is longer than some constant ''L''.
* There is a polytime ''O''(log ''L'' + log ''B'')-approximation algorithm, and an ''O''(''L''<sup>2</sup>)-approximation algorithm.

<ref>{{Cite book|last=Briest|first=Patrick|date=2008|journal=Automata, Languages and Programming|publisher=Springer Berlin Heidelberg|isbn=9783540705758|editor-last=Aceto|editor-first=Luca|series=Lecture Notes in Computer Science|volume=5125|pages=808–819|language=en|chapter=Uniform Budgets and the Envy-Free Pricing Problem|citeseerx=10.1.1.205.433|doi=10.1007/978-3-540-70575-8_66|editor2-last=Damgård|editor2-first=Ivan|editor3-last=Goldberg|editor3-first=Leslie Ann|editor4-last=Halldórsson|editor4-first=Magnús M.|editor5-last=Ingólfsdóttir|editor5-first=Anna|editor6-last=Walukiewicz|editor6-first=Igor}}</ref><ref>{{Cite journal|last1=Chen|first1=Ning|last2=Ghosh|first2=Arpita|last3=Vassilvitskii|first3=Sergei|year=2011|title=SIAM (Society for Industrial and Applied Mathematics)|journal=SIAM Journal on Computing|volume=40|issue=3|pages=623–645|citeseerx=10.1.1.193.6235|doi=10.1137/080740970}}</ref><ref>{{Cite book|last1=Wang|first1=Yajun|url=https://archive.org/details/internetnetworke0000wine/page/483|title=Envy-Free Pricing with General Supply Constraints|last2=Lu|first2=Pinyan|last3=Im|first3=Sungjin|date=13 December 2010|journal=Internet and Network Economics|publisher=Springer, Berlin, Heidelberg|isbn=978-3-642-17571-8|series=Lecture Notes in Computer Science|volume=6484|pages=[https://archive.org/details/internetnetworke0000wine/page/483 483–491]|language=en|doi=10.1007/978-3-642-17572-5_41|url-access=registration}}</ref><ref>{{Cite book|last1=Feldman|first1=Michal|title=Revenue Maximizing Envy-free Multi-unit Auctions with Budgets|last2=Fiat|first2=Amos|last3=Leonardi|first3=Stefano|last4=Sankowski|first4=Piotr|date=2012|journal=Proceedings of the 13th ACM Conference on Electronic Commerce|publisher=ACM|isbn=9781450314152|series=EC '12|location=New York, NY, USA|pages=532–549|citeseerx=<!-- 10.1.1.643.8120-->|doi=10.1145/2229012.2229052|author1-link=Michal Feldman|s2cid=15639601}}</ref><ref>{{Cite journal|last1=Chen|first1=Ning|last2=Deng|first2=Xiaotie|date=1 February 2014|title=Envy-free Pricing in Multi-item Markets|journal=ACM Transactions on Algorithms|volume=10|issue=2|pages=7:1–7:15|citeseerx=10.1.1.297.784|doi=10.1145/2567923|issn=1549-6325|s2cid=15309106}}</ref>


== References ==
== References ==

Revision as of 13:37, 4 April 2021

Envy-free pricing[1] is a kind of fair item allocation. There is a single seller that owns some items, and a set of buyers who are interested in these items. The buyers have different valuations to the items, and they have a quasilinear utility function; this means that the utility an agent gains from a bundle of items equals the agent's value for the bundle minus the total price of items in the bundle. The seller should determine a price for each item, and sell the items to some of the buyers, such that there is no envy. Two kinds of envy are considered:

  • Agent envy means that some agent assigns a higher utility (a higher difference value-price) to a bundle allocated to another agent.
  • Market envy means that some agent assigns a higher utility (a higher difference value-price) to any bundle.

Obviously, every market envy-free allocation is also agent envy-free, but not vice-versa.

There always exists a market envy-free allocation (which is also agent envy-free): if the prices of all items are very high, and no item is sold (all buyers get an empty bundle), then there is no envy, since no agent would like to get any bundle for such high prices. However, such an allocation is very inefficient. The challenge in envy-free pricing is to find envy-free prices that also maximize one of the following objectives:

  • The social welfare - the sum of buyers' utilities;
  • The seller's revenue - the sum of prices paid by buyers.

Envy-free pricing is related, but not identical, to other fair allocation problems:

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

Results

A Walrasian equilibrium is an market-envy-free pricing with the additional requirement that all items with a positive price must be allocated (all unallocated items must have a zero price). It maximizes the social welfare.^ However, a Walrasian equilibrium might not exist (it is guaranteed to exist only when agents have gross substitute valuations). Moreover, even when it exists, the sellers' revenue might be low. This motivates the relaxation to envy-free pricing, in which the seller may use reserve prices to increase the revenue.

Guruswami, Hartline, Karlin, Kempe, Kenyon and McSherry[1] (who introduced the term envy-free pricing) focused on maximizing the seller's revenue subject to market-envy-freeness. For two classes of utility functions: unit demand and single-minded, they showed:

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

Balcan, Blum and Mansour also studied maximizing the seller's revenue subject to market-envy-freeness. 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.

Briest and Krysta[3] also studied maximizing the seller's revenue subject to market-envy-freeness, when the supply is unlimited (i.e., digital goods), and the buyers are single-minded - each buyer wants only a single subset of goods. They showed that:

  • The problem is weakly NP-hard even in the restricted case in which the requested subsets are nested, i.e., contained inside each other or non-intersecting.
  • The problem is APX-hard even for very sparse instances defined on general graphs, where the number of requests per edge is bounded by a constant B and no path is longer than some constant L.
  • There is a polytime O(log L + log B)-approximation algorithm, and an O(L2)-approximation algorithm.

[4][5][6][7][8]

References

  1. ^ a b "On profit-maximizing envy-free pricing | Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms". dl.acm.org. Retrieved 2020-01-16.{{cite web}}: CS1 maint: url-status (link)
  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
  3. ^ Briest, Patrick; Krysta, Piotr (2006-01-22). "Single-minded unlimited supply pricing on sparse instances". Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. SODA '06. Miami, Florida: Society for Industrial and Applied Mathematics: 1093–1102. ISBN 978-0-89871-605-4.
  4. ^ Briest, Patrick (2008). "Uniform Budgets and the Envy-Free Pricing Problem". In Aceto, Luca; Damgård, Ivan; Goldberg, Leslie Ann; Halldórsson, Magnús M.; Ingólfsdóttir, Anna; Walukiewicz, Igor (eds.). Lecture Notes in Computer Science. Vol. 5125. Springer Berlin Heidelberg. pp. 808–819. CiteSeerX 10.1.1.205.433. doi:10.1007/978-3-540-70575-8_66. ISBN 9783540705758. {{cite book}}: |journal= ignored (help); Missing or empty |title= (help)
  5. ^ Chen, Ning; Ghosh, Arpita; Vassilvitskii, Sergei (2011). "SIAM (Society for Industrial and Applied Mathematics)". SIAM Journal on Computing. 40 (3): 623–645. CiteSeerX 10.1.1.193.6235. doi:10.1137/080740970.
  6. ^ Wang, Yajun; Lu, Pinyan; Im, Sungjin (13 December 2010). Envy-Free Pricing with General Supply Constraints. Lecture Notes in Computer Science. Vol. 6484. Springer, Berlin, Heidelberg. pp. 483–491. doi:10.1007/978-3-642-17572-5_41. ISBN 978-3-642-17571-8. {{cite book}}: |journal= ignored (help)
  7. ^ Feldman, Michal; Fiat, Amos; Leonardi, Stefano; Sankowski, Piotr (2012). Revenue Maximizing Envy-free Multi-unit Auctions with Budgets. EC '12. New York, NY, USA: ACM. pp. 532–549. doi:10.1145/2229012.2229052. ISBN 9781450314152. S2CID 15639601. {{cite book}}: |journal= ignored (help)
  8. ^ Chen, Ning; Deng, Xiaotie (1 February 2014). "Envy-free Pricing in Multi-item Markets". ACM Transactions on Algorithms. 10 (2): 7:1–7:15. CiteSeerX 10.1.1.297.784. doi:10.1145/2567923. ISSN 1549-6325. S2CID 15309106.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Envy-free_pricing&oldid=1015941144"