Commitment and coordination in boundedly rational interactions

• Main Author: Cerny, Jakub
• Other Authors: Bo An
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2023
• Subjects: Science::Mathematics::Applied mathematics::Game theory; Science::Mathematics::Applied mathematics::Optimization; Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity
• Online Access: https://hdl.handle.net/10356/168637
• Institution: Nanyang Technological University

Computational intelligence has become an integral part of human society. Algorithms recommend us news to read during breakfast, help us choose routes to reach workplaces, or suggest restaurants to dine at; but, in the end, it is us - humans - who have the final word in these interactions. And we choose as we please, driven by copious motives and goals. In many cases, we remain oblivious to the fact that our actions eventually shape the entire society, influencing other people's options and decisions. From this interdependence of our behavior stems the need for a theory of greater human interaction. And while traditional game theory offers an elegant body of work, its results are built upon an inherently flawed assumption - the absolute rationality of decision-makers, which, as many experiments in the past decades demonstrated, human psyche seems to show rather a lack of. This thesis attempts to venture beyond this assumption and provides a series of results characterizing the implications of deviating from full rationality. To this end, it adopts perhaps the most widely accepted model of limited cognitive abilities called the quantal response. Quantal response assumes humans act stochastically, choosing actions with higher utilities more frequently. To aid in human decision-making, we study domain-agnostic integration of quantal response into two celebrated interaction archetypes: the models of commitment and coordination. These archetypes have been successfully applied to many specific real-world scenarios, and computed strategies were shown to greatly improve in efficacy when behavioral models are incorporated. Yet, the methods developed for solving these scenarios are not transferable to general models of commitment and coordination, where the integration of bounded rationality has never been addressed until now. Commitment is an ability of a single leading agent to influence the course of play even before the interaction starts by publicly announcing a strategic behavior they will truthfully follow. In order for the commitment to be respected by other agents, the so-called leader has to serve a prominent role in society. The capacity to adopt this role is hence commonly reserved for established market leaders or large governmental institutions. Under mild assumptions, the commitment was shown to benefit the leader greatly, and carefully crafted strategies may hence assist in optimizing social good in the entire society. We show how to integrate quantal response into commitment models in order to account for human-type behavior, we identify the problem's computational complexity, and design algorithms computing commitment strategies with guaranteed convergence and bounded error. Coordination then further improves the agents' strategic capabilities by letting them act upon their interests not only based on the reasoning about the leader's or their other opponents' behavior, but also by conditioning their strategies on external private signals. The process of selecting and revealing the signals is traditionally entrusted to a mediator mechanism, referred to as the correlation device. By optimizing the device's public distribution over signals, coordination facilitates reaching socially desirable outcomes previously considered unattainable. We investigate how quantal response affects the topology of the solution space, how computationally difficult it is to compute the solutions, and design algorithms that traverse the solution space while optimizing the signaling structure. We evaluate the scalability and robustness of all the introduced methods on multiple domains characteristic to commitment or coordination scenarios. The reported results indicate that our methods are sufficiently precise and surpass the contemporary state-of-the-art non-convex optimization solvers by several orders of magnitude in terms of computation speed. We hope our efforts may expedite the adoption of game-theoretic methods for designing more efficient and egalitarian systems.