Walrasian Equilibrium: Hardness,Approximations and Tractable Instances

We study the complexity issues for Walrasian equilibrium in a special case of combinatorial auction, called single-minded auction, in which every participant is interested in only one subset of commodities. Chen et al. (J. Comput. Syst. Sci. 69(4): 675–687, 2004) showed that it is NP-hard to decide the existence of a Walrasian equilibrium for a single-minded auction and proposed a notion of approximate Walrasian equilibrium called relaxed Walrasian equilibrium. We show that every single-minded auction has a relaxed Walrasian equilibrium that satisfies at least two-thirds of the participants, proving a conjecture posed in Chen et al. (J. Comput. Syst. Sci. 69(4): 675–687, 2004). Motivated by practical considerations, we introduce another concept of approximate Walrasian equilibrium called weak Walrasian equilibrium. We show NP-completeness and hardness of approximation results for weak Walrasian equilibria. In search of positive results, we restrict our attention to the tollbooth problem (Guruswami et al. in Proceedings of the Symposium on Discrete Algorithms (SODA), pp. 1164–1173, 2005), where every participant is interested in a single path in some underlying graph. We give a polynomial time algorithm to determine the existence of a Walrasian equilibrium and compute one (if it exists), when the graph is a tree. However, the problem is still NP-hard for general graphs.     

WSN中层次性簇聚路由选择算法中的一种优化策略

对层次性簇聚路由算法,提出了一种优化策略。具体实施是在已选出的多个簇首中,以能量均衡损耗和节能为依据,设计一个优化路由机制．选出一个二级簇首,由该二级簇首与汇点通信。通过分析,该策略能够有效的降低网络的能量损耗,大大延长网络的生命周期。     

一种基于高频强调滤波和直方图均衡化的图像增强方法

直方图均衡化能够调节图像的动态灰度范围,是一种经典有效的图像增强方法,但它建立在合并相似像素灰度的基础之上,模糊了图像的细节。高频强调滤波将变换后的低频和高频分量都得到了增强,但是低频分量的增强要弱一些,这样会使得图像边缘更加清晰。实验表明,经该方法增强后的图像,其主观视觉效果明显改善。     

UNIFAC及其改进模型的评价研究

用UNIFAC及其修正模型估算了含芳香烃、二甲苯同分异构体和极性物质体系的汽液平衡,并将计算结果与实验数据相比较。结果表明,原始UNIFAC模型对含二甲苯同分异构体体系计算精度高于UNIFAC(Larsen)模型和UNIFAC(Dortmund)模型好,而对于极性或弱极性体系,则后2种模型结果较令人满意,但对于强极性体系偏差较大。     

基于系统动力学的环境污染演化博弈问题研究

用系统动力学建立环境污染管理问题中政府管理部门与生产排污企业之间的一个混合战略演化博弈模型.仿真结果表明:非对称结构的2*2混合策略演化博弈模型不存在演化均衡.从监管部门的角度出发,改变博弈支付矩阵在演化博弈过程始终保持不变的情况,在博弈支付矩阵中考虑动态惩罚策略.结果表明,本策略的演化博弈模型存在演化稳定均衡,即Nash均衡.系统动力学为演化博弈理论的验证和应用提供一个政策仿真实验平台.     

Stabilization of a 3D axially symmetric pendulum

Stabilizing controllers are developed for a 3D pendulum assuming that the pendulum has a single axis of symmetry and that the center of mass lies on the axis of symmetry. This assumption allows development of a reduced model that forms the basis for controller design and global closed-loop analysis; this reduced model is parameterized by the constant angular velocity component of the 3D pendulum about its axis of symmetry. Several different controllers are proposed. Controllers based on angular velocity feedback only, asymptotically stabilize the hanging equilibrium. Then controllers are introduced, based on angular velocity and reduced attitude feedback, that asymptotically stabilize either the hanging equilibrium or the inverted equilibrium. These problems can be viewed as stabilization of a Lagrange top. Finally, if the angular velocity about the axis of symmetry is assumed to be zero, controllers are introduced, based on angular velocity and reduced attitude feedback, that asymptotically stabilize either the hanging equilibrium or the inverted equilibrium. This problem can be viewed as stabilization of a spherical pendulum.     

Correlation of slurry reactor Fischer-Tropsch yield data

First stage slurry reactor Fischer-Tropsch (FT) yield data from Mobil's two-step pilot plant operations for the DOE have been correlated using a modified Schulz-Flory approach but allowing for changes in the probability of chain growth, , at key product molecular weights. Triple values of are invoked to explain (1) the high methane yield and (2) the very broad molecular weight distribution of the wax fraction, as compared to (3) moderate values of ₂ of between 0.79 and 0.85 for the C₂–C₂₀ hydrocarbons. Over this range, wax yields from 10 to 76 wt% are accommodated, at values of ₃ from 0.90 to 0.98. The second break in the yield-molecular weight curve occurs at the carbon number where most of the component remains in the reactor as liquid rather than leaving as vapor product. It is assumed that this is a function of vapor-liquid equilibrium. The correlation has proven useful in developing a computer model of the FT synthesis loop which is part of a baseline design and economic study for DOE/PETC.     

基于博弈论的多服务器多用户视频分析任务卸载算法

在过去的近10年中,人工智能相关的服务和应用大规模出现,它们要求高算力、高带宽和低时延.边缘计算目前被认为是这些应用最适合的计算模式,尤其是视频分析相关应用.研究多服务器多用户异构视频分析任务卸载问题,其中用户选择合适的边缘服务器,并将他们的原始视频数据上传至服务器进行视频分析.为了有效处理众多用户对有限网络资源的竞争和共享,并且能够获得稳定的网络资源分配局面,即每个用户不会单方面地改变自己的任务卸载决策,该多服务器多用户异构视频分析任务卸载问题被建模为一个多玩家的博弈问题.基于最小化整体时延的优化目标,先后研究非分布式视频分析场景和分布式视频分析场景两种情形,分别提出基于博弈论的潜在最优服务器选择算法和视频单元分配算法.通过严格的数学证明,两种情形下提出的算法均可以达到纳什均衡,同时保证较低的整体时延.最后,基于真实数据集的大量实验表明,所提方法比其他现有算法降低了平均26.3%的整体时延.     

认知雷达抗干扰中的博弈论分析综述

雷达对抗的核心研究内容主要是干扰策略与抗干扰策略之间的对抗博弈,其作为电子战研究领域的热点一直备受学者们关注.该文综述了学者们利用合作与非合作博弈方法来分析雷达在进行目标探测和干扰抑制时所使用的策略,主要通过不同体制的雷达利用认知技术感知和学习外界复杂的电磁环境,合理地分配发射功率、控制编码序列、设计波形、研究检测和跟踪方法以及分配雷达通信资源等.这样雷达既节约发射所消耗的功率,又可以自适应地搜索和跟踪目标而不被敌方所发现,从而使雷达在复杂多变的现代战场环境中达到自身最优的性能.最后,对认知雷达抗干扰中的博弈论分析研究进行总结和展望,并指出了一些博弈论在认知雷达抗干扰策略应用中所面临的潜在问题和挑战.     

横风下高速列车系统动力学的平衡状态法

基于车辆-轨道耦合动力学和空气动力学提出了一种快速计算横风下高速列车系统动力学行为的平衡状态方法.首先,忽略轨道不平顺并利用流固耦合联合仿真方法计算横风下高速列车的平衡状态;然后,将平衡状态下的气动力加载到车辆-轨道耦合动力学模型并计算高速列车动力学响应.利用建立的平衡状态方法,研究了列车在速度为13.8 m/s的横风下以350 km/h速度运行时的流固耦合动力学行为.比较了平衡状态方法和联合仿真方法两种方法下列车姿态、安全性和舒适性指标的差异,计算结果差别在3.26%以内.研究结果表明:平衡状态方法计算横风下高速列车流固耦合的效率更高.