הצגת המקור של הדף "מכרז הכל משלמים"

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

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

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

מתקבל כי התשלום לקונה ה-<math>i</math> הוא כדלקמן:
*אם קיים <math>j</math> כך ש- <math>b_j>b_i</math>, אזי התשלום הוא <math>-b_i</math>.
*אם הקונה ה-<math>i</math> הגיש את הצעת המחיר הגבוהה ביותר יחד עם עוד <math>m-1</math> קונים, אזי התשלום הוא <math>\frac{v_i}{m}-b_i</math>.

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

==דוגמאות==
'''דוגמה פשוטה''': 

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

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

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

נחפש שיווי משקל סימטרי, בו [[פונקציית התפלגות|פונקציית ההתפלגות המצטברת]] היא רציפה. בפרט, במקרה זה ההסתברות ששני קונים יציעו אותו ערך הוא 0 ולכן ניתן להתעלם ממקרה זה בחישובים. נניח כי הקונים <math>2,...,n</math> משתמשים באסטרטגיה המעורבת המיוצגת על ידי הפונקציה <math>P</math> הבנויה באופן המתואר לעיל, וכי הקונה ה-<math>1</math> מגיש את הצעת המחיר <math>b</math>. אזי התשלום של הקונה ה-<math>1</math> מחושב ע"י:
<center><math>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</math>
</center>
שכן <math>b_1 = b</math>, ושאר החישוב מתייחס לשני המאורעות האפשריים:

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

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

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

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

<div style="text-align: center;">
<math>
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.</math>
</div>

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

במקרה זה, [[שיווי משקל נאש|קבוצת נקודות שיווי המשקל]] של המשחק זהה לזו של משחק מהצורה '''War of Attrition''':{{הערה|זהו סוג נוסף של מכירות פומביות, הדומה מאוד למכרז הכל משלמים, אמנם כאן כולם משלמים את הצעת המחיר הנמוכה ביותר. להרחבה, מומלץ לקרוא על הערך ב[[ויקיפדיה האנגלית|וויקיפדיה האנגלית]]. קישור נמצא ב"ראו גם".}}

<math display="block">\{(0,b_2) | b_2 \geq v_1\} \cup \{(b_1,0) | b_1 \geq v_2\} </math>

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

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

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

*קמפיין בחירות: ההשקעה הכספית של המפלגה ה-i בקמפיין היא למעשה הצעת המחיר <math>x_i</math>. נניח כי רק מפלגה אחת זוכה בבחירות, והיא זו שמשקיעה הכי הרבה כסף בקמפיין. ואכן, על אף שרק מפלגה אחת זוכה בבחירות - כולן משלמות את ההוצאות על הקמפיינים.
*ניתן לחשוב גם על הגרלות הלוטו כעל מכרז הכל משלמים, שכן כל קוני כרטיסי ההגרלה שילמו עבורם, ואמנם לא כולם זוכים.
*המתנה בתור לקניית [[מוצר]] המוגבל בכמותו: לדוגמה, המתנה בתור לקניית כרטיסים להופעה של [[מדונה]]. ההצעה של הקונה היא השעה בה הגיע לתור, כאשר כל הקונים מחכים בתור, בין אם יישארו להם כרטיסים או לא. כאן כל הקונים משלמים בזמנם, אמנם לא כולם זוכים בכרטיס.

== משפט ==
תהי <math>\beta</math> אסטרטגיית [[שיווי משקל נאש|שיווי משקל]] סימטרי, [[פונקציה גזירה|גזירה]], מונוטונית עולה המקיימת  <math>\beta(0)=0</math> במכרז הכל משלמים. אזי{{הערה|המשפט לקוח מהספר "תורת המשחקים" מאת שמואל זמיר, מיכאל משלר ואילון סולן. את הוכחת המשפט ניתן למצוא גם כן בספר. העמודים הרלוונטיים הם 469, 477, 479-480.}}:
<center><math>\beta(v) = F_Y (v)E[Y|Y\leq v]</math>
</center>

באשר:

*במקרה זה, הכוונה באסטרטגיה היא ל[[פונקציה מדידה]] המקבלת ערכים פרטיים ומחזירה הצעות מחיר. בפרט, אם הערך הפרטי הוא <math>0</math>, הצעת המחיר המתאימה תהיה גם כן <math>0</math>.
*ה[[משתנה מקרי|משתנה המקרי]] <math>Y</math> מוגדר להיות המשתנה המקרי המציין את הגבוה ביותר מבין הערכים הפרטיים של הקונים <math>2,...,n</math>, כלומר, <math>Y = max \{v_2,...,v_n\}</math>.
:מנקודת מבטו של קונה <math>1</math>, המשתנה המקרי <math>Y</math> מייצג את הערך הפרטי הגבוה ביותר של יריביו.

*<math>F_Y</math> היא פונקציית ההתפלגות המצטברת של המשתנה המקרי <math>Y</math>.

== ראו גם ==
* [[מונחים בתורת המשחקים]]
* [[מכרז]]
* [[מכרז סגור מחיר ראשון]]
* [[מכרז מחיר שני]]
* [[:en:War of attrition (game)|War of Attrition]]

== לקריאה נוספת ==
*{{צ-ספר|מחבר=שמואל זמיר, [[מיכאל משלר]] ו[[אילון סולן]]|שם=תורת המשחקים|מו"ל=[[הוצאת מאגנס|מאגנס]]|שנת הוצאה=2008|מקום הוצאה=ירושלים|ISBN=9654932946}}

==הערות שוליים==
{{הערות שוליים}}

[[קטגוריה:תכנון מכניזמים]]
[[קטגוריה:מכירה פומבית]]