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 |