کاربرد LP در نظریه بازی¹

نظریه بازی‌ها شاخه‌ای از علم تصمیم‌گیری است که رفتار افراد، گروه‌ها یا سازمان‌ها را در شرایط رقابتی بررسی می‌کند. در این شرایط، هر بازیکن از میان چندین استراتژی ممکن، یکی را انتخاب می‌کند، بدون اینکه از تصمیم سایر بازیکنان آگاه باشد. نتیجه نهایی به ترکیب استراتژی‌های انتخاب‌شده بستگی دارد و میزان سود یا زیان هر بازیکن را مشخص می‌کند.

این نظریه در زمینه‌های مختلفی مانند رقابت شرکت‌ها، فعالیت‌های سیاسی، مزایده‌ها و مناقصه‌ها کاربرد دارد. یکی از مهم‌ترین انواع آن، بازی‌های دونفره با مجموع صفر² است که در آن سود یک بازیکن دقیقاً برابر با زیان بازیکن دیگر است؛ بنابراین منافع دو طرف کاملاً متضاد بوده و موفقیت یک طرف به معنای شکست طرف مقابل خواهد بود.

انواع بازی

همکاری‌محور / غیرهمکاری‌محور
- همکاری‌محور³: تشکیل ائتلاف، مفهوم هسته، مقدار شاپلی²²
- غیرهمکاری‌محور⁴: تعادل نش.²¹
ساکن / پویا
- ساکن⁵: فرم عادی، یک‌بار
- پویا⁶: فرم گسترده، چندمرحله‌ای
اطلاعات کامل / اطلاعات ناقص
- کامل⁷: همهٔ پرداخت‌ها و انواع شناخته‌شده
- ناقص⁸: انواع خصوصی، بازی‌های بیزی
اطلاعات کامل / اطلاعات نامکمل (دیده شدن حرکات)
- کامل⁷: همهٔ حرکات پیشین معلوم
- نامکمل⁹: برخی حرکات مخفی (مجموعه‌های اطلاعاتی)
قطعی / تصادفی
- قطعی¹⁰: پرداخت ثابت
- تصادفی¹¹: انتقال حالت با احتمالات
افق محدود / افق نامحدود
- محدود¹²: دوره‌های شمارش‌پذیر
- نامحدود (تخفیفی)¹³: بر اساس رابطه زیر تعریف می‌شود

\[\sum_{t=0}^{\infty} \delta^{t} u_i(a_t)\]

تکراری / یک‌بار
- تکراری¹⁴: تکرار بازی مرحله‌ای
- یک‌بار¹⁵: تعامل صرفاً یک‌باره
نظریهٔ تکاملی
- دینامیک تکثیر‌کنندهٔ استراتژی‌ها در جمعیت¹⁶
نظریهٔ حراج
- حراج تک‌جمله‌ای، ترکیبی، چندواحد؛ مکانیزم‌های ویکری²³، انگلیسی، هلندی¹⁷
طراحی مکانیزم / نظریهٔ پیاده‌سازی
- ساخت بازی برای دستیابی به نتایج مطلوب (سازگاری مشوق)¹⁸
نظریهٔ مذاکره
- راه‌حل مذاکرهٔ نش¹⁹
سیگنال‌دادن و پالایش
- بازی‌های اطلاعات نامتقارن²⁴؛ ارسال یا استخراج سیگنال²⁰

مثال (رقابت در سهم بازار)

فرض کنید دو شرکت تنها تولیدکنندگان یک محصول هستند و برای افزایش سهم بازار با یکدیگر رقابت می‌کنند. هر شرکت باید یکی از سه استراتژی زیر را انتخاب کند:

افزایش تبلیغات
ارائه تخفیف عمده
افزایش مدت گارانتی

جدول پرداخت نشان می‌دهد که هر ترکیب از استراتژی‌ها چه میزان تغییر در سهم بازار شرکت A ایجاد می‌کند. این مسئله یک بازی دونفره با مجموع صفر است؛ یعنی هر مقدار افزایش سهم بازار برای شرکت A دقیقاً به همان میزان کاهش سهم بازار شرکت B خواهد بود و برعکس.

هدف شرکت A بیشینه کردن افزایش سهم بازار و هدف شرکت B کمینه کردن آن است. از آنجا که هر شرکت قبل از آگاهی از تصمیم رقیب باید استراتژی خود را انتخاب کند، هر کدام فرض می‌کنند رقیب بهترین تصمیم ممکن را برای خود خواهد گرفت. بنابراین شرکت A برای هر استراتژی، بدترین نتیجه‌ای را که ممکن است در برابر واکنش شرکت B به دست آورد بررسی می‌کند و حداقل سود هر استراتژی را محاسبه می‌کند. این مقادیر حداقل، مبنایی برای تعیین استراتژی بهینه در نظریه بازی‌ها هستند.

	افزایش تبلیغات \(b_1\)	تخفیف عمده \(b_2\)	تمدید گارانتی \(b_3\)
افزایش تبلیغات \(a_1\)	4	3	2
تخفیف عمده \(a_2\)	-1	4	1
تمدید گارانتی \(a_3\)	5	-2	0

استراتژی ناب

اگر برای هر دو بازیکن الزام به انتخاب یک گزینه داشته باشند و صرف‌نظر از تصمیم بازیکن دیگر به همان استراتژی پایبند بمانند، بازی دارای راه‌حل استراتژی ناب است اگر بیشینهٔ کمینه‌های سطرها برابر با کمینهٔ بیشینه‌های ستون‌ها باشد. در این حالت بازیکنان نمی‌توانند با تغییر استراتژی، پرداخت خود را بهبود دهند. چنین بازی‌ای نقطهٔ تعادل دارد. شرط وجود استراتژی ناب به صورت زیر است:

\[\max_i\,\min_j\,x_{ij}\;=\;\min_j\,\max_i\,x_{ij}\]

برای تعیین وجود یا عدم وجود راه‌حل استراتژی ناب در نظریه بازی‌ها، مراحل زیر را اجرا می‌کنیم:

کمترین مقدار هر سطر برای بازیکن A محاسبه می‌شود.
بزرگ‌ترین مقدار از میان این کمینه‌ها انتخاب می‌شود (حداکثر کمینه‌های سطرها).
بیشترین مقدار هر ستون برای بازیکن B محاسبه می‌شود.
کوچک‌ترین مقدار از میان این بیشینه‌ها انتخاب می‌شود (حداقل بیشینه‌های ستون‌ها).
زمانی که بیشینه کمینه‌های سطرها برابر با کمینه بیشینه‌های ستون‌ها باشد، بازی دارای راه‌حل استراتژی ناب است؛ این مقدار ارزش بازی را نشان می‌دهد و استراتژی‌های به دست آمده در مراحل ۲ و ۴، استراتژی‌های بهینه بازیکنان A و B هستند.

استراتژی ترکیبی

با استراتژی ترکیبی هر بازیکن استراتژی خود را بر اساس توزیع احتمالی انتخاب می‌کند. در مثال سهم بازار هر شرکت ابتدا توزیع احتمالی بهینه‌ای برای انتخاب بین افزایش تبلیغات، ارائه تخفیف‌های عمده یا تمدید گارانتی تعیین می‌کند. سپس هنگام اجرای بازی هر شرکت از توزیع احتمالی خود برای انتخاب تصادفی یکی از سه استراتژی استفاده می‌کند.

فرض کنید جدول فوق بصورت زیر تغییر کند. در این صورت اگر هر دو شرکت A و شرکت B استراتژی تمدید گارانتی را انتخاب کنند، پرداختی به شرکت A اکنون ۵٪ افزایش سهم بازار است، در حالی که قبلاً ۰٪ بود. حداقل‌های سطر تغییر نمی‌کنند، اما حداکثرهای ستون تغییر می‌یابند.

	افزایش تبلیغات \(b_1\)	تخفیف عمده \(b_2\)	تمدید گارانتی \(b_3\)
افزایش تبلیغات \(a_1\)	4	3	2
تخفیف عمده \(a_2\)	-1	4	1
تمدید گارانتی \(a_3\)	5	-2	5

متغیرهای مساله بصورت زیر تعریف می‌شود:

\(PA_1\): احتمال اینکه شرکت A استراتژی \(a_1\) را انتخاب کند.
\(PA_2\): احتمال اینکه شرکت A استراتژی \(a_2\) را انتخاب کند.
\(PA_3\): احتمال اینکه شرکت A استراتژی \(a_3\) را انتخاب کند.
\(PB_1\): احتمال اینکه شرکت B استراتژی \(b_1\) را انتخاب کند.
\(PB_2\): احتمال اینکه شرکت B استراتژی \(b_2\) را انتخاب کند.
\(PB_3\): احتمال اینکه شرکت B استراتژی \(b_3\) را انتخاب کند.
\(GA\): سود شرکت A
\(LB\): ضرر شرکت B

سهم بازار برای شرکت A

استراتژی شرکت B	سود مورد انتظار شرکت A
\(b_1\)	\(4PA_1 - 1PA_2 + 5PA_3\)
\(b_2\)	\(3PA_1 + 4PA_2 - 2PA_3\)
\(b_3\)	\(2PA_1 + 1PA_2 + 5PA_3\)

مساله را می‌توان بصورت زیر مدل کرد:

\[\begin{align} Maximize\ GA \\ \\ Subject\ to \\ \\ 4PA_1 - 1PA_2 + 5PA_3 & \ge GA\\ 3PA_1 + 4PA_2 - 2PA_3 & \ge GA\\ 2PA_1 + 1PA_2 + 5PA_3 & \ge GA\\ PA_1 + PA_2 + PA_3 & = 1\\ PA_1, PA_2, PA_3 & \ge 0 \end{align}\]

result = linprog(
    [0, 0, 0, -1],
    [
        [-4, 1, -5, 1],
        [-3, -4, 2, 1],
        [-2, -1, -5, 1],
    ],
    [0, 0, 0],
    [
        [1, 1, 1, 0]
    ],
    [1],
)
print(result.x, -result.fun)
# [0.875, 0, 0.125, 2.375] 2.375

سهم بازار برای شرکت B

استراتژی شرکت A	زیان مورد انتظار شرکت B
\(a_1\)	\(4PB_1 + 3PB_2 + 2PB_3\)
\(a_2\)	\(-1PB_1 + 4PB_2 + 1PB_3\)
\(a_3\)	\(5PB_1 - 2PB_2 + 5PB_3\)

\[\begin{align} Minimize\ LB \\ \\ Subject\ to \\ \\ 4PB_1 + 3PB_2 + 2PB_3 &\le LB\\ -1PB_1 + 4PB_2 + 1PB_3 &\le LB\\ 5PB_1 - 2PB_2 + 5PB_3 &\le LB\\ PB_1 + PB_2 + PB_3 & = 1\\ PB_1, PB_2, PB_3 &\ge 0 \end{align}\]

result = linprog(
    [0, 0, 0, 1],
    [
        [4, 3, 2, -1],
        [-1, 4, 1, -1],
        [5, -2, 5, -1],
    ],
    [0, 0, 0],
    [
        [1, 1, 1, 0]
    ],
    [1],
)
print(result.x, result.fun)
# [0, 0.375, 0.625, 2.375] 2.375

Game Theory ↩
Zero-sum Game ↩
Cooperative ↩
Non‑cooperative ↩
Static ↩
Dynamic ↩
Complete information ↩↩
Incomplete information ↩
Imperfect (partial) information ↩
Deterministic ↩
Stochastic ↩
Finite horizon ↩
Infinite horizon (discounted) ↩
Repeated ↩
One‑shot ↩
Evolutionary theory ↩
Auction theory ↩
Mechanism design / Implementation theory ↩
Nash Bargaining theory ↩
Signaling and screening ↩
Nash equilibrium ↩
Shapley Value ↩
Vickrey auction (second-price sealed‑bid auction) ↩
Asymmetric games ↩

کاربرد LP در نظریه بازی1