CSCE 782: Problem Set 5

Selfish Mailmen

We first define a new greedy mailmen problem which is similar to the one from the previous problem except for a few differences:

1. The mailmen and letters all start at a central location.
2. Each mailman goes directly home after his route. Their homes are randomly placed.
3. Each letter has a price associated with it. The mailman who delivers the letter gets that price.
4. The mailmen incur a cost which is directly proportional to the distance they travel.
5. The mailmen do not tell anyone else their cost function.
6. The mailmen are greedy rational agents with a linear utility of money.

Given this new problem, your task is to design an exchange mechanism that is incentive compatible for the mailmen and still converges to the social welfare solution for the system. Note that you are not to implement your exchange mechansism in netlogo (well, you can, if you want to). Instead you must provide a clearly written writeup that includes

1. Overview of your proposed solution.
2. Detailed algorithms in pseudo-code that describe exactly what each agent needs to do. If an agent needs to do any calculation you must give the formula it should use. That is, this should be very close to code.
3. An informal proof that your mechanism converges on the social welfare while being incentive compatible.
4. An analysis of the time complexity of your solution. How long does it take as a function of letters? of mailmen?

Submission Instructions

As will all the problem sets, you will hand them in using our department's dropbox. You are to hand it either a plain text file, PDF, or MS Word file (without any macros or viruses!). You should hand in only one file. Your file should begin with: