Computational Game Theory

Homework number 1

1. Auction and Nash Equilibrium:

a. Consider a first price auction where each participant pays $1 to participate in the auction.

Are there deterministic Nash Equilibriums?

(Assume that a player can choose not to participate.)

b. Consider a second price auction where the participant that bids the second price receives $1 (if there are more then one, they share it).

What are the deterministic Nash Equilibriums?

(Assume that all the valuations and the bids are positive integer numbers. In case of a tie, the player with the higher ID wins.)

2. Job Scheduling: Show how to compute efficiently a Nash equilibrium for n jobs and m (different speed) machines.

(Hint: consider the jobs in a sorted order.)

3. PoA and Job Scheduling: In unrelated machines a job has a different load on each machine, i.e., w_i(J) is the load og J on machine M_i. Show that for unrelated machines the price of anarchy can be unbounded.

Bonus: For identical machines and unit size jobs, for correlated equilibrium, give an example where the price of anarchy is high (There is an example with √m, when m=n).

Can you give also an upper bound?!

4. Selfish Routing:

a. Show that if the link delay function is l_e (x) = a x , for a constant a>0,then OPT=NASH.

b. Consider a quadratic delay function is l(x) = ax² + bx +1, for some constants a and b. Derive an example that NASH differs from OPT (as much as you can).

The homework is due April 25 (in class)

סיכומי הרצאות

הרצאה	שם פרטי	שם משפחה	דואר אלקטרוני
1.	יובל שחר	נצר פתל	yuvalne@txtechnion.ac.il fattalsh@post.tau.ac.il
2.	עדי מיכל ריקי	אדיב רוזן רוזן	adiadiv@hotmail.com michalros@gmail.com rosenric@rau.ac.il
3.	אורן מיה לוטם	פולג קפלן	oren@poleg.org mayaben@post.tau.ac.il lotem@eng.tau.ac.il
4.	עמרי הילה יעקב	תובל הוך	hila_p@yahoo.com yaakov.hoch@weizmann.ac.il
5.	נתן זאב	רובין ברונשטיין	rubianat@post.tau.ac.il bronstein@post.tau.ac.il
6.	אנדרי ליאור	סטולרנקו גביש	stloyare@tau.ac.il lgavish@tau.ac.il
7.	שרון צח אייל	ברוקנר צחי אהרון שניידר	bruckner@post.tau.ac.il zachdres@post.tau.ac.il pyalsch@gmail.com
8.	אורן אייל ליאור	מור דוד גביש	orenmohr@yahoo.com eyaldav1@post.tau.ac.il liorg@post.tau.ac.il
9.	סרגיי איליה ליזה	פיסידקי אבן-חן פוטיחה	pisotsky@gmail.com elih@post.tau.ac.il liza.potikha@gmail.com
10.	ענת גליום גיא	הלפרין רובדיין טננבאום	anat@eng.tau.ac.il galca8@yahoo.com guy_tennenbaum@yahoo.com
11.	ידעאל הלל	ולדמן פליישר	yedaelwa@post.tau.ac.il hillel_f@yahoo.com
12.	אמיר סבאלנה	אפשטיין אולונצקי	amirep@tau.ac.il olonetski@tau.ac.il

אסף ארנון asapha@smile.net.il

ליאור שפירא liors@post.tau.ac.il