선망 없는 가격

Envy-free pricing

선망 없는 가격은[1] 일종의 공정한 품목 할당이다.일부 품목을 소유하고 있는 싱글 셀러와 이들 품목에 관심이 있는 바이어 세트가 있다.구매자들은 상품에 대해 서로 다른 가치를 가지고 있고, 그들은 퀘이린 효용 함수를 가지고 있다; 이것은 대리인이 상품 묶음에서 얻는 효용성이 번들에 대한 대리인의 가치와 같은 것을 의미한다.판매자는 품목별로 가격을 정해 일부 구매자에게 판매해야 부러움이 없다.다음과 같은 두 가지 종류의 질투가 고려된다.

  • 에이전트 부러움이란 어떤 에이전트가 다른 에이전트에 할당된 번들에 더 높은 유틸리티(더 높은 차이 값-가격)를 할당하는 것을 의미한다.
  • 시장 선망이란 일부 대리점이 어떤 묶음에도 더 높은 효용(더 높은 차이 값 가격)을 할당하는 것을 의미한다.

무농약 조건은 시장이 안정되어 있다는 것과 구매자들이 판매자를 원망하지 않는다는 것을 보장한다.정의상, 모든 시장 부러움 없는 할당은 에이전트 부러움도 없으나 그 반대는 아니다.

시장 부러움 없는 할당은 항상 존재한다. 모든 품목의 가격이 매우 높고, 어떤 품목도 팔리지 않는다면(모든 구매자들은 빈 보따리를 얻는다), 그렇게 높은 가격에 어떤 보따리를 받고 싶어하지 않기 때문에 부러움이 없다.그러나 그러한 배분은 매우 비효율적이다.선망 없는 가격 책정 시 과제는 다음 목표 중 하나를 극대화하는 선망 없는 가격을 찾는 것이다.

  • 사회복지 - 구매자의 공공요금의 합계;
  • 판매자의 수익(또는 이익) - 구매자가 지불한 가격의 합계.

질투 없는 가격 책정은 다른 공정한 배분 문제와 관련이 있지만 동일하지는 않다.

  • 부러움 없는 아이템 할당에서는 금전적 지급이 허용되지 않는다.
  • 렌탈 조화 문제에서는 화폐 지급이 허용되고, 대리인은 콰실린(quasilinar)이지만, 모든 사물은 할당되어야 한다(각 대리인은 정확히 하나의 사물을 얻어야 한다).

결과.

왈라시안 평형이란 포지티브 가격을 가진 모든 품목을 할당해야 한다는 추가 요건(할당되지 않은 모든 품목은 제로 가격을 가져야 함)과 함께 시장이 없는 가격이다.그것은 사회 복지를 극대화한다.^ 그러나, 왈라시아 균형은 존재하지 않을 수 있다(대리인이 총대체 가치를 갖는 경우에만 존재한다고 보장된다).더욱이, 그것이 존재하더라도, 판매자의 수익은 낮을 수 있다.판매자가 일부 품목을 폐기하도록 허용하면 판매자가 더 높은 수익을 얻는 데 도움이 될 수 있다.

시장별 자유도를 고려하여 셀러의 매출 극대화

많은 저자들은 시장에 잘 적응하는 자유에 따라 판매자의 수익을 극대화하는 가격 벡터를 찾는 계산 문제를 연구했다.

구루스와미, 하르트라인, 칼린, 켐페, 케년, 맥셰리[1](무선비 가격 책정이라는 용어를 도입한 사람)는 효용 기능의 두 부류인 단위 수요와 단심(一心)을 연구했다.그들은 다음과 같은 것을 보여주었다.

  • 판매자의 매출을 극대화하기 위해 시장에 적응하지 못하는 가격을 계산하는 것은 두 경우 모두 APX 하드다.
  • 두 경우 모두 수익에 대한 로그 근사 알고리즘이 있다.
  • 일부 특수 사례에는 다항식 시간 알고리즘이 있다.

발칸, 블럼, 만수르는[2] 두 가지 설정을 연구했다: 무제한 공급 상품(예: 디지털 상품)과 공급이 제한된 상품이다.그들은 무작위로 선정된 단일 가격이 최대 사회복지수준의 비견비례적인 수익인 기대수입을 달성한다는 것을 보여주었다.

  • 무제한 공급으로, 무작위 단일 가격은 최대 사회복지 수준에 근접한 로그 요인을 달성한다.이것은 심지어 일반적인 (단일화가 아닌) 평가에서도 사실이다.단일 에이전트 및 m 품목 유형의 경우 수익은 최대 복지의 4 로그(2m) 이상, n 구매자의 경우 최대 복지의 O(log (n) + log (m) 이상이다.
  • 제한된 공급으로, 하위 부가 가치의 경우, 무작위 단일 가격은 최대 복지의 2 이내에서O(√(log n loglog n)) 수익을 달성한다.
  • 멀티유닛의 경우, 구매자가 품목의 1분의 1 이상을 요구하지 않는 경우, 임의의 단일가격은 최대 복지의 O(log n) 내에서 수익을 달성한다.
  • 부분적인 하위 가법 구매자에 대한 낮은 한계: 모든 단일 가격은 근사비 2를Ω(log1/4n) 가진다.

브리스트와 크리스타는[3] 무제한의 공급과 편협한 구매자가 있는 상품에 초점을 맞췄다 - 각각의 구매자는 오직 한 묶음의 상품만을 원한다.그들은 다음과 같은 것을 보여주었다.

  • 문제는 수배된 번들이 중첩되어 있어도 약하게 NP-hard이다.
  • 문제는 매우 희박한 경우에도 APX-hard이다.
  • 로그 요인 근사 알고리즘이 있다.

Briest는[4] 단위 수요 Min-prising 구매자에 초점을 맞췄다.그러한 구매자들은 각각 수배 물품의 하위 집합을 가지고 있으며, 그는 그 가격을 고려해 볼 때 가장 저렴한 수배 물품을 구입하고 싶어한다.그는 획일적인 예산에 초점을 맞췄다.그는 몇 가지 합리적인 복잡성 가정 하에서 다음과 같은 것을 보여주었다.

  • 일부 ε> 0의 경우, 균일한 예산으로 단위 수요 최소구매 가격 문제는 폴리타임으로 근사치할 수 없다.
  • 소비자들에게 명시적인 확률 분포로 주어지는 조금 더 일반적인 문제는 더 추측하기가 어렵다.
  • 모든 결과는 외향적인 구매자들에게도 적용된다.

Chen, Ghosh, Basilvtskii는[5] 미터법 대체성이 있는 항목에 초점을 맞췄다 - 구매자 i의 항목 j 값은 vi - c이고i,j 대체비용 c는i,j 미터법을 형성한다.라는 것을 보여준다.

  • 미터법 대체성으로, 문제는 다항식 시간에 정확히 해결될 수 있다.
  • 대체 비용이 대략 미터법(즉, 삼각형 불평등을 근사적으로 충족)에 불과할 경우, 문제는 NP-강도가 된다.

왕, 루, 임은[6] 매트로이드 제약과 같은 항목에 대해 독립적 시스템으로 주어진 공급 제약에 대한 문제를 연구한다.그들은 단위 수요 구매자에 초점을 맞춘다.

Chen과 Dung은[7] 멀티아이템 시장을 연구한다: 각각의 유닛을 공급하고 각각의 구매자가 하나의 아이템을 사고자 하는 n개의 분할할 수 없는 아이템이 있다.그들은 다음과 같이 보여준다.

  • 모든 구매자가 긍정적 평가(강력한 완벽한 그래프 정리)로 최대 두 개의 항목을 평가할 때 EF 가격을 극대화하는 수익을 계산하는 폴리타임 알고리즘.
  • 일부 구매자가 최소 3개 품목에 관심을 갖는다면 문제는 NP경제가 된다.

Chung and Smoly는[8] 공급이 제한된 단일 마인드 에이전트에 대한 폴리타임 근사 알고리즘을 제시한다.그들은 최대 사회복지 수입에 근접한 것이다.

Hartline과 Yan은[9] 사전 없는 진실된 메커니즘을 사용하여 수익 극대화를 연구한다.그것들은 또한 nvy-free 가격 결정의 단순한 구조와 진실된 메커니즘 설계와의 연결을 보여준다.

찰러묵, 추즈호이, 칸난, 칸나는[10] 이 문제의 두 가지 변형을 연구한다.두 변종 모두에서 각 구매자는 "원하는 품목" 세트를 가지고 있다.

  • 단위 수요 최소 구매 가격: 각 구매자는 에이전트 예산에 해당하는 경우 가장 저렴한 수배 물품을 구입하고, 그렇지 않으면 아무것도 구입하지 않는다.
  • 단심 가격: 각 구매자는 그들의 가격이 에이전트 예산일 경우 원하는 모든 물품을 구입하고, 그렇지 않을 경우 그는 아무것도 사지 않는다.

그들은 또한 톨게이트 가격 문제에 대해서도 연구한다. 즉, 각 품목이 그래프에서 가장자리이고 각 품목이 이 그래프에서 원하는 항목 집합이 경로인 단심 가격 결정의 특별한 경우.

찰러묵, 라카누킷, 나농카이[11] 등은 k-하이퍼그래프 가격결정이라는 변종에 근사 경도를 증명한다.그들은 또한 단위 수요의 최소 구매와 단일한 가격 책정에 대한 경도를 증명한다.[12]

Demaine, Feige, Hajiaghayi, Salavatipour는[13] 독특한 커버리지 문제로 인한 감소를 통해 근사치 경도 결과를 보여준다.

안셀레비치, 카르, 세카르는[14] 대형 시장에서 EF 가격 책정을 연구한다.그들은 수익-최대화와 복지-최대화를 모두 고려한다.

빌로, 플람미니, 모나코는[15] EF 가격 책정에 대해 날카로운 요구를 가지고 연구한다. 여기서 각 구매자는 정해진 수량의 품목에 관심을 갖는다.

콜리니 발데스치, 레오나르디, 산코프스키, 장과[16] 펠드만, 피아트, 레오나르디, 산코프스키가[17] 예산에 책정된 요원들과 함께 EF 가격 책정을 연구한다.

모나코, 산코프스키, 장은[18] 다중 단위 시장을 연구한다.그들은 시장-자유성과 에이전트-자유성 둘 다에서 수익 극대화를 연구한다.그들은 아이템-가격-가격-가격-가격-가격-가격-가격 둘 다를 고려한다.

질투-자유에 대한 느긋한 관념

  • 첸과 루드라는[19] 승자만이 부러워하지 않는 왈라시아 평형의 완화를 고려한다.부러움 없는 구매자의 수를 극대화하는 것이 목표다.
  • 알론·만수르·텐넨홀츠[20]·아마나티디스·풀라·마카키스·소나트[21] 등은 구매자가 소셜네트워크에 배열되는 시장-자유성의 완화를 고려하고, 가격은 네트워크에 인접한 노드 사이에만 비슷해야 하며, 패자는 부러워해서는 안 된다.
  • 플람미니, 마우로, 톤리[22][23] 등은 각각의 에이전트가 (주어진 소셜네트워크 상에서) 이웃 에이전트의 아이템만 보는 시장-자유성의 완화를 고려한다.
  • 엘바시오니, 푸즈, 그리고[24] 스마디는 승자들만이 부러워하지 않는 에이전트-완전성의 완화를 고려한다.그들은 보따리를 굽는 것을 고려한다.

참고 항목

  • 요구 Oracle - 질투 없는 가격 책정 알고리즘에 자주 사용되는 Oracle

참조

  1. ^ a b Guruswami, Venkatesan; Hartline, Jason D.; Karlin, Anna R.; Kempe, David; Kenyon, Claire; McSherry, Frank. On profit-maximizing envy-free pricing. Society for Industrial and Applied Mathematics. pp. 1164–1173. ISBN 978-0-89871-585-9.
  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. ISBN 9781605581699. S2CID 53038874.
  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. doi:10.1145/1109557.1109678. ISBN 978-0-89871-605-4. S2CID 4191038.
  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.). Automata, Languages and Programming. 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}}:누락 또는 비어 있음 title=(도움말)
  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. ^ Im, Sungjin; Lu, Pinyan; Wang, Yajun (2010). Saberi, Amin (ed.). "Envy-Free Pricing with General Supply Constraints". Internet and Network Economics. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 6484: 483–491. doi:10.1007/978-3-642-17572-5_41. ISBN 978-3-642-17572-5.
  7. ^ 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.
  8. ^ Cheung, M.; Swamy, C. (2008-10-01). "Approximation Algorithms for Single-minded Envy-free Profit-maximization Problems with Limited Supply". 2008 49th Annual IEEE Symposium on Foundations of Computer Science: 35–44. doi:10.1109/FOCS.2008.15. ISBN 978-0-7695-3436-7. S2CID 1318192.
  9. ^ Devanur, Nikhil R.; Hartline, Jason D.; Yan, Qiqi (2015-03-01). "Envy freedom and prior-free mechanism design". Journal of Economic Theory. 156: 103–143. arXiv:1212.3741. doi:10.1016/j.jet.2014.08.001. ISSN 0022-0531. S2CID 17990320.
  10. ^ Chalermsook, Parinya; Chuzhoy, Julia; Kannan, Sampath; Khanna, Sanjeev (2012). Gupta, Anupam; Jansen, Klaus; Rolim, José; Servedio, Rocco (eds.). "Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply". Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 7408: 73–84. doi:10.1007/978-3-642-32512-0_7. ISBN 978-3-642-32512-0.
  11. ^ Chalermsook, P.; Laekhanukit, B.; Nanongkai, D. (2013-10-01). "Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science: 370–379. arXiv:1308.2617. doi:10.1109/FOCS.2013.47. ISBN 978-0-7695-5135-7. S2CID 972321.
  12. ^ Chalermsook, Parinya; Laekhanukit, Bundit; Nanongkai, Danupon (2013-01-06). "Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More". Proceedings of the 2013 Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings. Society for Industrial and Applied Mathematics. pp. 1557–1576. arXiv:1212.4129. doi:10.1137/1.9781611973105.112. ISBN 978-1-61197-251-1. S2CID 6556716. Retrieved 2021-04-04.
  13. ^ Demaine, Erik D.; Feige, Uriel; Hajiaghayi, MohammadTaghi; Salavatipour, Mohammad R. (2008-01-01). "Combination Can Be Hard: Approximability of the Unique Coverage Problem". SIAM Journal on Computing. 38 (4): 1464–1483. doi:10.1137/060656048. ISSN 0097-5397. S2CID 12248889.
  14. ^ Anshelevich, Elliot; Kar, Koushik; Sekar, Shreyas (2017-08-09). "Envy-Free Pricing in Large Markets: Approximating Revenue and Welfare". ACM Transactions on Economics and Computation. 5 (3): 16:1–16:42. doi:10.1145/3105786. ISSN 2167-8375. S2CID 7008965.
  15. ^ Bilò, Vittorio; Flammini, Michele; Monaco, Gianpiero (2017-02-01). "Approximating the revenue maximization problem with sharp demands". Theoretical Computer Science. 662: 9–30. doi:10.1016/j.tcs.2016.12.002. ISSN 0304-3975.
  16. ^ Colini-Baldeschi, Riccardo; Leonardi, Stefano; Sankowski, Piotr; Zhang, Qiang (2014). Liu, Tie-Yan; Qi, Qi; Ye, Yinyu (eds.). "Revenue Maximizing Envy-Free Fixed-Price Auctions with Budgets". Web and Internet Economics. Lecture Notes in Computer Science. Cham: Springer International Publishing. 8877: 233–246. doi:10.1007/978-3-319-13129-0_18. hdl:11573/754515. ISBN 978-3-319-13129-0.
  17. ^ Feldman, Michal; Fiat, Amos; Leonardi, Stefano; Sankowski, Piotr (2012). Revenue Maximizing Envy-free Multi-unit Auctions with Budgets. Proceedings of the 13th ACM Conference on Electronic Commerce. EC '12. New York, NY, USA: ACM. pp. 532–549. doi:10.1145/2229012.2229052. ISBN 9781450314152. S2CID 15639601.
  18. ^ Monaco, Gianpiero; Sankowski, Piotr; Zhang, Qiang (2015-07-25). "Revenue maximization envy-free pricing for homogeneous resources". Proceedings of the 24th International Conference on Artificial Intelligence. IJCAI'15. Buenos Aires, Argentina: AAAI Press: 90–96. ISBN 978-1-57735-738-4.
  19. ^ Chen, Ning; Rudra, Atri (2008-09-01). "Walrasian Equilibrium: Hardness, Approximations and Tractable Instances". Algorithmica. 52 (1): 44–64. doi:10.1007/s00453-007-9103-9. ISSN 1432-0541. S2CID 18839423.
  20. ^ Alon, Noga; Mansour, Yishay; Tenneholtz, Moshe (2013-06-16). "Differential pricing with inequity aversion in social networks". Proceedings of the Fourteenth ACM Conference on Electronic Commerce. EC '13. Philadelphia, Pennsylvania, USA: Association for Computing Machinery: 9–24. doi:10.1145/2492002.2482545. ISBN 978-1-4503-1962-1.
  21. ^ Amanatidis, Georgios; Fulla, Peter; Markakis, Evangelos; Sornat, Krzysztof (2019-12-17). "Inequity Aversion Pricing over Social Networks: Approximation Algorithms and Hardness Results". arXiv:1606.06664 [cs.GT].
  22. ^ Flammini, Michele; Mauro, Manuel; Tonelli, Matteo (2019-04-01). "On social envy-freeness in multi-unit markets". Artificial Intelligence. 269: 1–26. doi:10.1016/j.artint.2018.12.003. ISSN 0004-3702. S2CID 19205358.
  23. ^ "Inequity Aversion Pricing in Multi-Unit Markets". iris.gssi.it. Retrieved 2021-04-05.
  24. ^ Elbassioni, Khaled; Fouz, Mahmoud; Swamy, Chaitanya (2010). Saberi, Amin (ed.). "Approximation Algorithms for Non-single-minded Profit-Maximization Problems with Limited Supply". Internet and Network Economics. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 6484: 462–472. arXiv:1312.0137. doi:10.1007/978-3-642-17572-5_39. ISBN 978-3-642-17572-5. S2CID 14124011.