CMSC 5728 Decision Analysis & Game Theory - Lecture 06
- English Auction
- First-Price Sealed Auctions
- Dutch Auction
- Second Price Auction, Sealed-Bid
Auctions
拍卖是出售没有固定市场的固定商品的一种方式
竞拍者进行投标
- 提议为商品支付各种金额的费用
商品出售给出价最大的投标人
一些拍卖都是信息不完整（可以建模为所谓的贝叶斯游戏）
私人价值拍卖
- 每个投标人可能具有不同的投标人价值（BV），即该投标人对商品的价值
- 投标人的BV是他/她的私人信息，而其他人不知道
根据规则对拍卖进行分类
- English
- Dutch
- First price sealed bid
拍卖中可能出现的问题是共谋（欺诈目的的秘密协议）
- 一群竞拍者不会互相竞价来保持低价格
- 伪造（虚假）出价的竞拍人提高价格（因此拍卖师获利）
- 如果存在共谋，则均衡分析不再有效
English Auction
规则
- 拍卖师向小组征集开标价
- 任何想要竞标的人都应至少喊出高于之前 c 的新价（例如 c = 1 美元）
- 出价一直持续到只剩最后一个人
- 最高出价者以等于其最终出价的价格出售了该物品
对于每个竞拍者 i，我们令
- vi 为 i 对该物品的估价（私人信息）
- Bi 为 i 的最终出价
- 如果 i 胜出，那么 i 的收益为 πi = vi - Bi，其他竞拍者的收益为0
NE
- 每个竞拍者 i 参与竞拍直到出价到达 vi，然后退出
- 最高的出价者 i 以价格 Bi < vi 获得物品，并且 πi = vi - Bi > 0
- Bi 是接近于第二高出价者的估价
- 对于每个竞拍者 j ≠ i，πj = 0，即收益都为0
- 假设竞拍者 j 偏离了预定计划
- 如果 j 通过提前退出偏离计划，那么 j 的收益为0，不会更好
- 如果 j 通过出价 Bj > vj 偏离计划，那么 j 的收益为 vj - Bj < 0，更坏
缺点
- 如果竞拍者们的估值范围很大，即不同竞拍者之间的估值差别很大，那么最高和第二高的估值之间的差异可能会很大
- 因此竞拍成功者可能能够以比其估价低得多的价格获得它
- 我们令 n 为竞拍者的数量
- n 越高，最高和第二高出价之间就越可能接近
- 因此竞拍成功者越有可能以接近它的估价值拍得该物品
First-Price Sealed Auctions
- 竞拍者在纸条上写下对物品的出价，然后交给拍卖人
- 拍卖人打开出价，找到最高出价者
- 最高出价者以自己的出价拍下物品
- 竞拍成功者的收益为 BV - 支付的价格
- 其他拍卖者收益为0
假设
- 有 n 个拍卖者
- 每个拍卖者有一个私人的估价 vi
- 关于 vi 的概率分布是常识
- 我们假设 vi 是均匀分布在 [0, 100] 上的
- 令 Bi 为 i 的出价
- 令 πi 为 i 的收益
NE
- 首先我们寻找最优的竞价策略
- 如果 Bi ≥ vi，那么 πi ≤ 0
- 所以我们假设理性：Bi < vi
- 因此，我们有
- 如果 Bi ≠ max{ Bj }，πi = 0
- 如果 Bi = max{ Bj }，πi = vi - Bi
- 竞拍者 i 需要出低于 vi 多少的价？
- Bi 越小
- i 越不可能拍得该物品
- i 拍得该物品，收益就越大
- Bi 越小
n = 2 情况
假设你的 BV 是 v，出价是 B
令 x 为其他竞拍者的 BV，ax 为其出价，0 < a < 1
你不知道 x 跟 a
你的预期收益是：
- E ( π ) = P ( your bid is higher ) * ( v - B ) + P ( your bid is lower ) * 0
如果 x 是均匀分布在 [0, 100] 上，那么概率密度函数是 f ( x ) = 1 / 100，0 ≤ x ≤ 100
所以 E ( π ) = B ( v - B ) / ( 100a )
如果你想要最大程度提高预期收益（因此你对金钱的估价是风险中立的），那么最高出价就是
- 当 v - 2B = 0 => B = v / 2 时，最大化
所以出该物品 1 / 2 的价格是值得的
n ≥ 2 情况
当 n 增加的时候，B -> v。因为竞争加剧导致出价接近估价。
Dutch Auction
规则
- 拍卖人以高价开始
- 拍卖人逐渐降低价格，直到一些买家喊“mine”
- 第一位喊”mine”的买家以拍卖人的叫价拍得商品
- 成功拍卖的竞拍者获利 BV - prices
- 其他竞拍者获利0
理论上来讲 Dutch Auction 等同于 first-price sealed auctions
- 对象以最高价出售给出价者
- 竞拍者必须在不知道其他任何出价者的出价的情况下选择出价
- 最佳出价策略是相同的
Second Price Sealed Auction
- 竞拍者在纸条上写下对物品的出价，然后交给拍卖人
- 拍卖人打开出价，找到最高出价者
- 最高出价者以第二高出价者的出价拍下物品
- 竞拍成功者的收益为 BV - 支付的价格
- 其他拍卖者收益为0
均衡竞价策略
- 以真实价值来出价是一种弱势策略，此属性也称为拍卖的真实或策略验证性。为了说明这一点，需要证明出价过高或过低不会增加收益，还可能降低收益。
- 令 V 为对物品的估价，X 为其他竞拍者出的最高价
- 令 SV 作为出价 V 的策略，πv 为使用 SV 的收益
- 令 SB 为出价 B ≠ V 的策略，πB 为使用 SB 的收益
B、V、 X 有 3! = 6 种排列顺序
本 auction 是近乎等于 English auctions的
- 物品给最高出价者
- 价格接近于第二高的 BV
Coalitional Games with Transferable Utility
给定一组 agents，一个联盟博弈定义了每组（或多个联盟）agents 能为自己做得收益
- 不关注
- agents 个人在联盟中的选择
- 他们如何合作
- 不关注
Transferable utility 假设：联盟的收益可以在其成员之间自由重新分配
- 只要系统中存在用于交换的通用货币，就满足
- 这意味着可以为每个联盟分配一个值作为其收益
一个 coalitional games with transferable utility 通常由 G = (N, v) 来表示
- N = {1, 2, …, n} 是一个 players 的有限集
- v: 2^N -> R 将与每个联盟 S ⊆ N 关联的实值收益 v(S)，联盟成员可以在相互之间分配
coalitional game theory 通常需要回答两个问题
- coalition 的形式是什么？
- “the grand coalition”（所有的 agents）
- coalition 如何将 payoff 分给它的成员？
- 上一个问题就取决于这个问题中的正确选择
- coalition 的形式是什么？
Example: A Voting Game
- 一个包含4个政党的100名代表的议会
- A：45名、B：25名、C：15名、D：15名
- 他们投票决定是否通过1亿元的支出单（以及每方控制的金额）
- 需要大于等于51的票才能通过
- 如果没有通过，每个政党都获得0
- 一个 voting game 会包括
- 一个 agents 集合 N
- 一个胜者 coalition W ⊆ 2^N
- 在这个例子中，所有 coalition 有足够的票通过这个支出单
- 对每个 coalition S ∈ W，v(S) = 1
- 对每个 coalition S ∉ W，v(S) = 0
Superadditive Games
如果 coalition 的价值至少等于其两个不相交成员的价值之和，那么一个 coalitional game G = (N, v) 是 superadditive
voting game 例子是 superadditive
如果 G 是 superadditive，那么 grand coalition 会是最可能的 payoff
如果以下成立，那么 G = (N, v) 是 superadditive
