Algorithm Examples

From BenningtonWiki
Jump to: navigation, search

Finding an organ donor

Alvin Roth, even though he is an economist, is smart enough to realize that repugnance will keep Americans from embracing a true market for organs anytime soon. So, along with several other scholars and medical personnel, he has helped design a clever alternative, the New England Program for Kidney Exchange. Imagine that you have a wife who is dying of renal failure, and that you would give her one of your kidneys, but you are not a biological match. Now imagine that another couple is in the same bind. The kidney exchange locates and matches the couples: you donate your kidney to the stranger's wife, while the stranger gives his kidney to your wife; the operations are performed simultaneously to make sure no one backs out. Although this system has yielded only a couple dozen transplants so far, it illustrates an economist's understanding of incentives: if you can't get someone to give an organ out of altruism, and you can't pay him either, what do you do? Find two parties who are desperate to align their incentives.

Freakonomics: Flesh Trade, New York Times Magazine, July 9, 2006

Responding to a carjacking

My cousin and his girlfriend were the victims of an attempted carjacking. Two armed men ordered them into the car. As one assailant was climbing into the backseat on the driver's side, my cousin grabbed the keys and ran, leaving his girlfriend. He quickly reached an emergency phone, and the police responded within minutes to find that the carjackers had fled, leaving his girlfriend unharmed. Did he do the right thing? C.D., Los Angeles

This does put your cousin in a bad light, but there is an upside: think of the money friends and family save by not having to buy wedding presents.

The question is this: Did his 100-meter dash add to her peril? If not, then ethically it's a neutral act. (Though it might not warm her heart; from her perspective, "run for help" may be indistinguishable from "run away.") He may have increased his safety, however, by decreasing hers. And that would be unethical.

If they could not simply surrender the car and if she could not join him in flight, your cousin's options were limited. Had he spotted a cop nearby, he would have been right to increase his girlfriend's danger momentarily to greatly raise the odds of saving her and himself. But that was not so. And his few minutes' absence was a long time to abandon her to the tender mercies of the carjackers.

I'm reluctant to be hard on him. Few of us would know what to do at such a moment, and it's unclear that he could have protected her had he remained, but I believe he made the wrong decision. Its happy outcome was the unpredictable result not of his being prudent but of the carjackers being jittery.

UPDATE: Cousin and girlfriend have since broken up.

The Ethicist, New York Times Magazine, July 9, 2006

Claiming an abandoned bicycle

A bicycle locked to a pole near my house was untouched through the fall and winter. When spring came, I balanced the lock so it would be in a different position if the bike were moved. It wasn't. Eventually I broke the lock and now ride the bike almost daily. Was it ethical to steal something that had clearly been abandoned by its owner? Kate Clifford, Philadelphia

It's not that it was ethical to "steal" it; you didn't steal it. You claimed abandoned property, and no reason not to.

The trick is determining if something is in fact abandoned. There are an awful lot of cars stashed by the curb with nobody near them. To your credit, you showed due diligence. You observed the bike for nearly a year and used a cunning spy-movie trick to see if it had been ridden when you weren't around. (I trust you went home now and then, at least to shower and sleep.) And all city dwellers know that bikes are sometimes leashed to poles and left to fend for themselves. What's more, you did your neighbors a service by removing what had been a nuisance.

Here in New York, the police respond similarly to complaints about an abandoned bike. In some precincts, according to Noah Budnick of Transportation Alternatives, "if the bike is damaged or shows signs of obvious disuse, the police will tag it with a notice saying that the bike will be removed in two weeks if it is not moved. After two weeks, the officers return, usually with Department of Sanitation agents, and if the bike is unmoved, they clip the lock and cart the bike away." In this, they and you act ethically.

The Ethicist, New York Times Magazine, July 9, 2006

Dealing with a deadbeat client

After I worked for months as a management consultant, my client became increasingly hard to pin down for payments due. I then withdrew, halfway through the project, for lack of funds. May I recoup some of my costs by using material I produced for him for future clients? May I share documents he provided, even if they might contain confidential information? (We have no nondisclosure agreement.) Anonymous, Montreal

You must respect the business secrets of even a deadbeat. Confidentiality is not contingent on pay but is a component of honorable conduct -- without which it would be tough to work with one another -- and not only a contractual obligation but also an expression of ordinary virtue.

Those parts of your work that do not impinge on this tightwad's privacy are yours to recycle. Marketing plans, supply-chain management schemes, hors d'oeuvre ideas for a sales rep's retirement party -- many of these are generally applicable and may be proffered to future clients.

The one person who may not use any of your work is the schnorrer himself. Similarly, if you had agreed to sell him your car and he refused to pay for it, he could not use it to drive to the mall to buy a lot of stuff he won't pay for.

The Ethicist, New York Times Magazine, June 18, 2006

Dividing something fairly

Game Theory deals with algorithms for getting what you want when dealing with other, usually antagonistic, people. I came up with a particularly clever game theory algorithm when living with a roommate and we had to divide something evenly (usually food). The algorithm which we agreed upon is: one person divides the food, the other person gets to pick first. It's in the first person's best interests to divide the food evenly, so that there's no bigger piece for the other to pick. If both pieces are equal-sized, there's no advantage to picking one or the other, and everything's fair.

Buying foreign stamps

Jen just got back from England and told me about her experience trying to mail a letter to the States. According to her, the postal workers were not very helpful and couldn't tell her what kind of stamp she needed (this strikes me as odd, since that's their job, but we'll go with this story). She got nowhere, and ended up leaving without mailing the letter. Dave suggested this algorithm: Say, okay, give me a 5 pound stamp (about 10 dollars). They would say, that's way too much. Okay, give me a 4 pound stamp. Repeat until they say, that's probably not enough, and then buy the previous stamp. Reminds me of:

Figuring the load limit of a bridge

Calvin and Hobbes:

C: How do they know the load limit on bridges, Dad?
D: They drive bigger and bigger trucks over the bridge until it breaks. Then they weigh the last truck and rebuild the bridge.