Robin Rombach, Post-Gazette
Tuomas Sandholm is a Carnegie Mellon University computer scientist who specializes in game theory, which is often used to find the best solutions to problems when there are millions of alternatives.
As scientific discovery evolves, researchers in one discipline are increasingly entering other fields through a side door.
That is how Tuomas Sandholm ended up working on kidney transplants.
Dr. Sandholm is a Carnegie Mellon University computer scientist who specializes in game theory, which is often used to find the best solutions to problems when there are millions of alternatives.
He has already used those skills to start an international company, Combinenet, which has conducted 450 electronic auctions that have saved the companies involved nearly $4.4 billion.
The Thinkers
This monthly series will highlight people from Western Pennsylvania who are on the forefront of new ideas in their fields.
He has also developed what may be the world's best computerized Texas Hold 'Em poker program. It has defeated all the other computerized poker systems and several top human online players.
In 2004, he helped organize a game theory conference, and heard a speech there by Harvard University economist Alvin Roth, who had pioneered the use of computers in a new method of organ transplants known as kidney exchange networks.
After hearing the talk, the Finnish-born professor said, "it became clear to me that there were lots of interesting algorithmic issues to look at."
Algorithms are the recipes computer scientists use to solve complex problems, and in this case, the challenge of figuring out the best way to match up living kidney donors with potential recipients was an open doorway beckoning him into a new research field.
More than 71,000 Americans are waiting for a kidney transplant today, but only about 17,000 transplants are done each year.
Because people can get along with only one of their two kidneys, transplants from living donors are becoming increasingly popular. Last year, they accounted for nearly 40 percent of all transplants, according to UNOS, the United Network for Organ Sharing.
Many times, though, a kidney patient's friend or loved one is not a compatible match. That has led to a new approach known as paired kidney exchanges, in which one kidney patient's relative or friend will donate an organ to another patient, whose own relative or friend will donate his organ to the first patient.
The technique has spawned four kidney exchange networks in the United States, which together have signed up scores of patient-donor pairs who are matched periodically by computer programs known as optimization software.
Although fewer than 200 paired kidney exchanges have been carried out to date, experts say there is the potential to create a national database of almost 10,000 patient-donor pairs and do 2,000 such transplants per year.
When dealing with that many people, the different versions of existing software run into two major problems, Dr. Sandholm said.
One program can handle all 10,000 pairs, he said, but only for two-way exchanges.
A network will function much more effectively, though, if it also can arrange three-way and four-way exchanges as well, Dr. Sandholm said.
He demonstrated that by drawing an A-B-C grouping on the white board in his office, in which pair A donates a kidney to pair B, which donates a kidney to pair C, which donates a kidney to pair A. In that arrangement, he said, none of the transplants would occur if only two-way exchanges were possible.
There is another computer program that can arrange these larger exchanges within the 10,000-pair list, he said, but it runs out of memory after doing calculations on 600 to 900 pairs.
By creating an algorithm that attacks the matching problem incrementally, Dr. Sandholm said, his group has bypassed the memory constraint, and can now create the optimal number of compatible matches using all 10,000 pairs.
It's not a trivial challenge. Because each donor might match scores of potential recipients, a set of 10,000 patient-donor pairs could have as many as 1 trillion potential three-way exchanges, he said.
The Carnegie Mellon algorithm, which Dr. Sandholm developed with fellow professor Avrim Blum and graduate student David Abraham, is so new that it has only been in use for three months. It is being tested by the Alliance for Paired Donation, a voluntary kidney exchange network based in Toledo, Ohio.
So far, it has been used for one two-transplant chain in New Jersey, said the alliance's medical director, Dr. Michael Rees. In its most recent application, it has identified one potential four-patient chain and several smaller chains, but final tests on those patients and donors have not yet been completed.
Dr. Sandholm has high hopes for kidney exchanges, especially if the current voluntary networks can eventually be combined to create a national database, which would increase the odds of good matches.
"If you look at the trends in the [United States]," he said, "there are two possible solutions to the kidney transplant problem. One is that a whole bunch of people will start donating their kidneys upon death, and there's nothing suggesting that's going to happen.
"It's a pretty grim situation. Supply doesn't meet demand and the imbalance keeps growing. So kidney exchange is really the only way to do it."
Tuomas Sandholm first started programming computers when he was 13.
His father, part of the Swedish-speaking minority in Finland, was a pharmacology and toxicology professor, and his mother was a professor of the dental specialty of peridontology, both at the University of Helsinki.
He earned master's and doctoral degrees in computer science at the University of Massachusetts, where his major research project was inventing an artificial-intelligence negotiating system that divvied up trucking jobs.
After teaching at Washington University in St. Louis for four years, he left to form his electronic auction firm, Combinenet, and then joined the Carnegie Mellon faculty in 2001.
Like Pittsburgh's FreeMarkets Inc., bought by Ariba Inc. in 2004, Combinenet hosts online auctions between companies that want to purchase goods and services, and firms that want to sell them.
Rather than just seeking the lowest bids, though, Combinenet's software allows buyers and sellers to stipulate many other conditions, such as delivery time or meeting legal obligations, in an approach known as "expressive commerce," Dr. Sandholm said.
For example, if a major company seeks bids through Combinenet on all its trucking services for a year, it can use the firm's software to build the most efficient route system possible by reducing the number of "deadhead" trips that carry no cargo.
One side effect is that smaller firms with the right routes can get pieces of the delivery business when they might not have been able to compete if they'd been limited to bidding on certain packages of routes.
To date, Combinenet has done auctions for 50 of the top Fortune 1,000 firms.
While he can't claim the same real-world benefit from his Texas Hold 'Em poker software, it has provided interesting solutions for complex combinatorial problems.
In some ways, Dr. Sandholm said, Texas Hold 'Em is far more difficult for a computer to play than chess.
In poker, a player doesn't know which cards the other players are holding or what cards will be dealt in the future.
What the computer program can do in the face of such uncertainties is calculate a good strategy -- the probability of making such moves as raising the bet or folding, for instance -- for each hand it is holding.
Because it has to keep the other players guessing, though, the software will then use those probabilities to choose randomly among the moves at any given moment in the game, creating an electronic form of bluffing.
A good analogy, he said, is the game "rock-paper-scissors." To be successful in that game, a player should choose randomly among the three moves each time.
While the poker program, which Dr. Sandholm developed with graduate student Andrew Gilpin, is strictly recreational for now, it's hard to predict what other types of problems it may be able to solve in the future.
Ultimately, he said, he has one goal: "I choose my research topics so they will make the world a better place."
Tuomas SandholmAge: 38
Residence: Mount Washington
Position: Computer science professor, Carnegie Mellon University.
Education: Bachelor's and master's degrees in industrial engineering and management science, Helsinki University of Technology, Finland, 1991; master's in computer science, University of Massachusetts, 1994; doctorate in computer science, University of Massachusetts, 1996.
Previous positions: Founder, Combinenet Inc., electronic auction firm, 2000; professor, Washington University, St. Louis, 1997-2000; research scientist, Technical Research Centre of Finland, 1990-92.
Academic honors: Computers and Thought Award, International Joint Conference on Artificial Intelligence, 2003; Autonomous Agents Research award, Association for Computing Machinery, 2001.
Other awards: Windsurfing, first place, Finnish nationals; 12th place, world competition, 1987.
Books and publications: Seventeen book chapters and 33 articles in referenced journals.
First Published: May 7, 2007, 3:30 a.m.
