Tuomas Sandholm: Poker and Game Theory | Lex Fridman Podcast #12

Lex Fridman 0:00 The following is a conversation with Tuomas Sandholm. He's a professor at CMU and co-creator of Libratus, which is the first AI system to beat top human players in the game of Heads-up No-Limit Texas Hold'Em. He has published over 450 papers on game theory and machine learning, including a best paper in 2017 at NIPS, now renamed to NeurIPS, which is where I caught up with him for this conversation. His research and companies have had wide-reaching impact in the real world, especially because he and his group not only propose new ideas, but also build systems to prove that these ideas work in the real world. This conversation is part of the MIT course on Artificial General Intelligence and the Artificial Intelligence podcast. If you enjoy it, subscribe on YouTube, iTunes, or simply connect with me on Twitter @lexfrid. And now here's my conversation with Tuomas Sandholm. Can you describe, at the high level, the game of poker, Texas Hold'Em, Heads-up Texas Hold'Em, for people who might not be familiar, uh, this card game?

Tuomas Sandholm 1:13 Yeah, happy to. So Heads-up No-Limit Texas Hold'Em has really emerged in the AI community as a main benchmark for testing these application-independent algorithms for imperfect information game solving. And this is a game, uh, that's actually played by humans. You don't see it that much on TV or casinos, because, uh, well, for various reasons, but, uh, uh, you do see it in some expert-level casinos, and you see it in the best poker movies of all time. It's actually an event in the World Series of Poker. But mostly it's played online and typically for pretty, uh, big sums of money. And this is a game that usually only experts play. So if you re- uh, go to your home game on a Friday night, it probably is not gonna be Heads-up No-Limit Texas Hold'Em. It might be, uh, No-Limit Texas Hold'Em in some cases, but typically for a, a big group when it's not as competitive. While heads-up means it's two players, so it's really like me against you. Am I better or are you better? Much like chess or, or, or Go in that sense, but an imperfect-information game, which makes it much harder, of course. I have to deal with issues of, uh, you knowing things that I don't know, and I know things that you don't know, instead of pieces being nicely laid on the board for both of us to see.

Lex Fridman 2:31 So in Texas Hold'Em, uh, there's, uh, two cards that you only see? The-

Tuomas Sandholm 2:36 Yes.

Lex Fridman 2:36 ... they belong to you?

Tuomas Sandholm 2:37 Yeah.

Lex Fridman 2:37 And then there is they gradually lay out some cards that add up overall to five cards that everybody can see.

Tuomas Sandholm 2:44 Yeah.

Lex Fridman 2:44 So the imperfect nature of the information is the two cards that you're holding in your hand.

Tuomas Sandholm 2:48 Up front, yeah. So as you said, you know, you first get two cards in private each, and then you, uh, there's a betting round. Then you get three cards in public on the table, then there's a betting round. Then you get the fourth card in public on the table, there's a betting round.

Lex Fridman 3:02 Mm-hmm.

Tuomas Sandholm 3:02 Then you get the five- fifth card on the table, there's a betting round. So there's a total of four betting rounds and four tranches of information revelation, if you will. The only- the first tranche is private, and then it's public from there.

Lex Fridman 3:16 And this is probably, probably by far the most popular game in AI and, um, just the general public in terms of imperfect information. So it's probably the most popular spectator game to watch, right? So, uh, th- which is why it's a super exciting game to tackle. So it's, it's on the order of chess, I would say, in terms of popularity, in terms of AI setting it as the bar of what is intelligence. So in 2017, Libratus... How do you pronounce it? Libratus.

Tuomas Sandholm 3:51 Libratus.

Lex Fridman 3:52 Libratus. Libratus beats...

Tuomas Sandholm 3:53 Little Latin there.

Lex Fridman 3:54 A little bit of Latin. Uh, Libratus beat a few, uh, four expert human players. Can you describe that event? What you learned from it? What was it like? What was the process in general for people who have not read the papers and, uh-

Tuomas Sandholm 4:09 Yeah.

Lex Fridman 4:09 ... studied?

Tuomas Sandholm 4:10 Yeah, so the event was that, uh, we invited four of the top ten players. With these, uh, specialist players in Heads-up No-Limit Texas Hold'Em, which is very important, because this game is actually quite different than the, the multiplayer version. We brought them in to Pittsburgh to play at the Rivers Casino, uh, for 20 days. We wanted to get to 120,000 hands in, because, uh, we wanted to get statistical significance. Uh, so it's a lot of hands for humans to play, even for these top pros who play fairly quickly normally. Uh, so we, uh, couldn't just have one of them play so many hands. 20 days, they were playing basically morning to evening, and, um, I raised $200,000 as a little incentive for them to play. And w- the setting was so that they didn't all get $50,000. Um, we actually paid them out based on how they did against the AI each.

Lex Fridman 5:05 Yeah.

Tuomas Sandholm 5:05 So they had an incentive to play, uh, as hard as they could, whether they're way ahead or way behind or right at the mark of beating the AI.

Lex Fridman 5:13 And you don't make any money, unfortunately.

Tuomas Sandholm 5:16 Right, no.

Lex Fridman 5:16 (laughs)

Tuomas Sandholm 5:16 We can't make any money, so, so originally, a couple of years earlier, I, uh, well, uh, I actually explored whether we could actually play for money, because that would be, of course, uh, interesting as well, uh, to play against the top people for money, but the Pennsylvania Gaming Board said no. So, so we, we couldn't. So this is much like an exhibit, like, uh, like for a musician or a boxer or something like that.

Lex Fridman 5:39 Nevertheless, you were keeping track of the money and Li- Li- Libratus, uh, won close to $2 million, I think. Uh, so (laughs) so if that- if it was for real money, uh, if you were able to earn money, that was a quite impressive and in- inspiring achievement. Just, uh, a few details. What, what were the players looking at? I mean, uh, were they behind a computer? What, what was the interface like?

Tuomas Sandholm 6:02 Yes, uh, they were playing much like they normally do. These top players, when they play this game, they play mostly online, so they're used to playing through a UI.

Lex Fridman 6:11 Yes.

Tuomas Sandholm 6:11 And they did the same thing here. So there was this layout. You could imagine, there's a table-

Lex Fridman 6:16 Yes.

Tuomas Sandholm 6:16 ... uh, on a screen. There's...... the, the, the human sitting there, and then there's the AI sitting there, and the, the, uh, the screen shows everything that's happening. The cards coming out, and shows the bets being made. And we also had the betting history for the human, so if the human forgot what had happened in the hand so far, they could actually reference back and, and, and, and so forth.

Lex Fridman 6:37 Is there a reason they were given access to the betting history for-

Tuomas Sandholm 6:41 Well, we, we just, uh, uh-

Lex Fridman 6:42 ... some kind of ...

Tuomas Sandholm 6:43 ... it, it's a, it, it didn't really matter-

Lex Fridman 6:45 Okay.

Tuomas Sandholm 6:45 ... that they wouldn't have forgotten anyway. These are top-quality people. But, uh, the, uh, we just wanted to put out there, so it's not a question of the human forgetting and the AI somehow trying to get advantage of better memory.

Lex Fridman 6:56 So, what was that like? I mean, that was an incredible accomplishment. So, what did it feel like before the event? Did you have doubt? Hope? Or what, where was your confidence at?

Tuomas Sandholm 7:08 Yeah, that's great. So, uh, great question. So, uh, 18 months earlier, I had organized a similar brains-versus-AI competition-

Lex Fridman 7:15 Mm-hmm.

Tuomas Sandholm 7:15 ... with a previous AI called Cloudico, and we couldn't beat the humans. Uh, so, uh, this time around, it was only 18 months later, and I knew that this new AI, Libratus, was way stronger, but it's hard to say how you'll do against the top humans before you try. So, I thought we had about a 50/50 shot. And the international betting sites put us as a, us as a four-to-one or five-to-one underdog.

Lex Fridman 7:41 Mm-hmm.

Tuomas Sandholm 7:41 So it is kinda interesting that people really believe in people and over AI. Uh, not just, pe- people don't just believe, over-believe in themselves, but they have overconfidence in other people as well, compared to the performance of AI. And, uh, yeah, so we were a four-to-one or five-to-one underdog, and even after three days of beating the humans in a row, we were still 50/50 on the international betting sites.

Lex Fridman 8:06 Do you think there's something special and magical about poker in, in the way people think about it? In a sense, you have, I mean, even in chess, there's no Hollywood movies. Poker is, uh, the s- the star of many movies, and there's this feeling that, uh, certain human em- facial expressions and body language, eye movement, all these tells are critical to poker. Like, you can look into somebody's soul and understand-

Tuomas Sandholm 8:36 (laughs)

Lex Fridman 8:36 ... their betting strategy and so on. And so, that's probably why, p- possibly, do you think that is why people have a confidence that humans will outper- because AI systems cannot, in this construct, perceive these kinds of tells? They're only looking at betting patterns and, uh, th- and nothing else. (laughs) The betting patterns and, and statistics. So, th- what's more important to you if you step back on human players, human-versus-human? What's the role of these tells, of these, uh, ideas that we romanticize?

Tuomas Sandholm 9:13 Yeah. So, I, I'll, I'll split it into two parts. So, one is, why do humans trust humans more than AI-

Lex Fridman 9:21 Yeah.

Tuomas Sandholm 9:21 ... and o- have overconfidence in humans?

Lex Fridman 9:23 Yes.

Tuomas Sandholm 9:23 I think that's, that's not really related to, to the tell question.

Lex Fridman 9:26 Mm-hmm.

Tuomas Sandholm 9:27 It's just that, uh, they've seen these top players, how good they are, and they're really fantastic. So, it's just hard to believe-

Lex Fridman 9:34 That you can beat them.

Tuomas Sandholm 9:35 ... yeah, or that an AI could beat them.

Lex Fridman 9:36 Yes.

Tuomas Sandholm 9:36 So I think that's where that comes from. And, and that's actually maybe a more general lesson about AI, that un- until you've seen it over-perform a human, it's hard to believe that it could. But, um, then the tells, um, a lot of these top players, they're so good at hiding tells that among the top players, it's actually not really-

Lex Fridman 9:58 Mm-hmm.

Tuomas Sandholm 9:58 ... worth it for them to invest a lot of effort trying to find tells in each other because they're so, so good at hiding them. So, uh, yes, at the kind of Friday evening game, tells are gonna be a huge thing.

Lex Fridman 10:11 Mm-hmm.

Tuomas Sandholm 10:11 You can read other people and if you're a good reader, you'll, you'll read them like an open book.

Lex Fridman 10:16 Mm-hmm.

Tuomas Sandholm 10:16 But at the top levels of poker now, the tells become a less, a much, much smaller and smaller aspect of the game as you go to the top levels.

Lex Fridman 10:24 The, the amount of strategies, the amounts of possible actions is, um, is very large, uh, 10 to the power of 100 plus, uh, so there has to be some... I've read a few of the papers related, um, there has, it has to form some abstractions of various hands and actions. So, what kind of abstractions are effective for the game of poker?

Tuomas Sandholm 10:49 Yeah. So, you're exactly right. So, uh, when you go from a game tree that's 10 to the 161-

Lex Fridman 10:55 161.

Tuomas Sandholm 10:55 ... especially in an imperfect information game, it's way too large to solve directly, even with, with our fastest equilibrium-finding algorithms. So, uh, you wanna abstract it first. And abstraction in games is much trickier than abstraction in MDPs or other single-agent settings, 'cause you have these abstraction pathologies, that if I have a finer-grained abstraction-

Lex Fridman 11:20 Mm-hmm.

Tuomas Sandholm 11:20 ... the strategy that I can get from that for the real game might actually be worse than the strategy I can get from the coarse-grained abstraction. So you have to be very careful.

Lex Fridman 11:28 Now, the, the kinds of abstractions, just to zoom out, we're talking about, there's the ha- hands abstractions and then there is betting strategies. What, what-

Tuomas Sandholm 11:37 Yeah. Betting actions, yeah.

Lex Fridman 11:38 B- betting actions?

Tuomas Sandholm 11:39 So, so, there's information abstraction to talk about general games. Information abstraction, which is the abstraction of what chance does. And this would be the cards in the case of poker.

Lex Fridman 11:49 Mm-hmm.

Tuomas Sandholm 11:50 And then there's action abstraction, which is abstracting the actions of the actual players-

Lex Fridman 11:56 Mm-hmm.

Tuomas Sandholm 11:57 ... which would be bets in the case of poker.

Lex Fridman 11:59 Yourself and the other players?

Tuomas Sandholm 12:01 Yes. Yourself and the other players. And, uh, for information abstraction, we were completely automated. So these wa- these are algorithms, uh, but they do what we call potential-aware abstraction where we don't just look at the valley of the hand, but also how it might materialize into good or bad hands over time. And it's a certain kind of bottom-up process, uh, with integer programming there and clustering and various aspects, how do you build, build this abstraction.

Lex Fridman 12:31 Mm-hmm.

Tuomas Sandholm 12:31 And then, in the action abstraction, there, it's largely based on how, um...... humans, other un- and other AIs have played this game in the past, but in the beginning, we actually used an automated action abstraction technology, which is provably convergent, that it finds optimal combination of bet sizes. But it's not very scalable, so we couldn't use it for the whole game, but we used it for the first couple of betting actions.

Lex Fridman 12:59 So what's more important, uh, the strength of the hand, so the, the information abstraction, or the, uh, how you play them? Uh, the actions. Does it... You know, the romanticized notion, again, is that it doesn't matter what hands you have, that the actions, the betting, uh, may be the way you win, no matter what hands you have.

Tuomas Sandholm 13:20 Yeah, so that's why you have to play a lot of hands, so that the role of luck gets smaller. So, uh, you c- you could otherwise get lucky and get some good hands, and then you're gonna win the match. Even with thousands of hands, you can get lucky, uh, because there's so much variance in no-limit Texas hold 'em, because if we both go all in, it's a huge stack, uh, of variance. So there are these massive swings in, uh, no-limit Texas hold 'em.

Lex Fridman 13:47 Mm-hmm.

Tuomas Sandholm 13:47 So that's why you have to play not just thousands, but, uh, over 100,000 hands to get statistical significance.

Lex Fridman 13:55 So, so let me, let me ask another way this question. If you didn't even look at your hands, but they didn't know that, your opponents didn't know that, uh, how well would you be able to do?

Tuomas Sandholm 14:06 Uh, that's a good question. There's actually... I heard this story that there's this Norwegian female poker player called Anette Oberstad-

Lex Fridman 14:13 Mm-hmm.

Tuomas Sandholm 14:13 ... who's actually won a tournament by doing exactly that. But that would be extremely rare. So, so I, uh, I... Y- y- y- you can-

Lex Fridman 14:21 (laughs)

Tuomas Sandholm 14:21 ... you cannot really play well that way. (laughs)

Lex Fridman 14:23 Oh, okay. So, (laughs) so the, the hands do have some role to play, okay.

Tuomas Sandholm 14:27 Yes.

Lex Fridman 14:27 So, Libratus does not, uh, use... As, as far as I understand, uh, use learning methods, uh, deep learning. Is there room for learning in, uh... You know, there, there's no reason why Libratus doesn't, you know, combine with an AlphaGo-type approach for estimating the quality, uh, for a function estimator. What are your thoughts on this, maybe as compared to another algorithm which I'm not that familiar with, DeepStack, the, the engine that does use deep learning, that it's unclear how well it does, but nevertheless uses deep learning? So what are your thoughts about learning methods to aid in the way that, uh, Libratus plays the game of poker?

Tuomas Sandholm 15:09 Yeah, so as you said, Libratus did not use learning methods, and, um, played very well without them. Since then, we have actually...

Lex Fridman 15:17 Awesome.

Tuomas Sandholm 15:17 Actually here, we have, uh, a couple of papers on things that do use learning techniques.

Lex Fridman 15:22 Excellent.

Tuomas Sandholm 15:23 Uh, so, um, and, and deep learning in particular. And th- uh, sort of the way you're talking about, where it's learning an evaluation function.

Lex Fridman 15:32 Mm-hmm.

Tuomas Sandholm 15:33 But, um, in imperfect information games, unlike, let's say, in Go, or now, now also in chess and shogi-

Lex Fridman 15:42 Mm-hmm.

Tuomas Sandholm 15:42 ... it's not, um, sufficient to learn an evaluation for a state, because the value of an information set, uh, depends not only on the exact state, but it also depends on both players' beliefs.

Lex Fridman 15:59 Mm-hmm.

Tuomas Sandholm 15:59 Like if I have a bad hand, I'm much better off if the opponent thinks I'm, I have a good hand, and vice versa. If I have a good hand, I'm much better off if the opponent believes I have a bad hand.

Lex Fridman 16:10 Mm-hmm.

Tuomas Sandholm 16:11 Uh, so the value of a state is not just a function of the cards. Uh, it depends on, uh, if you will, the path of play, but only to the extent that it's captured in the belief distributions. So, uh, so that's why it's not as simple as, uh, uh, as it is in perfect information games. And I don't wanna say it's simple there either. It's, of course-

Lex Fridman 16:31 Right.

Tuomas Sandholm 16:32 ... very complicated computationally there, too. But at least conceptually it's very straightforward. There's a state, there's an evaluation function, you can try to learn it. Here, you have to do something more. Uh, uh, and, uh, w- what we do is in one of these papers we're looking at allowing... where, where we allow the opponent to actually take different strategies-

Lex Fridman 16:52 Mm-hmm.

Tuomas Sandholm 16:53 ... at the leaf of the search tree, as, as... if you will. And, and that, uh, is a different way of doing it, and it doesn't assume, therefore, a particular way that the opponent plays. But it allows opponent to choose from a s- uh, set of different continuation strategies, and that forces us to not be too optimistic in a lookahead search. And that's o- that's one way you can do sound lookahead search in imperfect information games, which is very diff- difficult. And in, in, in... You asked, you were asking about DeepStack.

Lex Fridman 17:25 Yes.

Tuomas Sandholm 17:26 What they did, uh, it was very different than what we do, either in Libratus or in this new work. They were gen- randomly generating various situations in the game, then they were doing lookahead from there to the end of the game as if that was the start of a different game.

Lex Fridman 17:42 Mm-hmm.

Tuomas Sandholm 17:43 And then they were using deep learning to learn those, uh, values of those states, but the states were not just the physical states. They include the belief distributions.

Lex Fridman 17:52 When you talk about lookahead, uh, for DeepStack or with Libratus, does it mean considering every possibility that the game can involve? Is... Are we talking about extremely sort of ex- this exponentially growth of a tree?

Tuomas Sandholm 18:07 Yes. So we, we, we're talking about exactly that, much like you do in alpha-beta search or Monte Carlo tree search, but with different techniques. So there's a different search algorithm, and then we have to deal with the leaves differently. So if you think about what Libratus did, we didn't have to worry about this, because we only did it at the end of the game, so we would always terminate into a real situation, and we would know what the payout is. It didn't do these depth-limited lookaheads. But now in this new paper, uh-... which is called depth-limited, I think it's called depth-limited search for imperfect information games. We can actually do sound depth-limited lookahead. So we can actually start to do the lookahead from the beginning of the game on because that's too complicated to do for this whole long game. So when we brought this, we were just doing it for the end.

Lex Fridman 18:57 So, and then the other side, this belief distribution, so is it explicitly modeled what kind of beliefs that the opponent might have?

Tuomas Sandholm 19:07 Yeah. Yeah, it is explicitly modeled, but it's not assumed. The beliefs are actually output, not input. Of course, the starting beliefs are input, but they just fall from the rules of the game, because we know that the dealer deals uniformly from the deck.

Lex Fridman 19:24 Mm-hmm.

Tuomas Sandholm 19:24 So I know that every pair of cards that you might have is equally likely.

Lex Fridman 19:30 Yes.

Tuomas Sandholm 19:30 I know that for a fact. That just follows from the rules of the game. Of course, except the two cards that I have. I know you don't have those.

Lex Fridman 19:36 Yeah.

Tuomas Sandholm 19:37 Uh, you have to take that into account. That's called card removal, and that's very important.

Lex Fridman 19:41 Is, is the dealing always co- coming from a single deck in heads-up?

Tuomas Sandholm 19:45 Yes.

Lex Fridman 19:45 So you can assume-

Tuomas Sandholm 19:46 Single deck. That's called card removal. It's- So you, you, you know that if some, uh, if, if I have the ace of spades, I know you don't have-

Lex Fridman 19:52 Right.

Tuomas Sandholm 19:52 ... an ace of spades.

Lex Fridman 19:53 Okay, great. So in the beginning, your belief is basically the fact that it's a fair dealing of hands, but how do you adjust, start to adjust that belief?

Tuomas Sandholm 20:02 Well, that's, uh, where this beauty of game theory comes. So Nash equilibrium, which John Nash introduced in 1950-

Lex Fridman 20:10 Mm-hmm.

Tuomas Sandholm 20:10 ... introduces what rational play is when you have more than one player. And these are pairs of strategies where strategies are contingency plans, one for each player, uh, so that neither player wants to deviate to a different strategy-

Lex Fridman 20:26 Mm-hmm.

Tuomas Sandholm 20:27 ... given that the other doesn't deviate. But as a side effect, you get the beliefs from Bayes' rule. So Nash equilibrium really isn't just deriving... In these imperfect information games, Nash equilibrium d- doesn't just define strategies, it, it also defines beliefs for both of us, and it de- refines beliefs for each state. So at each state, uh, each... If they take all information sets.

Lex Fridman 20:53 Mm-hmm.

Tuomas Sandholm 20:53 At each information set in the game, there's a set of different states that we might be in, but w- I don't know which one we're in.

Lex Fridman 21:00 Mm-hmm.

Tuomas Sandholm 21:01 Nash equilibrium tells me exactly what is the probability distribution over those real-world states in my mind.

Lex Fridman 21:08 How does Nash equilibrium give you that distribution? So why...

Tuomas Sandholm 21:12 So I'll, I'll do a simple example.

Lex Fridman 21:13 Yeah.

Tuomas Sandholm 21:13 So, you know the game rock, piece, p- uh, paper, scissors? So we c- we can draw it as player one moves first and then player two moves, but of course, it's important that player two doesn't know what player one moved.

Lex Fridman 21:26 Mm-hmm.

Tuomas Sandholm 21:26 Otherwise, player two would win every time. So we can draw that as an information set, where player one makes one or three moves first, and then there's an information set for player two.

Lex Fridman 21:35 Mm-hmm.

Tuomas Sandholm 21:36 So player two doesn't know which of those nodes the worl- uh, world is in.

Lex Fridman 21:41 Mm-hmm. That's right.

Tuomas Sandholm 21:42 But once we know the strategy for player one, Nash equilibrium will say that you play one-third rock, one-third paper, one-third scissors. From that, I can derive my beliefs on the information set that they're one-third, one-third, one-third.

Lex Fridman 21:54 So Bayes gives you that. So-

Tuomas Sandholm 21:56 Bayes gives you.

Lex Fridman 21:57 But is that specific to a particular player, or is it t- uh, is that something you quickly update with the specific player?

Tuomas Sandholm 22:05 No, that, th- the, game theory isn't really player specific.

Lex Fridman 22:08 Mm-hmm.

Tuomas Sandholm 22:08 So that's wh- also why we don't need any data. Uh, we don't need any history, how these particular humans played in the past or how any AI or human had played before. It's all about rationality. So we just think... Uh, the AI just thinks about what would a rational opponent do-

Lex Fridman 22:25 Yes.

Tuomas Sandholm 22:25 ... and what would I do if I were ra- I am rational and what... Uh, that, that's, that's the idea of game theory. So it's really a data-free, opponent-free approach.

Lex Fridman 22:35 So it comes from the design of the game as opposed to the design of the player. (laughs)

Tuomas Sandholm 22:40 Exactly, there is no opponent modeling per se.

Lex Fridman 22:42 Okay.

Tuomas Sandholm 22:43 I mean, we've done some work on combining opponent modeling with game theory so you can exploit weak players even more. But that's another strand, and in Libratus we didn't turn that on 'cause I decided that these players are too good. And when you start to exploit an opponent, you typically open yourselves up, self up to exploitation. And these guys have so few holes to exploit, and they're world's leading experts in counter-exploitation. So I decided that we're not gonna turn that stuff on.

Lex Fridman 23:09 Actually, I saw a few of your papers about exploiting opponents. It sound very interesting to, uh, explore. Uh, do you think there's room for exploitation g- generally outside of libratus? Is, is there a subject, uh, or people differences that could be exploited? Maybe not just in poker, but in general interactions, negotiations, all these other domains that you're considering?

Tuomas Sandholm 23:33 Yeah, definitely. We've done some work on that, and I really like the work that hybridizes the two.

Lex Fridman 23:39 Mm-hmm.

Tuomas Sandholm 23:40 So you figure out what would a rational opponent do. And by the way, that's safe in these zero-sum games, two-player zero-sum games, because if the opponent does something irrational, yes, it might show, uh throw off my beliefs-

Lex Fridman 23:52 Mm-hmm.

Tuomas Sandholm 23:52 ... um, uh, but the amount that the player can gain by throwing o- off my belief is always less than they lose by playing poorly.

Lex Fridman 24:01 Yeah.

Tuomas Sandholm 24:02 So, so it's safe. But, uh, still, if somebody's weak as a player, you might wanna play differently to exploit them more.

Lex Fridman 24:10 Mm-hmm.

Tuomas Sandholm 24:10 So that you can think about it this way. A game theoretic strategy is un- unbeatable, but it doesn't maximally beat the other opponents. So the winnings per hand might be better with a different strategy. And the hybrid is that you start from a game theoretic approach, and then as you gain data from, uh, th- about the opponent in certain parts of the game tree, then in those parts of the game tree, you start to tweak your strategy more and more-

Lex Fridman 24:37 Mm-hmm.

Tuomas Sandholm 24:37 ... uh, towards exploitation while still staying fairly close to the game theoretic strategy so as to not open yourself up to exploitation too much.

Lex Fridman 24:46 ... h- how, how do you do that? Do you, um, try to vary up strategies, make it unpredictable? It's like, uh, uh, what is it, uh, tit-for-tat strategies and, um, prisoner's dilemma or...

Tuomas Sandholm 25:00 Well, it doesn't r- that, that's a repeated game, kind of-

Lex Fridman 25:03 Repeated games. That's right.

Tuomas Sandholm 25:04 ... s- s- simple prisoner's dilemma, repeated games.

Lex Fridman 25:05 Games, yeah.

Tuomas Sandholm 25:06 But, but even there, there is no proof that says that that's the best thing. But experimentally, it actually does...

Lex Fridman 25:12 It does well.

Tuomas Sandholm 25:13 Does well.

Lex Fridman 25:13 So what kind of games are there, first of all? Y- I don't know if this is something that you could just summarize. There's perfect information games where all the information is on the table. There is imperfect information games. There is repeated games that you play over and over. Uh, there's f- uh, zero sum games.

Tuomas Sandholm 25:31 Mm-hmm.

Lex Fridman 25:31 Uh, there's non-zero sum games.

Tuomas Sandholm 25:34 Yeah.

Lex Fridman 25:35 (laughs) And then there's a really important distinction you're making, two-player versus more players.

Tuomas Sandholm 25:40 Mm-hmm.

Lex Fridman 25:40 So what are... O- what other games are there, and what's the difference, for example, with this two-player game versus more players?

Tuomas Sandholm 25:49 Yeah.

Lex Fridman 25:50 What, what are the key differences in your view?

Tuomas Sandholm 25:51 Right. So let me start from the, the basics. So a repeated game is a game where the same exact game is played over and over. In these extensive form games, uh, whereas... K- think about tree form, maybe with these information sets to represent incomplete information. You can have kind of repetitive interactions. E- even repeated games are a special case of that, by the way.

Lex Fridman 26:18 Mm-hmm.

Tuomas Sandholm 26:18 But, uh, i- the game doesn't have to be exactly the same. It's like in sourcing auctions. Yes, we're gonna see the same supply base year to year, but what I'm buying is a little different every time, and the supply base is a little different every time, and so on. So it's not really repeated.

Lex Fridman 26:34 Mm-hmm.

Tuomas Sandholm 26:34 So to find a purely repeated game is actually very rare in the world. So they're really a very, uh, coarse model of what's going on.

Lex Fridman 26:43 Mm-hmm.

Tuomas Sandholm 26:43 Then if you move up from r- uh, just repeated, simple repeated matrix games, uh, not all the way to extensive form games, but in between, they're stochastic games, where, you know, there's these, uh... Y- think about it like li- uh, these little matrix games.

Lex Fridman 27:00 Mm-hmm.

Tuomas Sandholm 27:00 And when you take an action and your opponent takes an action, they determine not which next state I'm going to, next game-

Lex Fridman 27:08 Mm-hmm.

Tuomas Sandholm 27:08 ... I'm going to, but the distribution of our next games where I might be going to.

Lex Fridman 27:12 Interesting.

Tuomas Sandholm 27:13 So, so that's the stochastic game. But it's like matrix games repeated, stochastic games, extensive form games.

Lex Fridman 27:20 Mm-hmm.

Tuomas Sandholm 27:20 That is, uh, from less to more general. And, and, uh, poker is an example of the last one, so it's really in the most general setting. Uh, extensive form games, and that's kind of what the AI community has been working on and being benchmarked on with this heads-up no-limit Texas hold 'em.

Lex Fridman 27:38 Can you describe extensive form games? What's, what's the motto here? So, uh, how, how do you describe-

Tuomas Sandholm 27:41 Yeah, so if you, if you're familiar with the, the tree form... So it's really the tree form. Like in chess, there's a search tree.

Lex Fridman 27:47 Versus a matrix that-

Tuomas Sandholm 27:48 Versus a matrix, yeah. And, uh, that's... The matrix is called the matrix form or bi-matrix form or normal form game.

Lex Fridman 27:55 Mm-hmm.

Tuomas Sandholm 27:55 And here, you have the tree form, so you can actually do certain types of reasoning there that you lose the information when you go to normal form.

Lex Fridman 28:04 I see.

Tuomas Sandholm 28:04 Th- there, there's s- a certain form of equivalence, like if you go from tree form and you said every possible contingency plan-

Lex Fridman 28:10 Mm-hmm.

Tuomas Sandholm 28:11 ... is a strategy, then I can actually go back to the normal form, but I lose some information from the seq- lack of sequentiality. Then the multiplayer versus two-player distinction-

Lex Fridman 28:21 Yeah.

Tuomas Sandholm 28:21 ... is an important one. So two-player games in zero sum are conceptually easier-

Lex Fridman 28:30 Mm-hmm.

Tuomas Sandholm 28:31 ... and computationally easier. They're still huge like this one, this one-

Lex Fridman 28:35 Mm-hmm.

Tuomas Sandholm 28:36 ... uh, uh, but they're conceptually easier and computationally easier in that, conceptually, you don't have to worry about which equilibrium is the other guy going to play-

Lex Fridman 28:45 Mm-hmm.

Tuomas Sandholm 28:45 ... when there are multiple, because any equilibrium strategy is the best response to any other equilibrium strategy.

Lex Fridman 28:51 Mm-hmm.

Tuomas Sandholm 28:52 So I can play a different equilibrium from you and we'll still get the right values of the game.

Lex Fridman 28:57 Mm-hmm.

Tuomas Sandholm 28:57 That falls apart even with two players when you have general sum games.

Lex Fridman 29:01 Even without cooperation, just in general.

Tuomas Sandholm 29:03 Even without cooperation.

Lex Fridman 29:04 Okay.

Tuomas Sandholm 29:04 So, uh, there's a big gap from two-player zero sum to two-player general sum, or even to three-player zero sum. That's a, that's a big gap, at least in theory.

Lex Fridman 29:14 Can you maybe, non-mathematically, provide the intuition why it all falls apart with three or more players? Uh, it s- it seems like you should still be able to have a Nash equilibrium that... Yeah, th- that's instructive, that holds.

Tuomas Sandholm 29:31 Okay. So it is true that all finite games have a Nash equilibrium, right? So this is what John Nash actually proved. So they do have a Nash equilibrium. That's not the problem. The problem is that there can be many.

Lex Fridman 29:46 Ah.

Tuomas Sandholm 29:46 And then there's a question of which equilibrium to select. So... And if you select your strategy from a different equilibrium and I select mine-

Lex Fridman 29:54 Mm-hmm.

Tuomas Sandholm 29:57 ... the- th- the, uh, the, then, then what does that mean?

Lex Fridman 29:59 Right.

Tuomas Sandholm 29:59 Uh, and, and in these non-zero sum games, we may lose some joint benefit w- uh, by being just simply stupid. We could actually both be better off if we did something else.

Lex Fridman 30:09 Yes.

Tuomas Sandholm 30:09 And in three-player, you get other problems also, like collusion. Like maybe you and I can gang up on a third player-

Lex Fridman 30:16 Mm-hmm.

Tuomas Sandholm 30:16 ... and we can do radically better by colluding. So th- uh, there are lots of issues that come up there.

Lex Fridman 30:22 So, uh, No Brown, the s- student you worked with on this, has mentioned... Uh, I looked through the AMA on Reddit. He mentioned that the ability of poker players to collaborate would make the game... He was asked the question of how would you make the game of poker... Uh, or both of you were asked the question, how would you make the game of poker, uh, beyond being solvable by current AI methods? And he said that, uh, there's not many (laughs)

Tuomas Sandholm 30:50 Yes.

Lex Fridman 30:50 ... ways of making poker more difficult, uh-... but a collaboration or cooperation between players, uh, would make it extremely difficult. So can you provide the intuition behind why that is, uh, if you agree with that idea?

Tuomas Sandholm 31:05 Yeah, yeah. So, uh, we've d- uh, I've done a lot of work on, uh, coalitional games.

Lex Fridman 31:09 Mm-hmm.

Tuomas Sandholm 31:10 And we actually have a paper here with, uh, my other student, Gabriele Farina and some other collaborators on, uh, at the, at NIPS on that.

Lex Fridman 31:16 Yes.

Tuomas Sandholm 31:16 Actually just came back from the poster session where we presented this.

Lex Fridman 31:19 (laughs)

Tuomas Sandholm 31:19 But, uh, so, uh, w- when you have collusion, it's a, it's a different problem.

Lex Fridman 31:23 Yes.

Tuomas Sandholm 31:23 And it typically gets even harder then. Even the game representations, some of the game representations don't really allow good computation, so we actually introduced a new game representation for, for that.

Lex Fridman 31:38 Is that kinda cooperation part of the model? Is, are you, do you have w- uh, do you have information about the fact that other players are cooperating or is it just this chaos that where nothing is known?

Tuomas Sandholm 31:50 So, so there's some- some things unknown.

Lex Fridman 31:52 Can you give an example of a, a collusion type game? Or, or is it usually-

Tuomas Sandholm 31:56 So like bridge.

Lex Fridman 31:58 Right.

Tuomas Sandholm 31:58 Yeah. So think about bridge. It's like when you and I are on a team, our payoffs are the same.

Lex Fridman 32:03 Mm-hmm.

Tuomas Sandholm 32:04 The problem is that we can't talk. So, so when I get my cards, I can't whisper to you what my cards are.

Lex Fridman 32:10 Mm-hmm.

Tuomas Sandholm 32:10 That would not be allowed.

Lex Fridman 32:12 Mm-hmm.

Tuomas Sandholm 32:12 So, uh, we have to somehow coordinate our strategies ahead of time, and only ahead of time, and then there are certain signals we can talk about-

Lex Fridman 32:22 Mm-hmm.

Tuomas Sandholm 32:22 ... but they have to be such that the other team also understands them.

Lex Fridman 32:26 Mm-hmm.

Tuomas Sandholm 32:26 So, uh, so that's, that's, that's an ex- example where the coordination is already built into the rules of the game.

Lex Fridman 32:32 Mm-hmm.

Tuomas Sandholm 32:33 But in many other situations like auctions, or negotiations, or diplomatic relationships, poker, it's not really built in, but it still can be very helpful for the colluders.

Lex Fridman 32:45 I've, I've read you write somewhere the, when negotiations you come to the table with prior, uh, like a strategy that, mm, like that you're willing to do and not willing to do, those kinds of things. So how do you start to, now moving away from poker, moving beyond poker into other applications like negotiations, how do you start applying this to other, to other domains?

Tuomas Sandholm 33:09 Yeah.

Lex Fridman 33:10 Maybe even real world domains that you have worked on?

Tuomas Sandholm 33:12 Yeah. I actually have two startup companies doing exactly that. One is called Strategic Machine, and that's for kind of business applications, gaming, sports, all sorts of things like that. Any applications of this, to business and to sports and to, uh, gaming-

Lex Fridman 33:29 Mm-hmm.

Tuomas Sandholm 33:29 ... to va- various types of things, f- in finance, electricity markets, and so on. And the other is called Strategy Robot, where we are taking this to, uh, military, security, cyber security, and intelligence applications.

Lex Fridman 33:43 I think you worked, uh, a little bit in, um... how, how do you put it? Advertisement, uh, sort, sort of suggesting, um, ads kind of thing, um, auctioning-

Tuomas Sandholm 33:55 Yes, that's another company. Optimized Markets.

Lex Fridman 33:57 Optimized Markets.

Tuomas Sandholm 33:57 But that's much more about like combinatorial market and optimization based technology that's not using these, uh, game theoretic reasoning technologies.

Lex Fridman 34:06 I see. Okay, so what high l- sort of high level do you think about our ability to use game theoretic concepts to model human behavior? Do you think, do you think human behavior is amenable to this kinda modeling? So outside of the poker games, and where have you seen it done successfully in your work?

Tuomas Sandholm 34:27 I'm not sure the goal really is modeling humans. Uh, uh, like for example, if I'm playing a zero sum game-

Lex Fridman 34:36 Yes.

Tuomas Sandholm 34:36 ... I don't really care that the opponent is actually following my model of rational behavior-

Lex Fridman 34:42 Mm-hmm.

Tuomas Sandholm 34:43 ... because if they're not, that's even better for me.

Lex Fridman 34:46 Right. So, so the, see with the opponents in games, there's a, the prerequisite is that you f- formalize the interaction in some way that can be amenable to analysis. And you've done this w- um, amazing work with mechanism design, designing games that have certain outcomes. Uh, but so I- I'll tell you an example from my, uh, from my world of autonomous vehicles, right?

Tuomas Sandholm 35:15 Okay.

Lex Fridman 35:15 We're studying pedestrians, and pedestrians and cars negotiate in this non-verbal communication. There's this weird in- game dance of tension where pedestrians are basically saying, "I trust that you won't kill me, and so as a jaywalker I will step onto the road even though I'm breaking the law," and there's this tension. And the question is we really don't know how to model that well, uh, in, in trying to model intent. And so people sometimes bring up ideas of game theory and so on.

Tuomas Sandholm 35:44 Mm-hmm.

Lex Fridman 35:44 Do you think that aspect of human behavior can use these kinds of imperfect information apro- approaches, modeling? How do we s- how do you start to attack a problem like that, uh, when you don't even know how the game, to design the game to describe the situation in order to solve it?

Tuomas Sandholm 36:04 Okay, so I haven't really thought about jaywalking-

Lex Fridman 36:06 (laughs)

Tuomas Sandholm 36:06 ... but one thing that, uh, I, I think could be a good application in, in, in autonomous vehicles is the following. So let's say that you have fleets of autonomous cars operated by different companies.

Lex Fridman 36:18 Mm-hmm.

Tuomas Sandholm 36:18 So maybe here's the Waymo fleet and here's the Uber fleet. Uh, if you think about the rules of the road, they define certain legal rules, but that still le- leaves a huge strategy space open.

Lex Fridman 36:30 Mm-hmm.

Tuomas Sandholm 36:30 Like as a simple example, when cars merge-

Lex Fridman 36:32 Mm-hmm.

Tuomas Sandholm 36:32 ... you know how humans merge, you know, they slow down and look at each other and, uh, w- try to, uh, try to merge. Wouldn't it be better if these situations would already be pre-negotiated so we can actually merge at full speed and we know that this is the situation, this is how we do it, and it's all gonna be faster?

Lex Fridman 36:50 Mm-hmm.

Tuomas Sandholm 36:50 But there are way too many situations to negotiate manually. So you could do, use automated negotiation. This is the idea at least. You could use automated negotiation to negotiate all of these situations, or many of them, in advance. And of course it might be that, hey...... maybe you're not gonna always let me go first. Maybe you said, "Okay, well, in these situations, I'll let you go first, but in exchange, you're gonna give me, Tuomas, you're gonna let me go first in these situations."

Lex Fridman 37:16 Yes.

Tuomas Sandholm 37:17 So it's this huge combinatorial negotiation.

Lex Fridman 37:20 And do you think there's room in that example of merging to model this whole situation as an imperfect information game, or do you really want to consider it to be a perfect information game?

Tuomas Sandholm 37:30 Oh, that's a good question. Yeah, that's a good question. Um-

Lex Fridman 37:33 Do you pay the price of, uh, assuming that you don't know everything?

Tuomas Sandholm 37:39 Yeah, I don't know. It's certainly much easier. Games with perfect information are much easier. So if you can get away with it, (laughs) uh, y- you should. But if the real situation is of imperfect information, then you're gonna have to deal with imfo- imperfect information.

Lex Fridman 37:55 Great. So what lessons have you learned? The Annual Computer Poker Competition, uh, an incredible accomplishment of AI. You know, you look at the history of Deep Blue, AlphaGo, these kind of, um, moments when AI stepped up in an engineering effort and a scientific effort combined to, to beat the best of human players. So what, what do you take away from this whole experience? What have you learned about designing AI systems that play these kinds of games, and what does that mean for sort of, uh, AI in general, for the future of AI development?

Tuomas Sandholm 38:30 Yeah, so that's a good question. Uh, so there's so much to say about it. I do like this type of performance-oriented research.

Lex Fridman 38:38 Mm-hmm.

Tuomas Sandholm 38:39 Although in my group we go all the way from, like, idea, to theory, to experiments, to big system building, to commercialization. So we span that spectrum, bu- but I think that in a lot of situations in AI, you really have to build the big systems and evaluate them at s- at scale before you know what works and doesn't. And we've seen that in the, uh, computational game theory community-

Lex Fridman 39:01 Mm-hmm.

Tuomas Sandholm 39:01 ... that there are a lot of techniques that look good in the small, but then they cease to look good in the large. And we've also seen that there are a lot of techniques that look superior in theory-

Lex Fridman 39:12 Mm-hmm.

Tuomas Sandholm 39:13 And I, I really mean in, in terms of convergence rates, better... Like, first, auto methods, better convergence rates, like the CFR-based, based algorithms, yet the CFR-ba- based algorithms are the fir- fastest in practice. So it really tells me that you have to test this in re- uh, reality. The theory isn't tight enough, if you will, to tell you which algorithms are better than the others. And, uh, you have to look at these things at... in the large, because w- any sort of projections you do from the small can, at least in this domain, be very misleading. So that, that's kind of from, from a kind of a science and engineering perspective. From personal perspective, it's been just a wild experience in that, uh, with the first poker competition, the first s- so first, uh, brains-versus-AI and machine poker competition that we organized. There had been, by the way, for other poker games, there had been previous competitions, but this was for heads-up no limit, this was the first. And, uh, I probably became the most hated person in the world of poker, and I didn't mean to. I, I, I s-

Lex Fridman 40:13 Why is that?

Tuomas Sandholm 40:13 Uh, the, the, uh-

Lex Fridman 40:14 For cracking the game, for solving-

Tuomas Sandholm 40:15 Yeah. Uh, it was qu- uh, a lot of people felt that it was a real threat to the whole game, the whole existence of the game. If, if, if AI becomes better than humans, people would be scared to play poker, because there are these superhuman AIs running around taking their money and, you know, all of that. So, so I just... uh, it was really aggressive. Uh-

Lex Fridman 40:36 Interesting.

Tuomas Sandholm 40:36 ... the comments were super aggressive. I got everything s- just short of death threats. (laughs)

Lex Fridman 40:42 (laughs) Do, do you think the same was true for chess? 'Cause right now, I mean, they just completed the world championships in chess, and humans just started ignoring the fact that there's AI systems now that outperform humans, and they still enjoy the game. It's still a beautiful game.

Tuomas Sandholm 40:55 See, that's what I think.

Lex Fridman 40:56 Yeah.

Tuomas Sandholm 40:56 Yeah, and I think the same thing happens in poker. And so, so I didn't think of myself as somebody who was gonna kill the game, and I don't think I did.

Lex Fridman 41:03 Yeah.

Tuomas Sandholm 41:03 I've really lu- learned to love this game. I wasn't a poker player before, but learned so many nuances about the... from these AIs, and they've really changed how the game is played, by the way.

Lex Fridman 41:13 Mm-hmm.

Tuomas Sandholm 41:13 So they have these very Martian ways of playing poker, and the top humans are now incorporating those types of strategies into their own play. So if anything, to me, our work has made poker a richer, more interesting game for humans to play, not something that is gonna steer humans away from it entirely.

Lex Fridman 41:34 Just a quick comment on something you said, which is... if I may say so, in academia is a little bit rare sometimes, it, it's, it's pretty brave to put your ideas to the test in the way you described, uh, s- saying that sometimes good ideas don't work when you actually try to apply them at scale. And so where does that come from? I mean, what... uh, if you could do, um... advice for people, what, what drives you in that sense? Were you always this way? (laughs) I mean, it ta- it takes a brave person, I guess is what I'm saying, to test their ideas and to see if this thing actually works against human... top human players and so on.

Tuomas Sandholm 42:11 Yeah, I don't know about brave, but it takes a lot of work.

Lex Fridman 42:14 Yes, it takes a lot of work.

Tuomas Sandholm 42:14 Uh, it, it takes a lot of work and a lot of time, uh, to organize, do... make something big, and to organize an event, and stuff like that.

Lex Fridman 42:23 And what drives you in that effort? Because you could still, I would argue, get a best paper award at NIPS as you did in '17 without doing this.

Tuomas Sandholm 42:31 That's right, yes. (laughs)

Lex Fridman 42:33 And s- and so, uh... (laughs)

Tuomas Sandholm 42:34 So in, uh, in, in general, I believe it's very important to do things in, uh, i- i- in the real world and at scale, uh, and that's really where the, the, the, the pudding, if you will-

Lex Fridman 42:46 Yeah.

Tuomas Sandholm 42:46 ... proof is in the pudding. That's w- that's where it is. In this particular case, it was kind of a competition, uh, between different groups-

Lex Fridman 42:55 Yeah.

Tuomas Sandholm 42:55 ... uh, uh, for many years.... as to who can be the first one to beat the top humans at heads-up no-limit Texas hold 'em. So it became, uh, uh, it became kind of a, uh, what you, uh, like a competition, who can get there?

Lex Fridman 43:09 Yeah, so a little friendly competition could be, uh, could do wonders for progress.

Tuomas Sandholm 43:14 Yes, absolutely. (laughs)

Lex Fridman 43:16 (laughs) So, uh, the topic of mechanism design, which is really interesting, also kind of new to me, uh, except as an observer of, I don't know, politics and any... I'm an obs- observer of mechanisms, but you, you write in your paper on automated mechanism design that, that I quickly read. So mech- mechanism design is designing the rules of the game so you get a certain desirable outcome, and you have this work on doing so in an automatic fashion, as opposed to fine-tuning it. So what have you learned from those efforts? Uh, if you look, s- say, I don't know, at a complex s- like, um, like our political system, c- can we design our political system to have, in an automated fashion, uh, to have outcomes that we want? Can we design something like, um, traffic lights, uh, to be smart, uh, where it gets outcomes that we want? So what, what are the lessons that you draw from that work?

Tuomas Sandholm 44:15 Yeah, so I still very much believe in the automated mechanism design direction.

Lex Fridman 44:19 Yes.

Tuomas Sandholm 44:20 But it's not a panacea. There are impossibility results in mechanism design saying that there is no mechanism that accomplishes objective X in class C. So, so there is, it, it's not going to... There's no way, using any mechanism design tools, manual or automated, to do certain things in mechanism design.

Lex Fridman 44:42 Can you describe that again? So meaning, there... it's impossible to achieve that, uh-

Tuomas Sandholm 44:48 Yeah. Yeah, c- cert- there's a certain imposs-

Lex Fridman 44:49 ... end or unlikely? Uh-

Tuomas Sandholm 44:50 Impossible.

Lex Fridman 44:51 Impossible.

Tuomas Sandholm 44:51 So, so, so these are, th- these are not statements about human ingenuity, that who might come up with something smart. These are proofs-

Lex Fridman 44:58 Yes.

Tuomas Sandholm 44:58 ... that if you want to accomplish properties X in class C, that is not doable with any mechanism. The good thing about automated mechanism design is that we're not really designing for a class. We're designing for specific settings at a time.

Lex Fridman 45:13 Mm-hmm.

Tuomas Sandholm 45:14 So even if there's an impossibility result for the whole class, it just me- doesn't mean that all of the cases in the class are impossible. It just means that some of the cases are impossible. So we can actually carve these islands of possibility within these known impossible classes, and we've actually done that. So one, one of the famous results in mechanism design is the Myerson-Satterthwaite theorem f- by Roger Myerson and Mark Satterthwaite from 1983. It's, it's an impossibility of efficient trade under imperfect information. We show that you can, in many settings, avoid that and get efficient trade anyway.

Lex Fridman 45:51 Depending on how they design the game. Okay, so-

Tuomas Sandholm 45:54 D- depending how you design the game. And of course, it's not... uh, it doesn't, in any way, any way, uh, contradict the impossibility result. The impossibility result is still there, but it just, uh, finds spots within this impossible class where, in those spots, you don't have the impossibility.

Lex Fridman 46:12 Sorry if I'm going a bit philosophical, but, uh, what lessons do you draw towards, like I mentioned, politics or the human interaction and designing mechanisms for, outside of just these kinds of trading or auctioning or, um, purely formal games, are human interaction, like a political system. What, how... can... do you think it- it's applicable to, yeah, politics, or to business, uh, to negotiations, these kinds of things, designing rules that have certain outcomes?

Tuomas Sandholm 46:49 Yeah, yeah. I, I do think so.

Lex Fridman 46:51 Have you seen success, that successfully done?

Tuomas Sandholm 46:54 There hasn't really... Oh, you mean mechanism design or automated mechanism?

Lex Fridman 46:57 Automated mechanism design.

Tuomas Sandholm 46:58 So, so mechanism design itself has had fairly limited success so far. There are certain cases, but most of the real-world situations are actually not sound from a mechanism design perspective.

Lex Fridman 47:14 Mm-hmm.

Tuomas Sandholm 47:14 Even in those cases where they've been designed by very knowledgeable mechanism design people-

Lex Fridman 47:19 Mm-hmm.

Tuomas Sandholm 47:20 ... the people are typically just taking some insights from the theory and applying those insights into the real world-

Lex Fridman 47:26 Yes.

Tuomas Sandholm 47:26 ... rather than applying-

Lex Fridman 47:27 Directly.

Tuomas Sandholm 47:27 ... the mechanisms directly. So one famous example of, is the FCC spectrum auctions. So, um, um, I- I've also had a small role in that, and, uh, very good economists have been work- excellent economists have been working on that with no game theory. Yet, the rules that are designed in practice there, they're such that bidding truthfully is not the best strategy. Usually, mechanism design, we try to, uh, make things easy for the participants so telling the truth is the best strategy.

Lex Fridman 47:58 Mm-hmm.

Tuomas Sandholm 47:58 But, uh, but even in those very high-stakes auctions where you have tens of billions of dollars worth of spectrum being auctioned, truth-telling is not the best strategy.

Lex Fridman 48:08 (laughs)

Tuomas Sandholm 48:09 And, and by the way, nobody knows even a single optimal bidding strategy for those auctions.

Lex Fridman 48:14 What's the challenge of coming up with an optimal... Because there's a lot of players and there's imperfect information?

Tuomas Sandholm 48:18 It's not so much that, um, a lot of players but many items for sale, and the- these mechanisms are such that even with just two items or one item, bidding truthfully wouldn't be the best strategy.

Lex Fridman 48:31 If you look at the history of AI, it's marked by seminal events. Uh, AlphaGo being a world champion, human Go player. I would put Libratus winning the heads-up no-limit hold 'em as one of such event.

Tuomas Sandholm 48:45 Thank you.

Lex Fridman 48:45 Uh, uh, and what, what do you think is the next such event, uh, whether it's in your life or in the broadly AI community, that you think might be out there that would surprise the world?

Tuomas Sandholm 49:01 ... so that's a great question, and I don't really know the answer. In terms of game solving, uh, Heads-up No Limit Texas Hold 'Em really was the one remaining widely agreed-upon benchmark, so that was the big milestone. Now, are there other things? Yeah, certainly there are, but there, uh, there is not one that the community has kind of focused on. So what could be other things? Uh, there are groups working on StarCraft. There are th- groups working on DOTA 2. These are video games.

Lex Fridman 49:31 Yes.

Tuomas Sandholm 49:31 Or you could have, like, Diplomacy or Hanabi, you know, things like that. These are, like, recreational games, but none of them are, uh, really acknowledged as kind of the main next challenge problem, uh, like chess, or Go, or Heads-up No Limit Texas Hold 'Em was. So I, I don't really know in the game-solving space what is or what will, will be the next benchmark. I hope, kind of hope that there will be a next benchmark 'cause really, the, uh, different groups working on the same problem really drove these application-independent techniques forward very quickly over 10 years.

Lex Fridman 50:07 Do you think there's an open problem that excites you that you start moving away from games into real-world games, like say, the stock market trading? Uh, it's-

Tuomas Sandholm 50:17 Yeah, so that, that's kind of how I am, so I am probably not going to work, eh, as hard on these, uh, recreational benchmarks. Uh, I'm doing two startups on game-solving technology, Strategic Machine and Strategy Robot, and we're really interested in pushing this, uh, stuff into practice.

Lex Fridman 50:37 What, what do you think would be, uh, really, you know, uh, a s- uh, a powerful result that would be surprising, that would, would be, um, uh, if you can say... Uh, I mean, it's, uh, th- uh, you know, five years, ten years from now, something that statistically you would say is not very likely, but if there's a breakthrough, w- w- what achieve...

Tuomas Sandholm 51:01 Yeah, so I think that overall, we're in a very different situation in game theory than we are in, let's say, machine learning.

Lex Fridman 51:11 Yes.

Tuomas Sandholm 51:11 So in machine learning, it's a fairly mature technology, and it's very broadly applied and proven success in the real world. In game-solving, there are almost no applications yet. We have just become superhuman, which machine learning, you could argue happened in the '90s, if not earlier, and, uh, at least from supervised learning ap- certain complex supervised learning applications. Now, I think the next, uh, challenge problem... I know you're not asking about it this way. You're, you're asking about the technology breakthrough-

Lex Fridman 51:43 Yeah.

Tuomas Sandholm 51:43 ... but I think the big, big breakthrough is to be able to show that, hey, maybe most of, let's say, military planning, or most of business strategy will actually be done strategically using computational game theory. That, that's what I would like to see as the next five or 10-year goal.

Lex Fridman 51:58 Maybe you can explain to me again... uh, forgive me if this is an obvious question, but, uh, you know, machine learning methods, neural networks are... suffer from not being transparent, not being explainable. Uh, game theoretic methods, you know, Nash equilibria, do they generally, when you see the different solutions, are they... uh, when you, when you talk about military operations, are they... once you see the strategies, do they make sense, are they explainable, uh, or do they suffer from the same problems as neural networks do?

Tuomas Sandholm 52:27 So that's, that's a good question. I would say a little bit yes and no, and, uh, well, what I mean by that is that these game-theoretic strategies, let's say Nash equilibrium-

Lex Fridman 52:38 Mm-hmm.

Tuomas Sandholm 52:39 ... it has provable properties. So it's unlike, let's say, deep learning, where you kind of cross your fingers, hopefully it'll work, and then after the fact, when you have the weights, you're still crossing your fingers, and, "I hope it will work."

Lex Fridman 52:50 Okay.

Tuomas Sandholm 52:51 Uh, h- here, you know that the solution quality is there. There's provable solution-quality guarantees. Now, that doesn't necessarily mean that the strategies are human-understandable. That's a whole other problem. So it's, uh... so I think that deep learning and computational game theory are in the same boat in that sense, that both are difficult to understand. But at least the game-theoretic techniques, they have these g- guarantees of solution quality.

Lex Fridman 53:19 Guarantees. So d- do you see business operations, strategic operations, or even military in the future being at least the, the strong candidates being proposed by automated systems? Do you see that?

Tuomas Sandholm 53:34 Yeah, I do. I do. But that's more of a beli- belief than a, uh, uh-

Lex Fridman 53:38 (laughs)

Tuomas Sandholm 53:38 ... and a substantiated fact.

Lex Fridman 53:39 Depending on where you land in optimism or pessimism, that's a really ex- to me, that's an exciting future, especially if there's, uh, uh, provable things, uh, in terms of optimality. So looking into the future, there's, uh, a few folks worried about th- uh, especially y- you look at the game of poker, which is probably one of the last benchmarks in terms of games being solved, they, they worry about the future and the existential threats of artificial

Lex Fridman 54:10 intelligence, so the negative impact in whatever form on society. Is that something that concerns you as much, or are you more optimistic about the positive impacts of AI, or...

Tuomas Sandholm 54:21 Oh, I am much more optimistic about the positive impacts. So just in my own work, what we've done so far, w- we run the nationwide kidney exchange. Hundreds of people are walking around, alive today. Who wouldn't be?

Lex Fridman 54:33 Mm-hmm.

Tuomas Sandholm 54:34 And it's increased employment. You ha- you have a lot of people now running kidney exchanges and at transplant centers, uh, interacting with the kidney, uh, exchange. You have s- extra surgeons, nurses, anesthesiologists, hospitals, all of that.

Lex Fridman 54:51 Mm-hmm.

Tuomas Sandholm 54:51 Uh, so, so employment is increasing from that, and the world is becoming a better place. Another example is, uh, combinatorial sourcing auctions. We, uh, did 800 large-scale combinatorial sourcing auctions from 2001 to 2010, uh, in a previous startup of mine called Combinet, and, um...... we increase the supply chain efficiency on that $60 billion of spend by 12.6%. So that's over $6 billion of efficiency improvement in the world.

Lex Fridman 55:22 That's-

Tuomas Sandholm 55:22 And this is not like shifting value from somebody to somebody else, just efficiency improvement, like in trucking, less empty driving, so there's less waste, less carbon footprint, and so on.

Lex Fridman 55:33 This is a huge positive impact in the near term, but sort of, to, to stay in it for, for a little longer, because I think game theory has a role to play here-

Tuomas Sandholm 55:43 Oh, le- let me actually come back on that. That-

Lex Fridman 55:44 ... yes.

Tuomas Sandholm 55:44 ... is one thing. I think AI is also going to make the world much safer. So, uh, so, uh, so that's another aspect that often gets overlooked.

Lex Fridman 55:54 Well, let me ask this question, maybe you can speak to the, the safer. So I talked to Max Tegmark and Stuart Russell, uh, who are very concerned about existential threats of AI, and often the concern is about value misalignment, so AI systems basically up, uh, working, operating towards goals that are not the same as h- human civilization, human beings. So, it seems like game theory has a role to play there, uh, to m- to, uh, make sure the values are aligned with human beings. I don't know if that's how you think about it. If not, how do you think AI might help with this problem? Uh, how, how do you think AI might make the world safer?

Tuomas Sandholm 56:39 Yeah. I, I think this value misalignment is a fairly theoretical worry, and I haven't really seen it any... 'Cause I do a lot of real applications, I don't see it anywhere. Uh, the closest I've seen it was the following type of mental exercise really, where I had this argument in the late '80s when we were building these transportation optimization systems, and somebody had heard that it's a good idea to have high utilization of assets. So they told me that, "Hey, why don't you put that as objective?" And we didn't even put it as an objective because I just showed him that, you know, if you had that as your objective, the solution would be to load your trucks full and drive in circles.

Lex Fridman 57:22 Okay.

Tuomas Sandholm 57:22 Nothing would ever get delivered, you'd have 100% utilization.

Lex Fridman 57:25 That's right.

Tuomas Sandholm 57:25 So yeah, I know this phenomenon, I've known this for over 30 years and, but, but I've never seen it actually be a problem reality- in reality. And yes, if you have the wrong objective, the AI will optimize that to the hilt, and it's gonna hurt more than some human who's kinda trying to solve it in a half-baked way with some human insight too, but I, I just haven't seen that materialize in practice.

Lex Fridman 57:49 There's this gap that you actually put your finger on, uh, very clearly just now between theory and reality that's very difficult to put into words, I think. It's what you can theoretically imagine, uh, the, the worst possible case or even, yeah, I mean, bad cases, and what usually happens in reality. So for example, to me, maybe it's something you can comment on, uh, f- having grown up in... I h- grew up in the Soviet Union, you know, there's currently 10,000 nuclear weapons in the world, and for many decades, it's, uh, theoretically, uh, surprising to me that a nuclear war has not broken out. Do you think about this aspect, from a game theoretic perspective in general, why is that true? Uh, why in theory you can see how things would go terribly wrong and somehow yet they have not?

Tuomas Sandholm 58:44 Yeah.

Lex Fridman 58:44 How do you think about that?

Tuomas Sandholm 58:45 So, so I do think that about that a lot. I think the biggest two threats that we're facing as mankind, one is climate change and the other is nuclear war. So as, so, so those are my main two worries that I worry about, and I, I've tried to do something about climate... Uh, thought about trying to do something for climate change twice, actually. For two of my startups I've actually commissioned studies of what we could do on those things, and we didn't really find a sweet spot but I'm still keeping an eye out on that if there's something where we could actually provide a market solution or optimization solution or some other technology solution to problems. Right now, um, like for example, pollution credit markets was what we were looking at then, and it was much more the lack of political will by those markets were not so successful rather than bad market design. So I could go in and make a better market design, but that wouldn't really move the needle on the world very much if there's no political will, and in the US, you know, the market, uh, at least the Chicago market was just shut down, uh, uh, and, and so on. So it, then it doesn't really help how great your market design was. So-

Lex Fridman 59:51 And on the nuclear side, it's more, so global warming is a more encroaching problem, you know, nuclear weapons (laughs) have been here, it's an obvious problem that's just been sitting there, so how do you think about... what is the mechanism design there that just made everything seem stable and are you still extremely worried?

Tuomas Sandholm 1:00:15 I am still extremely worried. So, uh, y- yeah, you probably know the simple game theory of MAD. So, so, so, uh, this was, uh, mutually assured destruction-

Lex Fridman 1:00:23 Mm-hmm.

Tuomas Sandholm 1:00:24 ... and it's li- it doesn't require any computation, with small matrices you can actually convince yourself that the game is such that nobody wants to initiate.

Lex Fridman 1:00:31 Mm-hmm.

Tuomas Sandholm 1:00:31 Yeah, that's a very coarse-grained analysis, and it really works in a situation where you have two super powers or small number of super powers. Now things are very different. You have, uh, smaller nukes so the threshold o- of initiating is smaller and you have smaller countries and non-n- non-nation actors who may get h- nukes and so on, so it's, I, I think it's riskier now than it was maybe ever before.

Lex Fridman 1:00:58 And what idea, application of AI, you've talked about it a little bit but, what is the most exciting to you right now? I mean, you're here at NIPS, NeurIPS now-You, you ha-have a few excellent pieces of work, but what are you thinking into the future? With several companies you're doing, what's the most exciting thing or one of the exciting things?

Tuomas Sandholm 1:01:21 The number-one thing for me right now is coming up with these scalable techniques for game solving and applying them into the real world. Uh, I'm still very interested in market design as well, and we're doing that in the optimized markets. But I'm most interested if number one right now is strategic machine, strategy robot, getting that technology out there and seeing as you are in the trenches doing applications, what needs to be actually filled, what technology gaps still need to be, be filled. So it's so hard to just put your feet on the table and imagine what needs to be done. But when you're actually doing real applications, the applications tell you what needs to be done. And I really enjoy that interaction.

Lex Fridman 1:02:01 Is it a challenging process to apply some of the state-of-the-art techniques you're working on a-and having the, the various, uh, players in industry or the military or people who could really benefit from it actually use it? What's that process like of... You know, in autonomous vehicles, we work with automotive companies and they're, uh, in, in many ways, they're a little bit old-fashioned. It's difficult. They really want to use this technology. There's clearly will have a significant benefit, but the systems aren't quite in place to easily have them integrated in terms of data, in terms of compute, in terms of all these kinds of things. So do you s- is that one of the bigger challenges, uh, that you're facing? Uh, and how do you tackle that challenge?

Tuomas Sandholm 1:02:50 Yeah, I think that's always a challenge. Uh, that, that kind of slowness and inertia really of let's do things the way we've always done it. You just have to find the internal champions at the customer who understand that, hey, things can't be the same way in the future, otherwise bad things are going to happen.

Lex Fridman 1:03:06 Right.

Tuomas Sandholm 1:03:07 And it's in autonomous vehicles, it's actually very interesting that the car makers are doing that and they're very traditional. But at the same time, you have tech companies who have nothing to do with cars or transportation-

Lex Fridman 1:03:17 Mm-hmm.

Tuomas Sandholm 1:03:17 ... like Google and Baidu really pushing on autonomous cars. I, I find that fascinating.

Lex Fridman 1:03:23 Clearly, you're super excited about actually these ideas having an impact in the world. Uh, in terms of the technology, in terms of ideas and research, are there directions that you're also excited about, whether that's on the, some of the approaches you talked about for the imperfect information games, whether it's applying deep learning to some of these problems? Is there something that you're excited in, um, in the research side of things?

Tuomas Sandholm 1:03:49 Yeah, yeah. Lot, lots of different things in, in the game solving.

Lex Fridman 1:03:52 Mm-hmm.

Tuomas Sandholm 1:03:53 Uh, sol- solving even bigger games, uh, games where you have, um, more hidden action of the player actions as well. Uh, poker is a game where really the chance actions are hidden, or some of them are hidden, but the player actions are public. Uh, multiplayer games of various sorts, collusion, uh, opponent exploitation, all, all... and, and even longer games. Some games that basically go forever, but they're not repeated.

Lex Fridman 1:04:24 Mm-hmm.

Tuomas Sandholm 1:04:24 So seek extensive form games that go forever. What, what would that even look like? How do you represent that? How do you solve that?

Lex Fridman 1:04:32 What's an example of a game like that? What... Uh, is this some of the stochastic games that you mentioned?

Tuomas Sandholm 1:04:36 Let's say business strategy. So it's a- and not just modeling like a particular interaction, but thinking about the business from here to eternity.

Lex Fridman 1:04:43 Mm-hmm.

Tuomas Sandholm 1:04:44 Or, uh-

Lex Fridman 1:04:45 I see.

Tuomas Sandholm 1:04:45 ... or let's, let's say, um, military strategy. So it's not like war is gonna go away. How, uh, how do you dare think about military strategy that's gonna go forever? Uh, how do you even model that? How do you know whether a move was good-

Lex Fridman 1:05:00 Mm-hmm.

Tuomas Sandholm 1:05:01 ... that you, you... somebody made and, and, and so on? Uh, so that, that's kind of one direction. I'm also very interested in learning much more scalable techniques for integer programming. So we had an ICML paper this summer on that for the first automated algorithm configuration paper that has theoretical generalization guarantees. So if I see these many training examples and I tune my algorithm in this way-

Lex Fridman 1:05:28 Mm-hmm.

Tuomas Sandholm 1:05:28 ... it's going to have good performance on the real distribution, which I've not seen. So w- which is kind of interesting that, you know, algorithm configuration has been going on now for at least 17 years seriously-

Lex Fridman 1:05:41 Mm-hmm.

Tuomas Sandholm 1:05:42 ... and there has not been any generalization th- uh, theory before.

Lex Fridman 1:05:46 Well, this is really exciting and it's been... it's a huge honor to talk to you. Thank you so much, Tuomas. Thank you for bringing Libratus to the world and all the great work you're doing.

Tuomas Sandholm 1:05:54 Well, thank you very much. It's been fun. Good questions.

Lex Fridman 1:05:56 (laughs)