| paper | d4-conf-aaai-2021-1887 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in the binary bit model. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 8
Given rational type masses \(\mu_t>0\) summing to \(1\), per-capita budgets \(b_t\), and normalized nonnegative piecewise-linear valuations \(v_t\) on \([0,1]\) with \(K\) shared segments, define \(B_t=\mu_t b_t\) and let \(U_t^*\) be type \(t\)'s aggregate utility at the Fisher equilibrium. Compute a feasible pure aggregate allocation \(y_t=\mathbf{1}_{A_t}\), where each \(A_t\) is a union of at most \(K\) intervals and \(\sum_t y_t\leq 1\), such that \(\int_0^1 v_t(\theta)y_t(\theta)\,d\theta\geq U_t^*-\epsilon\) for every type \(t\).
Use a population with type mass \(\mu_t\), per-capita budget \(b_t\), and valuation \(v_t\). Let \(x_t\) be the type's per-capita bundle and \(y_t=\mu_t x_t\) its aggregate allocation, with \(\sum_t y_t\leq 1\). Set \(B_t=\mu_t b_t\); the population objective \(\sum_t\mu_t b_t\log\int_0^1v_t x_t\) and the representative-buyer objective \(\sum_tB_t\log\int_0^1v_t y_t\) differ only by an additive constant.
The mirror covers Theorem 8's approximate piecewise-linear equilibrium-utility allocation and pure interval construction with \(n=\tau\). It leaves the general-valuation stochastic method, quasilinear extension, and broader existence and duality results outside the mirror.
The strongest mirror is Mass-Weighted Piecewise-Linear Fisher Allocation. Let the population have finite type support \(\mathcal T\), with \(\tau\) types and rational masses \(\mu_t>0\) summing to \(1\). A type is a complete market description: its members have the same valuation function \(v_t\) and per-capita budget \(b_t\). Take the cake to be \([0,1]\), with nonnegative piecewise-linear valuations on a common \(K\)-segment partition, normalized so that \(\int_0^1v_t(\theta)\,d\theta=1\), and normalize total budget by \(\sum_t\mu_tb_t=1\).
The scenario is a large equal-income fair-division population—say, many users whose valuations of a continuum of service qualities fall into a modest number of recurring profiles. The population can be much larger than \(\tau\); a profile’s mass is the fraction of people in that cohort. Each cohort receives the same per-capita bundle \(x_t\), and feasibility is \(\sum_t\mu_tx_t(\theta)\leq1\) almost everywhere: supply is scaled per unit of population. The underlying objective is to maximize \(\sum_t\mu_tb_t\log u_t\), where \(u_t=\int_0^1v_t(\theta)x_t(\theta)\,d\theta\). Equivalently, at prices \(p\), each type chooses a utility-maximizing bundle costing at most \(b_t\), and the population allocation clears the market.
My lead anchor is Theorem 8, proved in this paper. For \(n\) buyers with piecewise-linear valuations over \(K\) segments and normalized budgets, it computes feasible segment utilities whose total for every buyer is at least that buyer’s equilibrium utility minus \(\epsilon\), in \(O(n^4K(\log(nK)+\log(\kappa/\epsilon)))\) time, where \(\kappa=1/\min_i B_i\). It also constructs a pure allocation of at most \(K\) intervals per buyer in \(O(nK)\) additional time. The theorem is the paper’s result; its proof uses a separately cited ellipsoid-method bound. [Theorem 8 in the full text](https://arxiv.org/pdf/2010.03025)
The reduction to the population mirror is direct. Give the representative buyer for type \(t\) aggregate budget \(B_t=\mu_tb_t\) and aggregate bundle \(y_t=\mu_tx_t\). Then \(\sum_ty_t\leq1\), and its utility \(U_t=\int v_ty_t=\mu_tu_t\) is the mass-weighted utility of that cohort. The representative-buyer EG objective \(\sum_tB_t\log U_t\) differs from the population objective only by the constant \(\sum_tB_t\log\mu_t\), so both have the same optimum. Theorem 8 therefore gives a concrete solution notion: return feasible segment utilities with \(U_t\geq U_t^*-\epsilon\) for every type, together with the corresponding pure partition of the item interval by type. This is an additive approximation to the cohort’s mass-weighted equilibrium utility.
I expect Class A, tractable, with the theorem’s running time in \(\tau\), \(K\), and \(\log(1/\min_t\mu_tb_t)\), rather than in the total population. A binary bit-complexity bound in the rational input length \(L\) should be made explicit before claiming the full encoding-sensitive result. The authors should recognize this as their Fisher-equilibrium allocation problem for a nonatomic population of identical buyers within each type, with aggregate budgets and allocations. It covers Theorem 8’s piecewise-linear, one-dimensional allocation result; it does not attempt to mirror the paper’s general-valuation stochastic method, its quasilinear extension, or its broader existence and duality results.
The weakest point is that this is exact aggregation into a weighted finite market with \(\tau\) representative buyers. That makes it a credible high-multiplicity mirror, but the algorithm transfers almost mechanically; it is not a new complexity phenomenon, and the paper supplies no hardness result whose discrete difficulty might dissolve. The regime also depends on genuinely repeated valuation-and-budget profiles. If those profiles are nearly all unique, then \(\tau\) approaches the population size and the computational gain disappears. Further questions are whether the finite-population and mass models admit a precise two-way approximation guarantee, and how the result changes when agents within a type differ slightly in budgets or valuations.
The strongest negative case is that the mirror depends on an exact low-support regime that the paper does not establish for its applications. A type must include the entire piecewise-linear valuation and budget. Since both can vary, a population of \(N\) buyers may have \(\tau=N\); replacing distinct curves with a few representative ones changes the market and needs its own error analysis. The proposed additive guarantee also applies to aggregate utility \(U_t=\mu_tu_t\), so for a small-mass type it may say little about that type’s per-capita utility. A stronger formulation would ask for per-capita error, which requires tighter accuracy for small \(\mu_t\).
That is a real limitation of the proposed regime and guarantee, but it does not defeat the better mirror. A large population with recurring, identical valuation-and-budget profiles is a plausible instance regime. For it, the reduction is exact: set \(B_t=\mu_tb_t\) and \(y_t=\mu_tx_t\). The feasibility and demand constraints scale accordingly, and \(\sum_t B_t\log\!\int v_ty_t\) differs from the population objective only by the constant \(\sum_t B_t\log\mu_t\). Theorem 8 then applies with \(n=\tau\). Per-capita accuracy can be obtained by tightening the aggregate error; the theorem’s dependence on the inverse minimum budget already reflects small type masses.
One might object that this is a mechanical weighted version of the paper’s finite-buyer algorithm. But a known or easy answer does not make a well-posed population mirror unworthy, and the paper’s continuum is over items, not over buyers. High-multiplicity support is evidence for the regime, not a novelty collision. Nor does the paper’s small-\(n\) fair-division setting rule out a distinct large-population regime.
So the negative case is limited to saying the mirror is not representative when nearly every buyer has a unique type, and that the stated approximation should be sharpened for small cohorts. I cannot honestly defeat the lead anchor across plausible scenarios: exact repeated types give a sensible continuous-population question and a concrete computational result.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.