Answer: Exact mass-weighted fitting with succinct rational valuations is polynomial-time solvable; its threshold decision problem belongs to \(\mathsf{P}\).
Theorem 3.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAn ǫ-approximate valuation function which (approximately) rationalises bidding behaviour exists if and only if the bidding graph has minimum mean cycle µ(G) ≥−ǫ.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a support of bidder-history types \(h\), rational masses \(\mu_h\) summing to \(1\), and each type’s price–bundle history \(((p_{h,r},x_{h,r}))_r\), choose a tolerance \(\epsilon_h\) and fitting valuation \(\hat v_h\) on \(\{0,1\}^n\) for every type, subject to \(\hat v_h(x_{h,r})-p_{h,r}\cdot x_{h,r}\ge \hat v_h(y)-p_{h,r}\cdot y-\epsilon_h\) for every \(h,r,y\). Minimize \(\sum_h\mu_h\epsilon_h\) and return the optimum with succinct fitting valuations or certificates.
A society is given by its support: a list of \(\tau\ge1\) bidder-history types with positive binary-rational masses \(\mu_h\) summing to \(1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\ge1\) items. Type \(h\) has a nonempty, explicitly listed history \(((p_{h,r},x_{h,r}))_{r=1}^{T_h}\), with \(p_{h,r}\in\mathbb Q_{\ge0}^{m}\) and \(x_{h,r}\in\{0,1\}^{m}\); repeated bundles are permitted. Let \(R=\sum_hT_h\) and let \(L\) be the total input bit length.
Choose independently for each type a tolerance \(\epsilon_h\in\mathbb R_{\ge0}\) and an unrestricted virtual valuation \(\hat v_h:\{0,1\}^{m}\to\mathbb R\). There are no budget constraints, monotonicity requirements, normalization, or individual-rationality constraints; utility ties are allowed.
Require \(\hat v_h(x_{h,r})-p_{h,r}\cdot x_{h,r}\ge\hat v_h(y)-p_{h,r}\cdot y-\epsilon_h\) for every \(h,r\) and every \(y\in\{0,1\}^{m}\), including \(y=x_{h,r}\). Minimize \(\sum_h\mu_h\epsilon_h\). Exact fitting output consists of the optimum, optimal tolerances, and finite rational descriptions of fitting valuations evaluable on any bundle in polynomial time. The threshold decision problem additionally takes a binary-rational \(B\) and asks whether the optimum is at most \(B\).
Is exact mass-weighted fitting, with succinct fitting valuations, solvable in polynomial time in \(m,\tau,R,L\), or is its threshold decision problem NP-hard?
For a finite single-bidder history, optimal additive fitting is computable in polynomial time, with the feasibility tolerance characterized by minimum cycle means ([Boodaghians–Vetta](https://arxiv.org/pdf/1505.00508v2)). No result specifically addressing this distributional formulation was identified in the search.
Exact mass-weighted fitting, including succinct fitting valuations, is polynomial-time solvable. Its threshold decision problem belongs to \(\mathsf{P}\).
The proof below gives an explicit algorithm. The cycle characterization agrees with [Boodaghians–Vetta, Sections 2.3 and 3.1](https://arxiv.org/pdf/1505.00508v2); we prove the needed statements directly, including the extension to every bundle and the exact bit-complexity bounds.
Fix one type and suppress its type index. Write its history as \(((p_r,x_r))_{r=1}^{T}\). Let
\(\displaystyle S=\{b_1,\ldots,b_n\}=\{x_r:1\le r\le T\}\)
be the set of distinct observed bundles, so \(1\le n\le T\). For each observation, let \(i(r)\) satisfy \(x_r=b_{i(r)}\).
For every ordered pair of observed bundles, define
\(\displaystyle w_{ij}=\min_{\{r:x_r=b_i\}}p_r\cdot(b_j-b_i).\)
Each minimum is over a nonempty finite set. In particular, \(w_{ii}=0\).
If \(a_i\) denotes the value assigned to \(b_i\), the fitting inequalities restricted to observed alternatives are equivalent to
\[\displaystyle a_j-a_i\le w_{ij}+\epsilon\qquad(1\le i,j\le n). \tag{1}\]
Indeed, for fixed \(i,j\), the original inequalities require the left-hand side to be at most \(p_r\cdot(b_j-b_i)+\epsilon\) for every observation with \(x_r=b_i\). Their conjunction is exactly (1). Thus repeated bundles are handled by retaining their tightest constraints.
Extension lemma. Suppose \(\epsilon\ge0\) and \(a_1,\ldots,a_n\) satisfy (1). Define
\(\displaystyle c=\min_{1\le r\le T}\bigl(a_{i(r)}-p_r\cdot x_r\bigr).\)
Assign \(\hat v(b_i)=a_i\) to observed bundles and \(\hat v(y)=c\) to every unobserved bundle \(y\).
This valuation satisfies every required fitting inequality.
Proof. If \(y=b_j\) is observed, (1) implies
\(\displaystyle \hat v(y)-\hat v(x_r)\le w_{i(r),j}+\epsilon\le p_r\cdot(y-x_r)+\epsilon,\)
which rearranges to the required inequality.
If \(y\) is unobserved, nonnegative prices and binary bundles give \(p_r\cdot y\ge0\). Hence
\(\displaystyle \hat v(y)-p_r\cdot y-\epsilon=c-p_r\cdot y-\epsilon\le c\le a_{i(r)}-p_r\cdot x_r.\)
This is again the required inequality. The construction assigns finite values to every bundle. If the \(a_i\) are rational, so is \(c\). \(\square\)
Consequently, feasibility on all \(2^m\) bundles is equivalent to feasibility of the finite system (1).
Consider the complete directed graph on vertices \(1,\ldots,n\), with arc weights \(w_{ij}\), including self-loops. A simple directed cycle visits no vertex twice except its initial and final vertex; self-loops count as cycles of length one.
For such a cycle \(C\), define its mean weight by
\(\displaystyle \operatorname{mean}(C)=\frac{\sum_{(i,j)\in C}w_{ij}}{|C|},\)
and let
\(\displaystyle \lambda=\min_C\operatorname{mean}(C).\)
There are finitely many simple cycles, and at least one exists. Since every self-loop has weight zero, \(\lambda\le0\).
Proposition. The minimum feasible tolerance is
\(\displaystyle \epsilon^\star=-\lambda.\)
Necessity. Suppose (1) holds. Summing it around any simple cycle \(C\) makes all valuation differences telescope, giving
\(\displaystyle 0\le\sum_{(i,j)\in C}w_{ij}+|C|\epsilon.\)
Therefore \(\epsilon\ge-\operatorname{mean}(C)\) for every \(C\), and hence \(\epsilon\ge-\lambda\).
Sufficiency and construction. Set \(\epsilon^\star=-\lambda\) and give arc \(i\to j\) the shifted weight
\(\displaystyle \ell_{ij}=w_{ij}+\epsilon^\star=w_{ij}-\lambda.\)
Every simple cycle has nonnegative shifted total weight, because
\(\displaystyle \sum_{(i,j)\in C}\ell_{ij}=|C|\bigl(\operatorname{mean}(C)-\lambda\bigr)\ge0.\)
Every closed directed walk decomposes into simple cycles: whenever a vertex repeats, remove the closed segment between two occurrences and continue recursively. This preserves the total weight as the sum of the removed cycle weights. Thus every closed walk also has nonnegative shifted weight.
Add a new source \(s\) with a zero-weight arc to every original vertex and no incoming arcs. Let \(d_i\) be the minimum weight of a path from \(s\) to \(i\).
These minima are finite and attained. Every vertex is reachable directly from \(s\); furthermore, deleting a closed segment from a path cannot increase its weight. A minimizing path can therefore be chosen without repeated vertices, from a finite collection of paths.
Appending arc \(i\to j\) to a minimum path to \(i\) gives
\(\displaystyle d_j\le d_i+\ell_{ij}=d_i+w_{ij}+\epsilon^\star.\)
Thus \(a_i=d_i\) satisfies (1). The extension lemma supplies a fitting valuation on all bundles. Since \(\lambda\le0\), the constructed tolerance is admissible. This proves both optimality and attainment. \(\square\)
In particular, a history containing only one distinct bundle has optimum zero.
A direct dynamic program suffices; no cycle enumeration is needed.
For each starting vertex \(s\), let \(D_k^{(s)}(j)\) be the minimum weight of a directed walk from \(s\) to \(j\) containing exactly \(k\) arcs. Initialize
\(\displaystyle D_0^{(s)}(s)=0,\qquad D_0^{(s)}(j)=+\infty\quad(j\ne s),\)
and compute, for \(1\le k\le n\),
\[\displaystyle D_k^{(s)}(j)=\min_{1\le i\le n}\bigl(D_{k-1}^{(s)}(i)+w_{ij}\bigr). \tag{2}\]
Then
\[\displaystyle \lambda=\min_{\substack{1\le s\le n\\1\le k\le n}}\frac{D_k^{(s)}(s)}{k}. \tag{3}\]
To verify (3), any walk counted by \(D_k^{(s)}(s)\) is closed. Its cycle decomposition shows that its mean is a weighted average of simple-cycle means, and therefore is at least \(\lambda\). This proves that the right-hand side of (3) is at least \(\lambda\).
Conversely, choose a simple cycle attaining \(\lambda\), choose a vertex \(s\) on it, and let \(k\le n\) be its length. This cycle is one of the walks considered by \(D_k^{(s)}(s)\), so
\(\displaystyle \frac{D_k^{(s)}(s)}{k}\le\lambda.\)
Thus equality holds.
Computing (2) for all starting vertices takes \(O(n^4)\) exact arithmetic operations.
The values \(d_i\) used in Section 2 can also be computed directly. Initialize \(d_j^{(0)}=0\) for every \(j\), and perform \(n-1\) iterations of
\(\displaystyle d_j^{(t+1)}=\min\left\{d_j^{(t)},\ \min_i\bigl(d_i^{(t)}+\ell_{ij}\bigr)\right\}.\)
By induction, \(d_j^{(t)}\) is the minimum weight of a walk ending at \(j\), starting at any original vertex, with at most \(t\) arcs. This represents a path from the added source because its first arc has weight zero. Cycle deletion shows that at most \(n-1\) arcs among original vertices suffice. Therefore \(d_j=d_j^{(n-1)}\). This computation takes \(O(n^3)\) arithmetic operations.
For each type \(h\), apply the preceding construction to its own history. Let \(\epsilon_h^\star\) be its optimal tolerance, and let \(\hat v_h^\star\) be the resulting valuation.
Every feasible society-wide solution satisfies \(\epsilon_h\ge\epsilon_h^\star\) for each \(h\). Since every mass \(\mu_h\) is positive,
\(\displaystyle \sum_{h=1}^{\tau}\mu_h\epsilon_h\ge\sum_{h=1}^{\tau}\mu_h\epsilon_h^\star.\)
Conversely, the independently constructed pairs \((\epsilon_h^\star,\hat v_h^\star)\) are jointly feasible: the problem imposes no constraints coupling different types. Hence the exact optimum is
\(\displaystyle \operatorname{OPT}=\sum_{h=1}^{\tau}\mu_h\epsilon_h^\star.\)
This proves that the optimum is attained and that its computation requires only the explicitly supplied support types.
For each type, output its tolerance, a table containing the distinct observed bundles and their rational values \(d_i\), and the rational constant
\(\displaystyle c_h=\min_r\bigl(d_{i(r)}-p_{h,r}\cdot x_{h,r}\bigr).\)
The valuation evaluation rule is: return the table value if the queried bundle occurs in the table; otherwise return \(c_h\). Comparing a query against all table entries takes \(O(mn_h)\) bit comparisons, where \(n_h\le T_h\). This is a finite rational description evaluable on every bundle in polynomial time.
It remains to bound the numerical encoding lengths, rather than just the arithmetic-operation count.
For a fixed type, let \(Q\) be the product of the denominators of all its input price coordinates. Its binary length is bounded by the total input length \(L\). Every arc weight is an integer divided by \(Q\), with numerator of polynomial bit length.
Each finite dynamic-programming entry is the weight of a walk of at most \(n\) arcs. It therefore also has denominator \(Q\) and a numerator of polynomial bit length. Formula (3) selects one candidate, so for some integer \(z\) and \(1\le k\le n\),
\(\displaystyle \epsilon^\star=-\frac{z}{Qk}.\)
All shifted weights consequently have common denominator \(Qk\). Each distance \(d_i\) is a sum of at most \(n-1\) shifted weights, and each candidate defining \(c_h\) is a distance minus an input dot product. All these rationals have polynomial bit length.
Finally, taking products of the denominators of the masses and the computed tolerances gives a common denominator for \(\operatorname{OPT}\) whose bit length is polynomial in \(L,\tau,R\). Exact summation and comparison with the input threshold \(B\) therefore also take polynomial time.
Constructing the graph for type \(h\) takes \(O(mT_hn_h)\) arithmetic operations. Including the cycle computation, the total arithmetic-operation bound is
\(\displaystyle O\left(\sum_{h=1}^{\tau}\bigl(mT_hn_h+n_h^4\bigr)\right)\subseteq O(mR^2+R^4).\)
Together with the bit-length bounds, this establishes polynomial bit complexity for the complete exact fitting output and for threshold decision.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned task. The argument establishes a polynomial-time algorithm for exact mass-weighted fitting, including rational tolerances, succinct fitting valuations, and threshold decision. I found no major or minor mathematical issues.
Every observed bundle has at least one associated observation, so each minimum defining \(w_{ij}\) exists. For a fixed pair \(b_i,b_j\), the original constraints are
\[
a_j-a_i\le p_r\cdot(b_j-b_i)+\epsilon
\]
for every observation with \(x_r=b_i\). Taking the minimum of their right-hand sides gives exactly (1). This handles repeated bundles without discarding any relevant constraint.
The identity \(w_{ii}=0\) is correct. Its corresponding constraint is consistent with the explicitly required \(\epsilon\ge0\).
For observed alternatives, the two inequalities used in the proof have the correct direction: \(w_{i(r),j}\) is at most the price expression from observation \(r\).
For unobserved alternatives, the proof uses precisely the hypotheses supplied by the task: prices are nonnegative, bundles are binary, and tolerances are nonnegative. Thus
\[
c-p_r\cdot y-\epsilon\le c\le a_{i(r)}-p_r\cdot x_r.
\]
This proves every required constraint for every unobserved bundle.
The minimum defining \(c\) is over a nonempty finite history. All assigned values are finite, and rational observed values give rational \(c\). The unrestricted valuation model permits this construction. Consequently, the finite system is genuinely equivalent to the full feasibility problem.
The graph is finite and contains self-loops, so the minimum over simple cycles exists and satisfies \(\lambda\le0\).
Summing (1) around a cycle correctly cancels all valuation differences and yields
\[
\epsilon\ge-\operatorname{mean}(C).
\]
Taking the strongest such bound gives \(\epsilon\ge-\lambda\).
At \(\epsilon^\star=-\lambda\), every simple cycle has nonnegative shifted weight. The stated decomposition of closed walks into simple cycles correctly extends this property to every closed walk.
The added source reaches every vertex. Since closed segments have nonnegative weight, removing them cannot increase a walk’s weight. Hence the minimum can be taken over finitely many paths without repeated vertices; it is finite and attained.
Appending an arc gives the valid inequality
\[
d_j\le d_i+w_{ij}+\epsilon^\star.
\]
Thus the distances satisfy (1), and the extension lemma supplies a valuation on all bundles. Because \(\lambda\le0\), the constructed tolerance meets its domain restriction.
The single-distinct-bundle case is covered correctly: its only simple cycle has weight zero, and the optimum is zero.
Recurrence (2) correctly computes minimum weights of walks having exactly the specified number of arcs.
Every closed walk in (3) decomposes into simple cycles. Its mean is a length-weighted average of their means and is therefore at least \(\lambda\). Conversely, a minimizing simple cycle has length at most \(n\) and appears among the walks considered by (3). These two directions establish equality.
There are \(n\) starting vertices, \(n\) lengths, \(n\) terminal vertices, and \(n\) predecessor choices, giving the stated \(O(n^4)\) arithmetic-operation bound.
The initialization represents the zero-cost source arcs. The recurrence computes minimum weights with at most the specified number of original-graph arcs.
After deleting repeated-vertex segments, at most \(n-1\) original-graph arcs are needed. Thus \(n-1\) iterations suffice. The \(n=1\) case correctly requires zero iterations. The stated \(O(n^3)\) bound is valid.
The task imposes no constraints linking different types. Therefore every feasible solution satisfies the separate lower bounds \(\epsilon_h\ge\epsilon_h^\star\), and multiplying by the positive masses preserves those inequalities.
The independently constructed solutions are jointly feasible and attain
\[
\operatorname{OPT}=\sum_{h=1}^{\tau}\mu_h\epsilon_h^\star.
\]
This uses only the explicitly supplied support, as required.
Each description contains a finite table of observed bundles and rational values, together with one rational default value. Its evaluation rule is unambiguous, including when every possible bundle is observed.
Comparing a binary query bundle with the table requires \(O(mn_h)\) bit comparisons. The resulting description is therefore succinct and evaluable in polynomial time.
The product \(Q\) of input price denominators has bit length bounded by the input encoding length. Dot products and selected arc weights can be represented over this denominator with polynomial-length numerators.
Dynamic-programming entries sum at most \(n\) arc weights. Dividing a selected entry by a cycle length introduces only the additional factor \(k\le n\). Shifted weights, distances, and default valuation constants consequently retain polynomial encoding length.
The common-denominator argument for the weighted optimum is also valid: the bit length of a product of denominators is bounded by the sum of their bit lengths. Exact arithmetic and comparison with the input threshold therefore take polynomial time.
Finally, \(n_h\le T_h\) and \(\sum_hT_h=R\) justify the aggregate bound \(O(mR^2+R^4)\).
The external citation is not needed for any inference: the prover supplies direct proofs of the cycle characterization and all algorithmic claims. No additional clarification or repair is required.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.