Computational Game Theory


Homework number 3


1.     Strategy Proof

We have a tree T. Each player is located in a node in the tree T, which is its private information. We like to select one node X. The cost of a player is the distance (in edges) from his location to X. Build a strategy proof algorithm (without money) to select X, which is not a dictatorship.


2.     Sequential Mechanism:  Assume that we have two Strategy Proof mechanisms, A and B over the same set of players. Would running sequentially, first mechanism A and then mechanism B maintain the strategy proof property?


HINT : Consider selling two identical products by running sequentially two second price auctions.


CORRECTION: The question should be: Is the joint action, where every agent bids its true value in both mechanisms a Nash Equilibrium.


3.     Market Clearing Price: Assume that we have n products and n buyers in a matching market. Each buyer has a non-negative valuation for each product, and each buyer will buy exactly one product. Assume that every buyer has a higher valuation for product a then product b. Does this implies that in ANY market clearing prices the price of product a is higher than the price of product b.



The homework is due June 7, 2010