אפשרות להארכה חריגה בתרגיל בית 3 תמורת קנס בנקודות | |
| סטודנטים/ות יקרים/ות, חלקכם/ן פנו אלינו בבקשה לדחות את מועד ההגשה של תרגיל 3 באופן גורף. לצערנו, אופציה זו אינה אפשרית, שכן נהלי הטכניון אוסרים על קביעת הגשות בתקופת המבחנים (מספיק שסטודנט/ית אחד/ת יגישו בדיעבד תלונה לגורמי המנהלה, והחוק עשוי להיות לצידם). שקלנו את האפשרות להגדיל את מכסת 12 ימי האיחור המותרים, אך הדבר לא יהיה הוגן כלפי סטודנטים/ות שהחליטו "לחסוך" בימי הדחייה בתרגילים קודמים לטובת התרגיל האחרון. הארכות פרטניות חריגות אושרו בעבר רק לאור מילואים או נסיבות אישיות חריגות מאוד, או, לחילופין, בתמורה לקנס משמעותי בציון. נציין גם שתרגיל בית 3 שפורסם היה קצר משמעותית מהתכנון המקורי, וניתן לצבור בו 110 נקודות. למען שמירת ההגינות כלפי הסטודנטים/ות שהמקרים שלהם/ן מתוארים בפסקה הקודמת, הוחלט על המדיניות הבאה: - בהתאם לתכנון מהסילבוס שעודכן בעקבות המצב הביטחוני באמצע הסמסטר, מותר לנצל ללא קנס עד 12 ימי איחור מצטברים במהלך הסמסטר. - יום איחור חריג (ביחס ל-12 הימים המותרים) יחיד בתרגיל בית 3 יגרור קנס של 8 נקודות לציון תרגיל 3. - איחור של 2-4 ימים חריגים בתרגיל 3 יגרור קנס של 15 נקודות לציון תרגיל 3. - איחור חריג ארוך יותר יאושר רק באופן פרטני ובתמורה לקנס נוסף בציון. - לעומת 12 ימי האיחור הקלנדריים המצטברים המותרים בסמסטר ללא קנס, ומצד שני - בדומה למדיניות בהגשת דו"ח האמצע, ימי שישי ושבת נספרים כיום אחד בחישוב הקנס על ימי איחור חריגים. - נא להודיע למתרגל בדוא"ל על הכוונה להשתמש באפשרות להגיש את תרגיל 3 באיחור חריג לפני תום תקופת 12 ימי האיחור המצטברים המותרים שלכם/ן. למען הסר ספק: סטודנטים/ות שומרי/ות שבת, או כאלה שאינם יכולים לעבוד ביום ספציפי מסיבות מיוחדות (כמו מילואים), יכולים/ות לבקש להתעלם מימים אילו בספירת 12 ימי האיחור המצטברים שלהם/ן (בדומה לסיבות אובייקטיביות אחרות שנועדו להבטיח שוויון הזדמנויות). בהצלחה! |
| עדכון אחרון ב- 1/7/2021, 19:12:29 Last updated on 1/7/2021, 19:12:29 Последняя модификация 1/7/2021, 19:12:29 تمت الحتلنة الأخيرة ب- 1/7/2021, 19:12:29 |
Last Tutorial Summary + Invitation to an Exciting Conference | |
| Dear students, Last Monday we finished solving Pr. 14.2. We considered the generalized second-price auction (from Pr. 3.1, HW1) in a slightly more general setting than the problem required, and showed that while the PoA of a PNE in the induced payoff-maximization game can be 0, limiting each bid by the valuation of the corresponding bidder yields PoA for CCE of at least 1/4 (as the resultant game is (0.5,1)-smooth w.r.t. a certain optimal outcome). Moreover, we solved Ex. 13.3 (an equivalent definition for CE). Please note that my proof on the whiteboard included a small typo in the explanation for the first direction - I wrote s_i':=s_{i_0}, while I should have written s_i':=delta(s_{i_0}). Furthermore, we saw the statement of Brouwer's fixed-point theorem (which is proved using Sperner's lemma, and it implies the existence of a MNE in every finite game) and showed that none of its requirements can be dropped (Ex. 20.3). We gave up on solving Pr 17.1 that was initially planned for the previous tutorial. The course staff hope that you enjoyed the course and that you will be interested in learning more game theory. If you do - you might be interested in registering to the Stony Brook International Conference on Game Theory. It will be held online on July 5-8. Registration is free of charge, but you must register by Friday, July 2 (according to another source - by Thursday, July 1). Here is a link to the conference website: http://www.gtcenter.org/?page=Conference.html Arguably, two of the most exciting parts of the conference will be the lectures of the recent winners of the Nobel Prize in economics - Robert Wilson (05.07 20:00-21:00) and Paul Milgrom (08.07 20:00-21:00). Please note that the conference is on game theory in general (not just AGT). Good luck in the exams and the final project! |
| עדכון אחרון ב- 1/7/2021, 02:52:00 Last updated on 1/7/2021, 02:52:00 Последняя модификация 1/7/2021, 02:52:00 تمت الحتلنة الأخيرة ب- 1/7/2021, 02:52:00 |
Sperner's Lemma in the New York Times | |
| As mentioned in the last lecture: https://www.nytimes.com/2014/04/29/science/to-divide-the-rent-start-with-a-triangle.html |
| פורסם ב- 29/6/2021, 19:27:33 Created on 29/6/2021, 19:27:33 Создано 29/6/2021, 19:27:33 تم النشر ب- 29/6/2021, 19:27:33 |
Clarifications and Hints for Pr. 17.2 | |
| In part (a), the requirement to prove that the minimal number of mistakes is "precisely" something means that you should not only prove that any deterministic algorithm can make at least such a number of mistakes, but also that there exists a deterministic algorithm making not more than this number of mistakes. In part (c), following Roughgarden's hint that suggests an algorithm, it can be a good idea to recursively express the number of potentially omniscient experts in each iteration of this algorithm in terms of the probabilities for a mistake in different iterations, and to use the fact that at least one expert is, indeed, omniscient. To bound the sum of the probabilities for a mistake in all the iterations (which is the expectation of the number of mistakes), the inequality from Figure 17.1 (which is a very general tool far beyond AGT) may be helpful. |
| עדכון אחרון ב- 24/6/2021, 01:44:23 Last updated on 24/6/2021, 01:44:23 Последняя модификация 24/6/2021, 01:44:23 تمت الحتلنة الأخيرة ب- 24/6/2021, 01:44:23 |
The Tutorial Tomorrow | |
| Dear students, Tomorrow we shall solve Pr. 14.2 and 17.1. The solutions will not be uploaded to the course site, as these problems are possible candidates for HW in the next semesters. We shall not go over the solution of Ex. 13.6 that appears in the slides from the previous week, but it is recommended to read them on your own as a complement to Ex. 13.5 from HW3 (though it is probably more fun to do the computations from slides 16-17 yourself rather than reading them). See you tomorrow! |
| עדכון אחרון ב- 20/6/2021, 23:06:58 Last updated on 20/6/2021, 23:06:58 Последняя модификация 20/6/2021, 23:06:58 تمت الحتلنة الأخيرة ب- 20/6/2021, 23:06:58 |
HW 3 Is Published | |
| The due date is 01.07.2021 (23:59). Good luck! |
| עדכון אחרון ב- 15/6/2021, 19:55:43 Last updated on 15/6/2021, 19:55:43 Последняя модификация 15/6/2021, 19:55:43 تمت الحتلنة الأخيرة ب- 15/6/2021, 19:55:43 |
The Tutorial Tomorrow | |
| Dear students, I am glad to announce that we are going back to hybrid tutorials (Taub 7 + Zoom). Tomorrow we shall finish Chapter 8 from the course book and solve Ex. 13.2, 13.6 and Pr. 14.2. See you tomorrow! |
| עדכון אחרון ב- 13/6/2021, 22:53:19 Last updated on 13/6/2021, 22:53:19 Последняя модификация 13/6/2021, 22:53:19 تمت الحتلنة الأخيرة ب- 13/6/2021, 22:53:19 |
Reminder - A Clarification for Exercise 2.3 (Already Sent Before) | |
| You are not allowed to assume that all the bids are distinct. You should specify a tiebreak rule for equal bids (considering one specific rule for which the auction is DSIC is enough). |
| פורסם ב- 6/6/2021, 23:54:06 Created on 6/6/2021, 23:54:06 Создано 6/6/2021, 23:54:06 تم النشر ب- 6/6/2021, 23:54:06 |
Retaliatory Bids in SAAs | |
| Dear students, Unfortunately, during the last tutorial, I misheard a question of a student who asked whether concealing the bidders' identities in SAAs may prevent retaliatory bids, and I answered to a totally unrelated question. Indeed, anonymous bidding limits the ability to make retaliatory bids (though in some cases, e.g., the identity of a bidder interested in a specific license might be guessed). However, anonymous bidding might introduce other problems, such as hurting small firms. For comparing slightly different spectrum auction formats used in practice, you can read, e.g., the following paper: Bajari, Patrick, and Jungwon Yeo. "Auction design and tacit collusion in FCC spectrum auctions." Information Economics and Policy 21, no. 2 (2009): 90-100. |
| עדכון אחרון ב- 3/6/2021, 17:56:48 Last updated on 3/6/2021, 17:56:48 Последняя модификация 3/6/2021, 17:56:48 تمت الحتلنة الأخيرة ب- 3/6/2021, 17:56:48 |
Three Lecture Hours Next Week | |
| Dear students, Next Monday there will be three consecutive lecture hours - there will be no tutorial. |
| עדכון אחרון ב- 3/6/2021, 01:18:16 Last updated on 3/6/2021, 01:18:16 Последняя модификация 3/6/2021, 01:18:16 تمت الحتلنة الأخيرة ب- 3/6/2021, 01:18:16 |
Bayesian Persuasion - An Important Point | |
| Dear students, I would like to highlight a point that probably wasn't highlighted enough during the tutorials (even though it follows immediately from the theorem in slide 28): In general, an optimal signaling scheme may have a support of an arbitrary size (sometimes - the support is even continuum-sized). Nevertheless, there always exists an optimal signaling scheme with support size at most k (the number of states) - a corollary of Caratheodory's theorem (which is beyond the course scope). The set of all the optimal signaling schemes exactly corresponds to all the possibilities to represent (p, v(p)) as a convex combination of some points on the graph of u (using the notations of slide 28). In particular, for k=2 states, there might exist an optimal signaling scheme not captured graphically by a segment with its endpoints on the graph of u. Rather - it might be captured, e.g., by a triangle containing (p, v(p)) with vertices on the graph of u. Note, however, that such a triangle must be degenerate - its vertices must be collinear. Anyway (hint!), in HW2 Q.1(c) you only have one optimal signaling scheme, and its support size is 2. |
| עדכון אחרון ב- 2/6/2021, 17:05:43 Last updated on 2/6/2021, 17:05:43 Последняя модификация 2/6/2021, 17:05:43 تمت الحتلنة الأخيرة ب- 2/6/2021, 17:05:43 |
The Tutorial Tomorrow Will Be Held via Zoom Only | |
| (following an update in the faculty guidelines from today) |
| פורסם ב- 30/5/2021, 14:29:05 Created on 30/5/2021, 14:29:05 Создано 30/5/2021, 14:29:05 تم النشر ب- 30/5/2021, 14:29:05 |
The Previous and The Next Tutorial | |
| Dear students, Yesterday we finished talking about Bayesian persuasion, focusing on the concavification and the straightforward policy approaches. What is worth mentioning, but I didn't have time for it - is that in the optimal straightforward signaling scheme in the example we solved, Receiver is *indifferent* between hiring and not hiring - that is, her expected utility for hiring equals her expected utility for not hiring (that equals zero); hiring occurs as ties are broken in Sender's favour. It is unsurprising, as if Receiver's expected utility upon hiring was strictly positive - Sender could have increased the probability of recommending hiring when the student is bad, increasing, therefore, Sender's expected utility. The next tutorial will be in a hybrid format (Taub 7 + Zoom). We shall go over chapter 8 of Roughgarden's book. Have a nice weekend! |
| עדכון אחרון ב- 27/5/2021, 15:50:13 Last updated on 27/5/2021, 15:50:13 Последняя модификация 27/5/2021, 15:50:13 تمت الحتلنة الأخيرة ب- 27/5/2021, 15:50:13 |
Final Project - Mid-Report and Detailed Guidelines | |
| Dear students, We published detailed guidelines for the final project and a template for the project (both the tex file and the compiled pdf file). You have to submit a mid-report to Inbal by email until June 13 (23:59) - a week later compared to the plan from the syllabus. A later submission will result in a grade penalty, as explained in the guidelines (you cannot use the "late day bank" intended for HW). Good luck! |
| עדכון אחרון ב- 26/5/2021, 17:39:49 Last updated on 26/5/2021, 17:39:49 Последняя модификация 26/5/2021, 17:39:49 تمت الحتلنة الأخيرة ب- 26/5/2021, 17:39:49 |
The Screen Recordings from Yesterday's Lessons Are Restored | |
| We thank Sagi for pointing out how to resolve the issue |
| עדכון אחרון ב- 25/5/2021, 13:58:33 Last updated on 25/5/2021, 13:58:33 Последняя модификация 25/5/2021, 13:58:33 تمت الحتلنة الأخيرة ب- 25/5/2021, 13:58:33 |
Research Papers on Bayesian Persuasion | |
| Following students' questions - there is no need to use research papers to solve HW2. However, if you wish to enrich your knowledge in the field (which is, of course, recommended) - you may start by going over the paper "Bayesian persuasion" by Kamenica and Gentzkow from 2011 (the paper that introduced the model) and the survey "Algorithmic information structure design: a survey" by Dughmi from 2017. |
| עדכון אחרון ב- 25/5/2021, 11:57:09 Last updated on 25/5/2021, 11:57:09 Последняя модификация 25/5/2021, 11:57:09 تمت الحتلنة الأخيرة ب- 25/5/2021, 11:57:09 |
Additional Tutorial This Wednesday + Updates | |
| Dear students, 1. There will be an additional tutorial on 26.5, 12:30-13:30 (Zoom only; the usual link remains valid). We'll finish talking about the concavification approach in Bayesian persuasion and we'll go over the straightforward policy approach. We'll further solve exercise 10.7. The tutorial is intended to help you with HW2. If you are unable to come to this tutorial - you can either watch its recording or read the remaining Bayesian persuasion slides on your own (they are much easier than the technical slides we went over so far), as well as the solution of exercise 10.7 (though it's not required for solving HW2). 2. Konstantin's reception hour on 26.5 will end at 12:15. If necessary - Konstantin can also answer questions right after the additional tutorial. 3. Unfortunately, due to a mysterious problem, both the lecture and the tutorial recordings from today don't contain screen recording (even though the presentations were shared with no apparent problems during the classes). However, you can find the presentations on the course website. 4. The Bayesian persuasion slides and the exercise 10.7 solution slides were slightly updated. Currently, no further updates are planned. 5. If you wish to find a partner for the final project - you may sign up to a paper in the form we published and to write your name and email (in addition to your ID) to allow other students contact you. Also, we understand that there is a WhatsApp group for this course students. |
| עדכון אחרון ב- 24/5/2021, 20:33:32 Last updated on 24/5/2021, 20:33:32 Последняя модификация 24/5/2021, 20:33:32 تمت الحتلنة الأخيرة ب- 24/5/2021, 20:33:32 |
The Bayesian Persuasion Slides Were Updated | |
| A crucial typo was corrected in slide 22 - we thank Nir for pointing it out. Moreover, some explanations were added to improve clarity. |
| פורסם ב- 24/5/2021, 00:55:24 Created on 24/5/2021, 00:55:24 Создано 24/5/2021, 00:55:24 تم النشر ب- 24/5/2021, 00:55:24 |
The Tutorial Tomorrow | |
| Dear students, Tomorrow we'll finish talking about Bayesian persuasion. We'll further solve exercise 10.7 (if we don't have enough time - you would be asked to read the solution on your own from the slides). Similarly to all the lessons scheduled in Taub - the tutorial will be via Zoom only (because of the ongoing air conditioning refurbishment). See you tomorrow! |
| עדכון אחרון ב- 23/5/2021, 15:52:52 Last updated on 23/5/2021, 15:52:52 Последняя модификация 23/5/2021, 15:52:52 تمت الحتلنة الأخيرة ب- 23/5/2021, 15:52:52 |
The Paper List for the Final Project Is Published under the Course Material | |
| Please sign up by May 27 (23:59). Please work in pairs (recommended) or triplets. All the changes after this deadline must be approved by the course staff. Good luck! |
| עדכון אחרון ב- 20/5/2021, 19:15:20 Last updated on 20/5/2021, 19:15:20 Последняя модификация 20/5/2021, 19:15:20 تمت الحتلنة الأخيرة ب- 20/5/2021, 19:15:20 |
A Clarification for Exercise 2.3 | |
| You are not allowed to assume that all the bids are distinct. You should specify a tiebreak rule for equal bids (considering one specific rule for which the auction is DSIC is enough). |
| פורסם ב- 17/5/2021, 22:49:28 Created on 17/5/2021, 22:49:28 Создано 17/5/2021, 22:49:28 تم النشر ب- 17/5/2021, 22:49:28 |
An Important Typo Was Corrected in Slide 27 from the Bayesian Persuasion Slides |
| פורסם ב- 16/5/2021, 18:40:15 Created on 16/5/2021, 18:40:15 Создано 16/5/2021, 18:40:15 تم النشر ب- 16/5/2021, 18:40:15 |
HW2 is Published | |
| The due date is June 8 (23:59). Please read carefully the guidelines before solving. Some of the material required to solve questions 1 and 4 will be taught next week (but you can find it in the Bayesian persuasion slides on the course website and chapter 10 of the course book, respectively). Please note that the Bayesian persuasion slides have been updated. We wish you good luck. Stay safe during this difficult period! |
| עדכון אחרון ב- 16/5/2021, 18:23:13 Last updated on 16/5/2021, 18:23:13 Последняя модификация 16/5/2021, 18:23:13 تمت الحتلنة الأخيرة ب- 16/5/2021, 18:23:13 |
הגדלת מכסת ימי האיחור המותרים בתרגילי הבית | |
| לאור המצב הביטחוני - מכסת ימי האיחור המצטברים בתרגילי הבית מוגדלת מ-10 ל-12. במקרים חריגים ניתן לפנות למתרגל. סגל הקורס מאחל לכם/ן חופש בטוח. |
| פורסם ב- 15/5/2021, 23:59:37 Created on 15/5/2021, 23:59:37 Создано 15/5/2021, 23:59:37 تم النشر ب- 15/5/2021, 23:59:37 |
תזכורת חשובה ביותר | |
| בהתאם להנחיות שהופצו עם פרסום התרגיל, ולאור הכוונה להתחיל בבדיקת התרגיל בהקדם - במידה ומגישים בזמן, לא ניתן להתחרט ולהגיש באיחור, ובמידה ומגישים באיחור של עד 4 ימים - לא ניתן להגיש בדוא"ל בסיום ארבעת הימים. בנוסף, כל הגשה בדוא"ל נחשבת סופית. על הסטודנטים/ות שהגישו בזמן ומעוניינים/ות שהגשה זו לא תיבדק, ובמקום זאת בכוונתם/ן להגיש באיחור לשלוח מייל למתרגל עד היום בחצות. בכל מקרה אחר - ההגשה המאוחרת לא תיבדק. |
| עדכון אחרון ב- 13/5/2021, 16:14:57 Last updated on 13/5/2021, 16:14:57 Последняя модификация 13/5/2021, 16:14:57 تمت الحتلنة الأخيرة ب- 13/5/2021, 16:14:57 |
הבהרה לאור שאלות על בעיה 2.2 | |
| יש להוכיח תנאי הכרחי ומספיק כפי שכתוב במשפט האחרון בניסוח הבעיה, ללא התייחסות למקסום סכום ה-utilities. הכוונה במשפט הראשון היא שחברי S שואפים למקסם את סכום ה-utilities שלהם בהנחה שמותר להם לתאם את ה-bids, זהו משפט פתיחה בלבד הנועד לתת רקע על פורמט המכרז ושאיפות חברי S. |
| עדכון אחרון ב- 10/5/2021, 16:01:17 Last updated on 10/5/2021, 16:01:17 Последняя модификация 10/5/2021, 16:01:17 تمت الحتلنة الأخيرة ب- 10/5/2021, 16:01:17 |
עדכון לשינוי לו"ז ההוראה החד-פעמי בשבוע הבא | |
| ביום שני הקרוב, התרגול הכפול יתקיים בשעות 10:30-12:30 ושעת ההרצאה תתקיים מיד לאחר מכן. ההרצאה והתרגול יועברו בזום בלבד, בקישורים הרגילים. |
| עדכון אחרון ב- 7/5/2021, 01:13:10 Last updated on 7/5/2021, 01:13:10 Последняя модификация 7/5/2021, 01:13:10 تمت الحتلنة الأخيرة ب- 7/5/2021, 01:13:10 |
שינוי חד-פעמי בלו"ז ההוראה בשבוע הבא | |
| ביום שני הקרוב תתקיים רק שעת ההרצאה הראשונה, ומיד אחריה תתקיימנה שעתיים רצופות של תרגול (הקישורים הרגילים לזום יישארו רלוונטיים). בנוסף, התרגול הכפול ייערך בזום בלבד - לא תהיה הוראה פרונטאלית בשבוע הבא. התרגול יעסוק ב-Bayesian persuasion, נושא שאינו מופיע בספר הקורס ולא יועבר בהרצאה, אך תהיה עליו שאלה בתרגיל הבית הקרוב. |
| עדכון אחרון ב- 6/5/2021, 18:00:29 Last updated on 6/5/2021, 18:00:29 Последняя модификация 6/5/2021, 18:00:29 تمت الحتلنة الأخيرة ب- 6/5/2021, 18:00:29 |
תשובות לשאלות נפוצות על תרגיל בית 1 | |
| בבעיה 2.2 יש להגיע לתנאי הכרחי ומספיק בו-זמנית (הדרך החלופית להבין את השאלה הופכת אותה לטריוויאלית). מותר להשתמש באופרטורים הלוגיים "או" ו-"וגם". בבעיה 5.1 - מותר להניח שפונקציית הצפיפות f הינה רציפה (בהתאם להנחות המופיעות בפרק 5 עצמו). בנוסף, ההנחה שההתפלגות הנתונה היא יוניפורמית רלוונטית רק לסעיף הראשון בבעיה זו (אחרת, בפרט, הניסוח של הסעיף השלישי חסר משמעות אמיתית, שכן התפלגות יוניפורמית הינה רגולרית). |
| עדכון אחרון ב- 6/5/2021, 14:59:14 Last updated on 6/5/2021, 14:59:14 Последняя модификация 6/5/2021, 14:59:14 تمت الحتلنة الأخيرة ب- 6/5/2021, 14:59:14 |
סיכום תרגול 6 | |
| בתרגול 6 פתרנו את הסעיף האחרון בבעיה 4.2 - הראינו שאפשר לתקן את ה-FPTAS לבעיית תרמיל הגב באופן שיניב כלל אלוקציה מונוטוני למכרז תרמיל הגב. לצורך כך - שינינו את האלגוריתם מלפני שבועיים כך שירוץ בכל פעם עם ערך קבוע אחר של m (שגדל פי 2 בכל איטרציה), כאשר מחזירים את קבוצת המנצחים המניבה את התועלת החברתית (social welfare) הגבוהה יותר, עם שובר שוויון לטובת ערך m נמוך יותר. כדי להבטיח שזמן הריצה יהיה פולינומי - יש להקטין ערכי v_j הגדולים מדי ביחס לערך ה-m הספציפי בו משתמשים בכל איטרציה, וכן לעצור את ריצת האלגוריתם בהגיענו לאיטרציה שהחל ממנה לא תהיה השפעה על פלט האלגוריתם. החלק המאתגר ביותר הוא ההוכחה שכלל האלוקציה החדש הינו מונוטוני. מדובר במקרה פרטי של הטענה המוכחת במאמר הבא: Approximation techniques for utilitarian mechanism design - Patrick Briest, Piotr Krysta and Berthold Vöcking (2005). בנוסף, פתרנו וריאציה של תרגיל 5.6 - הוכחנו שה-equal-revenue distribution (הנקראת כך כי במכרז posted price עם bidder יחיד, היא מניבה את אותו הרווח לכל בחירה של posted price) הינה התפלגות רגולרית עבורה לא מתקיים שוויון בין תוחלת הרווח לתוחלת התועלת החברתית הווירטואלית. ראינו שזה לא סותר את משפט 5.2, שכן ההתפלגות המדוברת אינה מקבלת ערכים בקטע סופי, ואף בעלת תוחלת אינסופית. בתרגול לא הוכחנו את משפט Bulow-Klemperer. מומלץ מאוד לעבור על ההוכחה מספר הקורס לבד - שכן בתרגיל הבית הקרוב תופיע שאלה בה תתבקשו להכליל את ההוכחה. |
| עדכון אחרון ב- 6/5/2021, 14:39:39 Last updated on 6/5/2021, 14:39:39 Последняя модификация 6/5/2021, 14:39:39 تمت الحتلنة الأخيرة ب- 6/5/2021, 14:39:39 |
לו"ז ההרצאות (טנטטיבי) + הודעה קצרה | |
| שלום לכולם! להלן סדר המעבר על פרקי הספר בהרצאות (לא בתרגולים), למי שרוצה לקרוא לפני השיעור או לעקוב תוך כדי השיעור: פרקים 1 עד 7 פרקים 10-11 פרקים 13-14 פרקים 17-18 פרק 20 אנחנו כרגע נמצאים באמצע פרק 6. הודעה קצרה: לאור תקלה בהקלטת המצגת אחרי ההפסקה, מעתה ננקוט באחת משתי דרכים - שתי הקלטות נפרדות לשני חלקי השיעור, או הקלטת ההפסקה. עמכם הסליחה! |
| עדכון אחרון ב- 2/5/2021, 14:51:39 Last updated on 2/5/2021, 14:51:39 Последняя модификация 2/5/2021, 14:51:39 تمت الحتلنة الأخيرة ب- 2/5/2021, 14:51:39 |
עדכונים חשובים | |
| 1. לאור משובים שקיבלנו מסטודנטים/ות על האורך ורמת הקושי של תרגיל בית 1 - הוחלט להזיז את מועד הגשתו ליום חמישי ה-13.5. 2. בנוסף, תרגיל בית 2 יהיה קצר יותר מתרגיל בית 1. מועד פרסומו יידחה בשבוע. 3. בתרגול האחרון פתרנו את הסעיף השלישי והרביעי בבעיה 4.2, בהם הוכחנו שכלל האלוקציה הנתון ע״י ה-FPTAS לבעית תרמיל הגב אינו מונוטוני עבור ערך m שבחרנו (הערך בו מחלקים את כל ה-valuations), אבל הוא כן היה מונוטוני אילו m היה קבוע. בתרגול הבא נראה דרך לא טריוויאלית להשתמש בתכונה זו כדי לתקן את כלל האלוקציה שמצאנו למכרז תרמיל הגב ולהפוך אותו למונוטוני. בנוסף, נפתור וריאציה של תרגיל 5.6 ונוכיח את משפט 6.5 (שלא יוכח בהרצאה). 4. אנא הגיעו לתרגול הבא עם רישום ה-FPTAS לבעית תרמיל הגב שהוצג במהלך פתרון בעיה 4.2 בתרגול (והוא שונה מעט מזה המופיע בספר הקורס), וכן פתרון שני הסעיפים הראשונים לבעיה זו (שהוצגו בתרגול 4) - נשתמש בהם במהלך פתרון הסעיף האחרון בשאלה, ולא נחזור עליהם מפאת חוסר זמן. 5. בתרגול שאחרי הבא (תרגול 7) יועבר חומר שלא יועבר בהרצאה, והוא אף לא מופיע בספר הקורס, אך תהיה עליו שאלה בתרגיל בית. |
| עדכון אחרון ב- 29/4/2021, 00:35:22 Last updated on 29/4/2021, 00:35:22 Последняя модификация 29/4/2021, 00:35:22 تمت الحتلنة الأخيرة ب- 29/4/2021, 00:35:22 |
שימו לב שההודעה על תרגולים 4-5 מיום ראשון כוללת גם התייחסות למידת הפורמאליות בפתרונות תרגילי הבית ביחס לתרגולים |
| פורסם ב- 28/4/2021, 13:56:34 Created on 28/4/2021, 13:56:34 Создано 28/4/2021, 13:56:34 تم النشر ب- 28/4/2021, 13:56:34 |
בגלל תקלה טכנית - התרגול היום עובר באופן חד-פעמי לטאוב 9 |
| פורסם ב- 26/4/2021, 11:54:53 Created on 26/4/2021, 11:54:53 Создано 26/4/2021, 11:54:53 تم النشر ب- 26/4/2021, 11:54:53 |
Tutorial 4 Summary and the Plan for Tomorrow | |
| Dear students, Last week, we solved problem 5.2 – in a posted-price auction, for a single bidder whose valuation has a strictly increasing, regular CDF with a strictly positive density function on a closed interval – using the median price as the posted price yields at least half the expected revenue of the optimal posted price. This problem provides a 0.5-factor approximation for revenue maximization in a single-bidder, posted-price auction (assuming that one can compute the median price). The proof uses the *revenue curve*, representing the expected revenue as a function of the selling probability (instead of the obvious representation as a function of the posted price, which is arguably more intuitive, but it lacks some useful properties of the revenue curve). You should analyze the revenue curve notion in problem 5.1 from HW1. In particular, in part (c), you should prove that for a regular distribution, the revenue curve is concave (and vice versa), from which problem 5.2 follows (using the definition of concavity). We further solved parts (a)-(b) of problem 4.2 that provide an FPTAS for the knapsack problem. We also discussed the notion of FPTAS in general and briefly mentioned several related notions. Tomorrow, we shall see the connection to knapsack auctions by solving parts (c)-(e). Moreover, we shall solve exercise 5.6 and probably some related parts of other exercises. Please note that due to a misunderstanding, the last tutorial was held as if the regularity notion was studied in the lecture. The course staff will do its best to ensure that such a situation will never be repeated. In the future, if you do not understand a certain term used in a lecture/tutorial – do not hesitate to tell us immediately. A remark regarding the formality of tutorials vs the expected level of formality in HW – in general, the solutions in the tutorials are formal enough for HW (unless I say otherwise, or I say that I skip steps). While I do some shortcuts in writing the task formulations, I usually avoid significant shortcuts in the solutions. In particular, exercises 1.3, 2.8 (apart from the one-line straightforward proof of (*) which I skipped), 2.1 (the two extremely short solutions I sent as part of an announcement) and problems 5.2 and (my slight modification of) 4.2 were (or will be) all solved formally enough. However, exercise 2.7, which I labelled *discussion*, was not solved formally (as the aim was to explain you the similarities and the differences between the two auction formats). Some final remarks: - When I ask in class whether someone is still writing – please feel free to answer. I highly encourage writing during classes, even if it decreases the pace. Moreover, I consider it positive that writing imposes a natural limit on the pace. Furthermore, students may take this time to “process” the material and ask questions. - We are not planning to publish full solutions for the tutorials. Please note that (especially a hard) question given this year in a tutorial might be given another year in HW. - Continuing the topic of the requirements from your HW solutions – it is highly recommended to go over your solutions before submitting. Usually, a solution containing a lot of small mistakes does not leave a good impression. Also, you should avoid writing claims that are mathematically wrong. See you tomorrow, Konstantin |
| עדכון אחרון ב- 25/4/2021, 23:46:23 Last updated on 25/4/2021, 23:46:23 Последняя модификация 25/4/2021, 23:46:23 تمت الحتلنة الأخيرة ب- 25/4/2021, 23:46:23 |
הצביעו והשפיעו! | |
| אנו מזכירים לכם/ן שאפשר להצביע בסקר אנונימי פנימי שישפיע על ההוראה בהמשך הסמסטר עד מוצ"ש בחצות. |
| עדכון אחרון ב- 22/4/2021, 13:01:44 Last updated on 22/4/2021, 13:01:44 Последняя модификация 22/4/2021, 13:01:44 تمت الحتلنة الأخيرة ب- 22/4/2021, 13:01:44 |
סקר פנימי על ההוראה בקורס | |
| להלן קישור לסקר אנונימי פנימי קצר שהכנו לצורך קבלת משוב על ההרצאות והתרגולים עד כה והרצון לשפר את החוויה בהמשך הסמסטר: https://forms.gle/aAMoUgvdfCbSD1jL8 נודה לכם/ן אם תוכלו להקדיש כמה דקות מזמנכם/ן ולענות על הסקר עד מוצ"ש ה-24.4 בחצות (כמובן, ההשתתפות בסקר אינה חובה). |
| עדכון אחרון ב- 21/4/2021, 02:06:55 Last updated on 21/4/2021, 02:06:55 Последняя модификация 21/4/2021, 02:06:55 تمت الحتلنة الأخيرة ب- 21/4/2021, 02:06:55 |
Summary of Tutorials 1-3 and the Plan for Tutorial 4 | |
| Dear students, I would like to remind you that during the first tutorial and the beginning of the second one, we discussed (based mostly on Chapter 1 of Roughgarden’s book) the three main topics of this course: 1. Mechanism Design - How to design a system with strategic participants so that their behavior is desirable for us (we provided an example from sports, but most of the corresponding part of the semester will be about auctions). 2. Price of Anarchy (PoA) - (informally) The ratio of the total cost at the worst possible equilibrium (chosen from a certain set of equilibria) to the optimal cost. We discussed Braess’s Paradox (building a highway might worsen traffic jams) and saw an example in which PoA=4/3. The relevant part of the course is expected to be significantly shorter than the other two. 3. Equilibria – We defined (informally) a *Nash equilibrium* as a profile (vector) of players’ strategies s.t. no player can better off by changing her strategy, while keeping other players’ strategies fixed. We defined a *pure strategy* as a strategy that is a part of the game definition and a *mixed strategy* as a distribution over pure strategies. On the one hand, we saw (by the example of Rock-Paper-Scissors) that a Nash equilibrium in pure strategies does not always exist. On the other hand, we formulated a theorem of Nash that every finite 2-player game has a mixed-strategy Nash equilibrium. It might have been intuitive, if each player affects herself and not the other players, to assume that in practice, a game always converges to a Nash equilibrium – in a non-equilibrium strategy profile, at least one player can better off by changing her strategy, so why wouldn’t she do that? However, Nash equilibria are not necessarily unique, and while in zero-sum games, such as Rock-Paper-Scissors, one can prove that every Nash equilibrium yields the same payoff – it is not true in general 2-player games. Moreover, one can compute a Nash equilibrium in a 2-player zero-sum game in a polynomial time, but the analogous problem for general 2-player games is PPAD-complete (hopefully, we shall talk about the PPAD complexity class at the semester end); and if the players cannot compute an equilibrium – how can they act according to it? Therefore, we shall see weaker definitions of equilibria, so that not only an equilibrium exists and can be computed in polynomial time, but there exists an efficient learning algorithm for the equilibrium. During the second tutorial, we further solved exercise 1.3 from Roughgarden’s book – to prove that there exists a unique Nash equilibrium in Rock-Paper-Scissors in which every player chooses her action uniformly. While solving the exercise, we learned that in general games, for every player, there exists a best reply to every fixed profile of mixed strategies of the other players that is a pure strategy. After solving the exercise, we noted that in the Nash equilibrium in Rock-Paper-Scissors, every player is indifferent between all of her actions – that is, no matter whether she chooses rock, paper or scissors, her expected payoff over the other player’s mixed strategy in the equilibrium is 0. We noted (without writing formally) that in every Nash equilibrium in a general game, every player *must* be indifferent between all the pure strategies assigned a strictly positive probability in her mixed strategy – otherwise, she could have reassigned the probability of the pure strategy yielding a lower expected payoff to the pure strategy yielding a higher expected payoff, contradicting the definition of a Nash equilibrium. In the third tutorial, we solved exercise 2.8 - to prove that in sponsored search (slot) auctions, the welfare-maximizing allocation rule is to assign to the i-th highest bidder the i-th highest slot, by proving a slightly stronger (and a very important) mathematical claim – the rearrangement inequality. The proof was by running an algorithm repeatedly swapping “wrong” pairs of sigma(i), sigma(j). Please note that the algorithm formulation contained a small inaccuracy – one should swap sigma(i) and sigma(j) if alpha_{sigma(i)} is strictly smaller than alpha_{sigma(j)} and v_i is strictly bigger than v_j (as if v_i=v_j, one cannot apply the claim (*) from which we started the proof). What I did not have time to talk about in class is that the presented proof method of the rearrangement inequality easily allows to generalize it to every setting in which a claim analogous to (*) holds – e.g., try to apply any convex function on the sums of the corresponding elements of the two sequences, rather than multiplying these elements. We also noted about the sponsored search (slot) auctions that even though they are DSIC, in reality – another auction format is often used for online ad auctions (for reasons that include simplicity of the payment rule and unwillingness to change an auction format that works). This is the *generalized second-price auction* (GSP), which you should explore in HW1. Moreover, we solved exercise 2.7. We discussed the English (open ascending single-item) auction in which the price is increased iteratively until all the bidders but one retire, and the last remaining bidder is declared to be the winner (with a certain tiebreak rule applied); she pays the last proposed price. We saw that this auction is eventually equivalent to the Vickrey (single-item second-price) auction presented in the lectures, in the sense that: (a) every bidder has a dominant strategy to retire exactly when the proposed price passes her true valuation; (b) assuming that all the bidders use the strategy from (a), the winner is the bidder with the highest valuation, and she pays eventually the second-highest valuation (why “eventually”? because the second-highest bidder retired immediately after the price passed her valuation; thus, the last proposed price is slightly above the second-highest valuation). However, in reality, there is a significant difference between the two auction formats (beyond the psychological feeling in the English auction that “the victory is close”). Suppose that all the bidders have the same value for the item being sold, but they only have *estimations* of it. To be concrete, assume that the estimation errors of the bidders are i.i.d. (independent and identically distributed) and their expected value is zero. If the number of bidders is large, the two highest bidders are very likely to overbid in the *Vickrey* auction (provided that they just bid on their estimated values), leading to the *winner’s curse* phenomenon – the winner is likely to get a negative utility. This phenomenon does not occur in the English auction, as the winner learns all the estimations of the other bidders when they retire; thus, she can obtain a much better updated estimation. Robert Wilson (1977) and Paul Milgrom (1981) (Noble Prize laureates in economics, 2020) showed how to deal with the winner’s curse – in a Nash equilibrium, the bids should equal appropriately conditioned estimations of the item value (which are lower than the unconditioned estimations). However, in the common-valued item setting, the English auction is still better than the Vickrey auction in terms of the auctioneer’s revenue (subject to some regularity conditions we shall not discuss). It follows from the “linkage principle” (Paul Milgrom – Robert Weber 1982); speaking informally, the auctioneer earns more by revealing as much information about the sold item as she can (and the English auction fits within this paradigm, as the bidders’ private estimations facilitate the computation of the true item value). Tomorrow, we shall discuss the Myerson’s *revenue-maximizing* auction; so why is the English auction (which maximizes welfare, as well as the Vickrey auction) still very popular? Among other reasons – because if the auctioneer neglects welfare considerations, it might cause the bidders to go to an alternative auction house. Unfortunately, I did not have enough time to solve exercise 2.1, which proves that the “third-price single-item auction”, in which the highest bidder wins are she pays the third-highest bid, is not DSIC. Because of this exercise simplicity, I shall provide the solution(s) here. First – note that by Myerson’s lemma, the payment rule for a DSIC auction allocating the item to the highest bidder is unique (provided that bidding 0 yields paying 0); the single-item second-price auction is DSIC; by uniqueness – the “third-price single-item auction” is not DSIC. However, it is easy to solve the exercise directly. Indeed, fix valuations v_1>v_2>…>v_n>0 of the 1,2,…,n bidder (resp.). Then truthful bidding is not a dominant strategy for the second bidder – if all the bidders bid truthfully, she loses and earns 0, while if she bids v_1+1 and all the others bid truthfully – she wins and pays v_3, earning v_2-v_3>0. Tomorrow, we are going to solve problems 4.2 and 5.2. This is part of my intention concerning the rest of the semester to solve slightly harder tasks than in tutorials 1-3, which were introductory tutorials. After the lessons tomorrow, the course staff plans to publish a poll to hear your preferences regarding the next lessons. See you tomorrow, Konstantin |
| עדכון אחרון ב- 19/4/2021, 01:15:07 Last updated on 19/4/2021, 01:15:07 Последняя модификация 19/4/2021, 01:15:07 تمت الحتلنة الأخيرة ب- 19/4/2021, 01:15:07 |
HW1 | |
| Dear students, HW1 consists of the following tasks from Tim Roughgarden's book "Twenty Lectures on Algorithmic Game Theory", published in 2016. The numbering refers to the book version available online via the Technion library portal (which redirects to the Cambridge University Press website): - Exercise 2.5 (10 points). In this exercise, you should describe the payment and the allocation rules of the auction you propose, and prove that the auction satisfies the requirements described in the exercise. - Problem 2.2 (20 points). In this problem, you may assume that there are at least 3 bidders and consider only nonempty sets S. - Problem 3.1 (5*6 points). In this problem, you should assume that b_i<=v_i for every 1<=i<=n. Moreover, if two bids are equal, you should assume that the bidder with the lower index gets the slot with the lower index. Furthermore, for parts (b)-(f), you should assume k=n. - Problem 4.3 (5+7+7 points). The expression "remove T_i from X" in the algorithm description means "remove all the elements of T_i from X". - Problem 5.1 (7*3 points). Please note that some of the material required to solve this problem will be taught next week. Important guidelines: - The deadline for HW1 is May 5 at 23:59 (three days later compared to the plan from the syllabus). The submission site would close a little later to capture force majeure cases. If you manage to submit your work under the "HW1 - on time" task - this would not count as a late submission. - If you wish to submit your work until May 9 at 23:59 using your "late day bank" (as explained in the syllabus, you are allowed to be late with your HW submissions at most 10 days on aggregate during the semester; this would not result in any penalty, but being late for more than 10 days on aggregate, without getting a permission in advance due to an objective reason, might lead to your submission not being accepted) - please use the "HW1 - up to 4 days late" task. Similarly to the "HW1 - on time" task, it would close a little after midnight. - If you wish to submit your work after May 9 at 23:59 - please send it to Konstantin's email. - Please note that the checking process is expected to begin shortly after the HW deadline. Therefore, if you submit on time - it is not possible to request after the HW deadline to make a late submission that replaces your on-time submission. Similarly, it is not possible to submit your HW under the "HW1 - up to 4 days late" task and to ask to replace your submission after May 9 at 23:59. Also, any submission via email is considered as final and cannot be replaced. - Please submit a single (Hebrew/English) pdf file created by Latex. Students with special requests regarding this requirement should contact Konstantin. - Roughgarden's book contains two types of tasks: "exercises" and "problems". Be careful not to get confused! - The submission is in singles only. Moreover, you must work independently and you are *not* allowed to consult with other students even at a high level (unlike on some other courses). If you feel stuck - you may come to Konstantin's reception hour or contact him via email (but you won't be told the full solution). - The course staff intends to enforce the above requirement. Please avoid putting yourselves and us in an unpleasant situation. - You may use any material from the lectures/tutorials and the book "Twenty Lectures on Algorithmic Game Theory" (including the hints to some tasks it contains). You may also use external sources of information to learn more about the following topics: NP-hardness, convexity/concavity, computing the derivative of the inverse function. - You are *not* allowed to use any sources (including research papers) apart from the cases listed above. - Even if in some task you are only requested to "describe" something, "provide" something, etc., you must also prove that what you describe/provide satisfies the task requirements. - You must prove all of your claims, unless they were taught at the class or in a basic course at the Technion (you may consult Konstantin in a case of a doubt). Good luck! |
| עדכון אחרון ב- 13/4/2021, 16:25:40 Last updated on 13/4/2021, 16:25:40 Последняя модификация 13/4/2021, 16:25:40 تمت الحتلنة الأخيرة ب- 13/4/2021, 16:25:40 |
הודעה לזכאים/ות להתאמות בתרגילי הבית | |
| סטודנטים/ות בעלי/ות זכאות להתאמות בתרגילי הבית (עקב הורות או סיבות אחרות; כולל הארכה במועדי ההגשה ו/או הפחתת מטלות) מתבקשים/ות להודיע על כך למתרגל בדוא"ל עד יום חמישי ה-8.4. כדאי להודיע גם אם אין כוונה לנצל את ההתאמות, ניתן לוותר עליהן בכל שלב. |
| עדכון אחרון ב- 24/3/2021, 15:30:54 Last updated on 24/3/2021, 15:30:54 Последняя модификация 24/3/2021, 15:30:54 تمت الحتلنة الأخيرة ب- 24/3/2021, 15:30:54 |
עדכונים מנהלתיים | |
| תחת הלשונית "חומר הקורס" ניתן למצוא קישורים לפגישות זום של ההרצאות, התרגולים ושעות הקבלה של המתרגל. ההרצאות תתקיימנה בשלב זה בזום בלבד. התרגולים יתקיימו בטאוב 7 וישודרו בזום בזמן אמת, סטודנטים/ות מוזמנים/ות להגיע גם לתרגולים הפרונטליים. לצורך עמידה במגבלות החוקיות הנוכחיות על פעילות הטכניון, סטודנטים/ות בעלי/ות תו ירוק בלבד יכולים/ות להגיע לתרגולים פרונטליים. לצורך זאת, נא להירשם מראש דרך האתר students.technion.ac.il או דרך אתר הקורס במודל שנפתח במיוחד למטרה זו (אפילו שנכון לעכשיו - יש מספיק מקומות בכיתה לכל הסטודנטים/ות הרשומים/ות לקורס). בהתאם להנחיות באתר יחידת הבטיחות של הטכניון, "סטודנטים יידרשו להדפיס את תעודת תו ירוק ולהניח את הדף בצורה בולטת על השולחן / לוח הכתיבה לצידם בעת השהייה בכיתה". בנוסף, חובה לעטות מסיכה במהלך כל התרגול ולשבת רק במקומות המסומנים. אנו מזכירים כי הפרת נהלי התו הירוק מהווה עבירת משמעת ואף עבירה על החוק. |
| עדכון אחרון ב- 18/3/2021, 17:16:35 Last updated on 18/3/2021, 17:16:35 Последняя модификация 18/3/2021, 17:16:35 تمت الحتلنة الأخيرة ب- 18/3/2021, 17:16:35 |
ברוכות הבאות וברוכים הבאים לקורס ״תורת המשחקים האלגוריתמית״ | |
| סילבוס מפורט הועלה לאתר הקורס. אנו מאחלים לכם/ן בריאות והצלחה בקורס. |
| עדכון אחרון ב- 21/1/2021, 23:09:45 Last updated on 21/1/2021, 23:09:45 Последняя модификация 21/1/2021, 23:09:45 تمت الحتلنة الأخيرة ب- 21/1/2021, 23:09:45 |