| paper | d4-conf-sagt-2015-0026 |
| 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: Exact mass-weighted fitting with succinct rational valuations is polynomial-time solvable; its threshold decision problem belongs to \(\mathsf{P}\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3.2
statement extracted from the paper’s text layer
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.
The population consists of bidders grouped by identical complete price–bundle histories, with mass \(\mu_h\) per type. Each type has its own tolerance and virtual valuation over the unchanged indivisible bundles \(\{0,1\}^n\); the objective is the mass-weighted average tolerance.
The mirror covers optimal additive rationality slack and minimum individually rational fits for repeated bidder-history types. It leaves the paper’s upper-bound maximum fits, finite-\(k\) bidding rules, and other auction-rule applications without a population analysis.
The strongest case I believe is a large auction with many bidders who fall into a modest number of bidding-history types. Here, “continuization” means making the bidder population continuous. The items remain indivisible, bundles remain in \(\{0,1\}^n\), and rounds remain discrete.
A type \(h\) is a bidder’s complete input to the paper’s fitting problem: the same item set and the same sequence of price–bundle observations \(((p_{h,r},x_{h,r}))_{r=1}^{T_h}\). Include any budget or valuation-bound data if the chosen variant uses it. Let \(\mu_h\) be the fraction of bidders of type \(h\), with \(\sum_h\mu_h=1\), and let \(\tau\) be the number of types. A plausible regime is a large procurement or platform auction with thousands or more small suppliers, but only tens or hundreds of standardized bid histories, so \(N\gg\tau\). Each type’s action is a virtual valuation function; its mass weights that type’s contribution to population measures.
My lead anchor is Theorem 3.2, proved in this paper. It says that an \(\epsilon\)-approximate valuation function rationalizing the bidding behavior exists if and only if the bidding graph has minimum mean cycle length at least \(-\epsilon\). Equivalently, if \(\lambda(G_h)\) is the minimum mean cycle length for type \(h\)’s graph, its best additive guarantee is \(\epsilon_h^*=-\lambda(G_h)\). The theorem and its proof supply a constructive route through minimum-mean-cycle and shortest-path computations.
The corresponding continuous problem is Population Minimum Rationality Slack. Given the rational masses \((\mu_h)\) and each type’s price–bundle history, choose a tolerance \(\epsilon_h\) and a virtual valuation \(\hat v_h:\{0,1\}^n\to\mathbb R\) 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 type \(h\), round \(r\), and bundle \(y\in\{0,1\}^n\). Minimize the population-average tolerance \(\sum_h\mu_h\epsilon_h\). A solution returns the optimal tolerances and fitting valuations, or equivalent succinct certificates. The optimum is \(\sum_h\mu_h(-\lambda(G_h))\). I would expect this to be tractable: run the paper’s computation on each type’s graph and combine the answers using the rational masses. Its input and running time can be stated in the number of items \(n\), support size \(\tau\), total number of observations \(R=\sum_h T_h\), and input bit length \(L\), rather than the total number of bidders.
A second, closely related anchor is Theorem 3.3, also proved in this paper. It says that the minimum individually rational, optimally approximate virtual valuation function exists and can be found in polynomial time. “Minimum” here means that at every observed bundle its value is no greater than the value of any other individually rational virtual valuation meeting the same optimal approximation guarantee. The theorem is about the fitted values of bundles in the bidding history; it does not establish a minimum value for every unobserved bundle.
That gives Population Minimum Individually Rational Fit: use the same continuous society, and for each type find an individually rational virtual valuation satisfying its optimal tolerance \(\epsilon_h^*=-\lambda(G_h)\). Among feasible valuations, return the coordinatewise minimum values on that type’s observed bundles. These per-type minima can then be weighted by \(\mu_h\) when assessing virtual value for populations of reported alternatives. I would also expect this problem to be tractable by applying the paper’s construction to each type. It follows from the lead problem but adds a distinct output: the least individually rational fitted values, rather than just the best rationality guarantee.
Theorem 3.2 is my strongest anchor because it gives an exact numerical characterization of the fitting question and a constructive computation. Theorem 3.3 is useful support for a population-level interpretation: in an auction with many repeated bidder types, the least fitted values can feed into aggregate analyses of reported alternatives. The authors should recognize the connection: Section 4.3 explicitly discusses applying relaxed revealed-preference rules to each bidder to obtain overall auction welfare guarantees.
The scope is deliberately narrow. These mirrors lift the paper’s results about fitting observed bidder histories to a population with repeated histories. They do not continuize bundles, bids, prices, time, or the axioms of revealed preference. The paper offers no named hardness result to anchor on, so I would not present this as a case where continuous mass dissolves discrete hardness. Both problems are Class A candidates, extending the paper’s polynomial methods to a high-multiplicity population description. Further questions include whether to minimize average tolerance, worst-type tolerance, or a tolerance for a specified fraction of the population, and how the fitted values support welfare claims when allocations are drawn from reported bundles.
The weakest point is that this population version largely applies a polynomial single-bidder result once per type; the continuum may compress the input and give a natural aggregate measure, but it does not produce a new tractability gain. The scenario also needs an auction with many bidders and genuinely repeated, complete bidding histories; it is a poor fit for auctions with only a handful of bidders. The paper’s own motivation still supports the mirror: it already treats bidder-level fitting as something that can inform auction-wide guarantees, and replacing many repeated bidders with their type masses is a direct population-level formulation of that use.
The best case against these mirrors is that the paper’s computational object is one bidder’s history over time. The vertices and cycles in its bidding graph connect bundles that the same bidder chose or could have chosen at different prices. A population distribution over histories adds an outer layer; it does not change what the graph computes.
For Theorem 3.2, the proposed population average is well-defined, but each type’s minimum rationality slack can be computed independently. The masses enter only as weights in \(\sum_h \mu_h\epsilon_h\); they affect the aggregate report, not the constraints or the cycle computation. A common tolerance across bidders would be more like the auction rule in Section 4, but its threshold is determined by the worst type; allowing a specified share of exceptions leads to a quantile of the independently computed slacks. Either way, the population layer supplies a summary statistic. To create stronger coupling, one would need to add an allocation or mechanism-design objective that this theorem does not study. Requiring one shared valuation function would create coupling too, but would generally misdescribe bidders with different preferences.
Theorem 3.3 has a related limitation. Its minimum is defined on each bidder’s observed bundles, not as a common valuation function for a heterogeneous population or as a complete valuation table for every possible allocation. Weighting those fitted values can summarize reported alternatives, but it does not by itself determine a population allocation or its welfare. Individual rationality also applies bidder by bidder; an aggregate value cannot compensate for a particular bidder’s failure of that condition. A version that couples these fits through feasible allocations and supply could be interesting, but it would need an allocation model, supply assumptions and a welfare question. Those additions would carry much of the new problem.
The proposed high-multiplicity regime is possible, though narrow. In a shared-price auction, many standardized bidders might make the same choices each round. But an exact type here includes the entire observed trajectory, and trajectories are endogenous to the auction. If types instead mean underlying preferences, budgets and other stable bidder attributes, the paper’s fitting results still require the observed histories those attributes generate. Replicating identical histories can reduce the input description, but it does not turn the within-bidder cycle problem into a population computation. The paper’s Section 4.3 already sketches the natural aggregate connection: apply bidder-level fits and derive auction-wide welfare guarantees. The continuous version looks like a population-level restatement of that aggregation unless a further collective decision is specified.
This case cannot honestly establish that no worthwhile mirror exists. Theorem 3.2 and Theorem 3.3 are named computational results, and a distribution over repeated bidder types is coherent. Moreover, Section 4.3 gives the authors a clear reason to recognize aggregate fits as relevant. The negative argument is therefore strongest as a priority objection: the proposed mirrors add little computational structure beyond combining existing per-bidder computations. It is weaker as a claim that no meaningful continuous-population question can be formulated.
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.