Conditional transaction mechanisms optimize evaluation order for offline users
Opening the Strategic Pandora Box: Conditional Transaction Mechanisms
Computer Science and Game Theory
Summary
Sometimes computer systems need to decide which tasks to handle first when not all users are online, and each decision affects how long final updates take. This paper studies how to design rules that choose the order to check conditions using each user's own estimate of success chances and value. The authors introduce new methods that aim to get payments or rewards close to a theoretical best, even without shared knowledge among users. Their work helps understand how to efficiently manage such conditional tasks when information is private and timing matters.
What this means in practice
- •For blockchain developers: Design transaction ordering rules that incentivize users to truthfully report transaction success probabilities in offline or delayed states.
- •For online marketplace operators: Implement conditional evaluation mechanisms that prioritize pending user actions with private information under uncertainty to improve platform efficiency.
A theory result. No direct application yet.
Authors
Yonatan Sompolinsky, Ori Newman, Xintong Wang, David Parkes
Abstract
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.