如何促进人类社会中的合作和良性竞争, 一直是经济学和管理学中的核心问题。传统研究大多基于经典博弈论方法, 通过纳什均衡分析设计管理机制, 但是现实中人们的行为往往会背离均衡。近年来, 从实验和实证数据出发, 综合博弈论和行为经济学方法研究合作和竞争行为已经成为经济和管理学主流方向之一。本文将首先简要介绍数据驱动的人类行为和机制设计主要研究方法, 包括博弈论、行为经济学、心理学和神经科学等。接下来从影响合作和竞争行为的内在因素、外在因素和制度因素三个维度, 总结数据驱动的人类合作和竞争问题的研究动态。最后, 本文列出了一些当前研究中存在的挑战性问题。
由于信息稀缺性、服务系统的不确定性以及顾客认知能力的有限性, 顾客很难准确估计接受服务后的预期效用, 进而做出理性决策。本文利用Logit选择模型描述有限理性顾客的策略行为, 基于排队博弈理论, 在几乎不可见和完全不可见两种信息水平下分析多重休假M/M/1排队系统中的顾客决策、机构利润与社会福利, 并通过数值算例对比不同信息水平下顾客有限理性水平对机构最优利润和社会福利的影响。结果表明, 在两种信息水平下, 有限理性顾客的均衡策略存在且唯一; 存在唯一最优价格, 使得机构利润最大化; 存在唯一最优价格, 使得社会福利最大化; 随着平均休假时间缩短, 顾客更愿意加入系统, 机构可以获得更多利润, 社会福利也会提高。此外, 在完全不可见情况下, 社会福利关于顾客有限理性水平的变化规律依赖服务价格, 是顾客有限理性水平的单峰函数; 存在一个特定有限理性水平, 使得机构利润和社会福利同时最大化。
广义混合拟变分不等式(GMQVI) 是变分不等式的推广。变分不等式及其推广模型被广泛地应用在经济学、交通、最优控制等领域。基于广义投影算子的相关性质和GMQVI解的特征, 在一定的单调性和紧性假设下, 本文在自反Banach空间中给出了问题(GMQVI) 的正则化间隙函数, 并由此构造了D-间隙函数。同时利用这些间隙函数, 得到了基于正则化间隙函数的局部误差界, 和利用D-间隙函数及正则项刻画的全局误差界。
本文创新性地将设施选址博弈与装箱问题相结合, 定义了一类新的设施选址装箱博弈问题。与经典模型不同, 我们首次分析了物品在访问设施后仍需进一步接受服务的情形, 并将优化目标设定为最小化所有物品的访问距离与所需装箱总数之和。在此模型中, 物品是博弈参与者, 各自拥有位置信息和尺寸信息。首先, 我们研究了物品尺寸为私有信息的情形, 物品的费用由装箱成本分摊。针对此情形下的纯装箱博弈和选址装箱博弈, 我们分别设计了具有策略证明性(防策略) 的机制, 其近似比分别介于[1.691, 2]和[5/3, 7/4] 之间。其次, 针对物品尺寸信息与位置信息均为私有信息且相互关联的更复杂情形, 我们考虑物品费用即为访问设施的实际距离。在此设定下, 我们设计了三个策略证明机制, 并分别严格证明了它们的近似比上下界：第一个机制为[47/35, 11/8], 第二个为[45/34, 1.7], 第三个为[11/9, 10/9]。本研究拓展了设施选址博弈的理论框架, 提出的机制设计方法能够有效处理物品访问设施距离优化与其后续装箱服务资源优化协同的问题, 并在参与者拥有私有信息且可能策略行事的复杂环境下, 保证方案的防策略性和近似效率。
研究带有碳排放成本和计件维护情形的单机调度问题。每完成若干个工件需进行一次维护活动, 机器在加工工件和维护活动时会产生相应的碳排放量。分别针对极小化最大完工时间和总完工时间两个目标函数, 建立了极小化加工成本和碳排放成本之和的调度模型。证明了该问题可转化为指派问题并给出了时间复杂度为$O(n^4)$的多项式时间算法。
本文考虑一类完全非凸的复合优化问题, 其目标函数由如下两部分组成: 关于全局变量不可分的连续可微非凸函数, 与两个关于独立变量的正常下半连续非凸函数。本文提出一种求解该问题的新型黄金比率邻近交替线性化极小化算法。在Kurdyka-Lojasiewicz (简记KL)性质假设下, 证明了由算法产生的迭代序列收敛到问题的稳定点。最后将新算法应用于求解稀疏信号恢复问题, 数值实验验证了新算法的有效性与优越性。
图G的一个正常k-染色是G的一个k色点染色, 使得任两个相邻的顶点都异色。平图G的一个多色k-染色是G的一个k色点染色, 使得每个面出现k种不同的颜色。面f的度数是f上顶点的个数, 用$g(f)$来表示, 令$g(G)=\min\left\{g(f)|f\in F(G)\right\}$, 其中$F(G)$是平图G所有面的集合。显然, 若平图G存在多色k-染色, 则$k\leq g(G)$。Horev等人(2012)证明了3-正则二部简单平图是正常多色4-可染的。在本文中, 我们推广了上述结果, 证明了对于最大度是3的连通二部简单平图G, 若$g(G)\geq 5$, 则G是正常多色4-可染的。条件$g(G)\geq 5$是紧的, 因为存在$g(G)=4$最大度是3的连通二部简单平图G不能正常多色4-染色。
对图G的支撑树T, 其形心是指这样的顶点v, 使得$T-v$的最大分枝具有尽可能少的顶点, 这个分枝的顶点数称为T的形心分枝度量。最小分枝支撑树问题是寻求G的支撑树T, 使得T的形心分枝度量为最小, 这个最小值称为图G的分枝指数。在通信网络设计中, 其实际意义是使从交换中心(形心)引出的所有分枝的负荷尽可能均衡。我们在2022年提出这种新型的选址问题, 并给出基本的理论结果。本文将加深对理论与算法的研究。首先证明此问题的加权形式即使对平面图也是NP-困难的。然后对一些重要的特殊图类, 如多面体图、超立方体、乘积图$K_m\times K_n$和二部图的补图等, 分别给出这些图类分枝指数的精确值, 并得到一个启发式算法。
本文以制造系统为背景, 提出一个在服务启动$N$-策略控制下具有检修策略和不同到达率的M/G/1排队模型。首先运用更新过程理论、全概率分解技术和拉普拉斯变换, 研究系统在任意时刻$t$队长的瞬态性质, 得到了瞬态队长分布关于时间$t$的拉普拉斯变换表达式。然后在瞬态分析的基础上, 使用洛必达法则得到队长稳态分布的递推表达式。最后, 在建立费用模型下, 应用更新报酬定理, 得到系统在长期运行下单位时间内的期望费用表达式, 并通过数值实例讨论了系统启动服务的最优控制策略和最优检修策略。
超图平衡二划分是超大规模集成电路物理设计的重要一环。Kernighan-Lin算法和Fiduccia-Mattheyses算法等迭代优化算法是求解该NP-困难问题的常用方法。然而, 这些算法具有以下缺点: 一是对于较差的初始解, 算法容易陷入局部最优。二是由于平衡条件的约束, 顶点的移动受到诸多限制。针对上述问题, 本文将超图平衡二划分问题转化为0-1规划问题, 并设计了求解该问题的离散迭代算法, 在一定程度上克服了传统的迭代算法受平衡条件与初始解约束的缺点。在ISPD98电路划分测试样例上, 本文的算法取得了比Fiduccia-Mattheyses算法质量更高的解。在20次随机实验中, 本文的平均割边数比Fiduccia-Mattheyses算法少13.2%。将本文的结果作为Fiduccia-Mattheyses算法的初始解作进一步优化, 所产生的平均割边数比Fiduccia-Mattheyses算法少30.1%。不仅如此, 本文的算法还可以嵌入到多级划分算法框架中, 取得的平均割边数比multilevel partitioning (MLPart) 少3.6%。
填充函数法是一种用于寻找无约束优化问题全局最优解的确定性方法, 这种方法的核心技术是构造填充函数, 使得迭代过程不断跳出当前的局部极小点。目前见到的填充函数一般都含有参数, 而参数的选取对算法的计算效果影响较大。本文利用填充函数的定义, 具体构造出一个新的无参数填充函数, 由此提出了新的全局优化无参数填充函数方法, 数值实验表明, 该方法是可行的和有效的, 具有更好的全局寻优能力。
稀疏正则化模型在信号和图像处理等反问题中有很广泛的应用。本文主要研究线性最小二乘$\ell_0$极小化问题的快速求解方法。外推向前向后分裂算法是最流行的求解方法之一。根据$\ell_0$正则化问题和该算法的特点, 我们将快速收敛的拟牛顿方法合理地应用于外推步中, 进而提出了一种分块变尺度外推算法, 并证明了其收敛性行为。我们在理论上证明了其快速性: 该方法具有线性收敛率, 甚至超线性收敛率。最后, 我们也通过数值实验展示了本文算法的有效性和快速性。
标量化方法是多目标优化问题研究的基本内容之一。本文首先对广义Tchebycheff范数的性质进行研究, 获得了其在非负象限上的严格单调性等结果。进一步, 利用广义Tchebycheff范数的这些性质研究了多目标优化问题弱有效解、有效解、严有效解和真有效解的两类标量化结果。同时也指出, 在目标函数的凸性假设下, 本文研究的标量化与加权标量化等价。
本文研究了单机上两代理串行分批排序问题, 分批时的每批加工时间有容量限制, 并且每批有一个分批费用, 该费用为常数, 且工件加工不可中断。对两个问题进行了考虑: 一个问题是在其中一个代理的最大完工时间与分批费用之和不超过某一阈值的前提下, 最小化另一个代理的总完工时间与分批费用之和; 另一个问题是在其中一个代理的总完工时间与分批费用之和不超过某一阈值的条件下, 最小化另一个代理的总完工时间与分批费用之和。这两个问题都是NP困难的, 对第一个问题给出了(2, 3/2)-近似算法。对第二个问题, 设计了渐近近似比为(2, 2)的近似算法。
设A和B是两个集合, A和B的对称差是由$A\cup B$中所有不属于$A\cap B$的元素组成的一个集合, 记为$A\Delta B$。若一个超图不含有三条互不相同的边A, B, C使得$A\Delta B\subset C$, 则称该超图是一个可消去超图。一个3-一致可消去超图同时不含$F_4=\{abc, abd, bcd\}$和$F_5=\{abc, abd, cde\}$作为子超图。Bollobás (1974) 给出了3-一致可消去超图的最大边数, 并得出平衡的完全3-部3-一致超图是唯一达到最大边数的3-一致可消去超图。Keevash和Mubayi (2004) 进一步确定了平衡的完全3-部3-一致超图是唯一不含$F_5$作为子超图且边数达到最大的3-一致超图。设$\mathcal{H}$是一个超图, W是顶点集$V(\mathcal{H})$的一个非空子集。如果超图$\mathcal{H}$中的任意一条边只包含W中的一个顶点, 则称W是超图$\mathcal{H}$的一个独立横贯。在本文中, 我们得到了具有独立横贯的3-一致可消去超图p-谱半径的最大值。进一步, 我们证明了当p>2时, 平衡的完全3-部3-一致超图是唯一具有独立横贯且p-谱半径达到最大的3-一致可消去超图。
本文研究广义弱混合向量拟平衡问题的逼近定理和通有收敛性。首先利用Fan-Knaster-Kuratowski-Mazurkiewicz (Fan-KKM) 引理给出了广义弱混合向量拟平衡问题解的存在性定理。然后基于Simon的有限理性理论, 在较弱的条件下给出了广义弱混合向量拟平衡问题的一个逼近定理。最后运用Fort定理, 证明了在Baire分类意义下广义弱混合向量拟平衡问题的解具有通有收敛的结果。
自填充函数算法被提出以来, 参数被视为制约算法效率的主要因素, 因此构造无参数的填充函数显得极为重要。为了提高算法效率, 本文构造了一类新的无参数的填充打洞函数, 分析并讨论了该函数的性质。基于新的填充打洞函数, 提出了一个新的全局优化算法, 并对算法进行了数值实验, 数值实验结果表明该算法可行且有效。
设$\mathcal{H}$是一个图族。$\mathcal{H}$的平面Turán数, 记为$\text{ex}_{\mathcal{P}}(n,\mathcal{H})$, 表示不包含$\mathcal{H}$中任一个图的n阶平面图的最大边数。本文研究图的特定子图-三角块的划分, 在该划分基础上对每个三角块对图G的顶点、边和面的贡献计数。结合平面图的结构特性并通过双向计数和归纳技巧得到如下结果: 设G是禁用$\{C_5,C_6\}$的连通n阶平面图, 如果$n \geq 14$, 则$e(G)\leq\frac{30n-84}{13}$。在此基础上, 构造了无穷多个达到该界值的极图。
本文引入了一种新的休假策略, 研究在该策略下带有损失销售和(s, S)库存策略的排队库存系统。当库存为空时, 服务员开始工作休假, 工作休假期间, 若补货成功, 服务员立刻开始正常服务顾客; 当工作休假结束时, 若库存仍为空, 服务员开始多重休假过程, 否则转为正常工作状态。利用马尔可夫过程方法对此系统进行稳态分析, 得到该策略下排队库存系统的稳态分布, 进而获得系统的一些稳态性能指标以及系统的平均费用函数。通过数值分析研究系统参数对最优策略和最优费用的影响。
