Matt Weinberg uses algorithmic mechanism design to keep websites credible, in spite of their users

By Doug Hulette

Try to cheat if you want - the system works anyway

Think about this: On an online-dating site, you link up with someone who sounds great but omits something egregious from her or his personal information; the truth emerges months later and smothers your nascent relationship. 

That’s just not cricket, and Matt Weinberg wants to do something about it. 

​
Photo by David Kelly Crow / Icons by Yannick from flaticon.com

Matt Weinberg, who joined the Computer Science Department early in 2017 as an assistant professor, believes the solution lies in algorithmic mechanism design, that is, ensuring that systems of all kinds — not just dating sites but such widely varied processes as auctions, cryptocurrencies like Bitcoin, and crowdsourcing — remain credible and accurate even when users may try to exploit them for their own purposes.

“Think about how often you see users manipulating a system to achieve their own goals: from health insurers who try to recruit healthy patients willing to pay high premiums, to online daters who manipulate their profiles in order to get more matches,” he says.  

The key is to make sure that the algorithms — the roadmap of rules that underpin calculations and other problem-solving processes in computerized systems — account for the humans using them, whose behavior we can’t hard-code like the system itself. Call it the intersection of computer science and the real world. 

“When real people interact with algorithms, they impose additional constraints beyond the algorithm’s speed, storage, and correctness,” Weinberg says. “For instance, real people have their own incentives that may misalign with the designer’s goal, and may therefore choose not to follow the intended use.” 

“Real people also behave more predictably in simple and transparent interactions, so this motivates formally considering the simplicity of algorithms deployed in these settings when measuring their quality.”

Weinberg completed his Ph.D. in 2014 at MIT. Before joining the CS faculty, he spent two years as a postdoc in Princeton’s CS Theory group, and two semesters as a research fellow at the Simons Institute at UC Berkeley.
 

In an email exchange, he talked about his dedication to mechanism design.

What does your typical project look like?

I’m a theorist, so a typical project first develops a mathematical model to capture user behavior, followed by an algorithm with provable guarantees even if the users manipulate the algorithm in their own interest. I don’t directly deal with data myself, but many of my projects are done in collaboration/consultation with domain experts like Princeton professors Mark Braverman, Nick Feamster, and Arvind Narayanan to make sure that our theoretical results actually provide useful guidance in practice. 

Why should people care about what you’re doing?

So many of the challenges with modern technology require mechanism design! In designing an online-dating platform, for instance, your goal might be to find the best matches for your participants. This is already a challenging problem touching typical CS areas like big data (how to process all the data reported by your participants), machine learning (how to predict the quality of a match given this data), and algorithms (use these predictions to make good quality matches, even as users join and leave). 
But there’s also a whole separate challenge: Your users don’t care about the success of your platform, they just want to find the best match for themselves! Depending on how you design your system, users may lie about their data to get more matches, or ignore your recommendations and just contact anyone of the target gender. So you have to not only solve these challenging CS problems but do so in a way that incentivizes your users to behave as desired. 

What’s a good example of how this works in practice?

Google and Bing are great examples: their goal in designing a search engine is to get as much revenue as possible from advertisers. Users just want to find the website they’re looking for without being bothered by ads. Advertisers want the opposite of both: their ads to get lots of views/clicks, and to pay as little as possible for it. Unsurprisingly, companies like Google/Bing that function quite well in the face of strategic manipulation by their users are exactly the same ones that invest heavily in mechanism design research.

Why can’t all these problems be solved by machine learning, where computers adapt to new situations without being explicitly programmed?

The problem is that user behavior changes depending on the solution deployed. So while we have plenty of data to predict how users will interact with our current systems (and machine learning is fantastic at this task), these data are basically useless for predicting how users will interact after any modifications to the system. To solve these problems, we really need a rigorous understanding of user incentives, and we need to be able to predict user behavior without simply copying expectations from past data.

In trying to predict behavior, it sounds like you’re treading on the soft ground of individual and group psychology. Is it really possible to predict all the ways that people may react to something? 

Of course not =). But this is where simplicity comes into play: because we design the platform, we can make sure that users face transparent decisions that we can confidently predict. For example, I feel pretty comfortable predicting that if I offer you the choice of getting $20 or getting $10, you’ll take the $20. Much of my own research focuses on understanding how to solve rich algorithmic problems while asking users to make decisions that are consistently simple and predictable, like this one.

Why did you choose to focus your career on mechanism design?

Mechanism design is unique because the problems are mathematically beautiful, but also really impactful. I love that there’s always a topic relevant to my friends’ non-CS careers: with the doctors we talk about health insurance and the residency match, with the bankers we talk about cryptocurrencies, and everyone loves to talk about online dating. 

On a more personal level, as an undergrad I had an awesome algorithms professor who let me work with him in mechanism design. When I applied to grad school, I found another awesome professor to advise me in mechanism design, and I never really looked back.