机制设计原理与应用(一)机制设计基础

什么是机制设计？

微观经济学和CS /EE的交叉学科。它采用了一种工程方法来设计激励机制，以实现战略环境中不完全信息的预期目标。机制设计具有广泛的应用,特别是在资源管理方面。

[TOC]

1 机制设计的基础

1.1 简介

例1：通过拍卖出售房屋

假设你要通过拍卖出售你的房子。

要求每个买家送来一个密封的最终出价，然后做出决定。
允许买家分几轮出价，在每一轮中，他们都被告知最高出价，然后被要求修改他们的出价。

问题：（机制设计旨在解决）你应该选择哪种形式的拍卖？如何设计一个拍卖，使最高价格的交易能够达成？

例2:D2D内容共享

考虑一个简单的设备对设备（D2D）的内容共享模式。

每个UE向BS声明一个内容请求，BS决定是否为其提供服务，并选择建立蜂窝状链接或请求拥有该内容的另一个UE通过D2D链接分享该内容。
由于D2D消耗传输功率，如果不能得到奖励，内容所有者UE可能不愿意参与内容共享。

由于蜂窝网络有严格的容量限制，BS可以采用一种机制来鼓励D2D内容共享，以减少蜂窝流量。

BS首先收集所有的内容请求。
内容所有者UE在D2D传输中竞标其成本。
BS决定链路和功率分配，并给予奖励。

问题：（机制设计的目的是解决）如何确定最佳的资源分配和奖励？如何确保智能UE将报告其实际成本？

1.2 机制设计与博弈及优化的关系

与传统的优化问题不同。机制设计是基于个人的私人信息。机制设计关心的是个人的战略和效用。

与传统的博弈问题不同。机制设计通常有一个集中的目标。机制设计要求个人遵守规则。

机制设计与优化和博弈有一些共同的想法。因此，在解决机制设计问题时可以应用一些优化和游戏技术/算法。

1.3 机制设计的定义

机制设计的重点是设计能够产生某种预期结果的游戏。机制设计理论也被称为反向博弈理论。

机制设计的一个关键特征是，最佳分配的确定取决于代理人私下拥有的信息。

这种私人信息必须从代理人那里引出。
智能代理可能误报他们的私人信息。
设计一种信息交互机制，即使代理人的行为具有战略性，结果也是最优的。

定义：机制设计可以被认为是对规则的设计，以保证完全战略代理中的理想结果。

1.4 机制设计的基础知识

拍卖是最典型的基于定价的机制之一。

一个资源分配和价格发现的过程。可以描述为：

1.问题：确定拍卖的分配和定价规则。可以允许哪些出价或如何出价？

应如何分配资源？
需要收取什么价格，或者是什么是锤子价格？

2.目标：达到某些目标（例如，收人最大化或者社会福利最大化）

3.基本要素：

买方：想购买商品的人。
卖家：拥有商品并愿意出售商品的人。
拍卖者：一个控制者（或卖方/买方本身）
商品：计算资源、能源、时间长度、渠道等。
价格：投标/要价，落锤价（最终付款）

4.术语：

私人信息（Private information）：个人的私人偏好。
价值（Value）：对买方需求的货币评估；价值可以是私人的。
竞价（Bid）：基于私人信息的策略。
结果Outcomes（包括支付和分配，payment and allocation）：根据出价决定。
买方的效用函数（Buyer’s utility function）：价值和支付之间的差异，买方能从这次拍卖中获得的。
卖方的收入（Seller’s revenue）：来自买方的总付款。
社会福利（Social welfare）：所有用户（包括买家和卖家）的效用之和。

5.拍卖机制的时间线：

进行招标过程
确定最终结果

1.5 拍卖机制的类别

正向或反向：买家或卖家方面的竞争。

单边或双边：单方面或双方的竞争。

单物品或多物品：需求提供单物品或多物品的商品。

离线或在线：静态或动态（即时）。

福利或收入最大化：不同的目标。

1.6 设计目标

社会福利最大化

收入最大化

举例如下：一个拍卖机制(Q,P).

U_i = v_i \cdot Q_i(b_i) - P_i(b_i, Q_i(b_i)) ; U_s = \sum_{i \in B} P_i(b_i, Q_i(b_i))

福利最大化：

max \sum_{i \in B} U_i + U_s

收入最大化：

max R_s = U_s = \sum_{i \in B} P_i(b_i, Q_i(b_i))

1.7 希望的属性限制条件

基本（必须包括）

激励相容性/真实性/战略防范性（Incentive compatibility/truthfulness/strategy-proofness，IC）：没有一个买家 i 可以通过虚假出价 $b_i \neq v_i$ 来提高自己的效用 $U_i$ ,而不考虑其他买家。真实性是一种弱优势策略；纳什均衡。
个人合理性（Individual rationality，IR）：每个真实的买方 i 在拍卖后都能获得一个非负的效用 $U_i$ 。
计算效率：不是制约因素而是一种要求。