这是本专栏的第 61 篇日记
在本学期最后一次Theory Seminar上，In-Koo Cho教授present了一篇与本校Jonathan Libgober教授合作的论文，标题为：”Machine Learning for Strategic Inference in a Simple Dynamic Game”. 目前并未公开放出working paper，但是可以发邮件向Jonathan索要（就是下图在自拍的这位，是我今年4月去Boston开会时在Harvard经济系偷拍的）。
有限理性(Bounded Rationality)，顾名思义，指的是人在进行决策时并不像传统经济学所假设的那样具有“完全的理性”。对于有限理性的建模有很多种方式，在本文中作者采用的是Rubinstein(1993)的想法：
一名卖家向一名买家出售一种商品，由于信息不对称，买家不知道商品的真实价值，而卖家知道且能够根据商品的真实价值选择不同的定价策略。进一步地，买家有两种不同的类型，卖家生产商品的成本由真实价值和买家类型共同决定，因此卖家有动力去区分不同的买家。但在买家完全理性的情况下，卖家并不能有效地将高成本的买家有效地排除出去，因此无法实现理论上的最高利润。
我们注意到，如果买家是完全理性的，那么他总可以根据卖家的定价策略和实际给出的售价，通过贝叶斯更新得出商品价值的后验分布，并理性地决定买或者不买。由于卖家的定价策略的任意性，这种理性的买或不买的决定并不一定是单调的：比如说，也许存在高中低三个价格，当观察到高价时，商品的期望价值很高因此可以买，当观察到低价时，商品的期望价值较低但仍高于售价，因此也可以买，但在中间这个价格时，商品的期望价值反而低于售价因此不能买。
因此，为了让卖家实现有效排除并提高利润，Rubinstein进一步假设，高成本的买家受到“有限理性”的限制，只能采取“阈值策略”(Threshold Strategy)：这类买家不能任意地根据售价决定买还是不买，而是只能选定一个“阈值”，在阈值以上总是做同一个决定，在阈值以下也总是做同一个决定。在这一前提下，卖家可以任意地接近理论上的最高利润，即高成本的买家几乎都被有效地排除了。
回到Cho&Libgober(2019)这篇文章，“有限理性”和机器学习，特别是AdaBoost又是怎么挂上钩的呢？
AdaBoost是Adaptive Boosting的简称，粗略地说，AdaBoost的想法是，通过不断增加“弱分类器”（分类效果仅略优于随机分类）的数量并给予合适的权重，提升分类的准确程度。在本文的情境中，给定卖家的定价策略，买家的任务就是实现一个将“价格”映射到“买/不买”的决策上的分类器，其中完全理性的买家的决策被视为正确的分类器，而有限理性、采用“阈值策略”的买家则只能实现一个“弱分类器”。换言之，本文给予了AdaBoost（以及其它机器学习方法）一个新的行为经济学的解读：给定无穷多具有某种有限理性特征的个体，能否通过自适应的做法调整个体决策的权重，使得最终构成的整体决策符合完全理性的特征？
具体来说，在Rubinstein(1993)的基础上，本文假设高成本的玩家仍然只限于使用“阈值策略”，但可以选择任意数目的此类策略并且赋予不同的权重，并根据加权平均的结果决定最终是买还是不买，具体的策略数目及权重的选择，则按照AdaBoost的算法进行。当然，为了让AdaBoost能够“学会”正确的分类，此时卖家和买家必须重复进行博弈，因此卖家和其它低成本的买家的“完全理性”需要额外考虑到动态博弈时对未来所有收益的折现，以及高成本玩家使用AdaBoost算法这一事实。
为了衡量AdaBoost算法的效果，作者引入了Uniformly PAC(Probably Approximate Correct) Learnability的概念。PAC大致的意思是，训练所得的分类器与正确分类器的差别超过任意小的epsilon的概率不超过任意小的delta。对于一族正确分类器，如果算法总能够在有限步迭代中达成这一目标则称为PAC Learnable，如果进一步地，所需迭代步数不依赖于真实分类器的选择，则称为Uniformly PAC Learnable。
为了简化问题，我们假定卖家能够给出的价格只有有限个（作为对比，通常的做法是允许卖家在连续的区间内任意选择价格），作者证明了如下两个定理：
如果卖家可以任意选择定价策略，且在选定后公开，那么AdaBoost是Uniformly PAC Learnable的。
如果卖家可以任意选择定价策略，但在选定后不公开，那么AdaBoost不是Uniformly PAC Learnable的。
定理1比较好理解，如果卖家公开定价策略，那么“正确分类器”，也即给定价格下完全理性的高成本玩家所应该做出的决策是确定的，问题转化为如何让算法去拟合一个给定的函数（不禁让人想起“神经网络能拟合任意函数”的事儿）；定理2则说明，如果卖家不公开定价策略，那么存在一部分定价策略具有“迷惑性”以至于AdaBoost学不会完全理性的决策。
到此为止，似乎本文的核心已经转向了纯粹的计算理论，只不过披了一层行为经济学“有限理性”的皮。但是让我们思考这样一个问题：什么样的定价策略才能顺利地骗过AdaBoost呢？作者于是给出了定理3：
3. 如果卖家只能选择那些对AdaBoost构成Best Response的定价策略，那么即使卖家不公开，AdaBoost也是Uniformly PAC Learnable的。
也就是说，如果卖家想要采用定理2当中那一小撮让AdaBoost学不会的定价策略， 是需要付出利润损失的；但是对于卖家来说，买家能否学会理性决策根本不重要，重要的是买家学到什么程度以及相应的自己能获得多少利润。如果买家学不会的时候自己要亏钱，学会了反而赚得更多，那何乐而不为呢？
相信读者已经意识到，这就是为什么本文标题还要加上 “博弈论”这个关键词的原因：基于机器学习本身的讨论只能把我们带到定理1和定理2，只有理解博弈论，特别是“最优反应”的概念，才能让我们进一步得到定理3。
Reference:
Cho, I. & Libgober, J. (2019). Machine Learning for Strategic Inference in a Simple Dynamic Game. Working Paper.
Rubinstein, A. (1993). On price recognition and computational complexity in a monopolistic model.Journal of Political Economy,101(3), 473-484.
（2019.12.11 @ 知乎专栏 @ 《有限理性、AdaBoost与博弈论》）
