March 2010


This is a continuation of the story of Sally who received a kidney transplant in September, 2009. The story is told by her husband, Greg. [The couple’s first names have been changed at their request.]

“Last night Sally received a call at about 9:20 pm to report to Swedish Hospital in Seattle. Some of you have known from past conversations that she is a kidney dialysis patient. She had to go back on dialysis in August, 2003, after her first transplant failed from chronic organ rejection after 11-1/2 years.

“There have been many emotional roller-coasters for us these past 4+ years, as she has been called in on several prior occasions (I think 8 times), admitted to the hospital, had a dozen tubes of blood taken each time for testing, only to be told after a 10 to 12 hour wait, ‘we’re sorry, but the cross-match test results did not work in your favor.’ This time the results were negative. A negative cross match test is a great result, because it means that her immune system will not respond too vigorously to antigens present in the donor kidney. This was her major hurdle to get past. They still needed to harvest the kidney from the donor and physically inspect it to make sure that it was in good condition.

“I am very happy to report that she went into surgery a few hours ago to receive this donated kidney. The operation is expected to last another couple of hours. I think she will be out of surgery sometime between 6:00 to 7:00 pm this evening. It is now 4:20 pm. I’m not sure how long it will be before she is alert enough to hold a conversation. I’m in the waiting room right now. My request to anyone who feels so inclined is to please say a prayer for Sally that there will not be an acute rejection and that she will fully recover. Despite the very sensitive screening tests that they perform, there is still a risk of rejection either immediately, or within a few days or weeks. Once one gets past a month or so, the chances of an acute rejection go way down.”

****

Greg continues the story a few hours later.

“Sally’s surgeon is William Marks, MD, PhD, the medical director at Swedish’s organ transplant program. He finished the operation at about 7:50 pm and then came up to the room to talk with me. He says that it may take up to a month for her new kidney to ‘wake-up’ and start fully functioning. The donor was not yet brain-dead when his/her family decided to donate the organs. Protocol requires that the transplant team wait until the heart stops beating before they can start recovering organs for transplantation. There is some period of time–I’m not sure how long–when the kidneys have no blood circulation and begin to shut down. However, Dr. Marks is confident that the kidney will recover now that it is getting adequate blood flow from Sally’s circulatory system. Sally will need to remain on dialysis until her new kidney starts functioning with enough output.

Marks

A tired but smiling Dr. William Marks after the successful surgery. Photo by Greg

“Sally and I don’t know anything about the donor at this point in time, due to privacy rules, other than the person was local to the Seattle area. It is our hope to be able to thank the donor’s surviving family members in person, sometime in the future, for their gracious actions during a time that must be very stressful for them.”

The third and final part of the story describes Sally’s post-surgery recovery process.

Technorati Tags:
Advertisements

I had dinner a few weeks ago with a group of Microsoft MVPs that were in town for an annual conference. I didn’t know any of them, but in the course of conversation, one of them asked another how his wife was doing. His response was that she was doing well; she had received a kidney transplant in September. Of course I wanted to hear more. Here’s the story of Sally as told by her husband, Greg. [The couple’s first names have been changed at their request.]

Sally received her first kidney transplant in 1992, after being on dialysis since 1985. Her first kidney was not a perfect match; she was told that it would likely last for only 5 years if she accepted it, which she did to get off of dialysis. It ended up lasting for about 11-1/2 years. During this time, she was healthy enough to purchase and operate two small restaurants, one in Philadelphia, and later one in Renton, Washington. In late 2000, she decided to sell her restaurant and pursue a lifelong dream of earning a college degree. She earned an Associate degree at Bellevue Community College in Information Technology with a high GPA. Afterwards, she enrolled in the accounting program at Central Washington University. However, in 2003, she suffered chronic organ rejection and returned to dialysis therapy while waiting for another kidney. Despite this setback, she stayed in school and graduated in 2005. In fact, she was one of ten people invited to apply to be the graduation speaker. And out of the ten, she was selected. Her speech is reproduced below.

“Earning a BS degree in Accounting means a lot to me. Not only have I earned a degree at the age of 50, but my success can serve to encourage other students who must battle physical disabilities.

“I may look perfectly healthy standing here in front of you today. In fact, my kidneys totally failed in August, 2003. Just walking to class, or up a flight of stairs, was very difficult. I had to start on hemodialysis. It was my second quarter at Central and I felt desperate. I asked God “Why me?” many times.

“Instead of feeling sorry for myself, I decided to pursue a degree as I intended. There have been many health related obstacles along the way, during these last two years.

“However, I managed it with the help of the wonderful Professors at Central, the staff at the Northwest Kidney Center, and the loving care of my husband, Greg. Thank you to all of you, from the bottom of my heart.

“Many people may wonder why anyone would attempt to earn a college degree at the age of 50. First of all, I didn’t have a chance in South Korea, where I was born and raised.

“With six other brothers and sisters to provide for, my parents had to struggle just to survive. I’ve dreamed of earning a college degree all my life. With hard work and determination, I have finally reached this goal.

“I believe that I am still young and have lots of potential to make a difference in my community. I hope each of you feels the same way about yourselves.

“If anyone hesitates to pursue a college degree because of their age, ethnicity, physical handicap, or other perceived difficulties, let me serve as a role model by encouraging them to pursue their dreams.

“The curriculum at Central has helped teach me to communicate effectively. In the 21st century, communication is one of the most important skills in any field. As a shy person all throughout my life, it amazes me to see myself giving a commencement speech in front of you. The training I have received at Central helps me to feel confident in myself and my area of specialization.

“A BS degree in Accounting is just a beginning for me. My plan is to pass the CPA exam, pursue a Master’s Degree, and further my education with on-the-job experience. One day, I hope to return to school as a teacher, so that I can share my knowledge and life experiences with my future students.

“I wish each of you much luck and happiness in the pursuit of your careers.

“We made it!”

At the end of her speech, she raised her right arm with a fist above her head and the graduating class immediately erupted into a roar of approval and standing applause for her and for themselves.

Part 2 describes the day of the transplant surgery.

I began my investigation of kidney matching software after receiving an email from my friend Carol Borthwick, who runs Qean Medical. Last year she sent me a link to a video from DEMO 09 for an innovative transplant matching program called Matchmaker from Silverstone Solutions. The software allows a clinician to compare the HLA profiles of patients with available donors. I contacted the firm, but have not received a response as of yet. My main question is how does this clinician-level view integrate with the national-level matching algorithms used by the large kidney exchanges and UNOS. My guess is it doesn’t. The inability to integrate with these databases may limit the market for this product.

Silverstone

Silverstone Matchmaker demo. Video still from DEMO 09.

****

I also found an electronic database and alert system from Transplant Connect. This company’s product helps organ procurement organizations (OPO) manage their caseload and quickly communicate deceased donor information to participating hospitals. The software supports the UNOS-designed xml schema for offering donor tissue and organs called DonorNet 2007.

[Update: Silverstone has a new product called MatchGrid. It is featured in a story in the Wall St. J. Apr 2011. The story in the Wall St. J. occurred after a 5-way kidney swap that is the basis for a 3-part Apr 2011 blog post.]

[Note: I’ve had a major revision in thinking about solutions to the O blood type problem. This blog post is no longer valid and will be replaced by a new one soon.]

Yesterday’s blog post showed that there is a shortage of O blood type kidneys for the patients who need them. There are two possible short-term solutions. One is to increase the number of altruistic O type donors in the exchange. The other is to encourage patients who are paired with an O type donor, but are not O type themselves, to enter the exchange.

Encouraging people with O blood type to become altruistic donors is not a solution

If you ever donate blood, you may be aware that blood centers are always asking for volunteers who are O- blood type. That’s because their blood is least likely to elicit an immune response from the recipient (assuming the recipient does not have high levels of HLA antibodies). Although people with O- blood constitute less than 10% of the U.S. population, I presume there are some who donate very frequently and that as a group these volunteers provide a significant proportion of the blood supply. Having lots of extra O- type blood available ensures there will never be a shortage of blood for patients with O type blood who need it.

This strategy cannot work for kidneys because a kidney donor can only donate once. This means people who are inclined to donate a kidney will do so and leave the pool. Currently, the annual number of altruistic kidney donors in the U.S. is about 200, so the number of O donors (both RhD+ and -) is under 100. To fill the current O type kidney shortfall would require about 4,000 one-time volunteers a year (this includes both the exchange and the UNOS waiting list). The number of altruistic donors is growing rapidly, but great effort would be needed to encourage a forty-fold increase in the number of healthy O type adults to donate. At some point this could lead to coercion. (For a taste of what a world dependent on “special people” could be like, read Kazuo Ishiguro’s novel, Never Let Me Go.)

Encouraging matching pairs to volunteer to enter the exchange is not a solution

There is a ready source of O type kidney donors, at least for exchanges. They are the donors in matched pairs. Currently, matched pairs never enter the exchange and may not even be aware that an exchange exists. Even if they are knowledgeable about exchanges, they would never consider participating in one because they have no need.

Further, it would be unethical to ask these matching pairs to enter into the exchange for the sole purpose of helping strangers get a match. We would be asking them to delay their transplant surgery in order to apply to the exchange, wait for a match to occur, and undergo additional compatibility testing. Then we would ask them to break an emotional bond between the pair. The recipient would have to take a kidney from a stranger and the donor would have to give a kidney to a stranger. The donor may back out of such an arrangement, leaving both recipients without a kidney. In return for their effort, the volunteering matched pair gets nothing in return (except the knowledge they’ve improved the life of a stranger). This would definitely not meet the ethical requirement of not harming patients either medically or psychologically.

Getting matched recipients to want to enter the exchange for their own benefit can work

Patients in unmatched pairs enter the exchange pool because they will never be worse off (they can exit the pool with the same donor they entered with at any time) and potentially better off (they can trade to get a match). They join the exchange to improve their lives.

There may be a way we can promise the same benefit to patients in a matched pair. That is, even though they match now, they may be willing to enter the exchange pool if there is a potential of finding someone who is a better match than their current partner. If no better match is found they can exit the pool at any time and continue with the transplant with the original donor.

This better match comes in the form of HLA compatibility. In the calculations of matching probabilities shown in yesterday’s post, we ignored HLA compatibility. Now we want to reintroduce it. As explained in an Oct 2008 blog post, there are 3 pairs of HLA genes that most strongly affect organ rejection. The benefits of finding a donor whose 6 HLAs are a subset of the recipient’s (called a 6-HLA match) are substantial. Getting a transplant from this donor can result in lower dosage of immunosuppressant medication. This will potentially leave the recipient’s immune system stronger, making them more resistant to infection and some cancers. A 6-HLA match kidney will also reduce the chance of organ rejection. Finally, if the recipient does require another transplant in the future, it will be easier to find a match since they will have developed fewer HLA antibodies.

It isn’t enough to promise patients a trade that produces a donor with a slightly lower level of HLA incompatibility; it has to be significantly better with proven medical benefits. Otherwise, we will be asking them to accept an exchange with a pair of strangers for the primary purpose of helping the strangers. Current research indicates that for patients who do not have any HLA sensitivity, a live transplant from a 4- or 5-HLA match doesn’t lead to significantly better results than one from a 1- or 2-HLA match. Thus, it may be necessary to restrict splitting of matched pair to cases only where a 6-HLA match is found.

Finding a 6-HLA match by chance is highly unlikely. So unless the donor is a sibling of the recipient, the donor-recipient pair are unlikely to be a 6-HLA match. Thus, if the recipient wants to find a 6-HLA match, their best bet to find one may be to enter the exchange pool.

Modification to existing matching algorithms

In the previous models for kidney exchange there was only one class of trader. All were looking for a minimum acceptable match. However, recipients (or their medical providers) hold private information regarding the advantages of seeking a 6-HLA match. They may decide that waiting for such a match will produce a better outcome (or greater utility to use economic parlance) than a shorter wait for a minimum acceptable match. It isn’t certain what proportion of kidney patients would enter the exchange for a chance to find a 6-HLA match. But my guess is that if the matching process was run once every two weeks or more frequently, then a large proportion would be willing to try it. I know that I would.

An article in Management Sci. Nov 2006 (subscription required) shows how using multiple queues, each with a different quality of organ and with longer waits for higher quality organs, can improve the allocation of cadaver organs. A similar approach can be used to encourage matched pairs to enter a kidney exchange.

In the proposal stated here, there will only be two queues available, one to get a minimum acceptable match and another to get a 6-HLA match. All participants would be told what the expected waiting time for each queue would be and could exit at any time. Patients with an unmatched donor may enter either queue. They could also switch queues at any time. Patients with a matched donor would only enter the second queue. There would be a constraint set so that traders in the second queue would never get split unless a 6-HLA match is found for the recipient. Toumas Sandholm of Carnegie Mellon University who has studied kidney exchanges and has been mentioned in this blog previously has proposed arrangements similar to this.

There are two ethical benefits from adding a separate queue to accommodate matched pairs in an exchange. First, all donors can be informed early that there is a chance that may not donate to recipient they are paired with and instead will enter into an exchange. Currently, donors are generally not informed of the existence of an exchange at the time they volunteer to be a donor. They may be surprised later to learn that the patient wants to enter an exchange. They may not want to donate to a stranger but feel an obligation to continue with the donation. Informing them early that there is a likelihood of entering an exchange allows them to decide if  they want to donate before they make a commitment and avoid anxiety and coercion later.

Second, the separate queues allows healthcare professionals and community outreach volunteers to inform all patients and potential donors of the benefits of an exchange. Under the current single queue exchange, matched pairs should not be informed of exchanges, much less encouraged to participate. The simple act of informing them about the exchange option would reveal a bias in favor of them. [Disclosure: I plan to become a community outreach volunteer after I complete my kidney donation and would like to be able to encourage matched pairs to enter the exchanges.]

Before a recommendation can be made to the kidney exchanges to add a second queue, evidence has to be provided that it will actually help patients in matched pairs find better kidneys. This would require simulations of two-queue exchanges to be conducted using generated data. I believe this is a promising avenue of research. With positive simulation results in hand, the National Kidney Registry, Alliance for Paired Donation, and UNOS could be persuaded to add a queue for matched pairs and help solve the shortage of O kidneys in exchanges.

[Update: There is a discussion of altruistic matched pairs in the Nephr. Times Feb 2010.]

[Note: This blog post contains two errors. First, Rh factor antigens do not form a heavy coat on solid organs like kidneys. They only do so on red blood cells. Thus, they do not strongly affect tissue compatibility or cause organ rejection.

Second, there are two forms of the A blood type, called Type A1 and non-Type A1. Some patients with Type O have low levels of A antibodies and can accept a kidney from a non-Type A1 donor. Similarly, some patients with Type B can accept a kidney from a non-Type A1B donor.

I will write an updated blog post to replace this one.]

Previous blog posts discussed kidney exchanges and how to improve outcomes by using exact matching and by adding a look-ahead feature. However, there is a fundamental problem with the current composition of traders (kidney patients and their donors) in the exchange that makes it impossible for everyone who enters the exchange to find a partner, no matter how good the software is or how long they wait. There is a solution to this mismatch problem. But first we need to understand why this problem occurs.

Not all pairs enter the exchange

Let’s develop a model of which recipient-donor pairs will enter the exchange and which will not. First we need to define what a match is. We define a match as being blood type compatible and human leukocyte antigen (HLA) compatible. For simplicity, we will ignore HLA compatibility for now. Table 1 below shows the probability that a donor’s kidney will match a recipient. Most of the cells in the table either have a value of 1.00 (shaded green) meaning that donor’s kidney will always match the recipient or 0.00 (unshaded), meaning it never will. The cells in the lower left quadrant with value 0.94 (shaded yellow) indicate the donor’s kidney will usually match, except for a woman who has RhD- blood type and has had a child with RhD+. She will now have antibodies to RhD+ antigens and cannot accept a kidney with RhD+ antigens.

Several assumptions are made in creating this table, as shown in the footnote below the table. As stated above, the most significant is that it ignores HLA sensitivity. About 45 percent of kidney patients have antibodies for foreign HLA. The most common causes are repeated injections of blood-derived EPO as a part of dialysis treatment or from a previous kidney transplant. Women with three or more children with the same father often develop HLA sensitivity as well. HLA sensitivity reduces the chance of a match for the individual and for the recipient population as a whole.

 Table 1. Probability of organ match*

Donor

100.0%

Total

37.4%

35.7%

8.5%

3.4%

6.6%

6.3%

1.5%

0.6%

Total

O+

A+

B+

AB+

O-

A-

B-

AB-

Recipient

37.4%

O+

1.00

0.00

0.00

0.00

1.00

0.00

0.00

0.00

35.7%

A+

1.00

1.00

0.00

0.00

1.00

1.00

0.00

0.00

8.5%

B+

1.00

0.00

1.00

0.00

1.00

0.00

1.00

0.00

3.4%

AB+

1.00

1.00

1.00

1.00

1.00

1.00

1.00

1.00

6.6%

O-

0.94

0.00

0.00

0.00

1.00

0.00

0.00

0.00

6.3%

A-

0.94

0.94

0.00

0.00

1.00

1.00

0.00

0.00

1.5%

B-

0.94

0.00

0.94

0.00

1.00

0.00

1.00

0.00

0.6%

AB-

0.94

0.94

0.94

0.94

1.00

1.00

1.00

1.00

*The following simplifying assumptions are made: 1) Blood type distribution is for U.S. only, all races combined; 2) Probability of having end-stage renal disease (ESRD) is independent of blood type; 3) All recipients have AB blood antigen sensitivity to non-matching blood types; 4) Non-match due to HLA sensitivity is ignored; 5) 40% of recipients are adult women who have had at least one child (if mother is RhD- and father is RhD+, then she will be incompatible with an RhD+ donor); 6) Recipient and donor blood types are independent (i.e., donors are not related to recipient, which would make them more likely to match, and donors to adult women with children are not the spouse, which would make them less likely to match); 7) Recipients stay with their first choice donor regardless of match (i.e., if the first choice donor does not match, the recipient does not continue to search for a compatible donor in order to avoid entering the exchange)

Based on the table above, we can calculate the distribution of matched and unmatched pairs. Table 2 below shows that nearly two-thirds of pairs (total percentage in upper left) will match immediately and do not need to enter the exchange. However, it is useful to divide these matches into two groups. Cells shaded green indicate matched pairs that would not benefit an unmatched pair if they were to enter the exchange. Cells shaded yellow indicate matched pairs that could benefit an unmatched pair if they were to enter the exchange and swap with them. Notice the composition of the cells shaded yellow, they are mostly O donors.

Table 2. Distribution of matched pairs*

Donor

64.4%

Total

37.1%

16.3%

1.2%

0.1%

6.6%

2.9%

0.2%

0.0%

Total

O+

A+

B+

AB+

O-

A-

B-

AB-

Recipient

16.5%

O+

14.0%

0.0%

0.0%

0.0%

2.5%

0.0%

0.0%

0.0%

30.7%

A+

13.4%

12.7%

0.0%

0.0%

2.4%

2.2%

0.0%

0.0%

4.6%

B+

3.2%

0.0%

0.7%

0.0%

0.6%

0.0%

0.1%

0.0%

3.4%

AB+

1.3%

1.2%

0.3%

0.1%

0.2%

0.2%

0.1%

0.0%

2.8%

O-

2.3%

0.0%

0.0%

0.0%

0.4%

0.0%

0.0%

0.0%

5.1%

A-

2.2%

2.1%

0.0%

0.0%

0.4%

0.4%

0.0%

0.0%

0.8%

B-

0.5%

0.0%

0.1%

0.0%

0.1%

0.0%

0.0%

0.0%

0.6%

AB-

0.2%

0.2%

0.0%

0.0%

0.0%

0.0%

0.0%

0.0%

*Based on same assumptions as first table

The remaining pairs are unmatched and need to enter an exchange to have a chance of getting a match. Table 3 below shows the composition of these unmatched pairs. Cells shaded green indicate that all pairs can match another unmatched pair. These are A/B pair to B/A pair swaps or RhD- recipients who can swap for a RhD- donor. Cells shaded yellow indicate that some but not all pairs can match another unmatched pair. Finally cells shaded red will not match another pair in the exchange.

Table 3. Distribution of unmatched pairs*

Donor

35.6%

Total

0.3%

19.4%

7.3%

3.3%

0.0%

3.4%

1.3%

0.6%

Total

O+

A+

B+

AB+

O-

A-

B-

AB-

Recipient

20.9%

O+

0.0%

13.4%

3.2%

1.3%

0.0%

2.4%

0.6%

0.2%

5.0%

A+

0.0%

0.0%

3.0%

1.2%

0.0%

0.0%

0.5%

0.2%

3.9%

B+

0.0%

3.0%

0.0%

0.3%

0.0%

0.5%

0.0%

0.1%

0.0%

AB+

0.0%

0.0%

0.0%

0.0%

0.0%

0.0%

0.0%

0.0%

3.8%

O-

0.1%

2.4%

0.6%

0.2%

0.0%

0.4%

0.1%

0.0%

1.2%

A-

0.1%

0.1%

0.5%

0.2%

0.0%

0.0%

0.1%

0.0%

0.7%

B-

0.0%

0.5%

0.0%

0.1%

0.0%

0.1%

0.0%

0.0%

0.0%

AB-

0.0%

0.0%

0.0%

0.0%

0.0%

0.0%

0.0%

0.0%

*Based on same assumptions as first table

Table 4 below shows the distribution of unmatched pairs after the exchange. Cells shaded red contain unmatched pairs. Notice that even after the exchange, over one-fourth of recipient-donor pairs are left without a match. And notice the composition. About 92% of these remaining pairs include a recipient with O blood type. There are only two short-term solutions to resolve this mismatch. One is to encourage more people with O blood type to step forward and become altruistic donors (unfortunately, an unlikely behavioral change and one with ethical issues). The other is to encourage the mirror image matched pairs (yellow cells in Table 2) to enter into the exchange pool to facilitate a swap. (Notice also that donors with type AB blood, like me, also have difficulty finding a match.)

Table 4. Distribution of unmatched pairs after exchange*

Donor

26.8%

Total

0.1%

15.8%

3.7%

3.3%

0.0%

2.6%

0.6%

0.5%

Total

O+

A+

B+

AB+

O-

A-

B-

AB-

Recipient

20.8%

O+

0.0%

13.4%

3.2%

1.3%

0.0%

2.2%

0.5%

0.2%

1.4%

A+

0.0%

0.0%

0.0%

1.2%

0.0%

0.0%

0.0%

0.2%

0.3%

B+

0.0%

0.0%

0.0%

0.3%

0.0%

0.0%

0.0%

0.0%

0.0%

AB+

0.0%

0.0%

0.0%

0.0%

0.0%

0.0%

0.0%

0.0%

3.8%

O-

0.1%

2.4%

0.6%

0.2%

0.0%

0.4%

0.1%

0.0%

0.4%

A-

0.0%

0.1%

0.0%

0.2%

0.0%

0.0%

0.0%

0.0%

0.1%

B-

0.0%

0.0%

0.0%

0.1%

0.0%

0.0%

0.0%

0.0%

0.0%

AB-

0.0%

0.0%

0.0%

0.0%

0.0%

0.0%

0.0%

0.0%

*Based on same assumptions as first table

The disadvantage that patients with O blood type face in getting a kidney has long been known. UNOS data shows they typically wait 20 months longer than patients with A blood type for a kidney transplant (some with HLA sensitivity wait for over 100 months) and thus are more likely to die while waiting for an organ. Many in the transplant community are advocating a change in the way cadaver organs are allocated to overcome this problem. For instance, see Nephrology Dialysis Transplantation Jan 2010 (subscription required) for proposed changes in Europe. Eventually, the same pressure may come to bear on the issue of who can and who must enter an exchange.

In the next blog post, I will propose a way out of this dilemma. The solution involves making matched pairs want to enter the exchange for their own benefit.

[Update: The proportion of kidney patients with antibodies to HLA is 45%, not 20% as originally stated.]

A Mar 2010 blog post explained how kidney exchanges can increase the number of patients who receive a live donor kidney. It also described how computers can find better (in fact, optimal) matches compared to random or arbitrary assignment of matches. This is all good. However, we can do even better. We can add a temporal dimension to the optimization decision.

In the exchange models described in my previous blog, it was implicitly assumed that the exchange would only be run once. However, in the real world, new traders (patients) enter the exchange daily (and unfortunately existing patients may be removed due to death). So the matching algorithm should be run repeatedly, not just once. A couple of questions arise when there are multiple rounds of matching. How should the matching algorithms described earlier be modified to ensure the maximum number of matches over time? And how often should the matching algorithm be run?

If all matches found in a round are allowed to exchange, then the pool of remaining traders will be depleted, leaving only the hardest to match patients. This means any new pair(s) entering the exchange the next round will be unlikely to find a match. If our goal is to maximize the number of matches over time, we may need to hold back some pairs each round in order to seed the next round.

However, we don’t know a priori the blood type and HLA type of the new donors and recipients to the exchange in any future round (that is, the composition of entrants is stochastic). However, we can model them using the historical medical data available on all previous donor/recipient pairs that have entered the exchange. Similarly, the pairs exiting the exchange between rounds is also not known, but it can be modeled based on historical data on the health and age of previous patients and donors who exited the exchanges.

Since the exact composition of traders in the next round is not known, our optimization technique needs to be probabilistic. Any model where the outcome of a given round is a result of a combination of random inputs and user decisions is known as a Markov decision process. There is plenty of previous research into these models that we can build on.

In an article in Intl. Joint Conf. on Artif. Intel. 2009, Tuomas Sandholm, who was one of the developers of the exact matching algorithm described in my previous blog post, and his coauthor tested models by varying three parameters for multi-round exchanges: sample size, look-ahead depth, and batch size.

Sample size is the size of a subset of the current traders in the exchange to be examined. A sample is used rather than the entire pool to reduce computational effort. The smaller the sample size, the faster the match can run, but the less accurate the result. Look-ahead depth is the number of future rounds to look at. As the number of future rounds examined goes up, the number of possible outcomes grows exponentially, as does the computing effort needed to explore them.

Batch size is the number of new pairs entering the exchange before the matching algorithm is run. Ideally, a match could be run every time a new pair enters the exchange. However, this won’t be practical if lots of pairs enter every day, as could happen is a unified national exchange. Further, a larger batch size also increases the chance of a match, just like a larger pool does. So using a larger batch size reduces the need to use look-ahead to estimate matches for future rounds. For the paper, the authors used batch sizes between 10 and 20, which they translated to a matching round every 1 to 2 months.

(Currently, the various kidney exchanges run their matches on a fixed time schedule rather than when a certain batch size is reached. This helps the participating hospitals know when they can expect matching data to be delivered. Although recipient/donor pairs enter and exit the pool at indeterminate intervals, their numbers per fixed time period can be estimated, if necessary, using the Poisson distribution.)

The paper reports results using both real data and generated data. For generated data, it found good results were obtained with sample sizes between 10 and 50 and look-ahead depths between 10 and 20 rounds. As can be seen in the figure below, in the early months, the single round algorithm (called offline-based) makes more matches than the multi-round algorithms (called 1 and 2), as would be expected since the multi-round algorithms withhold some trades. But after about 5 months, the multi-round algorithms catch up. After about three years of simulated matches, the multi-round approaches are way ahead and save about 6.5% more lives (about 13 patients in this study) compared to the single-round method.

MultiroundComparison

Image from Intl. Joint Conf. on Artif. Intel.

Thus, by holding back some matches today, we can improve matches tomorrow, which will save more lives. This is true even though the multi-round algorithm provides an approximate solution, rather than an exact optimum solution that the single-round solution does.

Note that none of the kidney exchanges are currently using this multi-round optimization model. And it is easy to see why. It isn’t ethical to run an experiment on real patients where some will be withheld a chance at a match today in the hope of saving some other patient’s life at some future date. As noted in the prior blog post, the two major kidney exchanges and the UNOS pilot program are all using the exact single round algorithm.

On the other hand, even if we can’t justify multi-round optimization by saying it saves more lives, perhaps we can justify it by saying it shortens the average waiting time for a match. That’s because even though some people in the early rounds have to wait a bit longer for a match, most of the entrants in later rounds have a shorter wait. The paper doesn’t report differences in average wait times, but it would be easy to calculate.

Another way to encourage adoption of the multi-round algorithm would be to run a comparison between the results of the multi-round algorithm and the single round algorithm at each step and find the patients who are left out by the multi-round algorithm. We can give these traders a greater weight in the next round to reduce the chance that they end up waiting more than a few rounds.

In my next blog post, I will discuss the problem of O blood type patients. Then I will propose a way to modify kidney exchanges to help them.

by George Taniwaki

Time series data are hard to display in a way that shows other relationships. That’s because one generally uses a static 2-dimensional chart. The x-axis is used to display time, leaving only one other axis to show another variable. The display can be greatly enhanced by using animation. Time can flow while the x and y axes can display relationship data or geographic data. This can aid in understanding how relationships vary over time.

Last week, Google announced the release of Google Public Data Explorer. This web-based data visualization tool (because all Google tools are web-based) takes time series data from public sources and provides a way to create animations. Data Explorer allows you to create line charts, bar charts, maps and scatterplots from web data. It has a pretty clear interface to change the axes. For scatterplots you can also change the color and size of the data points.

Google’s animated trend charts are based on technology called Trendalyzer it acquired in 2006 from Gapminder, a nonprofit foundation in Sweden. I mentioned Gapminder in a 2008 blog post that has been accidentally deleted.

Below is an example scatterplot I created using World Bank data for fertility rate by life expectancy worldwide by country. The data covers 1960 to 2007. First note that in 1960, there was a strong correlation between high fertility rate and low life expectancy. Also note the strong correlation between high income and high life expectancy. Many researchers have shown that women are likely to have more children if they fear that some of the children will not grow to adulthood. Note the one outlier among the high income countries that in 1960 had low life expectancy (54 years) and high fertility (5.7). That country is South Korea. If you play the animation, you can see Korea move down and to the right over time.

FertilityByLifeExp

Country fertility rate by life expectancy. Image by George Taniwaki

I’ve marked a few countries that display unusual behavior over time. China is an interesting outlier because in 1960 it was poor with a low life expectancy, but also with a low fertility rate. But if you play the animation, you see that this may have been a statistical anomaly because in 1962, the fertility rate jumps to 7.5. The fertility rate rapidly falls to under 3 as the one-child policy takes effect and continues to fall below the 2.1 replacement level in the 1990s. Rwanda, Timor-Leste, and Cambodia show short, horrifying drops in both life expectancy and fertility during genocide campaigns. Guinea-Bissau shows large fluctuations in fertility rate without a corresponding change in life expectancy. I can’t explain it. The country is very poor and perhaps its health statistics are unreliable, though this is true for many other countries. Lesotho and Zimbabwe are poor countries with high levels of HIV infection and AIDS that are causing both fertility rates and life expectancy to fall. The AIDS epidemic is taking a toll even on wealthier countries like South Africa.

Below is another scatterplot I created showing population by income in the U.S. by state. I would have liked to have shown income by education, city/rural ratio, or some other correlated variable, but no such variable was available in the dataset. I use log scale for population since there is such a large range in state size. I also use a log range for income because the data is not adjusted for inflation and I want the data range to show the change in income dispersion over time.

PopByInc

State population by income. Image by George Taniwaki

One of the most surprising things about the chart is that over the 40 years the rankings of state incomes doesn’t vary much. In 1969 the poorest state was Mississippi, and all the poorest states were in the southeast census region. If you play the animation, you’ll see some horizontal reordering, but not much. Even fast growing states like Nevada and Arizona don’t change order. They shoot up, but their income ranking doesn’t move much. Same with states with falling populations like Michigan and Ohio. The only exceptions are small states and districts like Hawaii, Alaska, and Washington DC. They zip around like flies. And maybe that explains why the data doesn’t move much. State level data is too coarse and it would be better to see data for the 100 largest cities or some other finer geographic region.

****

About a year ago, my friend Steve Duenser pointed me to a couple of nice animations by FlowingData that shows the growth of Target and Wal-Mart. The animations use Modest Maps, a Flash-based mapping tool.

By an odd coincidence, the three biggest discount store chains, Wal-Mart, Target, and Kmart, all started in 1962 which makes a time series comparison of store openings easier. Target is headquartered in Minneapolis and slowly began to expand throughout the U.S., jumping to large metropolitan areas. Wal-Mart grew much more quickly, but was invisible to most people because it concentrated on rural areas near its headquarters in Bentonville. It blanketed the southeastern U.S. before its steady expansion to the rest of the country. The videos showing geographic distribution make the different growth strategies more easy to observe than a tabular list would. It would be even more obvious if the two animations were combined to show overlays.

Target

Walmart

Target vs Wal-Mart. Images from FlowingData

****

Finally, my friend Carol Borthwick pointed out an interesting way of visualizing Twitter feeds across both time and space. An interactive map was shown in The New York Times after the Super Bowl last year. It’s a fun chart and makes you realize that there’s a lot of data on the web that’s just waiting to be mined. Unfortunately, there is no story indicating how the data was collected and organized, what tools were used, or how you can make your own Twitter charts.

SuperBowlTwitter

Map of Popular Twitter comments in real-time. Image from New York Times

[Update: I added a paragraph stating that Google’s animated trend charts are based on technology it acquired from Gapminder.]

Next Page »