Cryptographic protocols often make honesty assumptions---e.g., fewer than t out of n participants are adversarial. In practice, these assumptions can be hard to ensure, particularly given monetary incentives for participants to collude and deviate from the protocol.

Pen testing is the problem of selecting high-capacity resources when the only way to measure the capacity of a resource expends its capacity. We have a set of n pens with unknown amounts of ink and our goal is to select a feasible subset of pens maximizing the total ink in them. We are allowed to learn about the ink levels by writing with them, but this uses up ink that was previously in the pens. We identify optimal and near optimal pen testing algorithms by drawing analogues to auction theoretic frameworks of deferred-acceptance auctions and virtual values. Our framework allows the conversion of any near optimal deferred-acceptance mechanism into a near optimal pen testing algorithm. Moreover, these algorithms guarantee an additional overhead of at most (1+o(1)) ln n in the approximation factor to the omniscient algorithm that has access to the ink levels in the pens. We use this framework to give pen testing algorithms for various combinatorial constraints like matroid, knapsack, and general downward-closed constraints, and also for online environments.

We consider a revenue-optimizing auctioneer in single-dimensional environments with matroid feasibility constraints. Akbarpour and Li [2020] argue that any revenue-optimal, truthful, and credible mechanism requires unbounded communication. Recent works [Chitra et al., 2023, Essaidi et al., 2022, Ferreira and Weinberg, 2020] circumvent their impossibility for single-items setting through the use of cryptographic commitments and blockchains. We extend their results to matroid feasibility constraints.

Cryptographic Self-Selection is a paradigm employed by modern Proof-of-Stake consensus protocols to select a block-proposing "leader." Algorand [Chen and Micali, 2019] proposes a canonical protocol, and Ferreira et al. [2022] establish bounds f(α, β) on the maximum fraction of rounds a strategic player can lead as a function of their stake α and a network connectivity parameter β. While both their lower and upper bounds are non-trivial, there is a substantial gap between them (for example, they establish f(10%, 1) ∈ [10.08%, 21.12%]), leaving open the question of how significant of a concern these manipulations are. We develop computational methods to provably nail f(α, β) for any desired (α, β) up to arbitrary precision, and implement our method on a wide range of parameters (for example, we confirm f(10%, 1) ∈ [10.08%, 10.15%]).

This paper studies the fundamental limits of availability and throughput for independent and heterogeneous demands of a limited resource. Availability is the probability that the demands are below the capacity of the resource. Throughput is the expected fraction of the resource that is utilized by the demands. We offer a concentration inequality generator that gives lower bounds on feasible availability and throughput pairs with a given capacity and independent but not necessarily identical distributions of up-to-unit demands. We show that availability and throughput cannot both be poor. These bounds are analogous to tail inequalities on sums of independent random variables, but hold throughout the support of the demand distribution. This analysis gives analytically tractable bounds supporting the unit-demand characterization of Chawla et al. [2023] and generalizes to up-to-unit demands. Our bounds also provide an approach towards improved multi-unit prophet inequalities [Hajiaghayi et al., 2007]. They have applications to transaction fee mechanism design (for blockchains) where high availability limits the probability of profitable user-miner coalitions [Chung and Shi, 2023].

Transaction Fee Mechanism Design---a rapidly-evolving research agenda initiated by Roughgarden [2021]---studies auctions run by untrusted miners for transaction inclusion in a blockchain. Under previously-considered desiderata, an auction is considered 'good' if, informally-speaking, each party (i.e., the miner, the users, and coalitions of both miners and users) has no incentive to deviate from the fixed and pre-determined protocol. In other words, previous works posit that a 'good' auction should be 'simple for users', 'simple for miners', and 'resistant to collusion'.