Exercises

While we encourage working together on the exercises as well as using any written sources that you find, you must write your solution completely alone.  In every exercise please indicate the name of all those that you have worked with as well as all sources that you have used.

The list of grades will appear here.

Please submit exercises to Tali Gutman’s box in Ross 0, by 19:00 on the submission day.

Exercise

  • Exercise 1
    • Question 1: You were asked to find a Nash equilibrium. In case this is unclear, we expect you to explain why what you suggest here IS in fact a Nash equilibrium, and not just state a numeric example.
    • Question 4: You are required to give an example with n players such that there is a better reply sequence of length 2^n. This means you need a general example for every n, and examples for n=2,3,... etc. will not be considered a viable answer.
    • Solution guidelines for Ex1
    • Last year’s common errors for Q4
    • Grades for Ex1
  • Exercise 2 [Please note the related posts]
    • There’s been a mistake with the submission date, it is Monday, 13/12/2010.
    • We are REALLY sorry – we had a typo in Q1(b). You need to show that both the problems are co-NP hard (and not NP-hard). Following this unfortunate mishap, submission date changes to Wednesday, the 15th.
  • Exercise 3
    • You must choose 4 out of 6 questions, if you answer 5 you will get some bonus (still undecided), but you cannot submit 6.
    • You already have the required knowledge to solve the exercise.

Advertisements

Responses

  1. Hi,
    In Q4, are we talking about a finite game? You wrote that there are n players, but is this enough to assume it’s finite?
    thanks, Yotam

    • If you’re asking about n, then:
      Short answer: Yes, n is finite.
      Long answer: Even if n\rightarrow \infty , n has a single value at every point, and it is finite.

      If you’re asking about the game (as in, the number of steps), then:
      Short: It could be infinite.
      Long: That is for you to prove or disprove, and for me to grade 🙂

  2. בשאלה 2 הרמז מכוון רק לרדוקציה לבעיה השנייה (עבור שתי מכונות לא זהות או יותר) או גם לראשונה (עבור 3 מכונות זהות, או יותר)

  3. בשאלה 3, סעיף ב –
    מה הכוונה ב”שיווי משקל הטוב ביותר”?
    יכולים להיות מספר שיווי משקל שונים מקטגוריות שונות – נניח ש”מ של אסטרטגיות טהורות וש”מ של אסטרטגיות מעורבות, האם מספיק להתייחס רק לאסטרטגיות טהורות? אם לא, האם מותר להשוות ביניהם (למשל על ידי סכימת התועלות)?

    • בשאלה 3 בשני הסעיפים, יתכן שמדובר בש”מ מעורב.
      שים לב, שש”מ מעורב הינו הרחבה של ש”מ טהור, וכל ש”מ טהור הוא גם מעורב – פשוט עם סט תמיכה מאוד מצומצם.
      ש”מ מעורב – נמדד לפי תוחלת התועלת שלו.

  4. על מנת להראות שפונקציית בחירה חברתית איננה כנה, האם מספיק להראות מקרה אחד (כלומר – קבוצת נבחרים, קבוצת בוחרים ווקטור העדפות) שבו ינתן לבצע מניפולציה, או שצריך להראות משהו כללי יותר?

    • מספיק להראות מקרה שבו ניתן לבצע מניפולציה מוצלחת.
      (כלומר, לא רק ששינוי העדפות הבוחרים המניפולטיביים משנה את תוצאת הבחירה, אלא שהשינוי הזה מיטיב עם המניפולטורים)


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: