论文笔记[4]——On social envy-freeness in multi-unit markets

发表于 | 分类于

文章：Michele Flammini and Manuel Mauro and Matteo Tonelli, On social envy-freeness in multi-unit markets, Artificial Intelligence, volume 269, 2019, Pages 1-26.

准备工作

  • 一个多单位市场 \(\mu\) 可以用一个元组 \((n, m, (v_i)_{i\in n})\) 来表示：
    • \(N=\{1,\cdots,n\}\) 是 \(n\) 个买家；
    • \(M\) 是商品集合，是一组 \(m\) 个相同的物品；
    • \(v_i\) 是一族函数：对于每个买家 \(i\in N\)，\(v_i=(v_i(1),\cdots,v_i(m))\) 是一个估价函数（或说向量）.
      • 其意义是给定一堆物品 \(X\subset M\)，且 \(|X|=j\)，则 \(i\) 为了买到 \(X\)，愿意付出的价值是 \(v_i(j)\).
      • 我们假定 \(v_i(0)=0\)，且 \(j\geqslant 1\) 时，\(v_i(j)\geqslant 0\)，\(\forall i\in N\).
  • 对估价函数，有两种假定：
    • single-minded（一心一意的买家）：买家仅对一定数量的物品有兴趣，即只在一个特定的size处有正值（记为 \(m_i\)），其余时候都为 \(0\)；
    • general：不受上述限制.
  • 定价函数（向量）是指一个 \(m\) 元组 \(\overline{p}=(\overline{p}(1),\cdots,\overline{p}(m))\)，s.t. \(1\leqslant j\leqslant m\)，\(\overline{p}(j)\geqslant 0\) 表示 \(j\) 个物品的价格,
    • 对于商品的定价模式，也有两种假定：
      • item-pricing：按照物品来定价，例如单个物品价格是 \(p\)，则 \(\overline{p}(X)=|X|\cdot p\).
      • bundle-pricing：对一捆物品直接定价，并且该价格与物品数量不是成比例的（否则同item-pricing）.
  • 消费者的效用（utility）是指：消费者对所得物品的估价 \(-\) 消费者为此付出的价格. 即：\[u_i(X,\overline{p})=v_i(|X|)-\overline{p}(X).\]
  • 一个分配向量是指一个 \(n\) 元组 \(\overline(X)=\{X_1,\cdots,X_n\}\)，其中 \(X_i\subset M\) 表示分配给买家 \(i\) 的商品.
    • 称一个分配是可行的，如果：
      1. 货物够分：\(\sum\limits_{i=1}^n |X_i|\leqslant |X|\)；
      2. 买家不傻：\(u_i(X_i,\overline{p})\geqslant 0\).
  • 一个市场输出 \((\overline{X},p)\) 的总收益用 \(r(\overline{X},p)\) 表示.

Def 1. 一个市场 \(\mu\) 得出的一个可行分配 \((\overline{X},\overline{p})\) 在关系图 \(G(V,E)\) 下是社会无嫉妒（或称稳定）的，如果 \(u_i(X_i,\overline{p})\geqslant u_i(X_j,\overline{p})\)，\(\forall i\in N\)，\(j\in N(i)\)，其中 \(N(i)\) 表示图 \(G\) 中 \(i\) 的所有邻居构成的集合.

  • 该定义实际上是说，每个人相比邻居得到的，更喜欢自己得到的，那么就不会嫉妒邻居. 每个人都不嫉妒自己认识的人，那么久无嫉妒了；
  • 当图 \(G\) 是完全图时，此时的social envy-free即常义的无嫉妒.

Def 2. 给定一族市场模型 \(\mathcal{M}\) 和一族社会关系图 \(\mathcal{G}\)，无嫉妒的代价（price of envy-free）\(c(\mathcal{M}, \mathcal{G})\) 是指：不考虑无嫉妒时 \(\mathcal{M}\) 中模型能达到的最大收入与考虑无嫉妒后的最大收入的比值的上确界，即： \[c(\mathcal{M}, \mathcal{G})=\sup_{\mu\in\mathcal{M}, G\in\mathcal{G}}\frac{opt(\mu)}{opt(\mu,G)}.\]

  • 在对分配问题进行讨论时，我们经常将其规约到 MULTIPLE-CHOICE KNAPSACK（多重背包问题）.
    • 多重背包问题 \((o,z,w,k)\)：
      • \(O\)：物品集合；
      • \(z\)：物品体积；
      • \(w\)：物品价值；
      • \(k\)：背包容量.
    • 我们通常这样构造：
      • 背包的容量为 \(k\)；
      • 考虑 \(t\) 个物品类 \(\{O_1,\cdots,O_t\}\)；
      • 物品 \(o_{j,h}\) 的体积和价值分别是 \(z_{j,h}\) 和 \(w_{j,h}\).
    • 我们需要从每个物品类中恰好选取一个物品装入，使得总价值最大，且总体积不超过背包容量.
  • 多重背包问题已被证明是NP难的，但有FPTAS近似解法.

single-minded买家

按照定价模式，有两种情况，分述如下.

Item-pricing

Lemma 3. 对于single-minded买家，设 \(p^{opt}\) 是能达到最优稳定分配 \((\overline{X}^{opt},p^{opt})\) 的价格函数，且能最大化卖家的收入，则 \(p\in\mathbb{P}=\{\frac{v_i(m_i)}{m_i}|i\in N\}\).

这个引理实际上是在说，对于single-minded情况，最优定价 \(p^{opt}\) 一定是某个买家对单物品的估价.

Proof. 假设 \((\overline{X}^{opt},p^{opt})\) 中的 \(p^{opt}\notin\mathbb{P}\). 取 \(p=\frac{v_i(m_i)}{m_i}\in\mathbb{P}\) 为 \(\mathbb{P}\) 中比 \(p^{opt}\) 大的最小者，考虑 \((\overline{X}^{opt},p)\)：

由于二者的分配方案是一致的，故 \((\overline{X}^{opt},p)\) 也满足可行性的两个要求（货物够分，买家不傻）. 现将价格从 \(p^{opt}\) 涨至 \(p\)，没有任何卖家的效用会因此变为负值. 于是 \((\overline{X}^{opt},p)\) 也是social envy-free的，因为价格的上涨只会使得估值在 \(p^{opt}\) 与 \(p\) 之间的买家效用变为 \(0\)，因此对于买家对邻居的评估没有影响，故仍然是social envy-free的.
但是，值得注意的是 \(p\) 显然会比 \(p^{opt}\) 给卖家带来严格正的收益增幅，故 \(p\) 比 \(p^{opt}\) 更优. This is a contradition.

命题得证！

尽管有了该结论，但 (SINGLE, ITEM) 设定下的分配问题仍然是困难的：

Th 4. (SINGLE, ITEM) 设定下的分配问题是NP难的.

  • 其证明考虑从 SUBSET-SUM 问题进行规约.
    • SUBSET-SUM 问题：给定一个自然数集 \(A\subset\mathbb{N}\) 以及一个自然数 \(k\in\mathbb{N}\)，找到 \(S\subset A\)，s.t. \(\sum_{a_i\in S} a_i=k\).
    • 一个 SUBSET-SUM 问题通常可以被表示为 \((A=\{a_1,\cdots,a_n\},k)\).

Proof. 记 \(N=\{1,\cdots,N\}\)，\(M=\{1,\cdots,M\}\)，\(v_i(x)=\begin{cases} a_i, & x=a_i \\ 0, & x\neq a_i \end{cases}\)，则：
考虑 SUBSET-SUM 中的一个 \(S\)，若 \(a_i\in S\)，则给买家 \(i\)分配一捆大小为 \(a_i\) 的商品，否则不给 \(i\) 分配任何东西. 反过来，市场 \(\mu\) 的每一个输出也对应了一个 \(S\).
由 Lemma 3，要想达到最优结果，\(\mu\) 的单物品定价必定是 \(1\)，此时所有买家的效用都是 \(0\)，因而是稳定的.
因此，\(A\) 存在和为 \(k\) 的子集 \(S\)，当且仅当 \(\mu\) 在稳定前提下的最大收益是 \(k\).

尽管问题本身是NP的，但存在好的近似算法.

Th 5. (single,item) 分配问题有FPTAS.

考虑算法：

  • 对 \(\forall p\in\mathbb{P}\)：
    • 对 \(\forall j\)，定义：
      • \(N_j^+\)：对大小为 \(j\) 的商品集持严格正估价的买家数，\(n_j^+=|N_j^+|\)；
      • \(N_j^0\)：对大小为 \(j\) 的商品集持零估价的买家数，\(n_j^0=|N_j^0|\)；
    • 建立如下的背包问题 \(K(\overline{O},\overline{z},\overline{w},k)\)：
      • \(k=m\)；
      • 对每个至少有一个买家喜欢的 \(j\)，\(O_j=\{o_{j,0},\cdots,o_{j,n_j^0},\}\) 表示 \(j\) 生成的 \(n_j^0+1\) 个物品；
      • \(z_{j,h}=w_{j,h}=j\cdot (n_j^++h)\)，\(\forall o_{j,h}\in O_j\).
    • 求解该背包问题，对得到的结果做如下处理：
      • 若选择了物品 \(o_{j,h}\)，则给所有 \(N_j^+\) 中的买家以及 \(h\) 个 \(N_j^0\) 中的买家每人分配 \(j\) 个商品.
    • 得到分配方案后，即可计算收入并将其存下来.
  • 在所有 \(p\) 中，求使得收入最大的分配方案 \((\overline{X},p)=\arg\max_p r(\overline{X}',p')\).

以下对该算法进行证明：

Proof. 由 Lemma 3，对每个 \(p=\frac{v_i(m_i)}{m_i}\)，\(i\in N\)，我们建立一个多重背包问题 \(K(\mu\))…（具体构建方法见上述算法）
构建完成后，我们来证明：一个 \(K(\mu)\) 的解 \(T\)，对应着一个 \(\mu\) 的稳定输出 \((\overline{X},p)\). 事实上，\(T\) 所装载的物品不会超过背包容量，而背包容量恰好就是商品的总量. 进一步，\(\overline{X},p)\) 是稳定的，因为当我们分配了一捆数量为 \(j\) 商品时，只有 \(N_j^+\) 里的人可能会因此产生嫉妒. 于是对于确定的 \(p\)，\(K(\mu)\) 的 \((1-\epsilon)\)-近似解 \(T\)，都对应了一个 \(\mu\) 的 \((1-\epsilon)\)-近似解 \((\overline{X},p)\)，并且这个解是稳定的.

Th 6. (SINGLE, ITEM) 问题是强NP难的.

  • 证明考虑规约到问题 DENSEST K-SUBGRAPH：
    • 给定无向图 \(H(V,F)\) 和整数 \(k\)，求一个 \(S\subset V\)，s.t. \(|S|\leqslant k\) 且 \(S\) 能最大化 \(S\) 引出的边数.
    • 一个 DENSEST K-GRAPH 的实例由 \((G,k)\) 二元组表示.

Proof. 进行如下考虑：

  • 对市场 \(\mu\)： - 对每个 \(u\in V\)，将其与 \(|F|+1\) 个买家对应（记为 \(N_u\)）. 进一步，对每个 \(i\in N_u\)，都有 \(v_i(1)=1+\epsilon\)，其中 \(\epsilon=\frac{k}{|V|+1}\)； - 对图 \(G\) 的每条边 \(e\in F\)，存在一个买家 \(i_e\)，s.t. \(v_{i_e}=1\)； - 再来一个买家 \(w\)，s.t. \(v_w(|V|(|F|+1))=|V|(|F|+1)\)； - 总共有 \(m=(|V|+k)(|F|+1)+|F|\) 件商品.
  • 对社会关系图 \(G(N,E)\)： - 设 \(u\in V\)，则对所有 \(i,i'\in N_u\)，有 \(\{i,i'\}\in E\)； - 对 \(\forall i\in N_u\)，\(\{i,i_e\}\in E\)，其中 \(e\) 在 \(H\) 中是由 \(u\) 引出的.

以下证明 \(H\) 存在一个有 \(h\) 条边的 \(k\) 阶子图，当且仅当上述市场 \(\mu\) 在 \(G\) 下有一个稳定的输出 \((\overline{X},p)\)，s.t. \(r(\overline{X},p)=(|V|+k)(|F|+1)+h\).

简单来说，就是：

买家一共有 \((|V|+1)(|F|+1)\) 个：

  1. 给 \(V\) 里的每个点分别配 \(|F|+1\) 个未来在 \(G\) 中的邻居，记作 \(N_u\)，这些邻居都只喜欢一个物品，并且效用只比 \(0\) 严格大一点点；（这里共 \(|V|(|F|+1)\) 个）
  2. \(H\) 里的每条边，都对应一个买家，只喜欢一个物品，且效用是 \(0\)；（这里共 \(|F|\) 个）
  3. 有一个超级买家，喜欢很多物品，但效用是 \(0\)；（这里共 \(1\) 个）

物品总量是 \((|V|+k)(|F|+1)+|F|\)，小于总需求量：

  1. 上述第1步，共需要物品 \(|V|(|F|+1)\) 个；
  2. 上述第2步，共需要物品 \(|F|\) 个；
  3. 上述第3步，共需要物品 \(|V|(|F|+1)\) 个；

图 \(G\) 是这样规划的：

  1. 所有 \(N_u\) 内部的点两两相连；
  2. 点 \(u\) 在 \(H\) 中的所有邻居，在 \(G\) 中都要与 \(u\) 现在的所有邻居相连；

先证 \(\Rightarrow\)：假设 \(|S|=k\) 且 \(S\) 引出的边数为 \(h\). 考虑 \(p=1\) 时的输出，得到物品的买家为 \[\{w\}\cup\bigcup_{u\in S} N_u\cup\{i_e\in N:e=\{u,z\}\in F,~u,z\in S\}.\] 就是说，给：超级卖家 \(w\)，\(S\) 中的所有点对应的买家，以及 \(S\) 内部所有边对应的卖家 分配了商品.
考虑所有 \(i_e\) 中未得到物品的买家，他们所喜欢的物品对他们的效用也不过是 \(0\)，所以不会产生嫉妒；其他未得到物品的买家，他们所处的 \(N_u\) 中，\(u\notin S\)，即他们的邻居也都没有得到东西，故他们也不会产生嫉妒. 于是 \((\overline{X},p)\) 是稳定的，其总收益是 \((|V|+k)(|F|+1)+k\).

再证 \(\Leftarrow\)：假设存在总收益为 \((|V|+k)(|F|+1)+h\) 的稳定输出 \((\overline{X},p)\)，则：
在 \((\overline{X},p)\) 中，\(p\) 绝不能严格大于 \(1+\epsilon\)，否则收益将为 \(0\) （这是个废话）. 事实上，如果 \(p>1\)，那么只有 \(N_u\) 里的买家愿意购买，此时收益至多为 \[(1+\epsilon)[|V|(|F|+1)]<(|V|+k)(|F|+1)+h,~~其中~ \epsilon=\frac{k}{|V|+1}.\] 因此，必定有 \(p\leqslant 1\). 此时，为获取 \(r(\overline{X},p)=(|V|+k)(|F|+1)+h\) 的总收益，必须满足超级买家 \(w\) 的购买需求. 继续进行分配，由稳定性条件，\(N_u\) 只要有一个人得到了他想要的商品堆，\(N_u\) 里的其他人也必须得到他们想要的. 又根据解的可行性条件（商品够 + 人不傻），我们至多分给 \(k\) 个 \(N_u\) 足够的商品，考虑到预期收益，我们也必须分给 \(k\) 个 \(N_u\) 足够的商品. 至此，还剩 \(h\) 个商品，分配给 \(i_e\) 中的买家.
此时考虑 \(S=\{u:\forall i\in N_u,|X_i|=1\}\)（即所分到物品的 \(N_u\) 的 \(u\) 构成的集合），容易知道 \(|S|=k\). 以下只需说明 \(S\) 引导的 \(H\) 的子图至少有 \(h\) 条边，而这正是分配了物品的 \(i_e\) 的数量. 因此由一个市场也可以导出一个 DENSTEST K-GRAPH 的解.

由 DENSTEST K-GRAPH 的复杂性，命题得证.

由以上的定理可知，分配问题的 FPTAS 是不存在的（除非已经证明 \(P=NP\)）. 另一方面，我们可以找到一个较好的近似算法（一个 PTAS）.

  • 证明思路：给定了 \((\mu, G)\) 和给定的价格 \(p\)，\(j\leqslant m\)，\(h\leqslant n\).
    • 假设我们可以迅速求解一个受限制的子问题：将商品每 \(j\) 个捆成一捆，再在 \(G\) 下分给 \(h\) 个买家，且该分配在 \(G\) 下稳定（如果存在）.
    • \(J\) 表示所有“至少有一个买家喜欢的物品量”构成的集合，且至多含 \(n\) 个元素.
    • 在以上假设之下我们甚至可以找到一个 FTPAS，仍然是利用多重背包 \(K(\mu, G,p)\)：
      • 背包容量 \(k=m\)；
      • 对 \(\forall j\in J\)，考虑 \(O_j=\{o_{j,h}:存在~j~个商品分给~h~个买家的在~G~下稳定的分配\}\)；
      • 物品的重量和价值：\(z_{j,h}=w_{j,h}=j\cdot h\).
    • 事实上，这样的一个背包的物品个数是多项式的.
      • 至多有 \(n\) 个不同的物品类 \(O_j\)；
      • 每个物品类都至多有 \(n\) 个物品.
    • 于是由 Lemma 3，对每个 \(p=\frac{v_i(m_i)}{m_i}\) 跑一次 FPTAS，选取最大的总收益，这样就得到了一个多项式时间的 \((1-\epsilon)\)-近似. 即一个 (SINGLE, ITEM) 的FPTAS.

然而，由 Th 6，上述思路的基本假设就是不成立的…换言之，受限制的子问题是不可能在多项式时间内解决的. 然而，以下的近似结果仍能保持：

Lemma 7. 给定一个 (SINGLE, ITEM) 分配问题的实例和一组固定的价格 \(p\)，\(j\leqslant m\)，\(h\leqslant n\)，则求一个

  • 将商品 \(j\) 个一捆包装起来，分给至多 \(h\) 个买家的分配；
  • 在 \(G\) 下稳定；
  • 能最大化总收益；

这样的问题，存在一个 PTAS.

Proof. 记 \(N_j^+\) 和 $\(N_j^0\) 分别为在价格 \(p\) 下对 \(j\) 持严格正效用的买家以和持零效用的买家，记 \(G_j^*\) 为 \(N_j^+\) 引导的子图，则对于任意 \(\mu\) 的稳定（文中用了optimal）输出 \((\overline{X},p)\)，\(G_j^+\) 的所有连通分支中的买家要不都获得 \(j\) 个商品，要不都没有得到 \(j\) 个商品. （由稳定性易得）
取定 \(\epsilon>0\)，记 big 为 \(G_j^+\) 的至少包含 \(\epsilon\cdot h\) 个买家的连通分支（可能有多个），small 为其余的连通分支. 则，任意的optimal输出 \((\overline{X},o)\) 至多分给 \(h\) 个人每人 \(j\) 个商品，于是 \((\overline{X},p)\) 至多给 \(O(\lfloor\frac{1}{\epsilon}\rfloor)\) 个 big 连通分支分配商品. 当然，此外它还可以给一些 small 的连通分支分配商品. 再次，也可以给 \(N_j^0\) 中的买家分配，但仅限通过 \(G_j^+\) 与 \(G\) 相连的买家. （否则可能引起嫉妒） 考虑以下步骤：

  • 给所有 big 连通块分配商品；
  • 不停地给 small 连通块分配商品，直到无法分配. 无法分配有两种情况： - 商品不够分了： - 此时至少有 \((1-\epsilon)h\) 个买家被分配了商品； - 所有small都被分配了商品： - 继续给 \(N_j^0\) 中的弟兄们分配商品，直到无法继续，有以下两种情况： - 总共已经分配了 \(h\) 个买家：如此便是一个optimal分配； - 所有 \(N_j^0\) 中的买家都被分配了商品：我们也得到了最优的结果.

综上所述，以上算法可以产出一个 \((1-\epsilon)\)-近似最优结果，并且是多项式时间的.

由以上引理，给定价格 \(p\)，我们可以构造一个多重背包的近似实例 \(K_\epsilon(\mu, G, p)\)，对应于 MULTIPLE-CHOICE KNAPSACK 实例 \(K(\mu,G,p)\)：

  • 背包容量 \(k=m\)；
  • 对每个 \(j\in J\)，物品类 \(O_j=\{o_{j,l}:对某个~1\leqslant h\leqslant n~运行上述PTAS，j~个一捆，买家数~l\leqslant h\}\)；
  • 体积和价值：\(w_{j,l}=z_{j,l}=j\cdot h\).

显然，若 \(T=\{o_{j_1,h_1},\cdots,o_{j_t,h_t}\}\) 是 \(K(\mu,G,p)\) 的一个可行解，则存在一个 \(K_\epsilon(\mu,G,p)\) 的可行解 \(\{o_{j_1,l_1},\cdots,o_{j_t,l_t}\}\)，s.t. \((1-\epsilon)h_q\leqslant l_q\leqslant h_q\)，\(\forall 1\leqslant q\leqslant t\). 因此，若用 \(opt(K)\) 和 \(opt(K_\epsilon)\) 分别表示 \(K\) 和 \(K_\epsilon\) 的最优解，我们有 \(opt(K_\epsilon)\geqslant (1-\epsilon)opt(K)\). 进一步，\(opt(K_\epsilon)\) 对 \(K\) 也是可行的.

进一步，有以下定理成立：

Th 8. (SINGLE, ITEM) 问题有 PTAS.

考虑算法：

  • 对每个 \(p=\frac{v_i(m_i)}{m_i}\)：
    • 计算多重背包 \(K_{\epsilon/2}(\mu,G,p)\)；
    • 记 \(T\) 为 \((K_{\epsilon/2}(\mu,G,p),\epsilon/2)\)；
    • 对 \(\forall o_{j,l}\in T\):
      • \(\overline{X}\) 给 \(l\) 个买家每人一个大小为 \(j\) 的物品堆；
    • 算一下收益.
  • 收益对所有 \(p\) 取最大.

Proof. 证明暂时从略Orz.

Bundle-pricing

与item-pricing相同，bundle-pricing情形的计算也是困难的.

Th. 9 (SINGLE, BUNDLE) 分配问题是NP难的.

Proof. 与 Th 4 进行类似的规约（利用 SUBSET-SUM），集合 \(S\subset A\) 对应于一个市场 \(\mu\) 的输出：
买家 \(i\) 得到大小为 \(a_i\) 的一捆商品，当且仅当 \(a_i\in S\).
进一步，一个最优的稳定分配方案中，已分配的大小为 \(j\) 的物品堆价格至少是 \(j\)，否则提价到 \(j\) 可继续增大收入. 于是：
存在 SUBSET-SUM \((A,k)\) 的解，当且仅当 \(\mu\) 存在收益为 \(k\) 的最优稳定分配.

不过Bundle-pricing条件下，同样有好的近似.

Th 10. (SINGLE, BUNDLE) 分配问题有FPTAS.

Proof. 考虑给定的物品堆大小 \(j\leqslant m\)，令 \(i_{j,1},\cdots,i_{j,n_j}\) 为买家对 \(j\) 的喜好程度的顺序，即 \(v_{i_{j,1}}(j)\geqslant \cdots\geqslant v_{i_{j,n_j}}(j)\).
对于 \(h\leqslant n_j\)，取价格 \(v_{i_{j,h}}(j)\)，考虑 \(h\) 个大小为 \(j\) 的物品堆分给上述序列的前 \(h\) 位的情况，它将得到一个稳定的分配. 由于一心一意的买家只可能嫉妒和自己有相同喜好的买家，故上述过程可以对任意“至少有一个买家喜欢的bundle size”运行.
到这一步，就可以继续参考item情形的思路，规约到多重背包问题.

考虑以下算法：

  • 对每个 \(j\in J\)，令 \(i_1,\cdots,i_{n_j}\) 为 \(n_j\) 个喜欢大小为 \(j\) 的物品堆的买家的序，即 \(v_{i_1}(j)\geqslant\cdots\geqslant v_{i_{n_j}}(j)\).
  • 构造如下的多重背包问题：
    • 背包容量 \(k=m\)；
    • 物品类 \(O_j=\{o_{j,i,h}:i\in N,h]in M\}\)；
      • 体积 \(z_{j,i,h}=v_{j,h}(j)\cdot h\)；
      • 价值 \(w_{j,i,h}=j\cdot h\)；
  • 令 \(T\) 为背包问题 \((K,\epsilon)\) 的解；
  • 对每个 \(o_{j,i,h}\in T\)：
    • \(p(j)=v_{j,h}(j)\)；
    • 给 \(i_{j,1},\cdots,i_{j,h}\) 每人一个大小为 \(j\) 的物品堆
  • 应当注意，上述算法中没有用到社会关系图 \(G\) 的任何信息，即该算法在完全图下也是social envy-free的. 事实上，后文将证明，在 (SINGLE, BUNDLE) 设定下，social envy-free与否不影响总收益的大小.
  • 与前文类似，可立刻得到如下推论：

Cor 11. (SINGLE, BUNDLE) 分配问题有FPTAS.

自由处置

什么是自由处置（Free disposal）

自由处置是指，不考虑代价的情况下，拿到更多的东西总不是坏事。体现在估价函数上，就是指： \[v(j)\geqslant v(i),~~若~j\leqslant i.\] 如果对于single-minded买家 \(i\)，应有： \[v_i(j)\geqslant v_i(m_i),~~若~j\geqslant m_i.\]

以下引理来自文献27：Revenue maximization envy-free pricing for homogeneous resources. IJCAI 2015.

Lemma 12. 给定一个pair envy-free的输出 \((X,p)\)，若其不满足货物够分的条件，则可在多项式时间内找到一个pair envy-free的可行输出 \((X',p')\)，s.t. \(r(X',p')\geqslant \frac{m}{2}\cdot p\).

仍然考虑 (SINGLE, ITEM) 的买家，与非自由处置情形（能找到一个多项式规模的最优定价集 \(\mathbb{P}=\{\frac{v_i(m_i)}{m_i}\}\)）不同，此处不能找到多项式规模的最优定价集 \(\mathbb{P}\) （即至少能包含一个 \(p^{opt}\)，使其能构成一个稳定的最优输出 \((X^{opt}, p^{opt})\)）.

然而，考虑定价集 \(\mathbb{P}_\epsilon=\{(1+\epsilon/2)^\ell\}\)，其规模对于输入规模和 \(1/\epsilon\) 是多项式级别的，并且至少包含一个价格 \(p\)，s.t. 对于某个 \(p^{opt}\)，有 \(\frac{p^{opt}}{1+\epsilon/2}\leqslant p\leqslant p^{opt}\).

最终的算法需要对 \(\mathbb{P}_\epsilon\) 中的每一个 \(p\)，选择最优的分配方案.

不失一般性，设买家的最低估价为 \(1\)，再令 \(v_{max}\) 为最大的买家估价，给定 \(\epsilon>0\)，令 \(\mathbb{P}_\epsilon=\{(1+\epsilon/2)^\ell :-\log_{(1+\epsilon/2)}m\leqslant \ell\leqslant \log_{(1+\epsilon/2)}v_{max}\}\). 则 \(\mathbb{P}\) 的规模大约为 \(O(\log_{(1+\epsilon/2)}m+\log_{(1+\epsilon/2)}v_{max})=O(\frac{\log v_{max}+\log m}{\epsilon})\). 又由于 \(p^{opt}\) 须满足 \(\frac{1}{m}\leqslant p^{opt}\leqslant v_{max}\)，故 \(\mathbb{P}\) 中存在一个 \(p\)，s.t. \(\frac{p^{opt}}{1+\epsilon/2}\leqslant p\leqslant p^{opt}\).

定义一个子问题：

  • 给定市场 \(\mu\) 和定价 \(p\)，求一个 pair envy-free 的分配方案 \((\overline{X},p)\)，s.t. 该方案能最大化已分配的商品数量（无视商品总量的限制）.

则整个问题将通过如下算法转化为子问题的求解：

  • 记 \(\mathbb{P}_\epsilon=\{(1+\epsilon/2)^\ell :-\log_{(1+\epsilon/2)}m\leqslant \ell\leqslant \log_{(1+\epsilon/2)}v_{max}\}\)；
  • 对于每个 \(p\in\mathbb{P}_\epsilon\)：
    • 对 \((\mu,p)\) 找到一个（不考虑商品数量限制）卖掉商品最多的分配，记为 \((\overline{X}^p,p)\)（子问题他lei了）；
    • 记 \((\overline{X}^{p'},p')\) 为 \((\overline{X}^p,p)\) 按照 Lemma 12 的方法所得到的可行解；
    • 算一下收益；
  • 对所有 \(p\) 算最大收益.

记 \((\overline{X}^{opt},p^{opt})\) 是一个最优输出，\(p=(1+\epsilon/2)^{\lfloor \log_{(1+\epsilon/2)}p^{opt} \rfloor}\in\mathbb{P}_\epsilon\)，s.t. \(\frac{p^{opt}}{1+\epsilon/2}\leqslant p\leqslant p^{opt}\).

由于 \(p\leqslant p^{opt}\)，故在子问题中，\(p\) 对应的方案能比 \(p^{opt}\) 对应的方案卖掉更多（至少不会更少）的商品. 考虑 \(\overline{X}'\)，s.t. \(|X_i'|=|X_i^{opt}|\)，若 \(X_i^{opt}\neq\varnothing\)，且 \(|X_i'|\) 是被 \(\overline{X}^{opt}\) 分配的商品集大小中，在 \(p\) 下使 \(i\) 的效用最大的商品集大小？？？ 显然，\(\overline{X}'\) 在 \(p\) 下是pair envy-free的，并且至少分配了和 \(\overline{X}^{opt}\) 一样多的商品. 因此，对于子问题的最优解，它一定是这样的一个 \(\overline{X}^p\)，s.t. \(\sum\limits_{i=1}^n |X_i^p|\geqslant \sum\limits_{i=1}^n |X_i'|\leqslant \sum\limits_{i=1}^n |X_i^{opt}|\).

若 \(\sum\limits_{i=1}^n |X_i^p|> m\)，则 \((\overline{X}^p,p)\) 分配了过多的商品，应当用 Lemma 12 来修正为 \((\overline{X}^{p'},p')\).

于是，考虑到 \((\overline{X}^{p'},p')\) 至少分配了 \((\overline{X}^{opt},p^{opt})\) 所分配商品量的一半，并且价格 \(p'\geqslant p\geqslant \frac{p^{opt}}{1+\epsilon/2}\)，故 \(r(\overline{X}^{p'},p')\geqslant \frac{r(\overline{X}^{opt},p')}{2}\geqslant \frac{r(\overline{X}^{opt},p^{opt})}{2+\epsilon}\).

至此，我们只剩下子问题的最优解需要讨论.

给定一个pair envy-free的分配方案 \((\overline{X},p)\)，使其能在市场 \((\mu,p)\) 下最大化商品分配数. 记 \(B_{\overline{X}}\) 为 \(\overline{X}\) 中出现的所有“商品捆”大小构成的集合. 由于 \(\overline{X}\) 是pair envy-free 并且最优的，故对于每个对 \(B_{\overline{X}}\) 中至少一个 \(j\) 持非负效用的买家，我们都必须给该买家分配他认为最好（效用最高）的商品量. 因此，给定 \(B_\overline{X}\)，我们可以在多项式时间内将 \(\overline{X}\) 重建，换言之，子问题的解决只需确定 \(B_\overline{X}\).

注意到，给定 \(p\)，每个买家 \(i\)，若 \(m_i\leqslant \frac{v_i(m_i)}{p}\)，则 \(i\) 对所有处在区间 \([m_i, \lfloor\frac{v_i(m_i)}{p}\rfloor]\) 中的“捆大小”都具有非负效用（这是句废话）. 由于一捆商品的价格会随着size增大而增大，但价值并不会，因此效用是在递减的（也是废话）. 因此，给定 \(B_\overline{X}\)，（若下述集合为空，则取 \(0\)） \[|X_i|=\min\{t:t\in [m_i, \lfloor\frac{v_i(m_i)}{p}\rfloor]\cap B_\overline{X}\}.\]

由于输入可能是指数级别？？？为什么？故我们需要搞一个包含 \(B_\overline{X}\) 的多项式级别的集合 \(B_p\).

Lemma 14. 给定市场 \(\mu\) 和价格 \(p\)，令 \(B_p=\{\lfloor\frac{v_i(m_i)}{p}\rfloor :i\in n\}\)，则 \(B_\overline{X}\subset B_p\)，对所有最大化商品分配数的输出 \((\overline{X},p)\).

证明考虑反证法，假设存在 \(j\notin B_p\)，再记 \(N_i\) 为所有在 \((\overline{X},p)\) 中拿到 \(j\) 个物品的买家. 将他们得到的商品量调整为 \(\min_{i\in N_j}\frac{v_i(m_i)}{p}\) 即可. 细节略去.

最终子问题的解决办法如下:

  • 令 \(B_p=\{\lfloor\frac{v_i(m_i)}{p}\rfloor:i\in N\}\)；
  • 对 \(j\in B_p\)（从大到小）：
    • 计算一个“最大化‘收入’的分配”所分配掉的商品总数 \(x(j)\)，其所分配的最小的商品集大小为 \(j\)，即：\[x(j)=\max\{\max_{k\in B,k>j}\{x(k)+\Delta_k^j\},~j\cdot|N_j|\};\]
  • 返回最大的 \(x(j)\) 所对应的分配 \((\overline{X}^j,p)\).

General 买家

Item-pricing

  • 现有如下猜想：
    • 一个随机的 \(n\) 元3-SAT问题，有 \(m=\Delta n\) 条约束，该猜想断言对 \(\forall \epsilon>0\)，以及一个与 \(n\) 无关的大常数 \(\Delta\)，不存在这样的多项式时间算法，能够求解满足 \((1-\epsilon)\) 比例的约束.
  • 一个问题被称为是 R3SAT 困难的，如果”该问题有多项式时间解法“能够证伪上述猜想.

Def 15. MES 是如下的问题：

  • 给定全集 \(U\) 和一个有序子集族 \(\mathcal{C}=\{S_1,\cdots,S_c\}\)；
  • 一个长度为 \(\ell\) 的扩张序列(expanding sequence)\(\phi=(\phi(1)<\cdots<\phi(\ell))\) 是一系列集合 \(S_{\phi(1)},\cdots,S_{\phi(\ell)}\)，s.t. \(\forall 1\leqslant y\leqslant \ell\)，\(S_{\phi(y)}\not\subseteq\bigcup\limits_{l=1}^{y-1} S_{\phi(l)}\).
  • MES 的目标就是求出最长的序列(Maximum expanding sequence).
  • MES 问题是一个 R3SAT 困难的问题.

Def 16. 称一个 MES 问题是 \(\kappa\)-separable的，若 \(\mathcal{C}\) 的序列可以被分为 \(\kappa\) 个不交子列/子类 \(\mathcal{C}_1,\cdots,\mathcal{C}_\kappa\).
文献[21]证明了，\(\exists\epsilon>0\)，s.t 当 MES 问题是 \(f(c)\)-separable的，在 \(O(f(c)^\epsilon)\) 内逼近该问题也是 R3SAT 困难的. 其中 \(f\) 满足：

  • \(f\) 是不减的；
  • \(f(a)\leqslant a\) 且 \(f(a^b)\leqslant f(a)^b\)，\(\forall b>1\)，\(a\in\mathbb{N}\).

Th 17. 对一些 \(\epsilon>0\) 来说，在 \(O(\log^\epsilon n)\) 下逼近 (GENERAL, ITEM) 问题是 R3SAT-困难的.

Lemma 18. 如果市场 \(\mu\) 存在一个稳定的输出 \((\overline{X},p\neq 1)\)，记其收益为 \(r\)，则也存在一个稳定的输出 \((\overline{X}',1)\)，其收益为 \(r/4\).

Bundle-pricing

Th 22. (GENERAL, BUNDLE) 分配问题有 \(\frac{\log n}{1-\frac{1}{e}}\) 近似算法.

无嫉妒的代价

Th 24. (SINGLE, ITEM) 情形的代价是 \(2\).

Th 25. (SINGLE, BUNDLE) 情形的代价是 \(1\).

Th 26. (GENERAL, ITEM) 情形的代价是 \(\Theta(\log n)\).

Th 27. (GENERAL, BUNDLE) 情形的代价是 \(\Theta(\log n)\).