أوراكل الطلب

📅 آخر تحديث: ٤ أغسطس ٢٠٢٦
✍️ نُشر في: ٤ أغسطس ٢٠٢٦
الموسوعة الحرة

في نظرية الألعاب الخوارزمية ، وهي فرع من علوم الحاسوب والاقتصاد ، تُعرف دالة التنبؤ بالطلب بأنها دالة تُعيد، عند إعطائها متجه السعر، طلب أحد العملاء. وتُستخدم هذه الدالة في العديد من الخوارزميات المتعلقة بالتسعير والتحسين في الأسواق الإلكترونية . وعادةً ما تُقارن بدالة التنبؤ بالقيمة ، وهي دالة تُعيد، عند إعطائها مجموعة من العناصر، القيمة التي يُحددها أحد العملاء لكل عنصر.

يطلب

يُعرَّف طلب الوكيل بأنه مجموعة السلع التي يُفضِّلها الوكيل، مع الأخذ في الاعتبار أسعارًا ثابتة لهذه السلع. على سبيل المثال، لنفترض سوقًا يحتوي على ثلاثة سلع ووكيل واحد، بالقيم والأسعار التالية.

قيمةسعر
تفاحة25
موز43
الكرز61

لنفترض أن دالة منفعة الوكيل جمعية ( أي أن قيمة المجموعة هي مجموع قيم عناصرها)، وشبه خطية (أي أن منفعة المجموعة هي قيمتها مطروحًا منها سعرها). عندئذٍ، يكون طلب الوكيل، مع الأخذ في الاعتبار الأسعار، هو المجموعة {موز، كرز}، والتي تُعطي منفعة قدرها (4+6)-(3+1) = 6. كل مجموعة أخرى تُعطي الوكيل منفعة أقل. على سبيل المثال، المجموعة الفارغة تُعطي منفعة تساوي صفرًا، بينما مجموعة جميع العناصر تُعطي منفعة قدرها (2+4+6)-(5+3+1) = 3.

أوراكل

مع التقييمات الجمعية، يسهل حساب دالة الطلب، فلا حاجة إلى وسيط. مع ذلك، قد يمتلك الوكلاء عمومًا تقييمات توافقية . هذا يعني أنه لكل توليفة من العناصر، قد يكون لها قيمة مختلفة، وليست بالضرورة مجموع قيمها للعناصر الفردية. قد يتطلب وصف هذه الدالة على m عنصر ما يصل إلى 2 ^m عددًا، أي عددًا لكل مجموعة فرعية. قد يكون هذا غير عملي عندما يكون m كبيرًا. لذلك، تستخدم العديد من خوارزميات الأسواق نوعين من الوسطاء:

  • يمكن لـ "أوراكل القيمة" الإجابة على استعلامات القيمة : عند إعطاء حزمة، فإنه يعيد قيمتها.
  • يمكن لـ "أوراكل الطلب" الإجابة على استفسارات الطلب : فعند إعطاء متجه السعر، فإنه يعيد حزمة تعمل على زيادة المنفعة شبه الخطية (القيمة ناقص السعر).

التطبيقات

بعض الأمثلة على الخوارزميات التي تستخدم أوراكل الطلب هي:

  • تعظيم الرفاهية : يوجد n من العملاء و m من العناصر. يُمثَّل كل عميل بمؤشر قيمة ومؤشر طلب. المطلوب هو توزيع العناصر بين العملاء بحيث يكون مجموع القيم في أعلى مستوياته. بشكل عام، تُصنَّف هذه المسألة ضمن المسائل الصعبة حسابيًا (NP-hard)، ولكن توجد حلول تقريبية لحالات خاصة، مثل التقييمات شبه المعيارية (وتُسمى هذه المسألة "مسألة الرفاهية شبه المعيارية"). تستخدم بعض الخوارزميات مؤشر القيمة فقط؛ [ 1 ] بينما تستخدم خوارزميات أخرى مؤشر الطلب أيضًا . [ 2 ] [ 3 ]
  • التسعير الخالي من الحسد : يوجد n من الوكلاء و m من السلع. يُمثَّل كل وكيل بمؤشر قيمة ومؤشر طلب. المطلوب هو إيجاد متجه سعر وتوزيع للسلع، بحيث لا يشعر أي وكيل بالحسد، وبشرط تحقيق ذلك، يتم تعظيم إيرادات البائع.
  • حساب توازن السوق . [ 4 ]
  • تعلم الطلب على البدائل القوية . [ 5 ]

انظر أيضاً

مراجع

  1. ↑ فوندراك، جان (17 مايو 2008). "التقريب الأمثل لمسألة الرفاهية شبه المعيارية في نموذج أوراكل القيمة" . وقائع الندوة السنوية الأربعين لجمعية آلات الحوسبة حول نظرية الحوسبة . STOC '08. فيكتوريا، كولومبيا البريطانية، كندا: جمعية آلات الحوسبة. الصفحات 67-74 . doi : 10.1145/1374376.1374389 . ISBN  978-1-60558-047-0. S2CID 170510 . 
  2. ↑ دوبزينسكي، شاهار؛ شابيرا، مايكل (22 يناير 2006). "خوارزمية تقريب محسّنة للمزادات التوافقية مع مقدمي عروض شبه معيارية" . وقائع الندوة السنوية السابعة عشرة لجمعية ACM-SIAM حول الخوارزميات المنفصلة - SODA '06 . SODA '06. ميامي، فلوريدا: جمعية الرياضيات الصناعية والتطبيقية. الصفحات 1064-1073 . doi : 10.1145/1109557.1109675 . ISBN  978-0-89871-605-4. S2CID 13108913 . 
  3. ↑ فيج، أورييل؛ فوندراك، يان (9 ديسمبر 2010). "مشكلة الرفاهية شبه المعيارية مع استعلامات الطلب" . نظرية الحوسبة . 6 (1): 247-290 . doi : 10.4086/toc.2010.v006a011 . ISSN 1557-2862 . 
  4. ↑ كودينوتي، برونو؛ ماكيون، بنتون؛ فاراداراجان، كاستوري (22 مايو 2005). "توازن السوق عبر دالة الطلب الزائد" . وقائع الندوة السنوية السابعة والثلاثين لجمعية آلات الحوسبة حول نظرية الحوسبة . STOC '05. بالتيمور، ماريلاند، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. الصفحات 74-83 . doi : 10.1145/1060590.1060601 . ISBN  978-1-58113-960-0. S2CID 15453505 . 
  5. ↑ غولدبيرغ، بول دبليو؛ لوك، إدوين؛ مارمولخو-كوسيو، فرانسيسكو (2020). تشين، شوجين؛ غرافين، نيكولاي؛ هوفر، مارتن؛ ميهتا، روتا (محررون). "تعلم الطلب على البدائل القوية عبر الاستعلامات" . اقتصاديات الويب والإنترنت . سلسلة محاضرات في علوم الحاسوب. 12495. تشام: دار نشر سبرينغر الدولية: 401-415 . arXiv : 2005.01496 . doi : 10.1007/978-3-030-64946-3_28 . ISBN 978-3-030-64946-3. S2CID 218487768 .