| paper | d4-conf-atal-2007-0256 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: The decision problem is in \(\mathrm P\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Lemma 1
statement extracted from the paper’s text layer
Given a finite good set \(G\), supplier types \(T\) with rational masses \(\mu_t\) summing to \(1\), each type’s finite XOR menu \(\mathcal B_t\) of priced packages \(D_b=\{(I_{bk},O_{bk})\}_k\), rational per-capita initial and required inventories \(u_{\mathrm{in}},u_{\mathrm{out}}\), and an acyclic network of all offered transformations, choose masses \(x_{tb}\ge 0\) to maximize \(\sum_{t,b}p_bx_{tb}\). Require \(\sum_{b\in\mathcal B_t}x_{tb}\le\mu_t\) for each type and \(u_{\mathrm{in}}(g)+\sum_{t,b}x_{tb}\sum_k(O_{bk}(g)-I_{bk}(g))\ge u_{\mathrm{out}}(g)\) for each good \(g\); every accepted package’s transformations must admit a finite execution schedule on their assigned mass.
A continuum of suppliers grouped by complete bid-menu type, with mass \(\mu_t\) per type. Decision variable \(x_{tb}\) is the mass of type \(t\) assigned bid \(b\); maximize revenue subject to each type’s XOR capacity, per-capita inventory balances, and package execution. Acyclicity makes the balance constraints sufficient for scheduling the transformations in topological order.
Covers MMUCA winner determination for acyclic supply-chain networks with repeated supplier types and XOR bid menus; leaves cyclic reachability and the paper’s broader structural and behavioural Petri-net analyses aside.
The best mirror is a continuous-population winner determination problem for acyclic supply chains. The population is the continuum: a type is a supplier type with a fixed menu of bids, including its transformation packages and prices, and \(\mu_t\) is that type’s share of all bidders. In a market with many suppliers using standardized production recipes and contracts, the number of bidders can be enormous while the number of distinct offer types remains modest.
This fits the paper’s setting closely. It studies an auctioneer choosing bids to accept, subject to the requirement that the offered transformations can actually be carried out in sequence using available goods. In the mirror, \(x_{tb}\) is the mass of type-\(t\) bidders assigned bid \(b\). Each individual still receives an integral assignment; fractional \(x_{tb}\) describes a fraction of a large, homogeneous population. Goods inventories and required end stocks are expressed per capita so they scale with that population.
The paper has no numbered theorem classifying MMUCA winner determination as polynomial-time solvable or NP-hard. Its named computational anchor is Lemma 1, proved in this paper. Restated in full: given a weighted transition Petri net \(S\), initial marking \(M_0\), transition-cost vector \(c\), and endpoint constraints \(M_d\sim h\), the integer program
\[
\max x^\top c^\top
\quad\text{subject to}\quad
A^\top x+M_0\sim h
\]
characterizes the optimal firing-count vectors for the Constrained Maximum Weight Occurrence Sequence Problem if and only if the state equation \(A^\top x+M_0\) represents all markings reachable from \(M_0\). Here \(A\) is the transition-place incidence matrix, \(x\) is a nonnegative integer firing-count vector, and the endpoint constraints are imposed coordinatewise. The lemma is a formulation result, not a general tractability claim: its usefulness depends on the net class having that reachability property. Section 4 then maps MMUCA winner determination into this Petri-net problem; the paper describes that mapping and its benefits, though it does not state it as a numbered theorem.
The mirror question is Acyclic Continuous MMUCA Winner Determination:
Given a finite good set \(G\), a finite support of bidder types \(T\) with rational masses \(\mu_t\) summing to \(1\), each type’s finite XOR menu \(\mathcal B_t\), per-capita initial and required inventories \(u_{\mathrm{in}},u_{\mathrm{out}}\), and rational per-bid prices, choose the mass \(x_{tb}\ge 0\) assigned to each bid to maximize auctioneer revenue. The constraints include
\[
\sum_{b\in\mathcal B_t}x_{tb}\le \mu_t
\]
for each type. A bid may specify a package \(D_b\) of transformations \((I_{bk},O_{bk})\). Every accepted portion of the bidder population must have its full package implemented, so each transformation in \(D_b\) is executed on mass \(x_{tb}\). A solution must also give a finite execution schedule: before executing mass \(\delta\) of a transformation, the auctioneer must hold at least \(\delta I_{bk}\); execution updates inventory by \(\delta(O_{bk}-I_{bk})\); and the final inventory must cover \(u_{\mathrm{out}}\). The bid menu, transformation package, price, and quantities are all part of the bidder type.
For an acyclic WTPN, this mirror has a strong tractability case. Introduce one variable \(x_{tb}\) per type and bid. Maximize \(\sum_{t,b}p_bx_{tb}\), subject to the type-mass bounds and the final per-good balance constraints
\[
u_{\mathrm{in}}(g)+\sum_{t,b}x_{tb}
\sum_{k\in D_b}\bigl(O_{bk}(g)-I_{bk}(g)\bigr)
\ge u_{\mathrm{out}}(g).
\]
A topological ordering of the acyclic transformation network supplies an execution order: producers of a good precede its consumers, and the balance constraints ensure enough total stock is available. The continuous winner determination problem is therefore an LP of size polynomial in the listed types, bids, goods, and input bit length. This is a Class A expectation for the specified regime. Its computational question is the auctioneer’s underlying choice of accepted supplier mass and feasible production sequence; the LP is the method for solving it.
The scope is deliberately the paper’s winner determination problem for acyclic supply-chain networks. It does not continuize only goods, outcomes, or the Petri-net marking while leaving the bidder population finite. It also does not cover the paper’s broader goal of analyzing structural and behavioural properties of arbitrary Petri nets. Cyclic networks, richer free-disposal semantics, and their reachability behaviour are natural next questions; the lemma’s state-equation condition makes clear why those cases need separate treatment. A further useful question is how an optimal mass allocation translates back to a finite auction with \(n\) bidders: when can it be rounded with bounded revenue loss while preserving implementability?
The weakest point is the restriction to an acyclic regime with many suppliers sharing exactly the same offer types. That is plausible in repeated marketplaces with standardized recipes and tariffs, and the paper itself motivates supply-chain formation, but it is narrower than arbitrary MMUCAs. If individual prices, recipes, or menus make nearly every bidder a distinct type, the support grows with the population and the high-multiplicity benefit fades. Within the stated regime, though, the mirror preserves the paper’s central question—choosing bids whose transformations can be carried out—and gives its authors a recognizable continuous version to study.
The strongest objection is that Lemma 1 is a poor anchor for this mirror. It says that an integer program over firing counts captures the CMWOSP when the state equation captures reachability. It does not classify winner determination by population size or establish tractability in the number of bidder types. The proposed LP is therefore not a continuous version of that lemma so much as a new, restricted question about winner determination.
Restricting to acyclic networks also removes much of what makes the paper’s Petri-net contribution distinctive: sequencing can be handled by a topological order, and the remaining constraints are ordinary resource balances. The resulting LP looks like a standard fractional procurement and production problem. That makes the mirror narrower and less revealing about the reachability questions the paper studies.
But this does not defeat the best version of the mirror. A market with many suppliers sharing complete, standardized bid menus is a coherent high-multiplicity setting. The mass constraint \(\sum_b x_{tb}\le\mu_t\) captures each supplier’s XOR choice, and executing each transformation in a package on mass \(x_{tb}\) preserves the package semantics. For an acyclic network, a topological order gives an execution schedule, so the endpoint balance constraints suffice. The relaxation is meaningful even though it is simple.
So the negative case is weak. Lemma 1 does not itself supply the proposed population result, and the acyclic mirror strips away much of the paper’s Petri-net machinery. Yet the winner-determination mirror remains well-posed and recognizable; the paper’s scope and the mirror’s simplicity are not sound reasons to reject it. I cannot honestly defend the universal claim that no worthwhile continuous 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.