Non-Linear Pricing Restores Tractability for a Data Seller¶
会议: NeurIPS 2026（Accepted，按任务提供的录用清单）
arXiv: 2609.36589
领域: 优化/理论（数据市场与算法博弈论）
关键词: 非线性定价、预算约束、分段线性凸函数、线性规划、极点稀疏性
一句话总结¶
在已知买者线性估值与预算、按数据集分别定价的模型中，允许非线性价格反而把原先 APX-hard 的最优线性定价问题转化为可多项式求解的 LP，并保证存在总拐点数不超过买者数的最优方案；California Housing 构造实例还显示收益比至多 1.1、总拐点数至多 10。
研究背景与动机¶
数据卖方希望从多个预算有限的买者那里获得最大总收入，但买者并不是看到便宜数据就无限购买。每个人购买数据是为了改善预测，既考虑信息价值，也扣除实际付款，还必须满足预算。本文沿用高斯先验与加性高斯噪声下的精度增益建模：精度是方差的倒数，额外数据带来的精度增益可写成各数据集购买比例的线性组合。于是卖方掌握一个买者—数据集估值矩阵，买者的任务变成预算约束下的净效用最大化。
此前的 Revenue-optimal pricing for budget-constrained buyers in data markets 只允许每个数据集有一个固定单价。卖方改变单价时，会同时改变不同买者愿意购买的数据集与预算分配；该受限问题已经是 APX-hard。直觉上，更自由的价格函数可能需要搜索更复杂的函数空间，但本文发现困难恰恰部分来自“每个数据集只能选一个单价”：一条线性价格难以同时服务低估值买者和高估值买者，而分段价格能够先提供低边际价格的前缀，再向高估值买者出售更昂贵的后续部分。
这里讨论的是学术数据交易模型，不是金融投资建议。数据具有非竞争性，同一数据可以卖给多个买者，不存在所有买者购买量加起来不能超过库存的约束；作者还认为重复身份购买低价前缀会获得重叠记录，而非额外信息。不过这一解释依赖记录重叠和交付规则，不是一般性的抗串谋机制。核心 idea：先证明任何允许的可分价格都可以无损替换为斜率来自买者估值的分段线性凸价格，再把各斜率段的长度作为连续变量，使收益最大化成为线性规划。
方法详解¶
整体框架¶
输入是 \(n\) 个买者、\(m\) 个数据集、非负估值 \(\tau_{i,j}\) 和预算 \(b_i\)；输出是每个数据集对购买比例 \(x\in[0,1]\) 的总付款函数。价格对所有买者相同，按数据集可分相加，而且不购买时付款为零。卖方可以使用单调、下连续的函数；作者把 lower-continuous 定义为函数值等于局部下极限，即下半连续意义的条件，并非要求所有输入价格都通常连续。
买者对一个组合的估值是 \(\sum_{j=1}^{m}\tau_{i,j}x_j\)，净效用是该估值减去总付款。买者首先在预算以内最大化净效用，若有多个最优组合，收入定义取这些组合中最大的付款，也就是有利于卖方的 tie-breaking。它不能被偷换成“卖方直接最大化买者支出”，后者并不保证买者愿意买。
证明和算法围绕四个设计展开：预算耗尽关系先处理预算与需求的耦合；凸化与斜率离散化说明只需考虑 PLC（piecewise-linear convex，分段线性凸）价格；分片长度 LP 找到全局最优价格；极点稀疏性解释为什么最优方案仍然接近线性。这是机制与优化结构分析，不是神经网络训练流水线，因此不画网络式框架图。
关键设计¶
1. 预算耗尽关系：先区分净效用最优与付款最大
预算受限并不意味着买者必然花光预算。附录 A.2 给出一个单数据集的非凸价格，买者每单位估值为 2，预算为 1.3，却只在购买比例 0.4 处付款 0.4：继续购买会先降低净效用，而预算又不足以跨过这段损失、抵达更好的全量组合。无限预算时，同一买者则购买全量、付款 1.5。这个反例说明仅仅把无限预算需求的付款截断到预算，在一般价格下不成立。
对连续价格和凹净效用，作者证明了预算耗尽定理。线性估值减去凸价格正好满足凹性，因此有：
若无限预算最优需求的最大付款不超过预算，它本来就可购买；若超过预算，可以在预算内最优组合与无限预算最优组合之间取凸组合。价格连续性保证沿途能找到恰好付款等于预算的点，净效用凹性保证这个点仍是预算内最优。结论是存在一个符合收入定义的需求花光预算，而不是每个最优需求都必须花光预算。这一关系把后续证明拆成“先研究无限预算需求，再截断收入”，避免错误地逐数据集分配独立预算。
2. 凸化与斜率离散化：把函数空间缩到有限斜率集合
第一步用价格的下凸包替换原函数。虽然下凸包在一些位置更便宜，收入却不会下降：在线性估值下，无限预算买者不会最优地选择一个严格高于下凸包的价格点，因为该组合可表示成接触点的凸组合，而至少一个接触点具有更高净效用。对有限预算，不能直接照搬这句解释；附录 A.3 结合预算耗尽关系，分别处理凸化后无限预算最大付款是否达到预算，最终证明每个买者贡献的收入都不减。
第二步针对每个数据集，把凸价格的边际斜率对齐到该数据集的买者估值集合。低于最大估值的斜率向上取到最近候选值，超过最大估值的尾部则截到最大候选值。附录 A.5 的定义还处理了主文“向上取整”表述没有覆盖的尾部。由于候选集合包含每个买者的边际估值，需求的右端阈值不会向左移动，其对应的无限预算付款不会降低；再用预算耗尽关系，就得到预算受限收入不减。这里不要求有限预算下购买比例完全不变。
多数据集的关键不是各自单独使用买者完整预算，而是可分性：整个可分价格的下凸包等于各分量下凸包之和；无限预算下净效用需求可按分量分解，收入也可相加。于是结构定理保证：任意可分、单调、下连续价格，都存在一个每个买者收入不减的可分 PLC 替代，且每个数据集的斜率只来自它的买者估值。凸化的一些中间结果允许非可分函数，但最终算法的最优性仍限定在可分定价类，不是任意跨数据集捆绑价格。
3. 分片长度 LP：让价格设计成为连续资源分配
既然斜率已经确定，剩下只需决定每种斜率持续多长。令 \(z_{t,j}\) 表示数据集 \(j\) 中按斜率 \(\tau_{t,j}\) 收费的比例，把非零长度按斜率从低到高排列，就能还原凸价格。每个数据集的长度之和为 1，允许某些长度为零；相同估值对应的相邻片段可合并。
无限预算时，买者愿意购买边际价格不超过自己边际估值的片段，等号处依赖有利于卖方的 tie-breaking。因此其潜在付款是所有满足 \(\tau_{t,j}\leq\tau_{i,j}\) 的分片价格乘以长度之和，再受总预算截断。用收入变量 \(r_i\) 承接这两个上界，得到原文式 (3) 的 LP：
目标会将收入变量推到两个上界的较小者，因此这里不是只求一个松弛收入上界，而是精确实现买者需求收入。LP 有 \(nm+n\) 个变量，规模对买者数与数据集数是多项式；可求出价格后，再把每个买者的最优组合恢复为分片上的分数背包解。这里要按价值与付款之比处理跨数据集的预算分配，同时同一数据集的便宜片段会先于昂贵片段购买；不能把“所有非负净效用片段都值得买”误解为预算有限时购买顺序任意。
原文 LP 展示式没有显式写 \(r_i\geq0\)，而紧随其后的证明按非负收入讨论有界可行域；以上保留展示式，不默认为源文没有这个书写差异。实际最优收入非负，非负约束也符合收入变量的解释。
4. 极点稀疏性：非线性只需集中在少量数据集上
一般最优 LP 解可能把许多分片都设为正，作者保证的是存在一个最优基本可行解，其正长度数量至多 \(m+n\)。每个数据集至少需要一个正长度片段；超过这 \(m\) 个基础片段的部分才能产生内部拐点。合并相同斜率后，所有数据集的总拐点数至多 \(n\)，并且至少 \(\max(0,m-n)\) 个数据集完全线性。
这个界来自极点的紧约束计数，而不是额外添加稀疏正则项。若两类买者收入上界中有 \(k\) 条紧约束、长度矩阵有 \(d\) 个正项，那么长度和约束与零项约束一起给出足够多紧约束，推出 \(d\leq m+(k-n)\leq m+n\)。因此，当数据集数远大于买者数时，允许非线性不等于给所有数据集设计复杂价格。
作者还构造单数据集、\(n\) 个买者的实例：买者 \(i\) 的估值为 \(i\)，预算为 \(i(i+1)/(2n)\)，每种斜率的长度均为 \(1/n\)。该实例的唯一最优长度解有 \(n-1\) 个拐点，说明一般上界在量级上不能大幅改进。这是最坏情况结构证据，不是实测市场通常会有这么多拐点。
一个完整示例¶
附录 A.8 的分片解释给出三个边际价格：前 0.4 比例单价 10，接着 0.4 比例单价 25，最后 0.2 比例单价 65。购买 0.6 比例相当于买完第一片、再买第二片的一半；由原文价格式计算，总付款是 \(10\times0.4+25\times0.2=9\)。这不是把总价设成 \(25\times0.6\)，因为 PLC 保存了便宜前缀。
作为由该价格推导的说明性需求示例，设一个买者的每单位估值为 25、预算为 9。第一片提高净效用，第二片不再增加净效用，第三片会降低净效用；在最大净效用的可负担组合中，卖方有利的 tie-breaking 选择比例 0.6、付款 9。它同时展示了为什么 LP 的估值阈值必须包含等号，以及为什么预算截断作用于整个组合。
缓存中 Example 5 的 plin 参数写成 (0.4,0.4)，但随后展开的分段区间、付款式及分片大小对应断点 0.4 与 0.8。这里明确保留这一不一致，示例使用后者一致的分片说明，不把参数静默修成作者的精确公式。
实验关键数据¶
主实验¶
实验不是另测一种学习算法的预测 SOTA，而是用 California Housing 生成数据市场，再检查最优价格的收益与复杂度。原数据有 20,640 行、9 个数值列；房价中位数是所有买者已知的目标，剩余输入列划为 4 个卖方数据集：收入、住宅结构、人口特征、位置。随机取 80% 行作为训练集，其余为测试集；测试行按纬度排序后分给不同买者，模拟不同地区的预测需求。
对每个数据集训练岭回归，以各买者区域上的 MSE 倒数的增益构造 \(\tau_{i,j}\)。作者明确使用线性化估值，未证明真实组合数据的预测增益可加。预算按总估值缩放，并乘以 \(B_i\sim\operatorname{Beta}(\alpha_B,1)\) 和 \(f_{\max}\)；取若干 \(n\in[1,100]\)，每个选定买者数生成 16 个实例，参数范围为 \(f_{\max}\in[0.4,1.3]\)、\(\alpha_B\in[0.3,1]\)。
| 项目 | 原文报告 | 适用范围与解释 |
|---|---|---|
| 数据市场规模 | \(m=4\)，若干 \(n\in[1,100]\)，每个选定 \(n\) 有 16 个实例 | 一个真实数据集构造的模拟市场，不是多个独立市场数据集 |
| 非线性/线性最优收入比 | 至多 1.1 | 线性最优基线仅在 \(n\leq20\) 时计算；即该比较范围内非线性收益优势不超过 10% |
| 所有价格的总拐点数 | 至多 10 | LP 构造实例上的观察，不是每条价格各有 10 个拐点 |
| 计算耗时 | 16 秒，Apple M4，MacBook Air 2025 | 文中所述计算的总耗时，不是单实例延迟或统一硬件下的基线加速比 |
| 求解方式 | SciPy 调用 HiGHS dual-simplex；Python 与 NumPy | 未报告学习训练吞吐量，也未提供本笔记可确认的代码仓库链接 |
线性最优收入通过已有 \(O(n^{m}\cdot nm)\) 暴力算法求解，所以限制在 \(n\leq20\)；拐点观察则覆盖所选更大买者数。图 4 用均值线、四分位区间及最小—最大区间展示结果，缓存没有逐点数值，不能据此填出各买者数的精确均值或标准差。
消融实验¶
论文没有删模块式消融，以下整理其定价限制与理论反例分析，避免伪造实验配置。
| 配置或分析 | 可核验结果 | 说明 |
|---|---|---|
| 仅线性价格 | 已有工作证明 APX-hard | 每个数据集只选一个斜率；不是本文 LP 的同复杂度基线 |
| 可分、单调、下连续价格 | 存在收入不减的 PLC 替代 | 最优斜率来自买者估值，可用连续长度 LP 精确求解 |
| 最优基本可行解 | 正长度项至多 \(m+n\)，总拐点至多 \(n\) | 至少 \(\max(0,m-n)\) 个数据集线性；不是所有最优解都满足同一稀疏界 |
| 单数据集最坏结构实例 | 唯一最优解有 \(n-1\) 个拐点 | 估值为 \(i\)，预算为 \(i(i+1)/(2n)\)，长度均为 \(1/n\) |
| 富买者与低估值买者实例 | 收益比趋近 \(2-1/n\) | Example 1 中 \(\varepsilon\to0\) 的极限，不是任意有限 \(\varepsilon\) 的精确相等 |
| 非凸价格下的预算反例 | 预算 1.3 时付款 0.4；无限预算时付款 1.5 | 说明预算耗尽关系必须依赖连续价格与凹净效用条件 |
关键发现¶
- 线性差距定义为最优允许定价收入除以最优线性定价收入。在本文模型下，它也等于分片长度 LP 的整数间隙：要求每个长度变量取整数，就让每个数据集只剩一个长度为 1 的斜率。
- 构造实例可以逼近接近两倍的非线性收益，但 California Housing 的可比较实例至多为 1.1。观察支持的是这个线性化模拟设置中收益差距较小，不足以推断所有真实数据市场都如此。
- 文中 Conjecture 1 猜想线性差距至多为 2；“2”是猜想上界，不是已证定理。已证的是结构与多项式可解性，以及特定实例的收益比和拐点性质。
- 经验上的至多 10 个拐点与最坏实例的 \(n-1\) 个拐点形成对照，提示简单分段价格可能足够；本文并未求解预先规定拐点数量的最优定价问题。
亮点与洞察¶
- 扩大决策空间可以降低计算难度。线性定价对应每个数据集必须选择一种斜率的离散限制，而非线性定价允许连续分配长度；结构定理保证这种“松弛”正好对应合法、最优的经济机制。
- 预算是买者总需求的约束，不是各数据集彼此独立的上限。预算耗尽定理让一维阈值证明能组合到多数据集情形，这是从简单结构走向全局 LP 的关键桥梁。
- 简单性来自最优解几何，而非先验强制所有价格线性。选择基本可行解就能获得稀疏分段结构，可作为其他机制设计问题中寻找可实施最优方案的思路。
局限与展望¶
- 线性、可加估值是核心边界。Gaussian precision 模型提供一种依据，但实际数据常有相关性、互补性和收益递减；实验也主动线性化估值，因此不能把该 LP 直接用于任意非线性数据效用。
- 卖方已知估值与预算，并假设买者准确求解净效用最大化、采用有利于卖方的 tie-breaking。本文没有解决私有信息下的真实报告激励、估值学习误差或不利 tie-breaking。
- 最优性针对单卖方的可分价格；没有覆盖一般捆绑定价、竞争卖方均衡、买者之间的外部性或转售串谋。非竞争性数据和重复前缀交付的解释也不能替代抗重复身份机制证明。
- 实证仅来自一个数据源构造的 4 数据集市场，线性比较又止于 \(n\leq20\)。后续可测试更多估值结构、更多卖方数据集及参数扰动下的价格稳定性，但不能把这些扩展写成本文已验证结果。
- 缓存中的主文 Theorem 3 草图写“购买量相同”，并出现同一收入与自身相等的结尾；附录 Lemma 9 实际使用需求右端不左移的论证。A.9 的展示求和上限与后续加权推导也不一致；本文按清楚陈述的定理结论介绍，不猜补损坏证明公式。
- 源文 LP 未显式列出非负收入约束、Example 5 的断点参数冲突也需要读者注意。上述书写问题与一般线性差距是否有 2 的上界是不同问题，后者仍是作者明确标注的开放猜想。
相关工作与启发¶
- vs Revenue-optimal pricing for budget-constrained buyers in data markets（CGSS26b）：相同预算买者与数据估值背景下，前作限定线性单价并建立困难性；本文允许同一数据集分段收费，用结构定理和 LP 恢复精确可解性，并非只是给困难线性问题提供启发式。
- vs Myerson ironing：两者都把不规则结构“熨平”，但经典熨平作用于拍卖中的虚拟价值或分配规则，本文对所有买者共同面对的价格函数取凸包。本文不是在证明这些已知估值买者的私人信息真实报告机制。
- vs 竞争均衡与数据交换经济：数据定价 via competitive equilibrium、寡头数据市场及无货币交换研究关注均衡或稳定性；本文固定单卖方，以收入最大化为目标，不保证福利或公平最优。
- 后续研究线索：可研究估值估计误差下仍保持收入保证的鲁棒分段价格，或固定拐点预算下的复杂度与近似界。这些是由本文假设与稀疏结构引出的方向，不是论文已经给出的算法。
评分¶
- 新颖性: 4/5。将更自由的价格与更低的计算难度联系起来，结构定理而非单纯求解器构成核心贡献。
- 实验充分度: 4/5。理论证明与真实数据构造模拟互补，但数据源单一且线性基线比较规模受限。
- 写作质量: 4/5。主线清晰、附录解释充分，不过缓存中的若干公式和草图表述需要谨慎核对。
- 价值: 4/5。给出可计算、可解释且存在稀疏最优解的机制，应用价值受线性估值和已知预算假设约束。