מכרז Vickrey-Clarke-Groves

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

מכרז Vickrey–Clarke–Groves הוא סוג של מכירה פומבית סגורה המציעה לקונים מספר פריטים וכל קונה מגיש הצעת מחיר שונה לכל פריט. במכירה זו כל פריט מוקצה בצורה האופטימלית החברתית וכל קונה זוכה לכל היותר בפריט אחד. במנגנון זה כל קונה משלם את הנזק שהוא גורם לקונים האחרים ובכך מובטח שהאסטרטגיה הטובה ביותר עבור הקונה היא להציע את המחיר האמיתי שהקונה מעדיף לשלם עבור כל פריט ופריט. מנגנון זה הוא הכללה של מכרז מחיר שני עבור מספר רב של פריטים.

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

תהי M = \{t_1,\ldots,t_m\} קבוצת הפריטים המוצעים למכירה, ותהי N = \{b_1,\ldots,b_n\} קבוצת הקונים במכירה. נגדיר גם את V^M_N כערך הפונקציה החברתית המתקבל במנגנון המכירה עם קבוצת הפריטים M וקבוצת הקונים N לאחר שאלו הגישו את הצעותיהם.

אם הקונה b_i זוכה בפריט t_j אז המחיר שעליו לשלם לפי מנגנון VCG מוגדר להיות V^{M}_{N \setminus \{b_i\}}-V^{M \setminus \{t_j\}}_{N \setminus \{b_i\}}. הביטוי הראשון הוא ערך הפונקציה החברתית שמתקבל כאשר הקונה b_i אינו משתתף במכירה, הביטוי השני הוא ערך הפונקציה החברתית כאשר גם הקונה וגם הפריט t_j אינם משתתפים במכירה. כלומר, הביטוי השני הוא הערך המתקבל מכל שאר המשתתפים במכירה כאשר b_i השתתף במכירה והביטוי הראשון הוא הערך המתקבל מכל שאר המשתתפים במכירה כאשר b_i לא השתתף במכירה. לכן ההפרש ביניהם הוא הנזק שb_i גורם לשאר הקונים.

על סמך ההגדרות הנ"ל, אם הערך האמיתי של הפריט t_j בעיני הקונה b_i הוא A, אז התועלת המתקבלת לקונה b_i במכירה היא A - \left(V^{M}_{N \setminus \{b_i\}}-V^{M \setminus \{t_j\}}_{N \setminus \{b_i\}}\right) (הערך שהקונה מרוויח מהפריט פחות התשלום על הנזק שנגרם לשאר הקונים).

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

נניח שבמכירה מוצעים שני תפוחים וקיימים שלושה קונים. קונה א' רוצה תפוח אחד ומציע עבורו 5 ש"ח. קונה ב' מעוניין גם בתפוח אחד ומוכן לשלם עבורו 2 ש"ח. קונה ג' רוצה שני תפוחים ומוכן לשלם 6 ש"ח עבור שניהם בתנאי שהוא זוכה בשניהם (ולא בתפוח אחד בלבד). תחילה נעריך את תוצאת המכירה כאשר בוחרים בהצעות היקרות ביותר לכל פריט: קונה א' וקונה ב' זוכים כל אחד בתפוח אחד. כעת, כדי לחשב את התשלומים שעליהם לשלם עבור הנזקים שגרמו לקונים האחרים, נחשב את השפעת ההצעה על שאר הקונים. לפי התוצאה כרגע, התועלת של לקוח ב' היא 2 ש"ח. נניח ולקוח א' לא היה משתתף במכרז, לקוח ג' היה זוכה עם תועלת של 6 ש"ח ולכן לקוח א' משלם 6-2=4 ש"ח. בעבור לקוח ב': התועלת של לקוח א' כרגע היא 5 ש"ח והתועלת של לקוח ג' היא 0, נניח ולקוח ב' לא היה משתתף במכרז, לקוח ג' היה זוכר עם תועלת של 6 ש"ח ולכן לקוח ב' משלם 6-5=1 ש"ח. התוצאה הייתה זהה אם לקוח ג' לא היה משתתף ולכן הוא אינו חייב לשלם דבר.

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

נבחר קונה אחד באופן שרירותי b_1 ונתמקד בו. יהי v_i הערך האמיתי שהקונה מציעה לפריט t_i. נניח, בה"כ, שאם b_1 מציע את הערכותיו האמיתיות, מנגנון VCG מקצה לו את פריט t_1. נשים לב תחילה שלהצעותיו של b_1 אין השפעה על ערך התועלת שלו, בהנחה שהוא זוכה באותו פריט, מכיוון שהתועלת של b_1 בלתי תלויה בערכים האחרים.

נניח שb_1 אינו מציע את הערכותיו האמיתיות וזוכה בפריט t_j בזכות הצעותיו המטעות. במקרה שהיה מגיש את הערכותיו האמיתיות התועלת של b_1 היא U_1 = v_1-\left(V^{M}_{N \setminus \{b_1\}}-V^{M \setminus \{t_1\}}_{N \setminus \{b_1\}}\right). במקרה שהציע את הערכותיו המטעות התועלת היא U_2 = v_j-\left(V^{M}_{N \setminus \{b_1\}}-V^{M \setminus \{t_j\}}_{N \setminus \{b_1\}}\right). צריך להוכיח ש U_1 - U_2 \geq 0, כלומר התועלת של הצעת אמת עולה על התועלת של הצעה מטעה.

U_1 - U_2 = v_1 - \left(V^{M}_{N \setminus \{b_1\}} - V^{M \setminus \{t_1\}}_{N \setminus \{b_1\}}\right) - v_j + \left(V^{M}_{N \setminus \{b_1\}}-V^{M \setminus \{t_j\}}_{N \setminus \{b_1\}}\right) = \left[v_1 + V^{M \setminus \{t_1\}}_{N \setminus \{b_1\}}\right] - \left[v_j + V^{M \setminus \{t_j\}}_{N \setminus \{b_1\}}\right]

הביטוי הראשון הוא הערך המקסימלי המתקבל של פונקציית התועלת החברתית כש b_1 זכה בפריט t_1. הביטוי השני הוא הערך המקסימלי של פונקציית התועלת החברתית כש b_1 זכה בפריט t_j. מכיוון שאנחנו מניחים שמנגנון VCG הקצה לb_1 את הפריט t_1 אז הערך של הביטוי הראשון הוא הגדול יותר ולכן מתקבל U_1 - U_2 \geq 0.

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

ישנה הבחנה כללית יותר למנגנון VCG. נתבונן בקבוצה A היא קבוצת התוצאות האפשריות של n קונים המציעים ערכים שונים לכל תוצאה. ניתן לבטא זאת כפונקציה:

v_i : A \longrightarrow R_+

המבטאת לכל קונה i את הערך שנתן לכל תוצאה אפשרית. במכרז זה , כל קונה מציע את הערכותיו שלו ומנגנון VCG בוחר את האפשרות a \in A שממקסמת את  \sum_i v_i(a) וגובה מחיר p_i המוגדר באופן הבא:

p_i = h_i(v_{-i}) - \sum_{j \neq i} v_j(a)

כאשר v_{-i} = (v_1, \dots, v_{i-1}, v_{i+1}, \dots, v_n). כלומר h_i היא פונקציה התלויה רק בהצעות של הקונים האחרים. תנאי זה מספיק להבטיח אמירת אמת כאסטרטגיה שלטת

אפשר לקחת, לדוגמה, h_i(v_{-i}) = 0 אבל אז כל המחירים המתקבלים יהיו שליליים. באופן כללי במכירות אנחנו מעדיפים שהלקוחות ישלמו מאשר שהמכרז ישלם לקונים. הפונקציה:

h_i(v_{-i}) = \max_{b \in A} \sum_{j \neq i} v_j(b)

נקראת Clarke pivot rule. ויש לה שתי תכונות מעניינות:

  • היא מועילה לכל קונה בנפרד. v_i (a) - p_i \geq 0 כל קונה המשתתף במכרז מקבל תועלת חיובית, אף אחד לא חייב להציע הצעה.
  • היא מועילה למנהלי המכרז. p_i \geq 0. המנגנון לא משלם דבר לקונים.