申请成本不均等的大学入学申请

《ACM Transactions on Economics and Computation》：College Applications with Non-Homogeneous Application Costs

该研究探讨学生如何选择申请大学组合以最大化预期净收益，涉及异构申请成本、独立/相关性录取概率两种场景。针对独立情况提出多项式时间精确算法和近似方案，建立离散阈值动态规划框架；相关性场景转化为最长路径问题并给出高效解法。理论分析表明问题具有非单调子模性但违背Gross substitutes性质，开放了通用问题复杂度。贡献包括首次处理异构成本、提供新算法框架、揭示理论特性，为实证研究奠定基础。

　　

摘要AI 摘要

摘要

摘要

一名大学申请者向多所大学提交了申请，但她不确定哪些大学会录取她。如果她知道申请费用、每所大学的就读效用以及被每所大学录取的概率，那么她应该申请哪些大学才能使预期净收益最大化呢？这个问题属于非单调次模最大化问题。文献中有两种主要变体：一种是不同大学录取事件相互独立的情况，另一种是这些事件相互关联的情况。现有研究主要针对所有申请费用相同的情况。对于申请费用不同的情况，我们也提供了精确和近似算法。

AI 摘要

AI 生成的摘要（实验性摘要）

此摘要是由自动化工具生成的，并非由文章作者撰写或审核。它旨在帮助读者发现文章内容、评估其相关性，并协助相关领域的读者理解文章。它是对作者提供的摘要的补充，作者提供的摘要仍是文章的官方摘要。完整文章才是权威版本。点击此处了解更多。

点击 此处 对摘要的准确性、清晰度和实用性进行评论。您的反馈将有助于改进未来的摘要版本。

AI 生成的摘要

该摘要由基于已发表文章内容的自动化系统生成。

生成日期：2026年2月3日

本研究探讨了大学申请组合问题，即在申请费用不同且录取结果不确定的情况下，学生应申请哪些大学以最大化预期净收益。文章研究了两种主要情况：一种是各大学录取概率相互独立的情况；另一种是录取概率相互关联的情况（即录取结果取决于学生是否达到某些能力门槛）。

从本质上讲，这是一个非单调次模最大化问题。以往的研究仅在所有申请费用相等的情况下解决了这个问题，而本文将解决方案扩展到了费用不均的情况。本文证明了最优申请组合规模受到效用、概率和费用的限制，从而支持多种算法方法的应用。

对于独立情况，作者得出了三个主要结果：首先，当所有参数均为常数时，该问题可以通过对有限申请组合规模进行穷举搜索在多项式时间内解决；其次，他们开发了一种完全多项式时间的近似算法，当录取概率被限制在大学数量的倒数多项式范围内时，该算法可以实现任意小的误差因子；这种动态规划方法能够在离散的剩余概率阈值之间保持随机解，从而平衡早期大学的效用与后期选择的机会；第三，当录取概率来自固定大小的集合时，他们提出了一种四次多项式时间算法，通过用精确的剩余概率替换离散阈值来实现优化。

对于预算受限的独立情况，作者提出了一种近似算法，该算法仅通过加性误差因子来满足预算限制，改进了以往的乘性近似方法。他们通过反例证明了从非预算限制情况到预算限制情况的简单转换是行不通的。

对于关联情况，文章将大学按照选择性阈值进行排序：如果学生的随机得分超过某所大学的阈值，则该学生会被自动录取到所有选择性较低的大学。作者将这个问题重新表述为在无环有向网络中寻找最长路径的问题，其中节点代表大学，边代表申请组合的转换。路径长度等于预期净收益，因此即使费用不均，也能通过标准动态规划方法在多项式时间内得到高效解。

本文还阐述了两种情况的理论特性。他们证明了关联情况下的目标函数具有次模性，即增加大学数量时收益会递减；然而，他们也指出目标函数不满足完全替代性质，这意味着基于贪婪策略的边际改进算法在费用不均的情况下无法保证最优解。

对于一般无约束情况，问题的复杂性尚未明确，尽管相关次模最大化问题的 NP 难度结果表明这个问题较为复杂。本文为实际情况提供了实用的算法，特别是在录取概率不是极低的情况下，并为未来基于学生申请选择来估计其偏好的实证研究奠定了基础。

此内容由 AI 生成。了解更多