| paper | d4-conf-aaai-2000-0126 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 7
statement extracted from the paper’s text layer
Given ordered goods \(g_1,\ldots,g_m\), per-capita capacities \(q_j\), and a distribution \(\mu\) over \(\tau\) bid types, where type \(t\) specifies an interval \(I_t\) and price \(p_t\), choose accepted masses \(x_t\) to maximize \(\sum_t p_t x_t\), subject to \(0\le x_t\le\mu_t\) and \(\sum_{t:\,g_j\in I_t}x_t\le q_j\) for every good \(g_j\). Each individual receives either the entire interval or nothing; \(x_t\) is the mass of type \(t\) whose bid is accepted.
A high-multiplicity interval auction with types defined by each buyer's complete interval-and-price bid, mass \(\mu_t\), and per-capita capacity \(q_j\) for each good. The decision is how much mass of each type to accept; the objective is total revenue, with each accepted individual receiving their whole interval.
The mirror covers Theorem 7's multi-unit linear-goods allocation problem and leaves Theorems 1–6 and the paper's other auction variants unaddressed.
The strongest mirror I see is the multi-unit linear-goods result. Theorem 7, proved in this paper, says the MULGA problem is computationally tractable: given an ordered line of goods, \(q(i)\) copies of each good, and bids for contiguous intervals of goods, choose a revenue-maximizing set of bids subject to each good’s supply limit. The paper formulates this as an integer program and shows its LP relaxation is exact because each bid’s column has consecutive \(1\)s and the resulting matrix is totally unimodular.
I would call the continuous version High-Multiplicity Interval Auction. Its instance has goods \(g_1,\ldots,g_m\) in order; a rational per-capita supply \(q_j\) for each good; and a support \(T\) of \(\tau\) bid types. Type \(t\) has mass \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\), and specifies an interval \(I_t=[g_{a_t},\ldots,g_{b_t}]\) and a rational offer \(p_t\). Choose \(x_t\), the mass of type \(t\) whose bid is accepted, to maximize
\[
\sum_{t\in T}p_t x_t
\]
subject to \(0\le x_t\le\mu_t\) and
\[
\sum_{t:\,g_j\in I_t}x_t\le q_j\qquad\text{for each }g_j.
\]
A solution is an optimal vector \(x\) and its revenue. Each individual still receives either their whole interval or nothing; only a fraction of a type’s mass may win.
A plausible regime is a large, recurring market for time slots or other ordered capacity, where many households or organizations submit one of a small number of interval-and-price offers. For example, millions of requests might use a few hundred recurring templates, so \(\tau\ll N\). The type includes the offer price, as high multiplicity requires. Supplies scale with the population: a population of size \(N\) has \(Nq_j\) copies of good \(g_j\). This co-modification keeps the allocation meaningful as the population grows. It continuizes the society, not the bundle each person receives.
This mirror is tractable, by linear programming in time polynomial in \(m,\tau\), and the input bit length. It also has a precise high-multiplicity bridge: when \(N\mu_t\) and \(Nq_j\) are integers, scaling the continuous constraints by \(N\) gives the finite winner-determination problem. The interval matrix remains totally unimodular, including the type upper-bound constraints, so there is an integral optimal allocation at that scale. The continuous problem is therefore a compressed version of the paper’s allocation question, with a direct exactness result for compatible finite populations.
The paper’s preliminary statement that unrestricted CAP is NP-hard cites Rothkopf et al. (1998), but it is not a numbered result proved here, so I do not use it as an anchor. Theorem 7 is an algorithmic anchor, and the paper already solves its discrete problem; this mirror is not a claim that continuization dissolves hardness. Further questions include whether the same exact compression survives when bidders submit multiple bids with bidder-level constraints, and how far it extends from intervals to paths on trees.
The weak point is that the theorem is about winner determination from submitted bids, not about bidders’ strategic behavior or underlying valuations. And since Theorem 7 already gives a polynomial algorithm, the continuous version adds more as a high-multiplicity formulation and bridge than as a new tractability result. Still, repeated interval requests with per-capita supply are a credible population regime, and the mirror preserves the paper’s allocation problem rather than replacing it with fractional bundles.
I cannot honestly defeat Theorem 7 as an anchor. Its high-multiplicity mirror is a sensible auction problem: in a recurring market, many buyers can submit the same interval-and-price bid, while the seller scales each good’s supply with the buyer population. The type then includes the offer price, and accepting a fraction of a type’s mass means accepting whole bids from that fraction of otherwise identical buyers. The allocation objective does not need individual identities.
The strongest objection is that this regime needs repeated *exact* interval-and-price offers. If prices are highly individualized, the support size \(\tau\) may grow with the population, leaving little compression. But that limits the regime; it does not rule it out. Standardized offers in a large reservation market are plausible, and the authors could reasonably recognize the resulting problem as theirs. Nor does the fact that the continuous LP inherits the paper’s consecutive-ones structure defeat the mirror: it gives a direct high-multiplicity formulation and bridge.
So the negative case is weak at its central burden. The mirror may be narrow, but I see no fundamental reason it is not worthwhile in at least one scenario.
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.