Computational tractability

计算可处理性

A problem is “computationally tractable” (a concept in computer science) if the time a computer takes to solve it is of the same (or smaller) order as the number of inputs (raised to some exponent) for the problem:

Time needed to compute a solution ≤ C(n^{^k}) where:

• parameters, “C > 0” and “k > 0” are some constant; and

• the time taken to compute a solution is usually measured as the number of elementary operations required to compute the solution.

“C(n^{^k})” is called “polynomial time”, being a polynomial function.

For many VCG mechanisms, the optimisation problem cannot be solved within polynomial time. Optimisation involves aggregating across the private valuation functions, “v(a)” of “N” participants to find “MAX(over a)SUM(over -i)v-i(a)”. If the VCG mechanism applies to a single good, it is solvable in polynomial time. [Note 1] However, if the VCG mechanism is applied to a combination of several goods that are complementary or substitutes, optimisation becomes intractable. [Note 2]

It seems that if participants select their dominant strategies over some “feasible range” (limited by each participant’s prior knowledge of her rivals’ strategies), it may be possible to approximate the optimal solution using some other algorithm that is computationally tractable. However, truthful reporting is no longer the participants’ dominant strategy. [Note 3]

****************

Note 1: If there are “M” possible outcomes in set {a ∈ A}, then the number of inputs is: n = N*M where “N” is the number of participants. So polynomial time is C(NM)^{^k}.

Note 2: See these lecture notes on “combinatorial auctions” which allocates many goods that are substitutes and complements.

Note 3: See Nisan, Ronen, Computationally Feasible VCG mechanisms. The authors argue that the participants’ dominant strategy could be called “feasibly truthful”.

---

如果计算机解决问题所需的时间与问题输入数量（以某个指数量被上升）相同（或更少），则该问题就是“可处理计算”（计算机科学中的概念）：

计算解决方案的时间 ≤ C(n^{^k}) 其中：

• 参数“C > 0”和“k > 0” 是某个常数；并

• 计算解决方案所需的时间通常以计算解决方案所需的基本运算数量来衡量。

“C(n^{^k})”称为“多项式时间”，因为它是一个多项式函数。

对于许多VCG机制，优化问题无法在多项式时间内解决。优化涉及汇总“N”个参与者的私人估值函数“v(a)”，以找到“MAX(over a)SUM(over -i)v-i(a)”。如果VCG机制应用于单一物品，则可以在多项数时间内解决。[注1] 但是，如果VCG机制应用于多种互补或替代 的组合，则优化将变得难以实现。[注2]

似乎如果参与者在某个“可行范围”（受每个参与者对其竞争对手策略的先验知识限制）内选择其占优策略，则可能使用其他一些计算上可处理的算法来近似最佳解决方案。但是，如实报告不再是参与者的占优策略。[注3]

***************

注1: 如果集合 {a ∈ A} 中有“M”可能的结果，则输入的数量为：n = N*M，其中“N”是参与者的数量。因此多项式时间为：C(NM)^{^k}。

注2: 请参阅这些关于“组合拍卖”的讲义，该讲义分配了许多替代物品和互补物品。

注3: 请参阅 Nisan，Ronen 《计算上可行的VCG机制》。作者辩论参与者的占优策略可以称为“可行的如实”。