Consider an auction. You have two types of main protagonists or agents: a seller (or auctioneer) and many potential buyers. There are, of course, certain ground rules. For instance, one objective may be to design the auction in such a way that the person buying the item(s) up for sale is the buyer “who values that good the most.”
But, says Singapore Management University Associate Professor of Economics Takashi Kunimoto, what if you do not know which potential buyer does give the item the highest valuation?
“For example, I want to design a scheme in such a way that they’re willing to tell the truth about their valuation, and I can choose the person who values it the most. So that’s the kind of framework I have in mind to determine who’s going to be a winner, with what probability, and who pays how much.”
Professor Kunimoto, whose research interests include game theory, mechanism design, and macroeconomic theory, has written a paper in conjunction with two other SMU researchers, Professor of Economics Shurojit Chatterji, and Research Fellow Paulo Ramos, titled “Compellingness in Nash Implementation.”
John Nash, who featured in the Russell Crowe movie “A Beautiful Mind,” was awarded the Nobel Prize for Economics in 1994 for his work on the mathematics of game theory. Professor Kunimoto says that, when it comes to a group of agents interacting with each other—whether it be in an auction or in an institution or organization—he has to make a “fundamental assumption about where their interactions will lead,” often referred to as “Nash equilibrium.” (This is when no player can benefit by unilaterally changing their strategy and consequently is “somehow locked in and therefore cannot find anything better.”)
One potential issue with this framework, however, is that there may be many different Nash equilibria. “As a designer I don’t really know which one is going to be played,” says Professor Kunimoto.
This is where Nash implementation comes in. “Can I design a mechanism in such a way that every Nash equilibrium delivers an outcome I want to implement?”
Another Nobel laureate, Eric Maskin, had already established this basic framework, Professor Kunimoto told the Office of Research, but “one issue was omitted in literature. Even though you’re looking at many equilibria, somehow, they only focus on ‘pure strategy’ equilibria so they don’t resort to randomization.” (Pure strategy implies that the player chooses the same strategy each time in a deterministic manner).
This is where the classic example of a penalty shoot-out in football comes in. There is a striker and a goalkeeper. They can go left or right (although, in reality, there are other options). It is, as Professor Kunimoto points out, a zero-sum game. Either the striker scores or does not. “So, my best strategy is the worst strategy for the other. There’s a complete conflict of interest.”
In this zero-sum game, the equilibrium plays entails randomization, implying that the striker does not always try to place the ball in the same part of the net. “But implementing such a randomizing strategy might be quite sophisticated.”
“When I say that with Nash implementation, every Nash equilibrium delivers the right outcome, somehow I implicitly assume they’re going to play some pure strategy which involves no randomization.”
Professor Kunimoto then opts for a mixed strategy approach which does involve randomization and “should be even better” at predicting outcomes. “If that’s the case, maybe I’d better be more careful about how I design the mechanism.”
Of course, the mixed strategy equilibrium could be less likely to be played than the pure strategy equilibrium. If this is the case, one can call such a mixed strategy equilibrium ‘not compelling.” On the contrary, the mixed strategy equilibrium could be more likely to be played than the pure strategy equilibrium. In this case, one can call such a mixed strategy equilibrium ‘compelling.”
But, on the assumption that more than one mixed strategy could be played, “one might be called ‘compelling’ and the other might not.” (In the paper, the researchers call a mixed strategy equilibrium ‘compelling’ if its outcome Pareto—an action resulting in no one losing out although it helps one party—dominates any pure strategy outcome.)
To what extent then does the design of the mechanism need to be modified?
“The question is fundamental and was already addressed in the literature,” says Professor Kunimoto, “but somehow it was overlooked and that’s the context of the question I’m interested in.”
As we have seen, many assumptions are made in understanding the plausibility of both pure and mixed strategy equilibria in Nash implementation. However, isn’t a study of just two participating parties or agents somewhat limited in its focused approach?
“Yes, but we encountered difficulty characterizing how mixed strategy equilibria look like in the mechanism with more than two agents. To avoid some of the technical issues, we decided to confine our attention to the case of two agents.”
“When I design a mechanism, I do not necessarily look at one that works in the real world. To do that, maybe I have to come up with some robustness requirement, which, I hope, leads us to more natural mechanisms.”
“I just hope that finding a more natural mechanism might lead to a mechanism which might work in the real world, and I think my contribution is going to be somehow pushing this agenda towards finding more effective institutions—but it’s still a long way off.”
“Hopefully if we provide the set of guidelines, policymakers and others may find some of the applications useful, although given what I’ve said in the paper, it’s still a long shot.”
As for the paper itself, it has yet to be published and is likely to need some revision.
For instance, in the abstract, the researchers state that they “illustrate the difficulty of extending our result to the case of more than two agents.”
“When we extend our results to environments with three or more agents in a straightforward manner,” the paper concludes, “the class of environments in which compelling implementation is possible becomes very small.”
Professor Kunimoto says, however, they can handle more than two agents as this, he acknowledges, “was a significant limitation in the draft paper. Fortunately, we’re almost able to overcome that deficiency.”
To do that, they are now considering “mini versions of the two-person case, but in many pairs.”
In essence, it all comes down to ‘reverse engineering’ game theory. Instead of trying to make predictions about how the game is going to be played, “we want to go the other way round this,” Professor Kunimoto says.
“Somehow, I really want a particular prediction to be consistent with the objective I want to achieve. I want to design a mechanism, but the outcome is going to be exactly the one I want implemented.”
For more such insights, log into our website https://international-maths-challenge.com
Credit of the article given to Stuart Pallister, Singapore Management University