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.

a.1 How many possible task allocations are there?

a.2 List each agent’s preference (numeric value) for each of these.

a.3 Which task allocation will be chosen?

a.4 List the route of each salesman.

a.5 How much domain (travel) cost does each salesman incur?

a.6 How much tax does each agent pay/receive?

a.7 What is the budget balance/deficit?

a.8 Demonstrate a way—if one exists—how some agents can beneficially collude by revealing their preferences untruthfully. How would this changes answers?