CSCE 782: Problem Set 5
Due: 5 November 2003 @midnight
We first define a new greedy mailmen problem which is similar to
the one from the previous problem except for a few differences:
- The mailmen and letters all start at a central location.
- Each mailman goes directly home after his route. Their homes are randomly placed.
- Each letter has a price associated with it. The mailman who delivers the letter gets that price.
- The mailmen incur a cost which is directly proportional to the distance they travel.
- The mailmen do not tell anyone else their cost function.
- 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
- Overview of your proposed solution.
- 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.
- An informal proof that your mechanism converges on the
social welfare while being incentive compatible.
- An analysis of the time complexity of your solution. How
long does it take as a function of letters? of mailmen?
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.
José M. Vidal
Last modified: Wed Oct 29 15:31:02 EST 2003