最优算法机制设计若干问题的研究

我们从计算经济学和算法设计等两方面对该项目进行了研究： 1) 我们给出了随机的诚实机制的等价条件。它刻画出了随机的诚实机制的内在的组合特性。该结果能够指导我们设计诚实的机制。 2) 在此基础上，我们给出了一个框架可以将一系列优化问题的近似算法在不改变近似度的前提下，转换成诚实机制，这将有助于我们设计收益最优化的诚实机制。 3) 我们从理论上证明了如果一个竞拍者以多个身份进行拍卖的话，则广义二价拍卖机制将不一定会收敛到一个稳定的状态，甚至不存在一个诚实的而且社会效益最大化的机制。而在目前的现实的广告位置拍卖中，这种现象却屡见不鲜。因此，该研究成果告诉我们在设计拍卖机制的时候，应当严格禁止一个拍卖者以多个身份进行拍卖。 4) 我们提出了弱支配策略删除均衡的概念，并且证明在通用二价拍卖中，在只有两个参与者以及两个广告位的情况下，无论其删除过程怎样，其最终结果几乎满足社会效益最大化。 5) 我们对网络论坛中的帖子的文本内容设计了分析工具，并进行情感分析。该分析能够对股市进行较为准确的分析和预测。我们利用数据挖掘技术对网络论坛对股市进行分析的研究思路和技术可以帮助我们来挖掘广告竞拍者的竞拍行为。 6) 我们研究了世界上最大的B2C市场—eBay下的买家的策略行为，并给出了对称贝叶斯-纳什均衡。我们比较了在此均衡基础上的拍卖商的收益和带有两份拷贝的二价拍卖模型下的拍卖商的收益。我们证明了在绝大多数情况下前者的收益要小于后者的收益。 7) 我们研究了基于约束规划方法的调度问题中不确定信息的建模和求解算法，分析了调度问题中的不确定控制行为，运用定量约束满足问题模型对实时调度问题中的不确定控制行为进行基于定量化策略的建模，在约束求解前进行基于约束一致性验证的可调度性分析，并将其融合到已有的约束求解框架，以提高调度算法和系统的可靠性与可信度。此外，我们还分别研究了行车路线为树和图的情况下的车辆调度问题。我们证明了该优化问题的难解性，并给出了相应的近似算法。 8) 我们研究了二进制串在“与”、“或”、“非”等操作下的判定问题、计数问题和优化问题。评审专家纷纷表示该问题描述简单，结论非常有趣。

随着Internet技术的迅猛发展，越来越多的计算逐渐转移到并依赖于Internet这个巨大的计算平台。为了更好地理解Internet，理论计算机科学除了运用传统的逻辑、组合等数学工具外，也开始引入微观经济学以及博弈论的相关知识。本项目正是着眼于由理论计算机领域中的算法和博弈论中的机制设计相结合所产生的新的研究领域- - 算法机制设计中的优化问题。. 本项目将着手刻画收益最优的算法机制的内在组合特性，以及满足不同均衡解的诚实的算法机制的等价条件；并将研究结果应用到广告位置拍卖模型中，设计出公平、合理、实际的收益最优的拍卖机制。. 本项目属于计算机理论科学和经济学中博弈论的交叉学科，是当前国际理论计算机科学界的一个研究热点。本项目扎根于算法设计，研究内容为算法机制设计理论，研究背景为网络广告位置拍卖。其研究结果既可以增进两个学科的融合，又可以推动网络经济的发展。

非线性最优控制简介

解决最优控制问题最大的难点在于HJB方程的求解，只有当系统模型是低阶线性模型时，才有可能给出具有显式表达式的最优控制解。在实际系统里，乃至自然界中，几乎绝大多数系统都是非线性的系统，想得到具有显式表达式的控制量几乎不可能，这就需要借助计算机，以及选择合适的最优的数值解法，以得到最优解。一般的，最优控制问题的求解方法为数值算法。极大值原理和动态规划从理论方面研究了最优控制所应遵循的方程和条件，而最优控制的数值算法则是从计算方面来确定最优控制量的具体方法和步骤。

评价最优控制数值算法优劣的三个主要方面是算法的收敛性、计算复杂性以及数值稳定性。算法的收敛性是保证计算过程能达到正确结果的前提。算法的计算复杂性也尤其重要，这对实时控制具有特别重要的意义。一个好的算法应使计算量和存储量尽可能小，以便能由尽可能简单的计算机来实现计算。好的算法还应具有较好的数值稳定性，即计算的结果对初始数据和运算过程的误差不能过于敏感，同时具有处理病态问题的能力。典型的最优控制数值算法包括:求解由极大值原理导出的微分或差分方程的两点边值问题的各种算法，对动态规划中的贝尔曼方程进行数值求解_的算法，求解线性二次型最优控制问题的黎卡提方程的各种算法，处理控制或状态受约束问题的惩罚函数法，在控制策略的函数空间中利用搜索寻优或梯度寻优技术和牛顿一拉夫森方法等直接求解非线性系统最优控制问题的算法等。其中，针对非线性系统的开环最优控制问题和线性二次型最优控制问题展开的数值算法研究尤多。

非线性最优控制最优问题间接求解法

在间接法中，我们依靠最小值原理和其它一些必要条件得到一个两点边值问题，然后通过数值求解该问题得到相应的最优轨迹。在几种基于打靶法求解两点边值问题的方法中，多重打靶法是最引人瞩目的。而其它的一些间接数值求解法，比如伴随方程的向前一向后积分法、函数空间梯度法等，在过去的几年中应用并不十分广泛。间接法的主要优点是解的精度高，同时方法保证了求解满足最优条件。然而间接法常常会遇到比较严重的解的收敛性问题。如果在求解中，没有关于系统初始值的一个好的选取，或是没有关于约束和非约束下系统运动轨迹的先验知识，收敛过程可能需要花费很长的计算时间，甚至可能根本无法找到最优解。

非线性最优控制最优问题直接求解法

在直接法中，连续性的最优控制问题通过参数化的过程被转化为了一个有限维的优化问题。转化后的问题可以通过一些已有的比较成熟的约束优化算法进行数值求解。相对于间接法而言，直接法无需考虑最优化条件，而是直接求解问题本身。直接法不易受到收敛问题的影响，但估计的精度不如间接法。最优的必要条件不是直接满足的，而且伴随量的估计精度有时也会很差。现在比较常用的几种直接求解方法包括最优参数控制法，有限差分方法，配点法，微分包含方法和伪谱方法。在最优参数控制法中，控制量被单独参数化，同时数值积分方法被用来求解微分方程;在有限差分方法中，原微分方程和边界条件被近似为有限差分方程组:在配点法中，状态量和控制量同时被参数化，在各个节点处，局部分段多项式被用来近似微分方程;微分包含方法只是将状态量参数化，并使用由速端曲线定义的状态变化率;在伪谱方法中，通过全局多项式将状态量和控制量同时参数化，积分方程和微分方程通过求积法被近似。配点法和伪谱方法的一个重要的特点就是伴随量的相合估计。

将委托代理理论和拍卖理论进行有机结合，构建双重委托代理模型，从理论、模型和实证三个层面，深入考察招投标中串谋发生的内在机理及其对招投标结果的影响。在此基础上，考虑到现有招投标机制的缺陷，对招投标中的最优激励机制设计进行探讨。主要特色与创新在于：（1）着重于从多项目、多期重复动态两个维度来研究串谋，而且在研究中将串谋人数和贿赂进行内生；（2）将横向串谋与纵向串谋放在统一分析框架下进行研究，现有研究将两种串谋孤立开来进行研究，而实际上两种串谋是紧密联系且常常会同时发生；（3）现有研究只是笼统地认为增加透明度可以减少串谋的发生，但是没有对合理透明度水平进行系统研究。我们需要对招投标不同阶段应该采取什么样的合理透明度水平（包括披露什么信息，在哪个阶段披露以及对谁披露信息）进行系统深入研究；（4）运用实验经济学的方法对理论研究中的关键性结论进行实证分析，并对最优的招投标激励机制进行绩效评估。