مقاومة الاستراتيجيات

الموسوعة الحرة

في تصميم الآليات ، تُعرف الآلية المقاومة للاستراتيجية (SP) بأنها شكل من أشكال الألعاب حيث يمتلك كل لاعب استراتيجية مهيمنة ضعيفة ، بحيث لا يستطيع أي لاعب تحقيق مكاسب من خلال "التجسس" على اللاعبين الآخرين لمعرفة ما سيلعبونه. عندما يمتلك اللاعبون معلومات خاصة (مثل نوعهم أو قيمتهم بالنسبة لعنصر ما)، وتتكون مساحة استراتيجية كل لاعب من قيم المعلومات الممكنة (مثل الأنواع أو القيم الممكنة)، فإن الآلية الصادقة هي لعبة يكون فيها الكشف عن المعلومات الحقيقية استراتيجية مهيمنة ضعيفة لكل لاعب. [ 1 ] : 244 تُسمى آلية SP أيضًا بالآلية المتوافقة مع حوافز الاستراتيجية المهيمنة (DSIC) ، [ 1 ] : 415 لتمييزها عن أنواع التوافق الأخرى للحوافز .

تتمتع آلية SP بمناعة ضد التلاعب من قبل اللاعبين الأفراد (ولكن ليس من قبل التحالفات). في المقابل، في آلية جماعية مقاومة للتلاعب ، لا يمكن لأي مجموعة من الأشخاص التواطؤ لتضليل الرأي العام بشأن تفضيلاتهم بطريقة تُحسّن وضع جميع أعضائها. في آلية جماعية قوية مقاومة للتلاعب، لا يمكن لأي مجموعة من الأشخاص التواطؤ لتضليل الرأي العام بشأن تفضيلاتهم بطريقة تُحسّن وضع عضو واحد على الأقل من المجموعة دون الإضرار بوضع أي من الأعضاء الآخرين. [ 2 ]

أمثلة

من الأمثلة النموذجية لآليات SP ما يلي:

من الأمثلة النموذجية للآليات التي لا تُعدّ SP ما يلي:

مزود الخدمة في توجيه الشبكة

ينطبق مبدأ السعر المُحدد (SP) أيضًا على توجيه الشبكات . لنفترض أن الشبكة عبارة عن رسم بياني ، حيث يرتبط كل رابط (أي وصلة) بتكلفة إرسال خاصة بمالك تلك الوصلة. يرغب مالك الوصلة في الحصول على تعويض مقابل إعادة توجيه الرسائل. وبصفته مُرسل رسالة على الشبكة، يسعى لإيجاد المسار الأقل تكلفة. توجد طرق فعالة لتحقيق ذلك، حتى في الشبكات الكبيرة. مع ذلك، ثمة مشكلة واحدة: تكاليف كل وصلة غير معروفة. يتمثل أحد الأساليب البسيطة في سؤال مالك كل وصلة عن التكلفة، واستخدام هذه التكاليف المعلنة لإيجاد المسار الأقل تكلفة، ودفع التكاليف المعلنة لجميع الوصلات على هذا المسار. لكن يمكن إثبات أن آلية الدفع هذه ليست من مبدأ السعر المُحدد، أي أن مالكي بعض الوصلات قد يستفيدون من خلال التلاعب بالتكلفة. قد ينتهي بنا الأمر بدفع مبالغ تفوق التكلفة الفعلية بكثير. يمكن إثبات أنه في ظل افتراضات معينة حول الشبكة والجهات الفاعلة (مالكي الوصلات)، فإن أحد أشكال آلية VCG يُعد من مبدأ السعر المُحدد.

التعريفات الرسمية

هناك مجموعةX{\displaystyle X}من النتائج المحتملة.

هناكن{\displaystyle n}الوكلاء الذين لديهم تقييمات مختلفة لكل نتيجة. تقييم الوكيلأنا{\displaystyle i}يتم تمثيلها كدالة:

vأنا:X⟶R+{\displaystyle v_{i}:X\longrightarrow R_{+}}

والتي تعبر عن القيمة التي تمثلها لكل بديل، من الناحية النقدية.

يُفترض أن لدى الوكلاء دوال منفعة شبه خطية ؛ وهذا يعني أنه إذا كانت النتيجةx{\displaystyle x}بالإضافة إلى ذلك، يتلقى الوكيل دفعة مالية.صأنا{\displaystyle p_{i}}(إيجابي أو سلبي)، ثم المنفعة الكلية للعاملأنا{\displaystyle i}يكون:

uأنا:=vأنا(x)+صأنا{\displaystyle u_{i}:=v_{i}(x)+p_{i}}

يُرمز إلى متجه جميع دوال القيمة بـv{\displaystyle v}.

لكل وكيلأنا{\displaystyle i}، ويُرمز إلى متجه جميع دوال القيمة للعوامل الأخرى بـv-أنا{\displaystyle v_{-i}}. لذاv≡(vأنا،v-أنا){\displaystyle v\equiv (v_{i},v_{-i})}.

الآلية عبارة عن زوج من الوظائف :

  • أنياuتجoمهـ{\displaystyle Outcome}دالة تأخذ كمدخل متجه القيمةv{\displaystyle v}ويعيد نتيجةx∈X{\displaystyle x\in X}(يطلق عليها أيضًا وظيفة الاختيار الاجتماعي )؛
  • أPأyمهـنت{\displaystyle Payment}دالة تأخذ كمدخل متجه القيمة v{\displaystyle v}ويعيد متجهًا للمدفوعات،(ص1،...،صن){\displaystyle (p_{1},\dots ,p_{n})}، وتحديد المبلغ الذي يجب أن يحصل عليه كل لاعب (الدفع السلبي يعني أن اللاعب يجب أن يدفع مبلغًا إيجابيًا).

تُسمى الآلية مقاومة للاستراتيجية إذا كانت، بالنسبة لكل لاعبأنا{\displaystyle i}ولكل متجه قيمة من متجهات اللاعبين الآخرينv-أنا{\displaystyle v_{-i}}:

vأنا(ياuتجoمهـ(vأنا،v-أنا))+Pأyمهـنتأنا(vأنا،v-أنا)≥vأنا(ياuتجoمهـ(vأنا′،v-أنا))+Pأyمهـنتأنا(vأنا′،v-أنا){\displaystyle v_{i}(Outcome(v_{i},v_{-i}))+Payment_{i}(v_{i},v_{-i})\geq v_{i}(Outcome(v_{i}',v_{-i}))+Payment_{i}(v_{i}',v_{-i})}

توصيف

من المفيد وضع شروط بسيطة للتحقق مما إذا كانت آلية معينة من نوع SP أم لا. يوضح هذا القسم الفرعي شرطين بسيطين ضروريين وكافيين.

إذا كانت آلية التحويلات النقدية هي آلية ذات أولوية خاصة، فيجب أن تستوفي الشرطين التاليين، لكل وكيلأنا{\displaystyle i}: [ 1 ] : 226

1. الدفع للوكيلأنا{\displaystyle i}هي دالة للنتيجة المختارة وتقييمات الجهات الفاعلة الأخرىv-أنا{\displaystyle v_{-i}}- ولكن ليس ذلك نتيجة مباشرة لتقييم الوكيل نفسهvأنا{\displaystyle v_{i}}بصورة رسمية، توجد دالة سعريةPرأناجهـأنا{\displaystyle Price_{i}}، الذي يأخذ كمدخل نتيجةx∈X{\displaystyle x\in X}ومتجه تقييم للوكلاء الآخرينv-أنا{\displaystyle v_{-i}}ويعيد المبلغ المدفوع للوكيلأنا{\displaystyle i}بحيث يكون لكلvأنا،vأنا′،v-أنا{\displaystyle v_{i},v_{i}',v_{-i}}، لو:

ياuتجoمهـ(vأنا،v-أنا)=ياuتجoمهـ(vأنا′،v-أنا){\displaystyle Outcome(v_{i},v_{-i})=Outcome(v_{i}',v_{-i})}

ثم:

Pأyمهـنتأنا(vأنا،v-أنا)=Pأyمهـنتأنا(vأنا′،v-أنا){\displaystyle Payment_{i}(v_{i},v_{-i})=Payment_{i}(v_{i}',v_{-i})}

الدليل: إذاPأyمهـنتأنا(vأنا،v-أنا)>Pأyمهـنتأنا(vأنا′،v-أنا){\displaystyle Payment_{i}(v_{i},v_{-i})>Payment_{i}(v_{i}',v_{-i})}ثم وكيل ذو تقييمvأنا′{\displaystyle v_{i}'}يفضل الإبلاغvأنا{\displaystyle v_{i}}لأنه يمنحه نفس النتيجة ودفعة أكبر؛ وبالمثل، إذاPأyمهـنتأنا(vأنا،v-أنا)<Pأyمهـنتأنا(vأنا′،v-أنا){\displaystyle Payment_{i}(v_{i},v_{-i})<Payment_{i}(v_{i}',v_{-i})}ثم وكيل ذو تقييمvأنا{\displaystyle v_{i}}يفضل الإبلاغvأنا′{\displaystyle v_{i}'}.

وكنتيجة لذلك، توجد وظيفة "سعرية".Pرأناجهـأنا{\displaystyle Price_{i}}، الذي يأخذ كمدخل نتيجةx∈X{\displaystyle x\in X}ومتجه تقييم للوكلاء الآخرينv-أنا{\displaystyle v_{-i}}ويعيد المبلغ المدفوع للوكيلأنا{\displaystyle i}لكلvأنا،v-أنا{\displaystyle v_{i},v_{-i}}، لو:

ياuتجoمهـ(vأنا،v-أنا)=x{\displaystyle Outcome(v_{i},v_{-i})=x}

ثم:

Pأyمهـنتأنا(vأنا،v-أنا)=Pرأناجهـأنا(x،v-أنا){\displaystyle Payment_{i}(v_{i},v_{-i})=Price_{i}(x,v_{-i})}

2. النتيجة المختارة هي الأمثل للوكيلأنا{\displaystyle i}بالنظر إلى تقييمات الوكلاء الآخرين. رسميًا:

ياuتجoمهـ(vأنا،v-أنا)∈arg⁡الأعلىx[vأنا(x)+Pرأناجهـأنا(x،v-أنا)]{\displaystyle Outcome(v_{i},v_{-i})\in \arg \max _{x}[v_{i}(x)+Price_{i}(x,v_{-i})]}

حيث يتم تحقيق أقصى قدر من النتائج على جميع النتائج في نطاقياuتجoمهـ(⋅،v-أنا){\displaystyle Outcome(\cdot ,v_{-i})}.

الدليل: إذا كانت هناك نتيجة أخرىx′=ياuتجoمهـ(vأنا′،v-أنا){\displaystyle x'=Outcome(v_{i}',v_{-i})}بحيثvأنا(x′)+Pرأناجهـأنا(x′،v-أنا)>vأنا(x)+Pرأناجهـأنا(x،v-أنا){\displaystyle v_{i}(x')+Price_{i}(x',v_{-i})>v_{i}(x)+Price_{i}(x,v_{-i})}ثم وكيل ذو تقييمvأنا{\displaystyle v_{i}}يفضل الإبلاغvأنا′{\displaystyle v_{i}'}لأنه يمنحه منفعة إجمالية أكبر.

الشرطان 1 و 2 ليسا ضروريين فحسب، بل كافيين أيضًا: أي آلية تفي بالشرطين 1 و 2 هي SP.

دليل: إصلاح وكيلأنا{\displaystyle i}والتقييماتvأنا،vأنا′،v-أنا{\displaystyle v_{i},v_{i}',v_{-i}}. يُشير إلى:

x:=ياuتجoمهـ(vأنا،v-أنا){\displaystyle x:=Outcome(v_{i},v_{-i})}- النتيجة عندما يتصرف الفاعل بصدق.
x′:=ياuتجoمهـ(vأنا′،v-أنا){\displaystyle x':=Outcome(v_{i}',v_{-i})}- النتيجة عندما يتصرف الفاعل بشكل غير صادق.

بحسب الخاصية رقم 1، فإن فائدة الوكيل عند اللعب بصدق هي:

uأنا(vأنا)=vأنا(x)+Pرأناجهـأنا(x،v-أنا){\displaystyle u_{i}(v_{i})=v_{i}(x)+Price_{i}(x,v_{-i})}

وتكمن فائدة الوكيل عند اللعب بطريقة غير صادقة فيما يلي:

uأنا(vأنا′)=vأنا(x′)+Pرأناجهـأنا(x′،v-أنا){\displaystyle u_{i}(v_{i}')=v_{i}(x')+Price_{i}(x',v_{-i})}

بواسطة العقار رقم 2:

uأنا(vأنا)≥uأنا(vأنا′){\displaystyle u_{i}(v_{i})\geq u_{i}(v_{i}')}

لذا فإن التصرف بصدق يُعد استراتيجية مهيمنة بالنسبة للوكيل.

توصيف النتائج الوظيفية

الهدف الحقيقي للآلية هوياuتجoمهـ{\displaystyle Outcome}الوظيفة؛ وظيفة الدفع ليست سوى أداة لحث اللاعبين على الصدق. لذا، من المفيد معرفة، بالنظر إلى وظيفة نتيجة معينة، ما إذا كان من الممكن تنفيذها باستخدام آلية SP أم لا (تُسمى هذه الخاصية أيضًا قابلية التنفيذ ).

تُعد خاصية الرتابة ضرورية لضمان عدم وجود استراتيجيات فعّالة.

آليات الصدق في مجالات المعلمة الواحدة

المجال ذو المعلمة الواحدة هو لعبة يكون فيها كل لاعبأنا{\displaystyle i}يحصل على قيمة موجبة معينةvأنا{\displaystyle v_{i}}للدلالة على "الفوز" وقيمة 0 للدلالة على "الخسارة". مثال بسيط على ذلك هو مزاد عنصر واحد، حيثvأنا{\displaystyle v_{i}}القيمة التي يمتلكها اللاعبأنا{\displaystyle i}يُسند إلى العنصر.

في هذا السياق، يسهل تحديد الآليات الصادقة. لنبدأ ببعض التعريفات.

تُسمى الآلية بالآلية المعيارية إذا كان كل عرض خاسر يدفع 0.

تُسمى الآلية بالرتابة إذا زادت فرص فوز اللاعب (بشكل ضعيف) عندما يرفع عرضه.

بالنسبة لآلية رتيبة، لكل لاعب i ولكل مجموعة من عروض اللاعبين الآخرين، توجد قيمة حرجة ينتقل عندها اللاعب من الخسارة إلى الفوز.

تكون الآلية المعيارية على مجال ذي معلمة واحدة صادقة إذا تحقق الشرطان التاليان: [ 1 ] : 229-230

  1. تكون دالة التخصيص رتيبة في كل من العروض، و:
  2. كل عرض فائز يدفع القيمة الحرجة.

مصداقية الآليات العشوائية

توجد طرق متنوعة لتوسيع مفهوم الصدق ليشمل الآليات العشوائية. وهي، من الأقوى إلى الأضعف: [ 3 ] : 6-8

  • الصدق الشامل : لكل عملية عشوائية للخوارزمية، تكون الآلية الناتجة صادقة. بعبارة أخرى: الآلية الصادقة شاملاً هي عملية عشوائية لآليات صادقة حتمية، حيث قد تعتمد الأوزان على المدخلات.
  • الصدق ذو الهيمنة العشوائية القوية (strong-SD-truthfulness) : يتميز متجه الاحتمالات الذي يحصل عليه الفاعل عند صدقه بهيمنة عشوائية من الدرجة الأولى على متجه الاحتمالات الذي يحصل عليه عند تضليله. أي أن: احتمال الحصول على الأولوية القصوى لا يقل عن احتمال الحصول على الأولوية القصوى، واحتمال الحصول على إحدى الأولويتين القصوى لا يقل عن احتمال الحصول على الأولوية القصوى، واحتمال الحصول على إحدى الأولويات القصوى (من بين m أولوية) لا يقل عن احتمال الحصول على الأولوية القصوى.
  • الصدق المعجمي (الصدق المعجمي) : يكون لمتجه الاحتمالات التي يحصل عليها الفاعل عند صدقه أولوية معجمية على متجه الاحتمالات التي يحصل عليها عند تضليله. أي: احتمال الحصول على الأولوية القصوى أعلى، أو (احتمال الحصول على الأولوية القصوى متساوٍ، واحتمال الحصول على إحدى الأولويتين القصوى أعلى)، أو ... (احتمال الحصول على أول m -1 أولوية متساوٍ، واحتمال الحصول على إحدى الأولويات القصوى m أعلى)، أو (جميع الاحتمالات متساوية).
  • الصدق ذو الهيمنة العشوائية الضعيفة (الصدق ذو الهيمنة العشوائية الضعيفة) : إن متجه الاحتمالات التي يتلقاها الوكيل من خلال كونه صادقًا لا يهيمن عليه من الدرجة الأولى من الناحية العشوائية متجه الاحتمالات التي يحصل عليها من خلال الإبلاغ الخاطئ.

الاستدلال الكلي يستلزم الاستدلال القوي، والاستدلال المعجمي يستلزم الاستدلال الضعيف، وجميع الاستدلالات صارمة. [ 3 ] : نظرية 3.4

الصدق باحتمالية عالية

لكل ثابتϵ>0{\displaystyle \epsilon >0}يُطلق على الآلية العشوائية اسم "صادقة" باحتمالية1-ϵ{\displaystyle 1-\epsilon }إذا كان احتمال استفادة الوكيل من خلال تقديم عرض غير صادق لكل وكيل ولكل متجه من العروض هو على الأكثرϵ{\displaystyle \epsilon }حيث يتم حساب الاحتمالية على أساس عشوائية الآلية. [ 1 ] : 349

إذا كان الثابتϵ{\displaystyle \epsilon }عندما يؤول عدد المزايدين إلى الصفر مع ازدياد عددهم، يُطلق على الآلية حينها اسم "الصادقة باحتمالية عالية" . هذا المفهوم أضعف من مفهوم الصدق التام، ولكنه لا يزال مفيدًا في بعض الحالات؛ انظر على سبيل المثال تقدير الإجماع .

مقاومة الأسماء المستعارة

يُعدّ نوع جديد من الاحتيال الذي أصبح شائعاً مع وفرة المزادات عبر الإنترنت هو تقديم العروض بأسماء وهمية - وهي عروض يقدمها مزايد واحد باستخدام معرفات متعددة مثل عناوين بريد إلكتروني متعددة.

تعني خاصية منع التلاعب بالأسماء المزيفة أنه لا يوجد حافز لدى أي من اللاعبين لتقديم عروض بأسماء مزيفة. وهذا مفهوم أقوى من مفهوم منع التلاعب بالاستراتيجية. وعلى وجه الخصوص، فإن مزاد فيكري-كلارك-غروفز (VCG) ليس محصنًا ضد التلاعب بالأسماء المزيفة. [ 4 ]

إن مقاومة الاسم الزائف تختلف بشكل كبير عن مقاومة استراتيجية المجموعة لأنها تفترض أن الفرد بمفرده يمكنه محاكاة سلوكيات معينة تتطلب عادةً التنسيق التواطئي بين عدة أفراد.

مناعة استراتيجية واضحة

إن مفهوم "التحصين الواضح ضد الاستراتيجيات" (OSP) هو تعزيز لمفهوم "التحصين ضد الاستراتيجيات" والذي يعكس متانة هذا المفهوم في مواجهة العوامل ذات القدرات المعرفية المحدودة. [ 5 ]

يُعدّ مزاد السعر الثاني ذو العطاءات المغلقة مقاومًا للتلاعب، ولكنه ليس كذلك بشكلٍ واضح، لأنّ على المُزايدين أن يثقوا في بقاء عطاءاتهم سرية. [ 6 ] [ 7 ] في المقابل، يُعدّ مزاد الساعة التصاعدي مقاومًا للتلاعب بشكلٍ واضح، [ 5 ] على الرغم من أنّ المزادين متكافئان بالنسبة للوكلاء العقلانيين تمامًا. ومن الأمثلة الأخرى على الآليات المقاومة للتلاعب ولكن ليست كذلك بشكلٍ واضح ما يلي:

انظر أيضاً

للمزيد من القراءة

مراجع

  1. 1 2 3 4 5 فازيراني، فيجاي ف . نيسان, نعوم ; روغاردن, تيم ; تاردوس، إيفا (2007). نظرية اللعبة الخوارزمية (PDF) . كامبريدج، المملكة المتحدة: مطبعة جامعة كامبريدج. رقم ISBN 0-521-87282-0.
  2. ↑ "مقاومة استراتيجية المجموعة والاختيار الاجتماعي بين بديلين" (ملف PDF) . مؤرشف من الأصل (ملف PDF) بتاريخ 12-02-2020.
  3. 1 2 تشاكرابارتي، ديبارناب؛ سوامي، تشايتانيا (12 يناير 2014). "تعظيم الرفاهية والصدق في تصميم الآليات مع التفضيلات الترتيبية" . وقائع المؤتمر الخامس حول الابتكارات في علوم الحاسوب النظرية . ITCS '14. نيويورك، نيويورك، الولايات المتحدة الأمريكية: رابطة آلات الحوسبة. الصفحات 105-120 . arXiv : 1312.1831 . doi : 10.1145/2554797.2554810 . ISBN  978-1-4503-2698-8. S2CID 2428592 . 
  4. ↑ يوكو، م.؛ ساكوراي، ي.؛ ماتسوبارا، س. (2004). "أثر العطاءات بأسماء وهمية في المزادات التوافقية: احتيال جديد في مزادات الإنترنت". الألعاب والسلوك الاقتصادي . 46 : 174-188 . CiteSeerX 10.1.1.18.6796 . doi : 10.1016/S0899-8256(03)00045-9 . 
  5. 1 2 لي، شينغ وو (2017-11-01). "آليات واضحة مقاومة للاستراتيجية" . المجلة الاقتصادية الأمريكية . 107 (11): 3257-3287 . doi : 10.1257/aer.20160425 . ISSN 0002-8282 . 
  6. ↑ أكبربور، محمد؛ لي، شينغ وو (2017). "تصميم آلية موثوقة" . المجلة الإلكترونية لشبكة أبحاث العلوم الاجتماعية . doi : 10.2139/ssrn.3033208 . ISSN 1556-5068 . SSRN 3033208 .  
  7. ↑ كومو، أندرو؛ كومينرز، سكوت ديوك؛ رافغاردن، تيم (2025-07-02). "مزادات مقاومة للتلاعب" . وقائع المؤتمر السادس والعشرين لجمعية آلات الحوسبة حول الاقتصاد والحوسبة . EC '25. نيويورك، نيويورك، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. ص 784. doi : 10.1145/3736252.3742623 . ISBN  979-8-4007-1943-1.
  8. ↑ أشلاجي، إيتاي؛ غونتشاروفسكي، ياناي أ. (2018-09-01). "آليات المطابقة المستقرة ليست بالضرورة محصنة ضد التلاعب الاستراتيجي" . مجلة النظرية الاقتصادية . 177 : 405-425 . doi : 10.1016/j.jet.2018.07.001 . ISSN 0022-0531 .