## Problem sets

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 $f:L^n \rightarrow A$. Meaning, if all permutations of preferences are possible.
• Question 3: $\succ_i$ should be defined this way: $x\succ_i y$ if $d(x,x_i)
• Question 4b: The social choice function needs to be truthful
• Exercise 2 (due date: 04/05, extension until 11/05, submit in class)
• Exercise 3 (due date: 08/06, submit in class)

#### 14 Responses to “Problem sets”

1. 1 asher March 11, 2010 at 1:11 pm

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

2. 3 Assaf March 15, 2010 at 6:16 pm

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

3. 4 Assaf April 14, 2010 at 2:00 pm

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

4. 5 Assaf April 14, 2010 at 2:15 pm

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

5. 6 Osnat April 30, 2010 at 5:49 am

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

• 7 noamnisan April 30, 2010 at 8:03 am

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.

6. 8 Tomer May 2, 2010 at 11:09 am

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

• 9 noamnisan May 2, 2010 at 7:26 pm

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.

• 10 Tomer May 2, 2010 at 8:04 pm

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).

7. 11 Tomer May 2, 2010 at 2:26 pm

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.

• 12 noamnisan May 2, 2010 at 7:27 pm

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

8. 13 Assaf June 2, 2010 at 12:14 pm

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?

• June 13, 2010 at 9:05 pm

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.