Bottom-Up Program Synthesis for Interpretable Models of Human Decision-Making in Strategic Games
作者
Mallahnezhad, Mahdieh
出处
期刊: [University of Alberta] 日期:2025-01-01
标识
DOI:10.7939/83014
摘要
Human behavior in strategic settings often differs from the predictions of classical game theory. While the Nash equilibrium provides a central solution concept, experimental studies show that players in one-shot games frequently rely on boundedly rational or heuristic reasoning. Behavioral game theory has addressed this by introducing models such as level-k, cognitive hierarchy, and quantal response equilibrium, yet these approaches typically operate at the population level and rely on restrictive parametric forms that limit their ability to explain the diversity of individual decision rules. Black-box machine learning methods achieve stronger predictive accuracy, but they do so at the expense of interpretability. This thesis introduces a methodological alternative based on program synthesis. A domain-specific language (DSL) is designed to represent intuitive decision heuristics and reasoning patterns in matrix games. Through a Bottom-Up Search procedure, candidate programs are generated and evaluated against more than 7,000 human decisions drawn from experiments on 24 symmetric 3x3 normal-form games with over 300 participants. Each synthesized program is expressed as a transparent decision rule, enabling direct interpretation of individual strategies. The analysis identifies ten representative programs that explain a majority of participants, while a broader set of around sixty programs is sufficient to capture nearly all individuals with accuracies above 75% (meaning that for a given player, at least 75% of the program’s outputs across the 24 games are the same as that player’s actual choices). These programs capture a wide spectrum of behaviors, reported in previous work, including fairness rules, maximin reasoning, conditional altruism, and multi-step opponent modeling. They also reveal novel patterns such as layered fairness and reliance on default anchors. Overall, the results demonstrate that program synthesis can combine the predictive strength of data-driven models with the interpretability of behavioral theory, offering a new perspective on the study of human strategic reasoning.