Section 2: Mechanism Design in the Quasilinear Setting

Key Learning Points

• Define the quasilinear preference model.
• Talk about the design of mechanisms for agents with these preferences.
• Introduce famous Groves mechanisms, the VCG mechanism, or the Clarke tax mechanism and their limitations.

Activities

1. Read Section 10.3 and Section 10. 4 of the text.
2. Watch the following videos:
   1. VCG: Taste
   2. Vickrey-Clarke-Groves Mechanisms: Definitions
   3. VCG Example
   4. Limitations of VCG
   5. Individual Rationality and Budget Balance in VCG
   6. Myerson-Satterthwaite Theorem

3. Read the following example:

   Applying the Groves-Clarke mechanism to the house-painting problem introduced above. Remember that the second solution we tried, where the cost of painting was divided among those who voted to paint, was not strategy-proof.

   Now try to add Groves-Clark payments to make it strategy-proof.

   First, reevaluate the agents’ value, which will be decreased from 10 since they might have to pay for part of the painting if they voted yes;

   Then calculate the agents’ payments using Groves-Clarke mechanism. The set of payments the agents would receive if they all told the truth is shown in the following table:

   Name	$v_i(o,\overline{\theta })$	$v_i(o,\theta )+{\displaystyle \sum _{j\ne i}{v}_j}(\overline{\theta })$
   Alice	10 − 20/4 = 5	5 + 15 = 20
   Bob	0 − 0 = 0	0 + 20 = 20
   Caroline	10 − 20/4 = 5	5 + 15 = 20
   Donald	10 − 20/4 = 5	5 + 15 = 20
   Emily	10 − 20/4 = 5	5 + 15 = 20

   As you can see, all the agents get the same utility (20) from telling the truth.

4. Do the following exercises:

   Let there be a salesman located at each one of the following three coordinates: (0, 0), (0, 5), and (5, 0). Let there be a customer at each one of the following five locations: (1, 4), (1.5, 0), (2, 2), (3, 2), (5, 2). Each customer has to be assigned to exactly one salesman who will visit the customer. After visiting all of the customers assigned to him, the salesman has to return to his initial location. The domain cost that the salesman incurs from his travel is the Euclidean length of the trip. The tasks (locations of customers) are known to all salesmen.

   Write a program that uses the Clarke tax voting mechanism to solve this problem, i.e., tax is levied in a way that each salesman is motivated to reveal his preferences (over task allocations among agents) truthfully.

   1. How many possible task allocations are there?
   2. List each agent’s preference (numeric value) for each of these.
   3. Which task allocation will be chosen?
   4. List the route of each salesman.
   5. How much domain (travel) cost does each salesman incur?
   6. How much tax does each agent pay/receive?
   7. What is the budget balance/deficit?
   8. Demonstrate a way—if one exists—how some agents can beneficially collude by revealing their preferences untruthfully. How would this changes answers iii–vii?
5. Discuss the following question in the discussion forum: The Gibbard-Satterthwaite theorem states that it is impossible to devise a truth-promoting voting mechanism for insincere agents. On the other hand, the Clarke tax mechanism is such a voting mechanism. Explain why this is not a contradiction.