Is every computerized matching system an optimized one? No! Computerized matching simply means that a computer is used to process some or all of the data regarding the kidney donors and recipients. There are two steps involved in matching for kidney paired donation:
- (1) determining whether any two pairs could exchange kidneys, which is equivalent to drawing all of the edges between nodes in a graph, and
- (2) deciding which of the possible exchanges should actually take place, which is equivalent to choosing which edges from the graph which will enable the most and best kidney transplants.
Because a national kidney paired donation program would likely involve a large number of people, a computerized matching system which stops at step (1) would provide a very long list of possible matches. Choosing haphazardly from that list might deny kidney transplants to a number of patients. It is essential that a computerized matching system optimization system complete step (2), to choose carefully which of the possible matches should actually be transplanted.
The Optimized Match problem is formulated as a maximum edge weight matching, meaning that points are assigned to every edge (possible match) in the graph. Then, an optimized match selects the combination of edges which gets the most points while assigning each incompatible donor and patient to only one paired donation. There are many many possible combinations of matches for a pool of incompatible pairs - as many as 10^250 (yes, that's 1 with 250 zeroes!) for 1000 patients and their donors. Luckily, this problem can be solved very efficiently on a personal computer using a procedure based on the Edmonds algorithm.