Answers to homework questions are due two weeks after we post the exercise. 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.

- Exercise 1 (due date: 23/3, extension until 30/3, submit in Avital Gutman’s box in Ross 0)
- As you must have noticed from Q3,
**Gibbard-Satterthwaite**theorem applies for . Meaning, if all permutations of preferences are possible. - Question 3: should be defined this way: if
- Question 4b: The social choice function needs to be truthful

- As you must have noticed from Q3,
- Exercise 2 (due date: 04/05, extension until 11/05, submit in class)
- Exercise 3 (due date: 08/06, submit in class)

Do we need to show the complexity of the algorithms we use in question 2?

If its not clear that they are efficient (polynomial time) then you have to explain that.

Just to make sure i’ve understood question 1 correctly- In the definition of equilibrium, is it correct that s_1..s_n are strategies, whereas s’_i is a behavior?

thanks

in ex2, q1, are advertisers limited to (at most) 1 slot each?

Thanks

never mind, silly question… without the limitation it becomes uninteresting.

משהו לא ברור לי לגבי הדרישה בשאלה 2. ממה אני מבינה הדרישה היחידה היא למצוא מנגנון שממקסם את הרווחה החברתית ומקיים את הדרישה של פונקציית התשלומים שמורכבת מפונקצייה כלשהי התלויה רק בשאר השחקנים פחות סכום התועלות של שאר השחקנים. האם זה אכן כך? אני יכולה לבחור איזו פונקציה שאני רוצה עבור פונקציית התשלומים בתנאי שהיא בצורה שהגדרתי להלן, או שעליי לבחור דווקא את הפונקציה עליה דיברנו בכיתה – זאת שמחשבת בדיוק את הנזק שנגרם לחברה על ידי השתתפות השחקן במכרז ומחייבת אותו בתשלום הזה? איזה מבין השניים נכון? ובנוסף, האם עליי להראות משהו לגבי המנגנון שנבחר, שהוא כנה? לא מאפשר תשלומים שליליים וכו?

We are asking for the pivot payments. Equivalently, that losers pay 0. You just have to show/explain why these are the VCG payments (with Clarke pivot), and as such you get IC+NPT+IR as shown in class.

In q.3, do we have to prove formally that all our penalty functions are IC, or can we explain verbally?

We are not asking for completely formal proofs here. However the explanation should make it clear that you are able to turn your argument into a formal proof on demand.

Thanks. Another related question:

In the last few sectinos of q.3, can we find a function according to section (e) and rely on the general proof we gave there that such functions are IC, or should we do the dirty math and show IC anew? I find it especially dirty in section (h).

Should we answer q.3(e) for the case f is weakly-monotonic? This is also true, but can make a serious head-ache in the definitions and in the proof.

If you want, you can assume strict monotonicity, but state the assumption explicitly if you use it.

regarding q.3a in problem set 3 (two minded bidders).

I’m not sure it makes any difference, but if bidders are interested the union of the two sets, should we assume the adapted algorithm adds that union to the list of pairs (set/value) it sorts?

I believe that it doesn’t, or in any case – that’s the way it reads to me. The “natural adaptation” would treat the input as if there are 2n single minded bidders.