PaperlayerView exact revision on arXiv

Source-linked AI summary

Opening the Strategic Pandora Box: Conditional Transaction Mechanisms

Yonatan Sompolinsky, Ori Newman, Xintong Wang, David Parkes

arXiv:2609.12197v1cs.GT

TL;DR

Conditional transaction engines need to prioritize condition reads and the next write even though each read delays execution. This paper models each invocation as Strategic Pandora, proposes RW and RWSP with dynamic NBR benchmarks, and proves a constant-fraction revenue guarantee for qualifying pure equilibria under stated conditions.

  • Problem

    CTEs must allocate condition reads and the next transaction slot, while each read delays the eventual write and standard price- or time-priority policies cannot rank composite rules.

    Source: §1 · p. 2

  • Method

    The paper models one invocation as discounted Pandora's box and proposes RW and RWSP, assessing revenue with dynamic No-Betting Revenue.

    Source: §1.4 · p. 4

  • Results

    Under the stated competition and equilibrium conditions, every qualifying pure equilibrium of RW and RWSP earns a constant fraction of its corresponding dynamic NBR benchmark.

    Source: §1.4 · p. 4

  • Takeaways & Limitations

    A persistent rule can act for an offline user without a new real-time instruction, and users are not charged when outbid for the write.

    Source: §1 · pp. 1–2

    The framework does not guarantee admission, platform liveness, execution, or that a stored value remains current.

    Source: §2.3 · p. 7

Abstract

from arXiv · show

Conditional transaction engines (CTEs) execute conditional instructions for offline users. This paper formalizes the mechanism-design problem within each engine invocation. A conditional transaction mechanism (CTM) decides which pending conditions to evaluate first because each evaluation delays the eventual write. We model this problem as Strategic Pandora, a discounted variant of the Pandora's box model with independent Bernoulli boxes. Agents report privately assessed success probabilities and, in the full model, values for the write action. We propose the reported-Weitzman mechanism (RW) and the reported-values second-price mechanism (RWSP). To compare revenue without a common prior, we introduce dynamic No-Betting Revenue. Under the stated competition and equilibrium conditions, every qualifying pure equilibrium of RW or RWSP earns a constant fraction of its corresponding dynamic NBR benchmark.

1 Introduction

The paper formalizes how a conditional transaction engine should allocate condition reads and the next write when users may be offline and each read delays execution. It models the one-invocation problem as Strategic Pandora and introduces prior-free revenue benchmarks and mechanisms.

1 Introduction

  • CTEs let users submit IFTTT rules in advance, targeting situations where 24/7 monitoring is unsustainable or servers lose access under stress; they do not address platform-level failure.A selected rule can act on the user's behalf without a new real-time instruction.Source: §1 · pp. 1–2

1.1 Existing approaches

  • Existing keepers and listener services can trigger submissions but sit outside final sequencing; CTEs instead prioritize reads and writes within the engine.The cited event-based systems treat triggered transactions as non-mandatory sequencer inputs.Source: §1.1 · p. 3

1.2 The one-shot allocation problem

  • Each condition read consumes computation and delays the eventual write, so coupling reads to writes can avoid evaluating rules whose writes are outbid.The one-shot problem maps to discounted Pandora's box with independent Bernoulli boxes; the paper analyzes a fixed point in time, not the broader evolving process.Source: §1.2 · p. 3
  • Agents report rule-success probabilities, and in the full model also write values; RW and RWSP adapt Weitzman's solution to known-value and reported-value settings.The framework is prior-free and does not aim to learn the underlying probability parameter.Source: §1.2 · pp. 3–4

1.3 Prior-free mechanism design

  • With heterogeneous beliefs, summed subjective utilities can count transfers between agents as value; NBR and dynamic NBR define admissibility to avoid revenue inflated by betting.Dynamic NBR extends the criterion to sequential decisions.Source: §1.3 · p. 4

1.5 Conditional Transaction Engines

  • A CTM processes active rules and bids for one invocation, while the broader CTE runs successive CTM instances; this paper assumes fixed inputs and sets the operator aside.Protocols for bid submission and revision, including safeguards against sniping or information free-riding, are left to the broader CTE design.Source: §1.4 · p. 4, §1.5 · pp. 4–5

1.4 Our contributions

  • Under the stated competition and equilibrium conditions, every qualifying pure equilibrium of RW and RWSP earns a constant fraction of its corresponding dynamic NBR benchmark.The mechanisms address the known-box-values and reported-values models, respectively.Source: §1.4 · p. 4

2 Strategic Pandora and RW

The section models conditional-rule evaluation as discounted search over independent Bernoulli boxes, then uses reported probabilities and values to allocate reads, writes, and payments.

2.1 Discounted Pandora with Bernoulli boxes

  • Each of M independent boxes succeeds with probability p_j and yields v_j; inspection is free, but position t discounts value by δ^(t−1).Search stops at the first success.Source: §2.1 · p. 5
  • Ordering boxes by weakly decreasing discounted Weitzman index z_j maximizes value among policies that stop at the first success.The index is z(p, v) = pv/(1 − δ + δp).Source: §2.1 · p. 5

2.2 Agents and reports

  • Agents privately report box success probabilities; in the known-values model values are public, while the reported-values model selects reader and writer roles separately.True beliefs are interior and independent across boxes.Source: §2.2 · p. 5

2.3 The two mechanisms

  • RW orders boxes using the highest probability reports and charges each selected reader its box’s discounted Weitzman objective contribution up front.Revenue is collected before inspection, so realized successes and failures do not change it.Source: §2.3 · p. 6
  • In the two-box RW example, A is inspected first and total up-front revenue is 7.16 in every outcome, even when B is never reached.The example uses v_A = 10, v_B = 6, δ = 0.9, and reports 0.5 and 0.8; it does not assume equilibrium.Source: §2.3 · pp. 6–7
  • RWSP selects the highest probability reporter as reader and the highest value reporter as writer, with the second-highest value report setting the success transfer and index value.The reader’s up-front payment uses that reader’s reports about previously inspected boxes.Source: §2.3 · pp. 6–7

3 No-Betting Pareto Dominance, No-Betting Revenue, and Dynamic No-Betting Revenue

The section defines revenue benchmarks that remain meaningful under heterogeneous beliefs: NBR restricts admissible revenue, and dynamic NBR extends the certificate to sequential decisions.

3.1 Example: revenue without allocated value

  • Own-belief individual rationality alone permits retained revenue 2Λ for every Λ > 0 despite allocating no value, so it cannot provide a meaningful benchmark.The example’s transfers cancel under a common belief, motivating a requirement that revenue be supported by allocated value.Source: §3.1 · p. 8, §3 · p. 8

3.2 NBR: revenue comparison for a single decision

  • NBR-admissible outcomes have deterministic revenue, satisfy weak own-belief individual rationality, and meet an aggregate no-action certificate that bounds revenue by allocated value.Within the admissible class, outcomes are ranked by deterministic auctioneer revenue.Source: §3.2 · pp. 9–10

3.3 One box: probability player, value player, and auctioneer

  • In the RWSP single-box example, setting y = v and t_r = pv gives the auctioneer positive revenue pv while both agents have zero surplus.The example uses p_r = p_w = p in (0, 1), with the writer paying nothing up front.Source: §3.3 · p. 10

3.4 Dynamic NBR: The Sequential Extension of NBR

  • Dynamic NBR uses range-constrained product priors and permits a different certifying prior at each decision, evaluating all agents’ payoffs and reach probability under that decision’s prior.Its aggregate certificate bounds admissible revenue by certifiable allocated value; transfers that sum to zero at each decision do not increase the certificate’s right-hand side.Source: §3.4 · p. 11
  • With one Bernoulli box, dynamic NBR is equivalent to NBR; with several boxes, the certifying priors are products of marginals in agents’ belief ranges.The multi-box product set is not generally the convex hull of agents’ full joint priors.Source: §3.4 · p. 11

3.5 Why range constraints and the aggregate certificate are needed

  • The range restriction prevents a certificate from assigning success probability to a box every agent believes certain to fail to justify arbitrarily large payments.The aggregate certificate is also necessary: prohibiting up-front transfers to agents alone does not bound benchmark revenue because bets can be reproduced through state-contingent transfers.Source: §3.5 · p. 12

4 Revenue Guarantees for Strategic Pandora

The section compares mechanism revenue with dynamic NBR benchmarks and establishes guarantees for qualifying pure equilibria under specified competition and selection conditions.

4 Revenue Guarantees for Strategic Pandora

  • Under the stated competition and equilibrium conditions, every qualifying pure equilibrium of RW or RWSP earns a constant fraction of its corresponding dynamic NBR benchmark.The guarantees concern the respective admissible mechanism–equilibrium classes.Source: §4 · p. 12

4.1 Known box values

  • For known box values, a finite probability-competition depth independent of the number of boxes suffices for the RW comparison guarantee.The theorem applies to existing pure RW equilibria selected by the favorable membership tie rule; that selection separately ensures dynamic NBR membership.Source: §4.1 · pp. 12–13
  • Without a close probability rival, RW revenue can approach zero relative to the dynamic NBR benchmark even in a two-box instance.As the second-highest belief falls relative to the highest, a voluntary direct mechanism can approach the valuable box’s full value while RW collects only enough to stay ahead of the next belief.Source: §4.1 · p. 13

4.2 Reported values

  • For reported values, RWSP’s comparison requires probability competition, qualified value competition, and pointwise exact writer-allocation Envy-Free; its required probability depth remains independent of box count.Every pure interior-probability equilibrium satisfies dynamic NBR, while the comparison guarantee applies to equilibria meeting the stated competition and envy-free conditions.Source: §4.2 · p. 14

4.3 Scope of the Revenue Guarantees.

  • The guarantees apply only to their stated equilibrium classes; universal pure-equilibrium existence for RW on [0, 1] and existence of an RWSP equilibrium satisfying exact writer-allocation Envy-Free remain open.On the open report domain [0, 1), the paper gives a three-box instance with no pure ε-equilibrium below a fixed positive constant.Source: §4.1 · p. 13, §4.3 · p. 14

5 Related Work

The related work positions the paper across Pandora search, belief-robust revenue comparison, conditional transaction sequencing, and mechanism design for dynamic information and allocation.

Pandora, reservation indices, and learning

  • Weitzman’s reservation-value rule orders Pandora boxes, while later work studies broader objectives, order constraints, correlated boxes, online search, and learned contextual reservation values [Weitzman 1979].This paper uses independent Bernoulli boxes with delay and stops search at the first success; it takes probability reports as given rather than learning distributions.Source: §5 · p. 15

Dynamic mechanism design and information acquisition

  • Unlike dynamic mechanisms evaluated under one known or learned model, this paper compares revenue when agents may disagree about the same process and there is no common prior.It also differs from deliberation auctions: it orders inspections of shared conditions, and under reported values the probability reporter need not be the player valuing the resulting write.Source: §5 · p. 15

Heterogeneous beliefs and no-betting

  • NBR adapts no-betting comparisons by including the auctioneer and allowing weak agent gains; dynamic NBR extends its revenue certificate to sequential decisions.Unlike belief-neutral efficiency classifications that quantify over every belief in a set, this certificate requires one belief in the permitted set.Source: §5 · p. 16

Transaction sequencing and conditional execution

  • Existing exchanges, brokers, hooks, and batch auctions use price, time, or discrete intervals for sequencing, but those rules do not naturally rank composable conditional instructions across markets.The paper therefore focuses on content-agnostic mechanisms using reported condition probability and write value.Source: §5 · p. 16

Appendices

The appendices establish discounted Weitzman ordering and the certificate conditions used to analyze dynamic NBR. Their examples show that unrestricted or overly restrictive certification can misstate what revenue is supportable.

Appendix A: Discounted Pandora Ordering

  • Ordering boxes by weakly decreasing discounted Weitzman index maximizes the objective among policies that stop at the first success.The Bernoulli model awards the execution value of the first successful box, so later inspection only delays that award.Source: Appendix A · p. 20

B.1 Tie rules and equilibrium selection

  • The favorable membership tie rule is a narrower admissible tie-rule selection that rules out negative selected probability positions at selected pure equilibria.Implementation tie rules must depend only on recorded or public inputs; type-dependent rules are used only for analytical equilibrium selection.Source: §B.1 · p. 20

B.2 Exact Strategic Pandora certificates

  • Decision-specific priors establish individual utility inequalities whose sum supplies the aggregate revenue certificate required by the benchmark.For positive revenue, the auctioneer has a strict gain over no action; the aggregate definition also admits zero revenue.Source: §B.2 · p. 20

B.3 Why the Dynamic NBR Restrictions Are Needed

  • Boundary-belief examples illustrate why dynamic NBR constrains certifying beliefs to marginal ranges, allows a different prior at each decision, and requires aggregate certification.The examples lie outside the interior true-belief domain used in the main theorems.Source: §B.3 · p. 21

B.3.1 Unrestricted certifying beliefs

  • Without the range restriction, certification can use an event all agents regard as impossible, making certified revenue unbounded.The range restriction excludes this fictitious source of value.Source: §B.3.1 · p. 21

B.3.2 One prior for the complete outcome

These appendices show why dynamic NBR needs decision-specific certification and aggregate allocation bounds, then establish membership and revenue comparisons under specified conditions. In particular, constant probability competition yields a finite-depth comparison for qualifying pure RW equilibria.

B.3.2 One prior for the complete outcome

  • No single range-constrained product prior certifies the example’s complete sequential outcome, whereas decision-specific priors certify masses matching the mechanism revenue.The obstruction is reach: the reader on B is pessimistic about A and assigns more probability to reaching B.Source: §B.3.2 · p. 22

B.3.3 Prohibiting up-front transfers

  • Prohibiting up-front transfers alone does not bound benchmark revenue; the example retains deterministic revenue 2Λ despite allocating no box value.The aggregate certificate excludes the outcome from dynamic NBR because its aggregate allocation is zero.Source: §B.3.3 · p. 22

B.4 Revenue caps

  • The revenue cap uses aggregate certification and statewise feasibility, with a corresponding bound also established under reported values.Contingent transfers between agents cancel decision by decision in every state, leaving aggregate allocation.Source: §B.4 · pp. 22–23

B.5 Exact membership under known box values

  • For known box values, every RW equilibrium selected by the favorable membership tie rule satisfies the stronger agent-by-agent certificate and has exact dynamic NBR membership.Equilibrium opt-out supplies own-belief individual rationality, and RW revenue is deterministic.Source: §B.5 · p. 23

C.4 Constant depth and the restricted-class comparison

  • Under (PC-K0), a finite probability depth K0(δ), independent of the number of boxes, supports the stated dynamic NBR comparison for favorable-rule pure RW equilibria.The theorem specifies 0 < α ≤ 1 and 0 < δ < 1; the comparison applies at type profiles satisfying (PC-K0).Source: Appendix C · p. 23, §C.4 · p. 25

C.1 Two bounds; C.2 The position inequality

  • The appendix’s two bounds support the position inequality used to compare equilibrium revenue with top reported indices.The position argument considers agents among the largest Zi values who do not hold reader roles in the first L positions.Source: §C.2 · p. 24

C.3 Using constant probability competition

  • Constant probability competition supplies multiple agents with high Zi on a top-index box, which is used to obtain the revenue bound.The proof selects K agents with Zi at least αZ* on a box attaining Z*.Source: §C.3 · p. 25

Appendix D: Ordinary Mixed RW Revenue

Appendix D bounds expected revenue in ordinary mixed RW equilibria using agent-value and position bounds. Under constant probability competition, it gives a fraction-of-benchmark guarantee, while distinguishing this result from the paper’s pure-equilibrium dynamic NBR membership results.

Appendix D: Ordinary Mixed RW Revenue

  • Under constant probability competition, with the number of agents depending only on δ, expected revenue is an Ω(α(1 − δ)^2) fraction of the nonstrategic benchmark.Source: Appendix D · p. 26
  • For agents among the K largest Zi values, gross payoff is bounded by Zi and by τLZi when they hold no reader role in the first L positions.Summing these pointwise bounds yields a revenue inequality for the selected high-Z agents.Source: Appendix D · p. 27
  • The paper’s dynamic NBR membership results apply to pure equilibria, whereas Equation (D.8) gives the expected-revenue bound for ordinary mixed equilibria.The constant-probability-competition comparison uses the nonstrategic benchmark.Source: Appendix D · pp. 26–27

Appendix E: A Two-Box Separation

The two-box example separates RW revenue from the dynamic NBR benchmark when a box lacks a close probability rival. As the probability parameter tends to zero, the equilibrium’s RW revenue can become arbitrarily small relative to that benchmark.

Appendix E: A Two-Box Separation

  • RW revenue can become arbitrarily small relative to the dynamic NBR benchmark when one box lacks a close probability rival.The construction compares equilibrium revenue with a voluntary direct mechanism whose revenue approaches the benchmark as λ increases to 1.Source: Appendix E · p. 28
  • As r tends to zero, the example uses two boxes and two agents with probability reports p1 = (1, 1) and p2 = (r, 1).The discount factor δ is fixed in (0, 1).Source: Appendix E · p. 28
  • For sufficiently small r, the specified report profile is a pure equilibrium and RW revenue is rvA.The profile selects agent 1 on A and agent 2 on B, with A inspected first.Source: Appendix E · p. 28

Appendix F: Writer-Only No-Overbidding and Reported-Values Membership

Appendix F shows how interior-probability pure RWSP equilibria relate to dynamic NBR. Appendix G derives expected-revenue bounds for ordinary mixed RWSP equilibria, including a common guarantee under constant probability competition.

Appendix F: Writer-Only No-Overbidding and Reported-Values Membership

  • Interior-probability pure RWSP equilibria satisfy dynamic NBR; the proof uses agent-by-agent certificates and does not require exact writer-allocation Envy-Free.The appendix also states a writer-only no-overbidding result for selected writers distinct from readers.Source: Appendix F · pp. 29–30

Appendix G: Ordinary Mixed Revenue for the Second-Price Mechanism

  • The appendix derives expected-revenue bounds for ordinary mixed RWSP equilibria satisfying exact writer-allocation Envy-Free almost everywhere.It includes a common guarantee under constant probability competition.Source: Appendix G · p. 30

G.1 The equilibrium-specific bound

  • For the equilibrium-specific bound, integration gives r ≥ 1 − a log(1/a), while nonnegative utility gives a ≥ δr and hence r ≥ cδ.Source: §G.1 · p. 32

G.2 The type-dependent bound

  • The type-dependent bound uses early-role counts and Envy-Free to bound combined success values by vmax_j.An agent without an early role is bounded by its exact tail term; otherwise its gross utility is bounded by H_i.Source: §G.2 · p. 32

G.3 Probability-competition consequences

  • Under constant probability competition, the mixed-equilibrium bounds yield a common revenue guarantee using deviations independent of opponents’ realized reports.The proof requires neither value competition nor interior equilibrium reports.Source: Appendix G · p. 30, §G.3 · p. 33

Appendix H: Constant Probability Competition with Reported Values

The appendix proves a reported-values comparison for specified pure RWSP equilibria. Its proof gives a sharper finite-M comparison and a second bound using a geometric-mean discount ceiling.

Appendix H: Constant Probability Competition with Reported Values

  • The proof gives a sharper finite-M comparison, while its second bound uses GM(δ) ≤ (1 − δ)^−1.The theorem applies to existing pure interior-probability equilibria meeting constant probability competition, qualified value competition, and pointwise exact writer-allocation Envy-Free.Source: Appendix H · pp. 33–34

Appendix I: The Repair Potential and the Existence Boundary

With known box values, coordinatewise report-raising repairs weakly increase RW revenue and strictly increase a repair potential. The argument establishes convergence, but not pure-equilibrium existence or nonexistence.

Appendix I: The Repair Potential and the Existence Boundary

  • Coordinatewise report-raising repairs weakly increase RW revenue, while a strict secondary potential term makes every nontrivial repair strictly increase the potential.The repair sequence converges coordinatewise, and RW revenue converges as well.Source: Appendix I · p. 34
  • The convergence argument does not establish a Nash equilibrium because profitable order-changing deviations can combine a negative promoted-box position with a positive pre-existing role.The proposed support-preservation lemma is false, and the secondary term does not rule out simultaneous or order-changing deviations at the limit.Source: Appendix I · p. 34

Appendix J: Pure-Equilibrium Nonexistence Below the Unit Report Cap

On the open probability-report domain [0, 1), the appendix constructs a three-box instance with no pure ε-equilibrium below a positive threshold, despite all true probabilities being at most 3/5. The result does not settle equilibrium existence on the maintained closed domain [0, 1].

Appendix J: Pure-Equilibrium Nonexistence Below the Unit Report Cap

  • For reports in [0, 1), a three-box, eight-agent known-values instance has no pure ε-equilibrium for ε < 0.0474752, under any complete tie rule.Every true success probability in the instance is at most 3/5.Source: Appendix J · pp. 35–36
  • The construction gives a role-free agent a profitable deviation in either case, with reports chosen near one when the anchor box is already strictly first.For every ε below 0.0474752, the deviation can yield a gain greater than ε.Source: Appendix J · pp. 35–36
  • The open-domain result does not apply to [0, 1], where a suitable report-blind, agent-specific tie rule admits a tie-supported pure equilibrium.Universal pure-equilibrium existence on the closed domain remains open.Source: Appendix J · p. 36
Loading 2609.12197v1…