CSCE 782: Problem Set 5

Due: 5 November 2003 @midnight

Upload Problem Set

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:


I understand that it is the responsibility of every member of the Carolina community to uphold an maintain the academic standards and integrity of the University of South Carolina. Any member of the University community, who has reasonable grounds to believe that an infraction of the Code of Student Academic Responsibility has occurred, has an obligation to report the alleged violation.

I certify that I have neither given nor received unauthorized aid on this problem set.

A funny comic strip.

José M. Vidal
Last modified: Wed Oct 29 15:31:02 EST 2003