מכרז קומבינטורי
מכרז קומבינטורי הוא מושג בתורת המשחקים המציין מכירה פומבית או מכרז שהמשתתפים בו מציעים הצעות מחיר לקבוצה של מוצרים במקום למוצר בודד. מכרז קומבינטורי הוא מודל לבעיות כלכליות לא מעטות בעולם הממשי, והוא מציג בעיות הן בתחום הכלכלי והן בתחום החישובי.
הגדרה פורמלית
מכרז קומבינטורי מוגדר כבעיה הבאה: בהינתן אוסף של משאבים (סחורות, שירותים וכיוצא בזה), ואוסף שחקנים כך שלכל שחקן ישנה תועלת מסוימת עבור כל תת-קבוצה של המשאבים שיקבל, כיצד ניתן לחלק את המשאבים בין השחקנים כך שהתועלת החברתית תהיה מקסימלית (בדרך כלל, התועלת החברתית היא סך התועלות של כל שחקן מקבוצת המשאבים שקיבל, או סך הכסף שעורך המכרז יזכה בתום המכרז). לפי הגדרה זו, מכירה פומבית רגילה היא מקרה פרטי של מכרז קומבינטורי, כאשר לכל שחקן יש תועלת עבור כל משאב, והתועלת של השחקן מקבוצת משאבים היא פשוט סכום התועלות שלו מכל המשאבים בקבוצה.
בעיות הנובעות ממכרזים קומבינטוריים
- בעיה חישובית: בהינתן ההעדפות של השחקנים, חישוב הקצאת המשאבים האופטימלית הוא בעיה NP קשה, כלומר סביר להניח שלא ימצא לה פתרון בזמן ריצה פולינומי.
- בעיית תקשורת: לכל שחקן ישנה תועלת שונה מכל תת-קבוצה של המשאבים, ומכאן כי פונקציית התועלת של כל שחקן היא בגודל מעריכי; מכאן שישנו קושי בעצם הצגת התועלות של כל שחקן.
- בעיות אסטרטגיות: מכיוון שמכרז קומבינטורי הוא בעיה שמספר המשתנים שבה רב כל-כך, יצירת מכרז קומבינטורי כך שהאסטרטגיה של כל שחקן תהיה לחשוף את התועלת האמיתית שלו היא בעיה קשה מבחינה חישובית.
היסטוריה של המחקר
המושג של מכרז קומבינטורי הוגדר לראשונה על ידי רסנטי, סמית ובולפין בשנת 1982.[1] במאמר זה הוגדר המושג של מכרז קומבינטורי בהקשר של הקצאת זמני המראה ונחיתה בנמלי תעופה (ראו להלן) ובו הוצגו לראשונה אספקטים רבים של מכרזים קומבינטוריים, ובהם המודל המתמטי של מכרז קומבינטורי, הקשר בין מכרז קומבינטורי לבעיית תת-קבוצות זרות, הקושי החישובי בבעיה, השימוש בטכניקות של כלכלה ניסוית במכרזים קומבינטוריים ושיקולים אסטרטגיים. המחקר בנושא החל להתפתח באופן משמעותי יותר בתחילת שנות ה-2000, עם התפתחות השימושים המעשיים בעיקר בהקצאת תדרים סלולריים (ראו להלן). כיום ישנו גוף מחקר לא קטן בנושא, הן במציאת חסמים על הבעיות השונות והן בהצעת פתרונות.
יישומים מעשים
הקצאת תדרים סלולריים
הדוגמה הבולטת ביותר למכרז קומיבנטורי, שהיא אף הדוגמה שהביאה להרחבת ההתעניינות בתחום, היא הקצאת תדרים. ברוב המקרים מדובר בהקצאת רישיון שימוש בתחום תדרים של הספקטרום האלקטרומגנטי באזור גאוגרפי מסוים, בדרך כלל למפעילים סלולריים. במקרים אלו התועלת של המפעילים הסלולריים בקבוצה של רישיונות היא שונה מאשר סכום התועלות מכל רישיון בנפרד; למשל, למפעילים רבים אין טעם לקנות רישיונות כלל אם לא יצליחו להשיג רישיונות על פני מרחב גאוגרפי רציף גדול. הקצאת הרישיונות הסלולרים בשנות ה-2000 התנהלה כמכרזים קומבינטוריים מתוכננים במדינות שונות בעולם (כדוגמת ארצות הברית, בריטניה, אוסטרליה וניו זילנד), חלק מהמכרזים הללו נכשלו וחלקם הצליחו מעל למשוער[2]
דוגמאות נוספות
- תחבורה: מכרז קומבינטורי בו עורך המכרז הוא חברה המעוניינת לקנות שירותי תובלה עבור מספר רב של נתיבים מחברות תובלה שונות (כגון חברות הובלה יבשתית או ספנות). עובר חברות התובלה, המחיר שהן יציעו עבור קבוצת נתיבים יכול להיות שונה מסכום המחירים אותם יציעו עבור כל נתיב בנפרד, שכן תובלה של קבוצת נתיבים יכולה להוזיל את העלויות.
- רשתות תקשורת: בדומה לדוגמת התעבורה, קניית שירותי תקשורת מחשבים היא גם מכרז קומבינטורי בין ספקי הרשת השונים.
- הקצאת זמני המראה ונחיתה בנמלי תעופה: בדוגמה זו עורך המכרז הוא שדה התעופה המקצה זמני המראה ונחיתה לחברות התעופה השונות. לכל חברת תעופה ישנה עדיפות לקבוצת זמנים - למשל, זמן נחיתה והמראה עבור אותו המטוס, כך שהמטוס ישאר בשדה התעופה זמן מועט ככל האפשר - השונה מהתועלת עבור כל זמן בנפרד.
ראו גם
לקריאה נוספת
- טים הרטפורד, הכלכלן הסמוי, כנרת זמורה ביתן, 2006, פרק 7; הסבר על המושגים מנקודת ראות כלכלית ותיאור המכרזים הקומבינטוריים למכירת תדרים סלולריים.
- Cramton, P., Shoham, Y., Steinberg, R., Combinatorial Auctions, MIT Press, 2006. מסת"ב 0-262-03342-9
- de Vries, S., and Vohra, R., Combinatorial auctions: A survey. INFORMS Journal on Computing, )15(3)(2003 - סקר ספרות מקיף אך מעט מיושן.
- Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V ., Algorithmic Game Theory. Cambridge University Press, 2007. עותק מקוון. בפרט פרק 11, המתייחס באופן מקיף לנושא מנקודת ראות חישובית
- Rothkopf, M., Pekec, A., and Harstad, R., Computationally manageable combinatorial auctions. Management Science, 44(8)(1998), 1131-1147.
- Shoham, Y., Leyton-Brown, K. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, Cambridge University Press, 2009. מסת"ב 978-0-521-89943-7. עותק מקוון