מכרז הכל משלמים

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

בתורת המשחקים, מכרז הכל משלמים (all-pay auction) הינו סוג של מכירה פומבית בה מוצע למכירה חפץ מסוים, וכל קונה המשתתף במכרז מגיש הצעת מחיר לקנייתו. זהו מכרז סגור - הצעות המחיר מוגשות במעטפות סגורות, כלומר אין הקונים יודעים על הצעות המחיר האחד של השני. הזוכה במכירה הוא מגיש הצעת המחיר הגבוהה ביותר. במנגנון זה, כל קונה משלם את הצעת המחיר שהגיש, בין אם זכה בחפץ ובין אם לא. בכך נבדל סוג זה של מכירות פומביות מאלו מסוג מכרז מחיר ראשון, בהן רק הזוכה בחפץ משלם את גובה הצעתו. באופן דומה, מכירות מסוג זה נבדלות ממכירות פומביות מסוג מכרז מחיר שני, שכן בהן יתרה על כך שרק הזוכה בחפץ משלם - הוא משלם את גובה הצעת המחיר השנייה בגובהה.

סוג זה של מכרז מהווה מודל מתאים לתחרויות בהן מתקיים כי גם קונה שאינו זוכה משלם את הצעת המחיר שהגיש. לדוגמה, במירוץ חימוש בין מדינות, המדינה הזוכה במירוץ היא זו שהגיעה לכמות החימוש הגדולה ביותר, ואמנם כל המדינות "משלמות" את גודל השקעתן.

הגדרה פורמלית[עריכת קוד מקור | עריכה]

תהי N = \{1,...,n\} קבוצת הקונים במכירה. הקונה ה-i מגיש הצעת מחיר b_i אי-שלילית, במעטפה סגורה. הערך הפרטי של הקונה ה-i לחפץ הנמכר מסומן ב- v_i. כל הקונים משלמים את הצעת המחיר שהגישו, ברם, הזוכה במכירה הוא מגיש ההצעה הגבוהה ביותר.

מתקבל כי התשלום לקונה ה-i הינו כדלקמן:

  • אם קיים j כך ש- b_j>b_i, אזי התשלום הוא -b_i.
  • אם הקונה ה-i הגיש את הצעת המחיר הגבוהה ביותר יחד עם עוד m-1 קונים, אזי התשלום הוא \frac{v_i}{m}-b_i.
משמעות החלוקה ב-m הינה שהקונה ה-i למעשה חולק את הזכייה יחד עם עוד m-1 קונים, ובסה"כ יש m זוכים. בהתאם לכך, התשלום שלו מתייחס לערך הפרטי לאחר חלוקה במספר הזוכים הכולל. בפרט, כאשר הקונה ה-i הוא הזוכה היחיד, כלומר הוא חולק את הרווח שלו עם 1-1=0 קונים אחרים (m=1), מתקבל כי התשלום שלו הוא \frac{v_i}{1}-b_i=v_i-b_i, בהתאם למקרה הר"מ.
  • אם לכל j \neq i מתקיים b_j<b_i, אזי התשלום הוא v_i-b_i.

דוגמאות[עריכת קוד מקור | עריכה]

דוגמה פשוטה:

מתבצעת מכירה פומבית על חפץ מסוים בין n קונים, כאשר ייתכן רק זוכה אחד. לכל הקונים אותו ערך פרטי לחפץ, השווה 100. כל קונה יודע את הפרטי של החפץ עבורו. ברור כי אף קונה לא יציע הצעת מחיר הגדולה מ-100, שכן זהו גם הערך הפרטי של החפץ עבור כל קונה, ומכאן שבעיני כל קונה החפץ לא שווה יותר מ-100. אם כן, הצעת המחיר שמגיש כל קונה היא ערך כלשהו x הלקוח מהתחום [0,100].

הזוכה במכרז הוא מגיש ההצעה הגבוהה ביותר. נסמנה ב-b_{winner}. ידוע לנו כי לכל קונה, ובפרט של הזוכה, הערך הפרטי של החפץ עבורו הוא 100. אזי נקבל כי התשלום לזוכה הוא 100-b_{winner}, וכי התשלום לכל קונה אחר j שהגיש את הצעת המחיר b_j הוא -b_j.

ביחס למשחק זה, אסטרטגיה מעורבת של שחקן היא פונקציית הסתברות על הצעות המחיר האפשריות - כלל הערכים בין 0 ל-100. נייצג אסטרטגיה מעורבת על ידי פונקציית ההתפלגות המצטברת P שלה, כלומר, P(x) הוא ההסתברות שקונה יתן הצעת מחיר הקטנה מ-x או שווה לו. בפרט, P(0) = 0.

נחפש שיווי משקל סימטרי, בו פונקציית ההתפלגות המצטברת היא רציפה. בפרט, במקרה זה ההסתברות ששני קונים יציעו אותו ערך הוא 0 ולכן ניתן להתעלם ממקרה זה בחישובים. נניח כי הקונים 2,...,n משתמשים באסטרטגיה המעורבת המיוצגת על ידי הפונקציה P הבנויה באופן המתואר לעיל, וכי הקונה ה-1 מגיש את הצעת המחיר b. אזי התשלום של הקונה ה-1 מחושב ע"י:

u_1 (b_1,b_2,...,b_n) = u_1 (b,b_2,...,b_n) = P(b)^{n-1}(100-b)+(1-P(b)^{n-1})(-b) = 100P(b)^{n-1}-b

שכן b_1 = b, ושאר החישוב מתייחס לשני המאורעות האפשריים:

  • הקונה ה-1 הוא הזוכה במכירה: במקרה זה, התשלום לקונה ה-1 הוא 100-b, והסיכוי להתרחשות המאורע הוא P(b)^{n-1} מכיוון שאנו דורשים שכל שאר הצעות המחיר יהיו קטנות מהצעת המחיר של הקונה ה-1. כל הצעות המחיר הן בלתי תלויות (מעטפות סגורות), והסיכוי עבור כל קונה שיגיש הצעת מחיר הקטנה מ-b היא P(b).
  • הקונה ה-1 אינו הזוכה במכירה: במקרה זה, התשלום לקונה ה-1 הוא -b, והסיכוי להתרחשות המאורע הוא 1-P(b)^{n-1} שכן מאורע זה הוא המשלים למאורע הנ"ל.

בכדי שהקונה ה-1 יוכל לבחור באקראי, נדרוש כי התשלום הינו קבוע לכל x, כלומר 100P(x)^{n-1}-x = c. נכונות טענה זו נובעת מעקרון האדישות. נציב את העובדה ש- P(0)=0, ונקבל c=0. לכן בסה"כ מתקבל כי האסטרטגיה המעורבת בה משתמשים הקונים 2,...,n מיוצגת ע"י:

P(x) = {(\frac{x}{100})}^{\frac{1}{n-1}}

מכרז הכל משלמים, מחיר שני עם שני קונים:

פונקציית התשלום של הקונה ה-i נתונה על ידי (i=1,2):


u_i (b_1,b_2) = \left\{\begin{matrix}
-b_i &\; b_i<b_j \\
v_i-b_j &\; b_i>b_j
\end{matrix}\right.

ובנוסף, u_1 (b,b) = v_1-b , u_2(b,b) = -b. משמעות הדבר, היא שלקונה ה-1 יש עדיפות על קונה 2 במקרה ששניהם מגישים את אותה הצעת מחיר.

במקרה זה, קבוצת נקודות שיווי המשקל של המשחק זהה לזו של משחק מהצורה War of Attrition:‏[1]

\{(0,b_2) | b_2 \geq v_1\} \cup \{(b_1,0) | b_1 \geq v_2\}

הזוג (b,b) לא מהווה נקודת שיווי משקל נאש לאף ערך של b, מכיוון שהקונה מס' 2 יכול להעלות את התשלום שלו על ידי העלאת הצעת המחיר שלו במקצת או על ידי הפחתתה ל-0.

דוגמאות מחיי היום-יום:

למכרז הכל משלמים ביטויים רבים בעולם הספורט, בפוליטיקה, במחקר ופיתוח ועוד.

  • קמפיין בחירות: ההשקעה הכספית של המפלגה ה-i בקמפיין הינה למעשה הצעת המחיר x_i. נניח כי רק מפלגה אחת זוכה בבחירות, והיא זו שמשקיעה הכי הרבה כסף בקמפיין. ואכן, על אף שרק מפלגה אחת זוכה בבחירות - כולן משלמות את ההוצאות על הקמפיינים.
  • ניתן לחשוב גם על הגרלות הלוטו כעל מכרז הכל משלמים, שכן כל קוני כרטיסי ההגרלה שילמו עבורם, ואמנם לא כולם זוכים.
  • המתנה בתור לקניית מוצר המוגבל בכמותו: לדוגמה, המתנה בתור לקניית כרטיסים להופעה של מדונה. ההצעה של הקונה היא השעה בה הגיע לתור, כאשר כל הקונים מחכים בתור, בין אם ישארו להם כרטיסים או לא. כאן כל הקונים משלמים בזמנם, אמנם לא כולם זוכים בכרטיס.

משפט[עריכת קוד מקור | עריכה]

‏‏‏‏ תהי \beta אסטרטגיית שיווי משקל סימטרי, גזירה, מונוטונית עולה המקיימת \beta(0)=0 במכרז הכל משלמים. אזי[2]:

\beta(v) = F_Y (v)E[Y|Y\leq v]

באשר:

  • במקרה זה, הכוונה באסטרטגיה היא לפונקציה מדידה המקבלת ערכים פרטיים ומחזירה הצעות מחיר. בפרט, אם הערך הפרטי הוא 0, הצעת המחיר המתאימה תהיה גם כן 0.
  • המשתנה המקרי Y מוגדר להיות המשתנה המקרי המציין את הגבוה ביותר מבין הערכים הפרטיים של הקונים 2,...,n, כלומר, Y = max \{v_2,...,v_n\}.
מנקודת מבטו של קונה 1, המשתנה המקרי Y מייצג את הערך הפרטי הגבוה ביותר של יריביו.
  • F_Y היא פונקציית ההתפלגות המצטברת של המשתנה המקרי Y.

ראו גם[עריכת קוד מקור | עריכה]

לקריאה נוספת[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ זהו סוג נוסף של מכירות פומביות, הדומה מאוד למכרז הכל משלמים, אמנם כאן כולם משלמים את הצעת המחיר הנמוכה ביותר. להרחבה, מומלץ לקרוא על הערך בוויקיפדיה האנגלית. קישור נמצא ב"ראו גם".
  2. ^ המשפט לקוח מהספר "תורת המשחקים" מאת שמואל זמיר, מיכאל משלר ואילון סולן. את הוכחת המשפט ניתן למצוא גם כן בספר. העמודים הרלוונטיים הם 469, 477, 479-480.