Random Thoughts, With Haifeng Xu

If you’ve ever met a human before, you know that they can be selfish, shortsighted, and generally bad at acting in their best interests. Drivers on a road rush for short term personal gain, leading to traffic jams that slow down everyone’s commute. Shoppers afraid of a bread shortage buy out the whole store, leading to an actual shortage.

Anyone working in a field that requires understanding how people will act know this well: no matter how foolproof a theory is on paper, we humans hear the term foolproof and say, “challenge accepted.”

Luckily, a Ph.D. student in USC Viterbi’s Department of Computer Science is using the tools of his field to help bring better stability to the world. Haifeng Xu recently won a 2017 Google Ph.D. Fellowship for his work with algorithms, optimization and markets. As part of the honor, two years of Xu’s Ph.D. funding will be covered by Google. What is it about his work that is so groundbreaking? It all comes down to randomness.

“I like algorithms because they are everywhere,” Xu says. “From sending rockets to space, to deciding which road to take to work – I love to think about the world algorithmically.”

---

By achieving carefully designed randomness in his algorithm, he’s made the real world less random for all the irrational humans who wake up every morning and live in it.

---

To better appreciate what’s going on, we need to understand two concepts related to his work: game theory, and asymmetric information.

Game theory is the science that studies a group of people’s decision-making. Game theorists use math to try to determine how groups with multiple potentially competing interests should interact with each other. To what degree should they cooperate and/or share information, and to what degree should they act more selfishly?

One of the major factors determining how people behave is asymmetric information.  That is, information that one player has access to and the others do not. The information someone has will obviously affect the decisions they make, so it’s important to understand how this plays into the theory.

Here’s one example of how asymmetric information could be applied to game theory: Google Maps helps people navigate in their cars every day. The app has access to all the information about where traffic is good, where it’s bad, if there’s an accident on a particular route, how many cars are on the road, and what directions they’re traveling in. Currently, Google Maps users have access to all that information, which leads to every driver trying to get their screaming kids to preschool on the same road, resulting in congestion.

But what if instead, the app restricted the amount of information each individual driver saw?  In this case, asymmetric information would be working in everyone’s best interest.  If a faster route became available, an algorithm could decide how many people, and at what rate, are re-routed in the new direction. Sometimes keeping people blissfully ignorant is the best strategy.

But asymmetric information can also be used to give one side an edge. This is most often the case in security systems, where Xu is focused.

Imagine an airline – let’s call it Viterbi Airlines – with thousands of flights a day all over the world. Viterbi Airlines has air marshals traveling on many (but not all) of its flights on any given day. Because Viterbi Airlines is the best in the business, security implements an algorithm to determine which flights, going to which locations, on which days, will have a marshal on board.  A good algorithm needs to balance two important factors: the security of each flight, and the unpredictability (randomness) of the air marshals’ schedules.

Of course, not all targets are equal. A jumbo jet flying from London to L.A. on Christmas day is a bigger target than a small flight from San Jose to Burbank on a Wednesday morning. If a terrorist identified a marshal on a particular plane from London to L.A., he/she might be able to infer what subsequent flights back from L.A. to London would be unprotected.

That’s a lot of balls – or planes – in the air to juggle at once. Previous algorithms have attempted to balance the randomness of air marshal security with the need to prioritize high value targets – but none have been as successful as Xu’s.

What Xu has done is build an algorithm that, in addition to prioritizing high value targets, achieves max entropy – the maximum amount of randomness possible. At the same time, his algorithm makes calculations extremely fast – an obviously important factor in the security world. When these two things come together, you have a truly unique algorithm with the potential to change an entire industry.

However information is shared, or not shared, the ultimate goal is to maximize social good while minimizing social cost; all while keeping the system stable. This is called “good equilibrium” and it is the job of the computer scientist to design an algorithm that achieves this goal.  When it comes to security, Xu might have the best algorithm around.

Creating an algorithm like this is no small feat. In all of security game theory, there are only a handful of efficient, entropy-maximizing algorithms.  And two of them were designed by Xu.  People may tend to think that building a strong algorithm is all about being great at math. But there are a lot of great mathematicians out there, so what makes Xu so good at writing them?

---

“Haifeng takes the principles and techniques of theoretical computer science and unleashes them on important real-world problems.” – Shaddin Dughmi

---

The first answer to the question is his perspective. “I think it’s important to be able to look at a problem from many different angles. I draw inspiration, ideas, and tools from many different fields,” says Xu. “Of course you have to have a deep understanding of what you’re doing, but you must also be exceedingly curious about other areas too – this is where a lot of creativity comes in.”

The second answer is his approach. “Once I have a concrete understanding of the problem and its challenges, I like to remove all the non-essential components and simplify the problem to its most fundamental form,” says Xu. “Then I try to develop an algorithm for this parsed down, fundamental form of the problem. I’ve found that in most cases, the algorithm for the simpler, fundamental problem or its underlying principles works just as well for the original more complicated problem.”

Xu’s two advisors, Shaddin Dughmi and Milind Tambe, have seen his unique skill set in action first hand.

“Haifeng has a rare combination of skills,” says Dughmi.  “Powerful abstract thinking to look at a real-world application and boil it down to an elegant and simple mathematical question, mathematical skill and training to then analyze the problem and develop an elegant algorithm, and the affability and communication skills to tailor those results back to the application in a way that makes his collaborators happy.”

Xu splits his time between Tambe’s Teamcore Group, which addresses real-world problems, and USC’s CS Theory Group, which focuses on broader theoretical/mathematical challenges.

“Haifeng takes the principles and techniques of theoretical computer science and unleashes them on the important real-world problems considered by Teamcore. In the other direction, he distills the challenges faced by Teamcore into theoretical and mathematical questions which are of independent interest to theorists,” Dughmi says.

Straddling the two worlds of theory and application so closely has given Xu a unique outlook on how to approach big challenges.

At the same time, Xu has been strongly influenced by the culture of both groups, which encourage students to work on algorithms that directly and positively help society. “In the future, I would like to examine whether game theory can be used to help with international disputes and how we can modify our algorithms to avoid them in the future,” says Xu.  “I also want to explore negotiation games. In particular, what kind of rules can lead to a negotiation equilibrium with optimal social welfare.”

It’s true that good algorithms can make industries more efficient, increase profits, and allow us to focus on challenges we never had time for before.

The beauty of a great algorithm is not that it prevents human error, but that it frees us to focus on the things that really matter to people. Less time in the car means more time spent with family before work. A more secure airport means less time and energy spent worrying about loved ones and more time enjoying life.

Xu’s algorithm does exactly this. By achieving carefully designed randomness in his algorithm, he’s made the real world less random for all the irrational humans who have to wake up every morning and live in it.