| paper | d4-conf-aaai-2005-0320 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: Computing the exact optimal value is \(\mathrm{NP}\)-hard, even for \(k=2\). An optimal executable stopping rule is computable in polynomial time. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a finite offer set \(X\) with rational probabilities \(p_x\), buyer types \(T\) with rational masses \(\mu_t\) summing to \(1\), total population mass \(M>0\), and per-search cost \(\kappa(M)>0\), compute an optimal policy and its expected net utility from an initial set of known offers. A state records each type’s best known offer \(r_t\in X\); stopping yields \(M\sum_{t\in T}\mu_t U_t(r_t)\), while continuing pays \(\kappa(M)\), draws an offer according to \(p\), and updates each type’s record if its utility improves. In B2C, each offer can serve all mass of every type.
A finite-support high-multiplicity B2C search model: each complete buyer type \(t\) carries mass \(M\mu_t\); the state stores its best known offer; each new offer is drawn from a finite distribution and can serve all types; the policy chooses whether to stop or pay \(\kappa(M)\) and continue, maximizing expected aggregate utility minus search costs.
The mirror preserves the finite state graph and changes its payoff weights, so it adds no evident algorithmic challenge beyond analyzing the existing policy computation as a function of type support.
fatal: False
The mirror covers the B2C optimal-policy computation in Theorem 2 and its type-level state representation; it leaves the C2C assignment problem, coalition formation and stability, payoff division, and the paper’s performance experiments aside.
The best mirror is Continuous B2C Coalition Search with Finite Offer Support. The paper’s strongest anchor for it is Theorem 2, proved in this paper: for the finite marketplace and utility inputs to Algorithm 1, the algorithm terminates and returns the representative agent’s optimal search strategy from a given set of known opportunities. That strategy specifies whether to stop or continue for the opportunity sets the agent may encounter. The result establishes exact solvability, but gives no polynomial-time bound or standard complexity classification. The paper contains no named hardness result to anchor a question about whether discrete hardness disappears.
Here is a precise continuous version. There are finitely many buyer types \(T\), with positive rational shares \(\mu_t\) summing to \(1\), and total population mass \(M>0\). A type is a complete MAUT utility function \(U_t\), including every buyer characteristic relevant to the paper’s search and assignment decisions. The market has a finite set of opportunities \(X\), drawn independently with rational probabilities \(p_x\). Each search costs \(\kappa(M)>0\). An initial nonempty set of opportunities has already been found.
The question is to compute an optimal policy and its expected value. Its state records, for every type \(t\), that type’s best known opportunity \(r_t\). In the B2C setting, an opportunity can serve any demand, so all mass of type \(t\) can receive its best-known offer. Stopping yields \(M\sum_{t\in T}\mu_t U_t(r_t)\); continuing pays \(\kappa(M)\), draws another opportunity, and updates the records. A solution gives the stop-or-continue choice at every reachable state. From-scratch search follows by drawing the first opportunity and applying the continuation policy. This keeps the paper’s B2C reuse assumption and search decision intact: the population is continuous, while the opportunity process remains finite and discrete.
The intended regime is a large group-buying market for a product that sellers can supply at scale. For example, many buyers may share one of a small number of exact preference profiles over price, delivery, warranty, and product attributes. Then \(M\) can be very large while the number \(\tau=|T|\) of distinct supported types is moderate. Agents of one type are interchangeable for every purpose in the model; their mass records how much of the coalition they represent. At integer \(M=N\), with shares corresponding to the counts of each type, this recovers the paper’s repeated-type discrete case. Allowing rational masses and population scale is the high-multiplicity relaxation. The authors should recognize it as their problem: it preserves their representative agent, opportunity distribution, utility aggregation, search cost, and B2C assignment rule.
For this finite-offer version, I expect tractability when \(\tau\) is fixed. There are at most \((|X|+1)^\tau\) best-offer states, so an explicit-state optimal-stopping computation can find the exact policy without enumerating the \(M\) individuals. The masses affect the payoff arithmetic, not the number of states. This suggests an XP-style bound in \(\tau\), not a claim of polynomial time when \(\tau\) is part of the input. Natural next questions are whether the state structure yields a better dependence on \(\tau\), and what happens when the offer domain or its distribution is given compactly rather than as an explicit finite set. A C2C mirror would also need to model the paper’s one-item-per-seller constraint alongside the buyer mass.
The strongest point is that the repeated-type regime is plausible for large B2C coalitions, and the paper already studies precisely the state-dependent strategy that the mirror asks to compute. The weakness is equally real: Theorem 2 guarantees termination and optimality, not efficiency, so the anchor itself does not promise a complexity gain. The finite-state bound above is a consequence for the stated mirror, not a result proved by the authors. And because this paper supplies no named hardness anchor, this case cannot test the programme’s central question of whether a discrete hardness result dissolves under continuization.
The only serious anchor raised is Theorem 2. It is a real computational result: it proves that Algorithm 1 terminates and returns an optimal B2C search strategy. I would not argue that the paper has no computational anchor. The skeptical point is narrower: the proposed finite-support mirror appears to preserve the theorem’s entire state graph and change only its payoff weights.
In B2C, if \(n_t\) buyers have the same complete utility function \(U_t\), their best-known offers are always identical. The discrete state can therefore store one offer \(r_t\) per type, with stopping value \(\sum_t n_t U_t(r_t)\). The proposed continuous value, \(M\sum_t \mu_t U_t(r_t)\), is exactly the same when \(n_t=M\mu_t\). There are at most \((|X|+1)^\tau\) states either way. Rational masses change the arithmetic and the ratio between aggregate benefit and search cost; they do not create new allocation choices or a new optimization structure. Theorem 1 and Proposition 1 look similarly direct to lift: replace repeated individual utilities with weighted type utilities.
That makes the proposed mirror a plausible high-multiplicity formulation, but a weak candidate for a *distinctive* continuous-computation result. The paper already gives the optimal-policy algorithm; the mirror’s immediate payoff is to analyze its dependence on the number of exact types and on mass-weighted costs. A richer model with a genuinely continuous distribution of buyer utilities would avoid the finite-state reduction, but arbitrary utility functions and densities do not have a finite binary encoding. Finite parametric approximations return to the weighted finite-type model. This is a real modeling fork, though it does not show that the finite-type question is unworthy.
I also cannot rule out a stronger C2C mirror. If seller supply scales with population, the search problem could become one of assigning mass across types and discovered offers. The programme explicitly allows that kind of co-modification. It may yield a worthwhile stochastic matching problem, but its value depends on specifying supply and search-cost scaling, and it moves beyond the finite-state B2C anchor.
So the negative case is weak at its central point. Exact repeated buyer types are a sensible regime, and Theorem 2 supplies a mirrorable result. The best argument against is that the proposed B2C mirror looks like a weighted restatement of the existing finite-state computation, with no evident new continuous-optimization challenge. That may be too small a contribution, but it does not establish that no worthwhile mirror exists.
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.