分享 | 科研展示Tutorial：计算机与经济学篇
关键词：科研展示 Tutorial 计算机与经济学
编者按
2019年11月23日，第二届北京大学前沿计算研究中心及图灵班科研展示交流活动在静园五院举行，来自中心和图灵班的多位同学在会上展示了自己的科研成果。“学术教程”作为本届展示新增环节，旨在促进同学间更加深入的信息交流和经验分享。
以下分享部分教程内容，以飨读者。
计算机与经济学篇
Blockchain
陈宏崟
摘要
区块链是分布式数据存储、点对点传输、共识机制、加密算法等计算机技术的新型应用模式。它是比特币的底层技术和基础架构，本质上是一个去中心化的数据库。本次 tutorial 以比特币为例，介绍了区块链的运行机制，并详细解释了历史唯一性和不可篡改性及其来源。
报告人分享
区块链在当下是一个富有争议的技术：一方面区块链被认为是一门重要的技术，区块链拥有的诸多良好的性质，可以构建可靠的“信任”；另一方面如今区块链技术还尚未成熟，但已经有大量的资本流入，在区块链应用尚未规范，大众对区块链的认识尚且十分浅薄之时，收割着一波又一波的韭菜，这也在一定程度上影响了区块链技术的声誉。区块链目前主要被应用在分布式账本上，但是以太坊开发出的智能合约表面区块链能做的事情远远不止记账，区块链的未来应该与其他行业结合，推动下一轮的产业革命。
Pandora's Box Problem
林 涛
摘要
Pandora 在网络上搜索产品资料时，得到 n 个搜索结果链接，但是她只有打开链接、详细调查后，才能知道这个产品到底有多好。然而详细调查的过程是耗费 Pandora 的时间与精力的，在有限的时间精力中，如果点开的第一个产品的评价恰好又不错，那么她就可以立即购买了。假设调查的消耗和产品的质量都可以量化，那么 Pandora 如何让自己的收益最大？换成模型来讲，即 Pandora 手中有 n 个盒子，每个盒子 i 装着一个价值为 vi 的奖品， 服从分布 Fi。Pandora 事先只知道 Fi，只有打开了盒子才能知道 vi。但打开盒子i需要花费代价 ci。Pandora 可以打开多个盒子，但最终只能从打开的盒子中取一个奖品（当然是取最大的 vi）。她应该如何打开盒子？
报告人分享
此次 tutorial 介绍了一个收益最优且简单优雅的算法，称为 Weitzman's algorithm，并讨论了这个问题的一些拓展方法如 Prophet Inequality、放宽约束条件等，详细内容可以参考如下推荐材料。
推荐阅读
[1] Weitzman, Martin L. "Optimal search for the best alternative." Econometrica: Journal of the Econometric Society (1979): 641-654.
[2] Kleinberg, Robert, Bo Waggoner, and E. Glen Weyl. "Descending Price Optimally Coordinates Search." Proceedings of the 2016 ACM Conference on Economics and Computation. ACM, 2016.
[3] Esfandiari, Hossein, et al. "Online Pandora's Boxes and Bandits." arXiv preprint arXiv:1901.10698 (2019).
[4] Doval, Laura. "Whether or not to open Pandora's box." Journal of Economic Theory 175 (2018): 127-158.
[5] Beyhaghi, Hedyeh, and Robert Kleinberg. "Pandora's Problem with Nonobligatory Inspection." Proceedings of the 2019 ACM Conference on Economics and Computation. ACM, 2019.
[6] Gamlath, Buddhima, Sagar Kale, and Ola Svensso. "Beating greedy for stochastic bipartite matching." Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2019.
Some Recent Open Problems in Computational Economics
魏智德
摘要
recourse allocation 在 AI 和计算机科学领域有着广泛的应用。自从1979年，Hylland and Zeckhauser 提出 random allocation problem 以来，各种各样的机制被提出和研究。其中，the Probabilistic Serial mechanism 因其公平性和有效性著称,它是解决随机分配问题的最杰出的协议之一。但是，人们可以通过谎报自己的偏好来获得更大的效用收益。那么他是否能通过精心设计的谎报获得无穷大的收益呢？本次 tutorial 的讲者发现并证明了无论怎么谎报，其收益至多是真实上报的收益的1.5倍，在 tutorial 中，讲者给出了结论的详细证明，并拓展了通过实验进一步评估的效用收益，实验表明，人们操纵规则的动机非常有限。
报告人分享
这些结果为 the Probabilistic Serial mechanism 对策略操纵的鲁棒性提供了一些启示，这比知道它不是激励相容要更进了一步。
下面是报告者为大家提供的满满的干货（
说不定有同学感兴趣都看了呢（
推荐阅读
Mechanism Design in the Information Age
肖 涛
摘要
机制设计理论研究的是在自由选择、自愿交换、信息不完全及决策分散化的条件下，能否设计一套机制(规则或制度)来达到既定目标的理论。
本次 tutorial 中讲者给大家带来了机制设计领域的一个概述。先通过一个竞技体育的例子，说明了一个设计糟糕的机制会让整个竞争环境走向大家都不希望看到的结果，进而说明机制设计的重要性。接着，讲者展示了最经典的拍卖问题以及解决方案：对于效益最大化问题，一个最简单的做法是著名的 VCG 机制；对于单物品收益最大化问题，Myerson 给出了最优拍卖机制；对于多物品收益最大化，有一些基于简单机制的近似结果。这些理论非常经典，但模型过于理想化，故在新时代错综复杂的拍卖场景中遇到各种各样的挑战，比如预算可行性、差异拍卖行为以及私有数据操控。结合自己的一些工作，讲者分别介绍了这三类问题挑战的难点，以及一些现有的解决方案和结论。
推荐阅读
现实拍卖场景中还有很多挑战亟待解决，有很多有意思的理论和实际问题，而且机制设计也是一个很容易上手的方向。希望通过这个报告引起大家对机制设计的兴趣，并开始动手做相关研究。
Computational Social Choice
周子鑫
摘要
计算社会选择理论，是社会选择理论和理论计算机科学交叉的一门学科。它从计算角度分析社会偏好汇总这个问题。计算社会选择理论关注社会选择机制的有效性，计算复杂性，是否能被坏人操纵，操纵它的计算复杂性以及如何高效表达和获取个人偏好。本次 tutorial 中讲者通过讲解各种投票模式的理论模型向大家展示了该领域的概况。
报告人分享
选择这个题目是因为计算社会选择理论能通过计算的视角帮助我们更好地理解社会选择中涉及的公平性，社会总福利，计算高效性等问题，并设计出更好的，更适合特定场景的社会选择机制。对于这个学科未来的方向，我想一方面应该是结合 social learning，借助大数据和机器学习的工具来更有效地学习人们的偏好，从而得到更好的社会选择；另一方面由于社会选择理论本身具有良好的公理化刻画，具有良好的可解释性，因此在可解释 AI 的方面会有重要的应用。
第二届北京大学前沿计算研究中心及图灵班科研展示活动全纪录
近 期 热 点
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。