大作业要求

基本要求

1. 可以自由组成不超过3人的小组完成大作业，截止时间待定（课程结束后）

2. 下面给出选题参考

   • 一些选题是实现类的，需要实现论文中的算法等
   • 一些选题是理论类的，根据一篇或多篇理论性的论文写一篇阅读报告
   • 如果在以下推荐选题外还有自己感兴趣的题目，可以联系助教确定内容

3. 最终需要提交的内容如下

   • 实现类：要求提交一份实验报告（pdf 格式），实验代码需要打包提交。实验报告至少需要包括问题描述，文章的整体思路，以及关键定理的描述（不一定需要证明，但要解释清楚）、实现的核心算法介绍，以及实验结果与分析（包含运行结果截图等）
     • 总而言之，理论和实验都重要，因为大部分的文章在模型建立上有一定的创新性，关键的思想与定理需要理解
   • 理论类：要求提交一份阅读报告（pdf 格式），要求至少需要包括问题描述，文章的整体思路，以及关键定理的描述、insight 以及证明等
     • 注意不允许直接翻译论文作为报告，必须整理串联论文的思路，报告的目标应当是一本合格的教材能让其他人在不看论文的情况下学会论文的核心思想
   • 其余题目相关的个性化要求见选题参考

4. 评分

   • 最核心的两个评判标准：工作量和报告清晰程度
     • 不用太卷，三个人工作量在 3-5 天为宜
     • 报告的主要目标是把实现或理论写清楚，而不是页数越多越好，无效的工作量将不被视为工作量，报告清晰程度表明了你对文章 / 算法的理解深度
     • 下面的题目均给出了难度参考（1-5 分，并且难度只是基于助教本人的主观感受，仅供参考），这些难度只作为评判工作量的参考，实际仍然根据完成情况评分
     • 如果文章较难也不一定要全部理解或实现（例如理论文章证明太长太难可以只叙述大致思路），如果比较简单也可以添加自己的思考
   • 如果是实现类，请务必写清楚哪些代码是属于你们自己实现的，也就是请务必强调自己的工作量，理论类请务必标明参考文献
   • 原则上小组成员分数相同，如果出现“搭便车”行为，组内协调无果可以申请分数上的调整

5. 其它

   • 有问题请及时联系助教，特别是概念不理解或者感觉有的问题可能比较难的时候
   • 下面给出的论文均可以直接点击论文标题下载，如果你还希望搜索其他论文，可以使用 DBLP、Google scholar 等，论文请注意中稿会议 / 期刊级别，可参考 CCF 评级、清华评级等

实践类选题

选题一：机器学习模型版本化市场

• 难度：3.5

• 参考论文

  • Towards Model-based Pricing for Machine Learning in a Data Marketplace
  • Dealer: An End-to-End Model Marketplace with Differential Privacy

• 提示与要求

  • 参考文献第一篇主要考虑了机器学习模型无套利版本化定价问题，第二篇添加了数据提供方的收益分配部分
  • 理论部分应当特别关注第一篇参考文献中的机器学习模型版本化方法、无套利条件，应当叙述清楚
  • 实现应特别关注第二篇参考文献的算法 1-7，算法 8 给出了整体算法总结，你应当将其中算法的基本功能都实现并在报告中描述清楚
  • 实现只要求整体市场框架能运行即可，其中的数据都可以使用模拟或随机的，也无需前端界面
  • 如果希望拓展工作，一方面可以增加其他定价算法，另一方面可以让市场更真实，例如接入真实机器学习模型，实现前端界面等

选题二：机器学习模型交易完整流程

• 难度：3.5

• 参考论文

  • A Marketplace for Data: An Algorithmic Solution

• 提示与要求

  • 本文重点是三个步骤：第一步是诚实的机器学习模型拍卖，第二步是 MWU 算法动态定价，第三步是收益分配
  • 理论部分应当关注文章所有叙述的定理，最好能按自己的语言再将证明叙述，但也不强制要求
  • 实现部分将三个步骤连接起来，能输入一个买家运行一次完整流程即可，其中的数据都可以使用模拟或随机的，也无需前端界面
  • 如果希望拓展工作，一方面可以增加其他定价算法，另一方面可以让市场更真实，例如接入真实机器学习模型，实现前端界面等

选题三：无先验无穷拍卖

• 难度：3.5

• 参考论文：

  • Competitive Auctions

• 提示与要求：

  • 本文研究了买家估值无先验、产品数量无限的情况下的最优拍卖机制，提出了一个合理的 benchmark 衡量拍卖机制的好坏
  • 理论部分要求读者重点关注论文 1-4 节中的定理与证明，要求读者理解并用自己的语言重新组织并严禁清晰地叙述，第 5 节及之后的定理可以只了解结论，在报告中简要叙述即可
  • 实验部分要求实现 random sampling 拍卖机制，同学们应当随机生成大量买家的估值，然后看 random sampling 机制在实际容易出现的估值情况下的竞争比

选题四：数据市场中的恶意行为

• 难度：3

• 参考论文：

  • Protecting Data Markets from Strategic Buyers

• 提示与要求：

  • 本文讨论了数据市场中买家可能出现的一些策略性行为，并给出了简单的解决方案
  • 理论部分要求读者理解文章中给出的三种策略性行为以及相应的解决方案的合理性（在报告中简要描述即可），实验部分要求读者根据 7 EVALUATION 中提出的 RQ（research question）给出自己的实验对这些问题的回答
  • 必答题：你觉得论文作者给出的解决方案是否合理，在这些解决方案下买家是否仍然有可能实施更高级的策略性行为？你还能相到数据市场中其他可能出现的买家策略性行为吗？请给出一些并提供合理的解决方案。

选题五：动态定价

• 难度：3.5

• 参考论文：

  • Learning to Price Homogeneous Data

• 提示与要求：

  • 本文考虑了有多种不同类型的数据买家（即他们的需求不同）的情况下，如何利用多臂老虎机算法平衡对不同类型数据买家估值的探索与利用，考虑了随机以及对抗性场景的情况，分别提出了基于 UCB 和 FTPL 两个非常经典的算法的动态定价算法
  • 要求同学们理解并实现文章中基于 UCB 和 FTPL 的算法，理论部分要求同学们理解算法设计的思想，以及证明的思路（不要求理解非常具体的证明细节），实验部分可以自己随机产生一些数据（对抗性同学们可以自己思考如何生成数据）进行实验，检验算法的实际效果

选题六：查询定价版本化市场

• 难度：4

• 参考论文：

  • QIRANA: A Framework for Scalable Query Pricing

• 提示与要求：

  • 这篇文章基于查询无套利定价的理论（此前的其他文章已经提出）给出了适用于大型查询的查询无套利定价算法，核心在于基于支撑集的概念以及进一步的小优化大大降低计算量
  • 定价函数直接选定为 Weighted Coverage 函数即可，并且不需要实现带有聚合函数的查询定价，只需要实现 SPJ 查询定价即可，此外 history aware 应当实现
  • 基于文章给出的数据集（不需要全部做，只需要做出 1-2 个就够了）以及最后给出的查询（选择有代表性的实验即可）进行实验，最终提交的代码能输入查询输出价格即可，然后在报告中应该给出你们在一些有代表性的查询上给出的价格，检验算法的合理性

理论类选题

选题七：无套利查询定价理论

• 难度：3.5

• 参考论文：

  • The design of arbitrage-free data pricing schemes

• 提示与要求：

  • 本文给出了 QPS 和 APS 查询定价满足无套利的充要条件，通过格结构非常精妙且简洁地达到了目标
  • 报告中要求同学们将全文所有证明理解清楚并在报告中详细描述，并清晰地表达转化为格结构背后的直观想法是什么
  • 可以在本文之上拓展阅读其他无套利定价文献，综合其它文献中提到的方法和思想使得报告更加充实（但不是必须完成的要求）

选题八：信息定价机制设计

• 难度：5

• 参考论文：

  • Optimal Mechanisms for Selling Information
  • Selling Information Through Consulting

• 提示与要求：

  • 两篇参考文献解决的是同一问题，即允许动态出售信息的情况下的最优信息出售机制，但第二篇简化且合理化了第一篇的模型，因此阅读时第一篇冗余的复杂部分可以忽略，书写报告时也应当将两篇文章融合起来写
  • 注意第一篇文章在写作上略为晦涩，而在完成报告时要求同学们按照自己的理解重新组织，将其中的核心思想清晰表达，特别是动态机制的描述、多种情况下显示原理的证明或者不成立的理由、最优信息价格出售机制的线性规划
  • 两篇文章中的部分长证明可以根据同学们自身能力决定是否仔细阅读，但文章给出的具体计算例子必须理解并清晰描述，书写报告时复杂的证明可以只叙述核心思想

选题九：隐私数据获取机制

• 难度：4

• 参考论文：

  • Conducting Truthful Surveys, Cheaply
  • Optimal Data Acquisition for Statistical Estimation

• 提示与要求：

  • 第二篇参考文献只需要看到 4 Multi-dimensional Parameters for moment estimation 之前的内容即可
  • 以上两篇参考文献希望解决的是同一个问题，但第二篇是第一篇的改进版本，因此报告中应当将两篇文章融合起来写
  • 两篇文章研究的都是在数据提供方有隐私成本，隐私成本有先验分布，但隐私成本与隐私数据本身有未知相关性时，如何权衡收集到数据的方差和价格的机制设计问题；
  • 要求同学们重点分析两篇文章如何将问题形式化并转化为可解的问题（其中有一部分基于反向拍卖版本的迈尔森引理），并分析两篇文章给出的最优机制的特点（需要将核心定理的 insight 和证明严谨且清晰地叙述，复杂的证明可以只叙述核心思想）

选题十：隐私数据与价格歧视

• 难度：3.5

• 参考论文：

  • The Limits of Price Discrimination
  • Online Privacy and Information Disclosure

• 提示与要求：

  • 参考文献第一篇只需要阅读 C. Constructive Approaches and Direct Segmentations 之前的内容即可，注意开头的内容可能写得比较晦涩，看不懂了可以直接从 I. Model 开始阅读
  • 参考文献第一篇主要建模了使用隐私数据实施三级价格歧视的场景，并分析了福利情况
  • 参考文献第二篇基于参考文献第一篇的模型（将一维拓展到多维），并考虑了平台推荐系统带来的影响，研究了卖家使用或不使用价格歧视的情况下的卖家利润和消费者福利等
  • 重点应在参考文献第一篇如何建模价格歧视（分割市场）、如何得到福利三角形以及其中具体例子中体现出的 insight，以及第二篇参考文献的建模和重要结果的严谨推导；文章的核心建模需要叙述清晰，核心定理的 insight 以及证明要描述准确且清晰

选题十一：数据外部性（买家侧）

• 难度：4.5

• 参考论文：

  • A Monopolistic Market for Information
  • Selling Information in Competitive Environments

• 提示与要求：

  • 参考文献第一篇描述了在金融市场中，出售数据导致市场受到信息影响进而对没有购买数据的人产生外部性的情况下，垄断数据卖家最优出售数据的机制
  • 参考文献第二篇描述了在不完全信息博弈中出售信息时，面对数据买家之间竞争带来的外部性，垄断数据卖家最优出售数据的机制
  • 着重分析以下两个问题：第一，外部性使得出售信息的机制相较于没有外部性的情况下有什么不同，其中的 insight 是什么；第二，以上两篇文章描述的外部性之间有什么异同，从建模、博弈结果等角度展开分析
  • 文章的核心建模需要叙述清晰，核心定理的 insight 以及证明要描述准确且清晰（复杂的证明可以只叙述核心思想）

选题十二：数据外部性（卖家侧）

• 难度：4

• 参考论文：

  • Too Much Data: Prices and Inefficiencies in Data Markets

• 提示与要求：

  • 参考论文中 III. Competition among Platforms 一节不要求看
  • 本文主要讨论了不同隐私数据拥有者的隐私数据之间存在相关性的情况下（数据卖家之间存在外部性），数据市场的均衡、福利分析以及机制设计
  • 重点理解文章如何刻画隐私数据之间的相关性以及相关性对均衡价格、均衡福利等影响，以及最后如何设计去相关性的方法来解决外部性问题，用自己的语言重新叙述主要定理的证明，理解主要定理背后的 insight