最优机制设计的两种计算机方法

项目名称： 最优机制设计的两种计算机方法

项目编号： No.61303077

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 自动化技术、计算机技术

项目作者： 唐平中

作者单位： 清华大学

项目金额： 25万元

中文摘要： 最优机制问题是人工智能多主体系统，微观经济学，电子商务与在线广告产业共同关心的核心问题。该问题是，卖家在不知道买家对商品估值（但知道买家对商品估值的先验概率分布）的前提下，设计一个出售商品的"机制"，以最大化卖家收益。 出售单件商品的最优机制由Myerson提出，Myerson因此获得了2007年诺贝尔经济学奖。出售两件或多件商品的最优机制在一般情况下至今仍未解决，并进展不大。 本报告提出两条用计算机自动设计最优机制的思路：搜索算法和近似算法。搜索算法首先用参数空间表示所有机制，然后在参数空间进行全局搜索或局部搜索。本报告分析了两种搜索算法的优劣，并发现一类潜在优秀的局部搜索算法。近似算法旨在通过修改简单常用的机制，以近似最优收益。本报告首次提出用简单的"菜单"近似最优机制。在一些特殊的估值分布情形，我们发现简单的菜单已经接近或达到最优。

中文关键词： 最优机制设计；计算机方法；互联网广告；电子商务；人工智能

英文摘要： Optimal mechanism design is, arguably, one of the most central problems in the intersection of Multi-agent system resaerch, micro-economics, E-commerce as well as online ad-auctions. The problem is, for a seller, who has several items for sale but does not know the valuations of potential buyers (however, she does know the distributions according to which the valuations are drawn), to design an auction mechanism that maxmizes her expected revenue. Myerson solved the problem for the single-item case, for which he won Nobel Prize in economics 2007. Since then, few progresses have been made and optimal mechanism for selling multiple items remains unknown. In this report, we propose two potential solution of the problem using computers: search algorithms as weill as approximation algorithms. For search algorithm, we first represent the set of all possible mechanisms as a parameter space, among which we conduct search, using either global or local methods. We analyze the potential pros and cons of two possible search methods and advocate local search using a newly discovered set of start points. For approximation algorithms, the idea is to use simple mechanisms to approximate optimal revenue. In this report, we propose a special set of simple mechanisms: mechanisms that have simple "menue representation".We have s

英文关键词： optimal mechanism design；computational methods；online advertising；e-commerce；AI