{"schema_version":1,"experiment_id":"eoa_inverse_innovation_exp05_complete_proposal_portfolio20_20260803","cell_id":"computability_boundary_mapping__economics_finance","arm":"COMPLETE_PROPOSAL_PORTFOLIO","candidate_id":"cbm-ef-proof-carrying-auction-admission-002","proposal_index":2,"version":0,"title":"Proof-Carrying Admission for Executable Auction Rules","problem":"A digital marketplace permits executable allocation-and-payment rules and asks an automated reviewer to decide, for every submitted rule, whether execution terminates and truthful reporting is a dominant strategy for every admissible bidder type, report profile, and internal state. The host language may admit unbounded loops, recursion, persistent state, or external calls, while the type space, utility model, randomization semantics, and universal quantifiers remain partly implicit. Sampled bid simulations and unsuccessful proof searches can therefore be mistaken for class-wide verification or refutation.","actors":["Marketplace mechanism designers","Sellers or buyers submitting bids","Marketplace mechanism-admission board","Marketplace economists","Formal-verification engineers","Operations staff responsible for auction execution","Independent proof reviewer"],"observable_state":"A proposed allocation rule behaves as intended on sampled bid profiles, but the truthfulness prover times out or fails to find a proof. The admission workflow nevertheless requests a Boolean “incentive-compatible” verdict, encouraging a timeout to be recorded either as failure or as an analyst-approved pass. A proof checker may also be described as though it can generate a proof for every truthful mechanism.","consequence":"An uncertified rule can be deployed with exploitable reporting incentives or nonterminating executions, while a rule that may satisfy the declared property can be rejected merely because proof search did not succeed.","affected_objective":"Model-relative assurance that admitted auction rules terminate and satisfy their declared incentive property without converting missing proofs, finite tests, or timeouts into semantic verdicts.","intervention":"Replace universal verdict generation with a proof-carrying auction-admission protocol. Freeze a versioned specification of the executable rule language, admissible reports and types, utility function, allocation feasibility, payment semantics, randomization treatment, external capabilities, and the exact TOTAL_AND_TRUTHFUL property. For the unrestricted language, construct and independently check a proposed reduction that maps a candidate computation to an auction rule that becomes total and follows a fixed truthful allocation rule if and only if the source computation halts; until the mapping and semantic correspondence pass review, record the unrestricted status as unresolved. Permit a designer to submit a rule with a finite machine-checkable certificate establishing TOTAL_AND_TRUTHFUL under the frozen model. A small terminating checker validates supplied certificates but is not represented as a complete proof generator. In parallel, fairly search for proof candidates and finite counterexamples; a verified profitable misreport or nonterminating bounded trace refutes the submitted universal claim, while exhaustion of a declared search budget returns UNKNOWN. Preserve CERTIFIED, REFUTED, UNKNOWN, OUT_OF_MODEL, INVALID_CERTIFICATE, and SYSTEM_FAILURE as distinct outputs. Certification establishes eligibility for ordinary admission review, not automatic deployment, and every guarantee is superseded when the language, economic model, or checker changes.","structural_mapping":[{"archetype_element":"Unsupported total-exact automation goal","domain_realization":"The marketplace asks for a terminating truthfulness-and-termination verdict for every executable allocation-and-payment program."},{"archetype_element":"Problem-class and model specification","domain_realization":"The rule language, bidder types, reports, utilities, payments, randomness, state, external calls, and universal property are frozen before classification."},{"archetype_element":"Computability impossibility test","domain_realization":"A checked computation-to-auction mapping tests whether deciding TOTAL_AND_TRUTHFUL for unrestricted programs would decide a known undecidable source problem."},{"archetype_element":"Weaker constructive interface","domain_realization":"The system checks supplied certificates rather than promising to discover a proof or Boolean verdict for every rule."},{"archetype_element":"One-sided recognition and counterevidence","domain_realization":"A valid proof certifies the declared property, and a valid profitable-misreport or termination witness refutes it; unsuccessful bounded search remains UNKNOWN."},{"archetype_element":"Status honesty","domain_realization":"Certified, refuted, unknown, out-of-model, invalid-certificate, and system-failure states remain distinct through admission review."},{"archetype_element":"Version-linked reclassification","domain_realization":"Changes to rule semantics, bidder assumptions, proof calculus, or checker kernel invalidate the old guarantee and trigger a new decision record."}],"mechanism_mapping":[{"mechanism_slug":"halting_problem_reduction","role":"Tests the unrestricted verifier requirement by encoding a source computation into an executable auction rule whose total-and-truthful status reveals whether the source halts.","counterfactual_removal":"Without a checked reduction, failure to build a universal verifier would remain implementation evidence rather than an impossibility result."},{"mechanism_slug":"proof_checking","role":"Re-verifies each submitted totality-and-truthfulness certificate against a small rule set and exposes every premise about bidder utilities and execution semantics.","counterfactual_removal":"Without independent certificate checking, admission would depend on trusting the designer, proof-search engine, or an unchecked informal argument."},{"mechanism_slug":"theorem_prover_guided_search","role":"Searches for certificates or countermodels while retaining the checked artifact on success and the exact open proof obligation on failure.","counterfactual_removal":"Without artifact-producing search, successful automated reasoning could become an opaque assertion, and unsuccessful search would provide no inspectable uncertainty residue."},{"mechanism_slug":"enumeration_and_dovetailing","role":"Fairly interleaves candidate proof searches and counterexample executions so that one nonterminating branch cannot indefinitely starve every other candidate.","counterfactual_removal":"Without fair scheduling, an early divergent proof or execution attempt could prevent discovery of an available certificate or finite counterexample."},{"mechanism_slug":"semi_decision_with_explicit_unknown","role":"Wraps the one-sided searches in a declared resource bound, returning a checked result when found and UNKNOWN when the bound is exhausted.","counterfactual_removal":"Without an explicit UNKNOWN protocol, the operational need to terminate would pressure the system to reinterpret a timeout as truthful or not truthful."},{"mechanism_slug":"proof_by_counterexample","role":"Uses one well-formed type and report profile with a verified profitable deviation, or one in-scope execution violating termination, to refute the corresponding universal claim.","counterfactual_removal":"Without counterexample validation, adverse simulations would remain suggestive tests rather than decisive refutations of the declared universal property."},{"mechanism_slug":"computability_boundary_decision_record","role":"Records the unrestricted classification, certificate guarantee, formal economic assumptions, checker version, open residue, and recheck triggers.","counterfactual_removal":"Without the record, a certificate could remain authoritative after changes to bidder assumptions, rule semantics, or the trusted checker kernel."}],"causal_chain":["Formalizing the executable language and economic model separates the mathematical truthfulness claim from informal expectations about bidder behavior.","A valid, independently checked reduction can retire the requirement for one total exact verifier over the matching unrestricted program class; a defective or mismatched reduction leaves that classification unresolved.","Proof-carrying submission shifts the required terminating computation from universal proof discovery to checking a finite supplied certificate.","A verified certificate yields CERTIFIED only for the frozen model, while a verified profitable deviation or termination failure yields REFUTED for the submitted universal claim.","Fair proof and counterexample searches can discover evidence without allowing one divergent branch to block all others.","The bounded operational wrapper returns UNKNOWN when neither side produces checked evidence, preserving termination without fabricating a verdict.","The admission board considers certified rules through its ordinary economic, legal, and operational review while UNKNOWN and OUT_OF_MODEL rules receive no automated clearance or semantic rejection.","Versioned assumptions and checker identifiers cause later model or language changes to trigger re-verification before a certificate is reused."],"baseline":"Evaluation baseline: economists and engineers inspect rule code, simulate selected valuation and report profiles, run an automated prover for a fixed period, and enter a Boolean incentive-compatibility assessment. Passing examples are evidence about those examples, and an unsuccessful proof search is handled through analyst judgment rather than a formally distinct unknown state.","nearest_rivals":["Restrict the marketplace to a fixed catalog of preapproved auction formats.","Discretize every bidder type and report space, then exhaustively evaluate every finite deviation.","Use strategic-agent simulations or red-team bidders to search for profitable deviations without issuing class-wide certificates.","Rely entirely on manual mechanism-design review and contractual attestations from rule authors.","Deploy experimental rules with monitoring, transaction limits, and ex post compensation instead of pre-admission verification.","Require source-code termination checks while assessing incentive compatibility only through sampled economic scenarios."],"remaining_contrastive_claim":"The intervention makes certificate checking, rather than universal proof generation, the total automated service. Fixed auction catalogs and finite discretization regain decidability by narrowing expressiveness; simulations and manual review provide incomplete evidence; operational limits contain consequences after uncertainty remains. The proposed protocol instead admits an expressive rule only when it carries checked model-relative evidence, accepts checked counterexamples as refutations, and preserves all other cases as UNKNOWN or OUT_OF_MODEL.","authority_safety":{"decision_authority":"The marketplace mechanism-admission board retains authority to approve, reject, suspend, or retire auction rules. The formal-verification team may issue model-relative certificate statuses, and an independent reviewer must approve the proof kernel, reduction, and specification correspondence before those statuses inform admission.","authorized_first_step":"The head of marketplace economics may authorize an offline pilot using synthetic rules, synthetic bidder types, and a sandboxed checker that has no connection to production auctions, bidder records, payment systems, or rule deployment controls.","excluded_actions":["Deploy, approve, reject, suspend, or retire a production auction rule automatically","Execute bids, allocate goods, calculate live payments, or transfer funds","Treat UNKNOWN, INVALID_CERTIFICATE, OUT_OF_MODEL, timeout, or SYSTEM_FAILURE as REFUTED or CERTIFIED","Represent a model-relative truthfulness certificate as proof of bidders' actual preferences, beliefs, or conduct","Run untrusted submitted rules outside a resource-isolated sandbox","Reuse certificates after changes to the rule language, utility model, proof calculus, or checker without re-verification","Access confidential production bids or bidder identities during the offline pilot"],"halt_rollback":"Halt the pilot if the checker accepts a deliberately invalid proof, fails to terminate on any syntactically valid certificate, a verified counterexample contradicts an accepted certificate under the same model version, formal and executable rule semantics diverge, or result labels are collapsed downstream. Quarantine the affected artifacts, withdraw the pilot certificate labels, and return every evaluated rule to an unassessed manual-review state; the offline pilot performs no market action requiring transactional reversal."},"negative_tests":{"strongest_counterevidence":"The strongest counterevidence would be a checked specification showing that every admissible auction rule is already written in a strongly normalizing language, operates over finite enforceable type and report domains, and has a total exact procedure for checking the declared incentive property. The remaining question would then concern computational cost rather than a missing computability boundary.","problem_falsifier":"The problem is falsified if the admission system accepts no open-ended executable rules, all allowed state and report spaces are mechanically finite, every rule has a static execution bound, and the workflow already preserves unsuccessful proof search as UNKNOWN rather than a truthfulness verdict.","intervention_falsifier":"The intervention is falsified if the checker does not terminate for every certificate in its declared syntax, accepts any certificate contradicted by a checked in-model counterexample, or cannot establish correspondence between certified formal rules and executed allocation-and-payment behavior. Its bounded pilot also fails if every conforming submission remains UNKNOWN because the certificate language cannot express the required economic arguments.","risks":["The declared utility and information model may not represent actual bidder incentives.","A flaw in the trusted checker kernel could certify an invalid proof.","A certificate may prove the correct theorem about a formal rule that differs from the deployed implementation.","Proof obligations may favor simple mechanisms and turn UNKNOWN into an unintended barrier to admissible expressive rules.","Submitters may hide economically relevant behavior in interfaces declared outside the model.","Automated proof search may consume excessive resources or be used for denial of service.","A finite counterexample may be valid syntactically but depend on an economically inadmissible type unless scope checking is exact.","Decision-makers may treat CERTIFIED as a complete market-quality endorsement rather than one model-relative property.","Certificates can become stale when payment, randomization, bidder, or language assumptions change."]},"next_evidence_step":"Run one offline exercise on six synthetic executable allocation-and-payment rules, including planted total-and-truthful cases, a profitable-misreport case, a divergent execution, a malformed certificate, and one rule using unrestricted syntax. Freeze a model with at most three bidders and five declared values for bounded counterexample testing, while retaining one unrestricted-language specimen for the proposed reduction. Produce the exact TOTAL_AND_TRUTHFUL statement, the computation-to-auction mapping, a minimal certificate grammar and terminating checker, one checked positive certificate, one checked counterexample, and a decision record containing every output status. An independent reviewer must verify reduction direction, semantic preservation, checker termination, certificate correctness, and label propagation. No production rule, bid, payment, or admission decision enters the exercise.","prior_art_status":"UNSEARCHED","diversity_from_prior_proposals":"Proposal 1 addressed clearinghouse collateral solvency for programmable derivative contracts and intervened by enforcing a bounded contract-language fragment, applying exhaustive or sound abstract state analysis, and routing listing results by guarantee. Proposal 2 addresses termination and strategic truthfulness of executable auction mechanisms and intervenes through proof-carrying admission, a terminating certificate checker, and one-sided proof-versus-counterexample search without making fragment restriction its primary guarantee. Its economic property, decision institution, evidence artifact, fallback behavior, and causal path are different, and a marketplace can adopt it independently of any programmable-derivative or clearinghouse solvency system.","revision_record":{"parent_version":null,"progress_targets_addressed":[],"conceptual_changes":[],"operational_changes":[],"evidence_changes":[],"claim_changes":[]}}