Pith. sign in

REVIEW 1 major objections 3 minor 1 cited by

Order Auctions with Private Position Preferences

T0 review · 1 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read One demand bit raises order-auction welfare guarantee from 1/2 to 1-1/e.

desk verdict A solid mechanism-design paper with a clean one-bit separation between 1/2 and 1-1/e welfare guarantees, held back mainly by an unproved BNE-existence step for the continuous model. read the letter →

arxiv 2608.00786 v2 pith:6ICFJSTD submitted 2026-08-01 cs.GT

Ruijie Wang , Aviv Yaish This is my paper
classification cs.GT
keywords orderauctionspositionprivatepreferencesfirst-priceBayesianpriceofanarchywelfareguaranteecommunicationcomplexityVCGversus
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies auctions that sell two ordered positions when each bidder privately either values only the first position (a specialist) or values both positions equally (a generalist). It tries to establish how much demand information an order auction must elicit and what welfare that information buys. The central result is a sharp swap: under an item-agnostic first-price rule that awards positions by scalar bids, no strategy profile can implement the efficient allocation ex post, yet every Bayesian Nash equilibrium still guarantees at least half of the optimal expected welfare. If bidders instead send one extra bit declaring whether they want only the top position, the same first-price rule guarantees at least $1-\frac{1}{e}\approx 0.632$ of optimal expected welfare in every BNE. The paper also proves that this single bit per bidder is necessary and sufficient for any deterministic one-round efficient protocol, so the information cost of moving from the half-guarantee to the $1-\frac{1}{e}$ guarantee is exactly one bit.

What carries the argument

The load-bearing mechanism is a pointwise Bayesian smoothness inequality built from randomized deviations and threshold covering. For a bidder of value $v$, the paper uses the randomized first-price deviation that draws a bid from the density $g_v(z)=1/(v-z)$ on $[0,(1-1/e)v]$; this guarantees expected utility at least $\lambda v-t$ against any threshold $t$, where $\lambda=1-1/e$. Specialists in the item-agnostic auction are lower-bounded by an all-pay deviation, bidding uniformly on $[0,v]$. The paper then shows that the thresholds the efficient winners would need to beat are covered by the auction's current revenue: in the item-agnostic rule the sum of the efficient winners' thresholds never exceeds the two highest bids, and in the item-specific rule the same covering holds for the top-only and all-acceptable thresholds. Summing the deviation guarantees over efficient winners gives $\sum_i \mathbb{E}[u_i]\ge \lambda SW^* - REV$, and Bayesian smoothing turns this pointwise inequality into the welfare guarantee for every BNE. A second piece of machinery is the structural comparison of specialist and generalist inverse bid functions: in the item-agnostic auction they satisfy $v_S(b)=(n-2)(1/H(b)-1)v_G(b)$, and in the item-specific auction the inverse bid functions never intersect on the common regular interior support.

What would settle it

Exhibit a smooth strictly increasing iid value distribution satisfying the model for which the item-agnostic first-price auction has no Bayesian Nash equilibrium; since the welfare theorems quantify over every BNE, such an instance would render the guarantees vacuous. Short of that, a computed BNE for $n=3$ uniform values whose welfare ratio falls below $1-1/e$ for the ISFPA would directly falsify Theorem 6.2.

Watch

Extended reading notes

Core claim

At the paper's core is the claim that a single demand bit is both necessary and sufficient to raise the worst-case equilibrium welfare guarantee of a two-position first-price auction from $1/2$ to $1-1/e$. Formally, for the item-agnostic first-price auction (items go to the highest and second-highest scalar bids), with at least three bidders and both types present, no BNE is ex-post efficient under any payment rule (Proposition 4.2), and every BNE satisfies $\mathbb{E}[SW^{IA}]\ge \frac{1}{2}\mathbb{E}[SW^*]$ (Theorem 4.3). For the item-specific first-price auction, in which each bidder adds a top-only/all-acceptable declaration, every BNE satisfies $\mathbb{E}[SW^{IS}]\ge (1-\frac{1}{e})\mathbb{E}[SW^*]$ (Theorem 6.2). Complementing these welfare bounds, the paper proves a communication lower bound: any deterministic one-round protocol that implements the efficient allocation needs $n(\lceil\log_2 K\rceil+1)$ bits, which is $n$ bits more than the bid indices alone, and this bound is achieved (Theorem 5.4, Proposition 5.5). The paper also shows that the efficient, demand-aware allocation with VCG payments is the unique DSIC and IR no-positive-transfer rule, but that this rule is vulnerable to seller shill bids, whereas the first-price formats are shill-proof and false-name robust.

Load-bearing premise

The guarantees depend on the sharp specialist/generalist split and on the existence of a BNE in the continuous-value model, while the paper proves BNE existence only for finite discretizations; if some model-consistent continuous distribution admits no BNE, the every-equilibrium guarantee is vacuous.

Editorial extensions

If this is right

  • An auctioneer selling two ordered slots can guarantee at least $1-1/e$ of the efficient welfare in every equilibrium simply by letting bidders append one bit (top-only vs. either) to their first-price bids.
  • Any deterministic one-round auction that aims for full efficiency must spend at least one bit per bidder beyond the scalar bid; the item-specific first-price auction and the demand-aware efficient rule both achieve this bound.
  • Moving from an item-agnostic to an item-specific rule gives up a pointwise revenue advantage (an IA auction can charge a specialist for a worthless second slot) in exchange for a strict welfare improvement.
  • If efficiency and truthfulness are required together, the only no-positive-transfer payment rule is demand-aware VCG, but that rule is not shill-proof; first-price rules are identity-robust at the cost of efficiency.
  • The welfare guarantees also hold for approximate equilibria: every interim $\varepsilon$-BNE retains the same ratio up to an additive $n\varepsilon$ term.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same randomized-deviation argument may extend to $m$-position auctions, with the guarantee likely becoming $1-1/e$ for the top slot and lower for lower slots; the paper only analyzes two slots, so this is an untested extrapolation.
  • In settings like blockchain transaction ordering, the result suggests that a cheap binary preference declaration can mitigate the welfare loss from scalar-bid sequencing without requiring fully expressive multi-dimensional bids.
  • Because the guarantees hold for every BNE without solving for equilibrium, they are robust to the paper's own NP- and PPAD-completeness results on computing equilibria.
  • A small positive value for the second slot in the specialist type would change the efficient-welfare comparison and likely degrade the $1-1/e$ bound continuously; quantifying that degradation is a natural next step not taken in the paper.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 3 minor

Summary. The paper studies two-unit ordered auctions in which bidders are either specialists (positive value only for the first item) or generalists (equal value for both items), with iid values from a continuous distribution. The main results are: (i) no strategy profile ex-post implements the efficient allocation under the monotone bid-rank allocation rule, regardless of payments (Proposition 4.2); (ii) every BNE of the item-agnostic first-price auction obtains at least half of the efficient welfare (Theorem 4.3), giving a Bayesian price of anarchy at most 2; (iii) any deterministic one-round protocol implementing the efficient allocation requires each bidder to communicate one demand bit beyond the bid (Theorem 5.4); and (iv) with that demand bit, every BNE of the item-specific first-price auction obtains at least 1 - 1/e of efficient welfare (Theorem 6.2), giving a Bayesian price of anarchy at most e/(e-1). Additional results address demand-aware VCG uniqueness, bid-priority reversals, separability, shill and false-name robustness, revenue, and computational complexity. Proofs are provided in full in the appendices.

Significance. If the results are correct, this is a clean and useful contribution to auction theory and to applications such as blockchain transaction ordering and priority service. The constants 1/2 and 1 - 1/e are derived from explicit randomized deviations, not from fitted parameters, and the paper gives a matching communication lower bound that is tight (Theorem 5.4 and Proposition 5.5). The paper also usefully separates first-price formats from VCG: the former are ex-post seller-shill-proof and buyer false-name robust, while the latter is vulnerable to losing shills. The proof scaffolding, including the smoothness transfer and the all-pay-deviation argument for specialists, is transparent and appears sound. The main reservation is the missing proof of BNE existence for the continuous model, which is load-bearing for the distribution-free welfare claims.

major comments (1)
  1. [Section 3; Theorems 4.3 and 6.2; Definition 3.2] The main welfare theorems quantify over every BNE of the continuous model described in Section 3, and the distribution-free Bayesian price of anarchy in Corollaries 4.4 and 6.3 depends on BNE existence. However, the paper proves BNE existence only for the finite encoded instances of Appendix A, via the agent normal form and Nash's theorem (Theorem A.9). Propositions 4.5 and 6.5, which characterize inverse bid functions and no-crossing, also assume a symmetric monotone BNE without proving existence. If some model-consistent continuous distribution admits no BNE, then Theorem 4.3 and Theorem 6.2 are vacuously true but the advertised equilibrium welfare guarantees carry no force, and the BPoA ratio in Definition 3.2 is undefined. This is a missing proof step rather than a contradiction in the conditional statements. The authors should either prove non-vacuous existence for the continuous model, give a precise reduction to an existing existence theorem for asymmetric first-price auctions that covers this two-unit, two-demand-type setting, or explicitly restate every welfare theorem and corollary as "whenever a BNE exists" and adjust the distribution-free framing accordingly.
minor comments (3)
  1. [Section 5, Theorem 5.4] The theorem states the equality n⌈log2(2K−1)⌉ = n(⌈log2 K⌉+1) without restricting K, but this equality fails for K=1. For K=1 the type space is a singleton and the correct lower bound is 0 bits, not n bits. The statement and proof should explicitly assume K≥2, as the appendix already does.
  2. [Section 4, before Proposition 4.2 and after Corollary 4.4] The paragraph beginning "A technical difficulty that we will have to surmount when analyzing the IAFPA's efficiency..." appears twice in nearly identical form. The duplicate should be removed.
  3. [Section 3, Definition 3.2] The definition of BPoA writes the ratio without an explicit superscript M on the denominator's welfare term; using SW^M consistently in the displayed formula would avoid ambiguity.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: welfare bounds and communication lower bound are derived from explicit deviations and standard external theorems; self-citations are confined to related work.

full rationale

The central derivation chain is self-contained. The welfare guarantees in Theorems 4.3 and 6.2 are proven by explicit smoothness arguments: the paper constructs randomized deviations (uniform on [0,v] for specialists, density 1/(v-z) for generalists), derives the pointwise bounds E[u] >= v/2 - t and E[u] >= (1-1/e)v - t by direct integration, bounds the relevant thresholds by revenue via Propositions I.5 and I.6, and then applies the Bayesian smoothness transfer (Proposition I.4). The constants 1/2 and 1-1/e are not fitted or postulated; they emerge from the chosen deviation densities. The communication lower bound (Theorem 5.4) is an injectivity argument over the effective type space, and the matching upper bound (Proposition 5.5) is the obvious two-part encoding. The VCG uniqueness, shill-proofness, and revenue results use standard external theorems (Milgrom-Segal, Myerson, VCG, Brouwer/Nash, Papadimitriou) rather than self-citations. Self-citations (e.g., Gafni-Yaish papers) appear only in related-work and application discussions and are not load-bearing. The only notable gap is that BNE existence for the continuous model is not proved in the main text (Appendix A does it for finite encoded instances), but Definition 3.2 explicitly makes the BPoA undefined when no BNE exists, and the conditional statements about every BNE are not self-referential. Hence there is no circular step.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no fitted data parameters. Its central claims rest on the two-type preference model and on equilibrium existence; the latter is only proven for finite instances. No new physical or mathematical entities are postulated.

assumptions (4)
  • domain assumption Bidders have unit demand; specialists value Item 1 at v and Item 2 at zero, generalists value both items at v.
    This binary preference structure is the model. The efficient-welfare formula in Proposition 4.1 and the threshold bounds in Appendices I.5 and I.6 use this structure directly.
  • domain assumption Values are iid from a strictly increasing smooth distribution on [0,v], and demand types are independent of values with specialist probability alpha.
    Assumed in Section 3 and used for the distribution-free welfare theorems and for the alpha(1-alpha) reversal probability in Proposition 7.5.
  • domain assumption A fixed public bidder-priority rule breaks ties; the complexity appendix adds finite encodings, subjective priors, and no-overbidding.
    The communication lower bound and the NP/PPAD complexity classifications are stated relative to these conventions.
  • ad hoc to paper A BNE exists for every continuous model-consistent distribution in the main welfare theorems.
    The paper quantifies over BNEs of the continuous model but only proves existence for finite encoded instances in Theorem A.9. Without such existence, Theorems 4.3 and 6.2 are vacuous for distributions with no BNE.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Order Auctions with Private Position Preferences." pith.science (2026). https://pith.science/paper/6ICFJSTD

@misc{pith2026260800786,
  author       = {Pith},
  title        = {Pith review of: Order Auctions with Private Position Preferences},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6ICFJSTD}},
  note         = {Machine review of arXiv:2608.00786}
}
abstract

We study auctions where two positions are sold to unit-demand bidders with private heterogeneous order preferences: some are specialists} who value only the first position, while others are generalists indifferent between the two. First, we consider a first-price rule which allocates the first and second items to the highest and second-highest bidders, respectively. We show that no strategy profile ex-post implements the efficient allocation at every type profile, irrespective of payments, and provide a distribution-free equilibrium welfare guarantee of $\frac{1}{2}$. To augment this result, we prove that for deterministic one-round auctions and discrete bids, the efficient allocation requires each bidder to communicate at least one bit more than its bid's binary representation. We next ask what the same bit accomplishes in winner-pays-bid formats where bidders can also specify specific item preferences. In particular, we show that this strengthens our distribution-free equilibrium welfare guarantee to $1-\frac{1}{e}$. Finally, we discuss the applicability to priority service, blockchain transaction ordering, and cloud compute and artificial intelligence (AI) marketplaces.

Figures

Figures reproduced from arXiv: 2608.00786 by the authors.

Figure 1
Figure 1. Valuation ratio between specialists and generalists submitting equals bids. [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. The asymptotic probability that at least one specialist has a profitable entry [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Overview of our setting. Bidders realize private types: specialists strictly demand [PITH_FULL_IMAGE:figures/full_fig_p031_3.png] view at source ↗

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Freemium Is All You Need

    cs.GT 2026-08 reject novelty 6.0 of 10

    Under a stylized uniform-value model, an optimal freemium policy can be expressed by two value thresholds, but the paper's case analysis and dynamic optimality claim are not correct.

Reference graph

Works this paper leans on

80 extracted references · 54 canonical work pages · cited by 1 Pith paper

  1. [1]

    CredibleAuctions:ATrilemma

    MohammadAkbarpourandShengwuLi.“CredibleAuctions:ATrilemma”.In:Econo- metrica : journal of the Econometric Society88.2 (2020), pp. 425–467.issn: 0012- 9682.doi:10.3982/ecta15925

    doi:10.3982/ecta15925 2020

  2. [2]

    False-Name Bidding and Economic Efficiency in Combinatorial Auctions

    Colleen Alkalay-Houlihan and Adrian Vetta. “False-Name Bidding and Economic Efficiency in Combinatorial Auctions”. In:Proceedings of the AAAI Conference on Artificial Intelligence28.1 (June 2014).issn: 2374-3468.doi:10.1609/aaai.v28i1. 8828.url:https://ojs.aaai.org/index.php/AAAI/article/view/8828

    doi:10.1609/aaai.v28i1 2014

  3. [3]

    A Fair Consensus Protocol for Transaction Ordering

    Avi Asayag, Gad Cohen, Ido Grayevsky, Maya Leshkowitz, Ori Rottenstreich, Ronen Tamari, and David Yakira. “A Fair Consensus Protocol for Transaction Ordering”. In: IEEE 26th International Conference on Network Protocols (ICNP). 2018, pp. 55–65. doi:10.1109/icnp.2018.00016

    arXiv 2018

  4. [4]

    Transaction Fee Mech- anism Design in a Post-MEV World

    Maryam Bahrani, Pranav Garimidi, and Tim Roughgarden. “Transaction Fee Mech- anism Design in a Post-MEV World”. In:6th Conference on Advances in Financial Technologies (AFT). 2024, 29:1–29:24.doi:10.4230/lipics.aft.2024.29

    doi:10.4230/lipics.aft.2024.29 2024

  5. [5]

    George Boole.An Investigation of the Laws of Thought, on Which Are Founded the Mathematical Theories of Logic and Probabilities.London:WaltonandMaberly,1854

    work page

  6. [6]

    MEV Sharing with Dynamic Extraction Rates

    PedroBraga,GeorgiosChionas,PiotrKrysta,StefanosLeonardos,GeorgiosPiliouras, and Carmine Ventre. “MEV Sharing with Dynamic Extraction Rates”. In:Proceedings of the Workshop on Decentralized Finance and Security (DeFi). 2024, pp. 1–10.doi: 10.1145/3689931.3694910

    work page arXiv 2024

  7. [7]

    Über Abbildung von Mannigfaltigkeiten

    L. E. J. Brouwer. “Über Abbildung von Mannigfaltigkeiten”. In:Mathematische An- nalen71.1 (1911), pp. 97–115.doi:10.1007/BF01456931. 16

    work page doi:10.1007/bf01456931 1911

  8. [8]

    Mechanism Design for Automated Mar- ket Makers

    T-H. Hubert Chan, Ke Wu, and Elaine Shi. “Mechanism Design for Automated Mar- ket Makers”. In:7th Conference on Advances in Financial Technologies (AFT 2025). Ed. by Zeta Avarikioti and Nicolas Christin. Vol. 354. Leibniz International Proceed- ingsinInformatics(LIPIcs).Dagstuhl,Germany:SchlossDagstuhl–Leibniz-Zentrum für Informatik, 2025, 7:1–7:22.isbn: ...

    doi:10.4230/lipics.aft 2025

Show all 80 references
  1. [9]

    PriorityService:Pricing,Investment,andMarket Organization

    Hung-PoChaoandRobertWilson.“PriorityService:Pricing,Investment,andMarket Organization”. In:American Economic Review77.5 (1987), pp. 899–916

    1987

  2. [10]

    Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules

    Xi Chen and Binghui Peng. “Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules”. In:Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC). 2023, pp. 698–709.doi:10.1145/3564246.3585195

    2023

  3. [11]

    Foundations of Transaction Fee Mechanism Design

    Hao Chung and Elaine Shi. “Foundations of Transaction Fee Mechanism Design”. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2023, pp. 3856–3899.doi:10.1137/1.9781611977554.ch150

    2023 doi

  4. [12]

    Multipart Pricing of Public Goods

    Edward H. Clarke. “Multipart Pricing of Public Goods”. In:Public Choice11 (1971), pp. 17–33.doi:10.1007/BF01726210

    1971 doi

  5. [13]

    The Ad Types Problem

    RiccardoColini-Baldeschi,JuliánMestre,OkkeSchrijvers,andChristopherA.Wilkens. “The Ad Types Problem”. In:Web and Internet Economics (WINE). 2020, pp. 45–58. doi:10.1007/978-3-030-64946-3_4

    2020 doi

  6. [14]

    Using Mechanism Design to Prevent False- Name Manipulations

    Vincent Conitzer and Makoto Yokoo. “Using Mechanism Design to Prevent False- Name Manipulations”. In:AI Magazine31.4 (Sept. 2010), pp. 65–78.issn: 2371-9621. doi:10 . 1609 / aimag . v31i4 . 2315.url:https : / / ojs . aaai . org / aimagazine / index.php/aimagazine/article/view/2315

    2010

  7. [15]

    Flash Boys 2.0: Frontrunning in Decentralized Exchanges, Miner Extractable Value, and Consensus Instability

    Philip Daian, Steven Goldfeder, Tyler Kell, Yunqi Li, Xueyuan Zhao, Iddo Bentov, Lorenz Breidenbach, and Ari Juels. “Flash Boys 2.0: Frontrunning in Decentralized Exchanges, Miner Extractable Value, and Consensus Instability”. In:IEEE Sympo- sium on Security and Privacy (SP). ...

    2020

  8. [16]

    Efficiency of the First-Price Auction in the Autobidding World

    Yuan Deng, Jieming Mao, Vahab Mirrokni, Hanrui Zhang, and Song Zuo. “Efficiency of the First-Price Auction in the Autobidding World”. In:Advances in Neural In- formation Processing Systems. Vol. 37. Curran Associates, Inc., 2024, pp. 139270– 139293.doi:10.52202/079017-4420

    2024 doi

  9. [17]

    Expressiveness and Robustness of First-Price Position Auctions

    Paul Dütting, Felix Fischer, and David C. Parkes. “Expressiveness and Robustness of First-Price Position Auctions”. In:Mathematics of Operations Research44.1 (2019), pp. 196–211.doi:10.1287/moor.2017.0920

    2019

  10. [18]

    Equilib- ria in Auctions with Ad Types

    Hadi Elzayn, Riccardo Colini-Baldeschi, Brian Lan, and Okke Schrijvers. “Equilib- ria in Auctions with Ad Types”. In:Proceedings of the ACM Web Conference 2022 (WWW). 2022, pp. 68–78.doi:10.1145/3485447.3512052. 17

    2022

  11. [19]

    Reserve Price Opti- mization for First Price Auctions in Display Advertising

    Zhe Feng, Sebastien Lahaie, Jon Schneider, and Jinchao Ye. “Reserve Price Opti- mization for First Price Auctions in Display Advertising”. In:Proceedings of the 38th International Conference on Machine Learning. PMLR, July 2021, pp. 3230–3239. url:https://proceedings.mlr.press...

    2021

  12. [20]

    arXiv:2412.20853

    MatheusV.X.Ferreira,YotamGafni,andMaxResnick.Incentive-Compatible Collusion- Resistance via Posted Prices. arXiv:2412.20853. 2024.doi:10.48550/arXiv.2412. 20853

    2024 doi arXiv

  13. [21]

    Credible Decentralized Exchange Design via Verifiable Sequencing Rules

    Matheus Venturyne Xavier Ferreira and David C. Parkes. “Credible Decentralized Exchange Design via Verifiable Sequencing Rules”. In:Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC). 2023, pp. 723–736.doi:10 . 1145/3564246.3585233

    2023

  14. [22]

    On the Computation of Equilibria in Discrete First-Price Auctions

    Aris Filos-Ratsikas, Yiannis Giannakopoulos, Alexandros Hollender, and Charalam- pos Kokkalis. “On the Computation of Equilibria in Discrete First-Price Auctions”. In:Proceedings of the 25th ACM Conference on Economics and Computation (EC). 2024, pp. 379–399.doi:10.1145/367086...

    2024

  15. [23]

    On the Complexity of Equilibrium Computation in First-Price Auctions

    Aris Filos-Ratsikas, Yiannis Giannakopoulos, Alexandros Hollender, Philip Lazos, and Diogo Poças. “On the Complexity of Equilibrium Computation in First-Price Auctions”. In:Proceedings of the 22nd ACM Conference on Economics and Compu- tation (EC). 2021, pp. 454–476.doi:10.114...

    2021

  16. [24]

    Differentiation Under the Integral Sign

    Harley Flanders. “Differentiation Under the Integral Sign”. In:The American Mathe- matical Monthly80.6 (1973), pp. 615–627.doi:10.1080/00029890.1973.11993339

    1973

  17. [25]

    Sugli Integrali Multipli

    Guido Fubini. “Sugli Integrali Multipli”. In:Atti della Reale Accademia Nazionale dei Lincei. Rendiconti. 5th ser. 16.1 (1907), pp. 608–614

    1907

  18. [26]

    Deterring A Small Collusion is All You Need

    Yotam Gafni. “Deterring A Small Collusion is All You Need”. In:Proceedings of the ACM Web Conference 2026. 2026, pp. 31–39.doi:10.1145/3774904.3792121

    2026

  19. [27]

    VCG under Sybil (False-Name) Attacks - A Bayesian Analysis

    Yotam Gafni, Ron Lavi, and Moshe Tennenholtz. “VCG under Sybil (False-Name) Attacks - A Bayesian Analysis”. In:Proceedings of the AAAI Conference on Artificial Intelligence34.02 (Apr. 2020), pp. 1966–1973.issn: 2159-5399.doi:10.1609/aaai. v34i02.5567

    2020 doi

  20. [28]

    Worst-case Bounds on Power vs. Proportion in Weighted Voting Games with an Application to False-name Manip- ulation

    Yotam Gafni, Ron Lavi, and Moshe Tennenholtz. “Worst-case Bounds on Power vs. Proportion in Weighted Voting Games with an Application to False-name Manip- ulation”. In:Journal of Artificial Intelligence Research72 (2021), pp. 99–135.doi: 10.1613/jair.1.13136

    2021 doi

  21. [29]

    Optimal Mechanism Design for Agents with DSL Strategies: The Case of Sybil Attacks in Combinatorial Auctions

    Yotam Gafni and Moshe Tennenholtz. “Optimal Mechanism Design for Agents with DSL Strategies: The Case of Sybil Attacks in Combinatorial Auctions”. In:Electronic Proceedings in Theoretical Computer Science379 (2023), pp. 245–259.doi:10.4204/ EPTCS.379.20

    2023

  22. [30]

    2022.doi:10.48550/arXiv.2210.07793

    Yotam Gafni and Aviv Yaish.Greedy Transaction Fee Mechanisms for (Non-)myopic Miners. 2022.doi:10.48550/arXiv.2210.07793. 18

    2022 doi arXiv

  23. [31]

    Barriers to Collusion-Resistant Transaction Fee Mech- anisms

    Yotam Gafni and Aviv Yaish. “Barriers to Collusion-Resistant Transaction Fee Mech- anisms”. In:Proceedings of the 25th ACM Conference on Economics and Computation (EC). 2024, pp. 1074–1096.doi:10.1145/3670865.3673469

    2024

  24. [32]

    Discrete and Bayesian Transaction Fee Mechanisms

    Yotam Gafni and Aviv Yaish. “Discrete and Bayesian Transaction Fee Mechanisms”. In:Mathematical Research for Blockchain Economy (MARBLE). 2024, pp. 145–171. doi:10.1007/978-3-031-68974-1_8

    2024 doi

  25. [33]

    2024.doi:10.48550/ arXiv.2402.08549

    Yotam Gafni and Aviv Yaish.Scheduling With Time Discounts. 2024.doi:10.48550/ arXiv.2402.08549

    2024 doi

  26. [34]

    Transaction Fee Mechanisms Robust to Welfare- Increasing Collusion

    Yotam Gafni and Aviv Yaish. “Transaction Fee Mechanisms Robust to Welfare- Increasing Collusion”. In:Games and Economic Behavior157 (Mar. 2026), pp. 351– 375.issn: 0899-8256.doi:10.1016/j.geb.2026.02.005

    2026 doi

  27. [35]

    Revisiting the Prim- itives of Transaction Fee Mechanism Design

    Aadityan Ganesh, Clayton Thomas, and S. Matthew Weinberg. “Revisiting the Prim- itives of Transaction Fee Mechanism Design”. In:Proceedings of the 25th ACM Con- ference on Economics and Computation (EC). 2024, p. 703.doi:10.1145/3670865. 3673621

    2024 doi

  28. [36]

    Matthew Weinberg.Characterizing Off- Chain Influence Proof Transaction Fee Mechanisms

    Aadityan Ganesh, Clayton Thomas, and S. Matthew Weinberg.Characterizing Off- Chain Influence Proof Transaction Fee Mechanisms. 2025.doi:10.48550/arXiv. 2512.02354

    2025 doi

  29. [37]

    AMaximalCouplingforMarkovChains

    DavidGriffeath.“AMaximalCouplingforMarkovChains”.In:Zeitschrift für Wahrschein- lichkeitstheorie und Verwandte Gebiete31(1975),pp.95–106.doi:10.1007/BF00539434

    1975 doi

  30. [38]

    Incentives in Teams

    Theodore Groves. “Incentives in Teams”. In:Econometrica41.4 (1973), pp. 617–631. doi:10.2307/1914085

    1973 doi

  31. [39]

    The Centralizing Effects of Private Order Flow on Proposer-Builder Separation

    Tivas Gupta, Mallesh M. Pai, and Max Resnick. “The Centralizing Effects of Private Order Flow on Proposer-Builder Separation”. In:5th Conference on Advances in Fi- nancial Technologies (AFT 2023). Ed. by Joseph Bonneau and S. Matthew Weinberg. Vol. 282. Leibniz International P...

    2023 doi

  32. [40]

    A Theory of Monopoly Pricing Schemes with De- mand Uncertainty

    Milton Harris and Artur Raviv. “A Theory of Monopoly Pricing Schemes with De- mand Uncertainty”. In:American Economic Review71.3 (1981), pp. 347–365

    1981

  33. [41]

    SoK: Preventing Transaction Reordering Manipulations in Decentralized Finance

    Lioba Heimbach and Roger Wattenhofer. “SoK: Preventing Transaction Reordering Manipulations in Decentralized Finance”. In:Proceedings of the 4th ACM Conference on Advances in Financial Technologies (AFT). 2023, pp. 47–60.doi:10 . 1145 / 3558535.3559784

    2023

  34. [42]

    Monopoly without a Mo- nopolist: An Economic Analysis of the Bitcoin Payment System

    Gur Huberman, Jacob D. Leshno, and Ciamac Moallemi. “Monopoly without a Mo- nopolist: An Economic Analysis of the Bitcoin Payment System”. In:The Review of Economic Studies88.6 (Mar. 2021), pp. 3011–3040.issn: 0034-6527.doi:10 . 1093 / restud / rdab014. eprint:https : / / acad...

    2021

  35. [43]

    Order-Fairness for Byzantine Consensus

    Mahimna Kelkar, Fan Zhang, Steven Goldfeder, and Ari Juels. “Order-Fairness for Byzantine Consensus”. In:Advances in Cryptology – CRYPTO 2020. 2020, pp. 451– 480.doi:10.1007/978-3-030-56877-1_16

    2020 doi

  36. [44]

    Shill-Proof Auctions

    Andrew Komo, Scott Duke Kominers, and Tim Roughgarden. “Shill-Proof Auctions”. In:Proceedings of the 26th ACM Conference on Economics and Computation (EC). 2025, p. 784.doi:10.1145/3736252.3742623

    2025

  37. [45]

    2025.doi:10.48550/arXiv.2511.13080

    StevenLandersandBenjaminMarsh.MEV in Multiple Concurrent Proposer Blockchains. 2025.doi:10.48550/arXiv.2511.13080

    2025 doi

  38. [46]

    Redesigning Bitcoin’s Fee Market

    Ron Lavi, Or Sattath, and Aviv Zohar. “Redesigning Bitcoin’s Fee Market”. In:The World Wide Web Conference (WWW). 2019, pp. 2950–2956.doi:10.1145/3308558. 3313454

    2019 doi

  39. [47]

    First Price Auctions in the Asymmetric N Bidder Case

    Bernard Lebrun. “First Price Auctions in the Asymmetric N Bidder Case”. In:In- ternational Economic Review40.1 (1999), pp. 125–142.doi:10.1111/1468-2354. 00008

    1999 doi

  40. [48]

    MEV Makes Everyone Happy under Greedy Sequencing Rule

    Yuhao Li, Mengqian Zhang, Jichen Li, Elynn Chen, Xi Chen, and Xiaotie Deng. “MEV Makes Everyone Happy under Greedy Sequencing Rule”. In:Proceedings of the Workshop on Decentralized Finance and Security (DeFi). 2023, pp. 9–15.doi: 10.1145/3605768.3623543

    2023

  41. [49]

    Buying Time: Latency Racing vs. Bidding for Transaction Ordering

    Akaki Mamageishvili, Mahimna Kelkar, Jan Christoph Schlegel, and Edward W. Fel- ten. “Buying Time: Latency Racing vs. Bidding for Transaction Ordering”. In:5th Conference on Advances in Financial Technologies (AFT). 2023, 23:1–23:22.doi: 10.4230/lipics.aft.2023.23

    2023 doi

  42. [50]

    Asymmetric Auctions

    Eric Maskin and John Riley. “Asymmetric Auctions”. In:The Review of Economic Studies67.3 (2000), pp. 413–438.doi:10.1111/1467-937X.00137

    2000 doi

  43. [51]

    CLVROrdering of Transactions on AMMs

    RobertMcLaughlin,NirChemaya,DingyueLiu,andDahliaMalkhi.“CLVROrdering of Transactions on AMMs”. In:arXiv preprint arXiv:2408.02634(2024).doi:10 . 48550/arXiv.2408.02634

    2024 doi arXiv

  44. [52]

    Envelope Theorems for Arbitrary Choice Sets

    Paul Milgrom and Ilya Segal. “Envelope Theorems for Arbitrary Choice Sets”. In: Econometrica70.2 (2002), pp. 583–601.doi:10.1111/1468-0262.00296

    2002

  45. [53]

    Optimal Auction Design

    Roger B. Myerson. “Optimal Auction Design”. In:Mathematics of Operations Re- search6.1 (1981), pp. 58–73.doi:10.1287/moor.6.1.58

    1981 doi

  46. [54]

    Equilibrium Points in N-Person Games

    John F. Nash. “Equilibrium Points in N-Person Games”. In:Proceedings of the Na- tional Academy of Sciences36.1 (1950), pp. 48–49.doi:10.1073/pnas.36.1.48

    1950 doi

  47. [55]

    The Communication Requirements of Efficient Alloca- tions and Supporting Prices

    Noam Nisan and Ilya Segal. “The Communication Requirements of Efficient Alloca- tions and Supporting Prices”. In:Journal of Economic Theory129.1 (2006), pp. 192– 224.doi:10.1016/j.jet.2004.10.007

    2006 doi

  48. [56]

    Transaction Fee Mechanism for Order-Sensitive Blockchain-Based Applications

    Mohammad Sadegh Nourbakhsh, Feng Hao, and Arshad Jhumka. “Transaction Fee Mechanism for Order-Sensitive Blockchain-Based Applications”. In:Lecture Notes in Computer Science. Springer, 2024, pp. 327–343.doi:10.1007/978-3-031-54204- 6_20. 20

    2024 doi

  49. [57]

    Allocating Priority with Auctions: An Exper- imental Analysis

    Charles Noussair and David Porter. “Allocating Priority with Auctions: An Exper- imental Analysis”. In:Journal of Economic Behavior & Organization19.2 (1992), pp. 169–195.doi:10.1016/0167-2681(92)90089-T

    1992 doi

  50. [58]

    Enforcing Fairness in Blockchain Transaction Ordering

    Ariel Orda and Ori Rottenstreich. “Enforcing Fairness in Blockchain Transaction Ordering”. In:IEEE International Conference on Blockchain and Cryptocurrency (ICBC). 2019, pp. 368–375.doi:10.1109/bloc.2019.8751349

    2019

  51. [59]

    On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence

    Christos H. Papadimitriou. “On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence”. In:Journal of Computer and System Sciences48.3 (1994), pp. 498–532.doi:10.1016/S0022-0000(05)80063-7

    1994 doi

  52. [60]

    Rosenzweig and Bing Xu.Class Peers as Competitors and Educators: The Consequences of Rank-Based Rewards in US High Schools

    Mark R. Rosenzweig and Bing Xu.Class Peers as Competitors and Educators: The Consequences of Rank-Based Rewards in US High Schools. Tech. rep. 31135. National Bureau of Economic Research, 2023.doi:10.3386/w31135

    2023 doi

  53. [61]

    Transaction Fee Mechanism Design

    Tim Roughgarden. “Transaction Fee Mechanism Design”. In:Journal of the ACM 71.4 (2024), 30:1–30:25.doi:10.1145/3674143

    2024 doi

  54. [62]

    A false-name-proof double auction protocol for arbitrary evaluation values

    Yuko Sakurai and Makoto Yokoo. “A false-name-proof double auction protocol for arbitrary evaluation values”. In:Proceedings of the Second International Joint Confer- ence on Autonomous Agents and Multiagent Systems. AAMAS ’03. Melbourne, Aus- tralia: Association for Computing ...

    2003

  55. [63]

    2023.doi:10.48550/arXiv

    Jan Christoph Schlegel.Transaction Ordering Auctions. 2023.doi:10.48550/arXiv. 2312.02055

    2023 doi

  56. [64]

    What Can Cryptography Do for Decentralized Mechanism Design?

    Elaine Shi, Hao Chung, and Ke Wu. “What Can Cryptography Do for Decentralized Mechanism Design?” In:14th Innovations in Theoretical Computer Science Confer- ence (ITCS). 2023, 97:1–97:22.doi:10.4230/LIPIcs.ITCS.2023.97

    2023 doi

  57. [65]

    Comparing Position Auctions Computationally

    David Robert Martin Thompson and Kevin Leyton-Brown. “Comparing Position Auctions Computationally”. In:Proceedings of the 24th AAAI Conference on Ar- tificial Intelligence. 2010, pp. 1694–1697.doi:10.1609/aaai.v24i1.7710

    2010 doi

  58. [66]

    Online Ad Auctions

    Hal R. Varian. “Online Ad Auctions”. In:American Economic Review99.2 (2009), pp. 430–434.doi:10.1257/aer.99.2.430

    2009 doi

  59. [67]

    2026.url:https://docs.vast.ai/guides/instances/ choosing/instance-types#priority-levels

    Vast.ai.Instance Types. 2026.url:https://docs.vast.ai/guides/instances/ choosing/instance-types#priority-levels

    2026

  60. [68]

    Counterspeculation, Auctions, and Competitive Sealed Tenders

    William Vickrey. “Counterspeculation, Auctions, and Competitive Sealed Tenders”. In:The Journal of Finance16.1 (1961), pp. 8–37.doi:10 . 1111 / j . 1540 - 6261 . 1961.tb02789.x

    1961

  61. [69]

    Perils of Parallelism: Transaction Fee Mechanisms under Execution Uncertainty

    Sarisht Wadhwa, Aviv Yaish, Fan Zhang, and Kartik Nayak. “Perils of Parallelism: Transaction Fee Mechanisms under Execution Uncertainty”. In:35th USENIX Se- curity Symposium (USENIX Security 26). USENIXSEC ’26. USENIX Association, 2026.url:https://www.usenix.org/conference/use...

    2026

  62. [70]

    Data Independent Order Policy Enforcement: Limitations and Solutions

    Sarisht Wadhwa, Luca Zanolini, Aditya Asgaonkar, Francesco D’Amato, Chengrui Fang, Fan Zhang, and Kartik Nayak. “Data Independent Order Policy Enforcement: Limitations and Solutions”. In:Proceedings of the ACM SIGSAC Conference on Computer and Communications Security (CCS). 20...

    2024

  63. [71]

    Prooφ: A ZKP Market Mechanism

    Wenhao Wang, Lulu Zhou, Aviv Yaish, Fan Zhang, Ben Fisch, and Benjamin Livshits. “Prooφ: A ZKP Market Mechanism”. In:Financial Cryptography and Data Security (FC). 2025.doi:10.1007/978-3-032-07024-1_11

    2025 doi

  64. [72]

    Maximizing Miner Revenue in Transaction Fee MechanismDesign

    Ke Wu, Elaine Shi, and Hao Chung. “Maximizing Miner Revenue in Transaction Fee MechanismDesign”.In:15th Innovations in Theoretical Computer Science Conference (ITCS). 2024, 98:1–98:23.doi:10.4230/LIPIcs.ITCS.2024.98

    2024 doi

  65. [73]

    Inequality in the Age of Pseudonymity

    Aviv Yaish, Nir Chemaya, Dahlia Malkhi, and Lin William Cong. “Inequality in the Age of Pseudonymity”. In:Proceedings of the Fortieth AAAI Conference on Artificial Intelligence and Fortieth Conference on Innovative Applications of Artificial Intelli- gence and Eighteenth Sympo...

    2026 doi

  66. [74]

    2023.url:https://ia.cr/2023/892

    Aviv Yaish, Maya Dotan, Kaihua Qin, Aviv Zohar, and Arthur Gervais.Suboptimality in DeFi. 2023.url:https://ia.cr/2023/892

    2023

  67. [75]

    Robust double auction protocol against false-name bids

    M. Yokoo, Y. Sakurai, and S. Matsubara. “Robust double auction protocol against false-name bids”. In:Proceedings 21st International Conference on Distributed Com- puting Systems. Apr. 2001, pp. 137–145.doi:10.1109/ICDSC.2001.918942

    2001

  68. [76]

    False-name-Proof Combinatorial Auction Mechanisms

    Makoto Yokoo. “False-name-Proof Combinatorial Auction Mechanisms”. en. In:Com- putational Foundations of Social Choice. Ed. by Felix Brandt, Vincent Conitzer, Lane A. Hemaspaandra, Jean-Francois Laslier, and William S. Zwicker. Vol. 10101. Dagstuhl Seminar Proceedings (DagSemP...

    2010 doi

  69. [77]

    Robust combinatorial auction protocol against false-name bids

    Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara. “Robust combinatorial auction protocol against false-name bids”. In:Artificial Intelligence130.2 (2001), pp. 167– 181.issn: 0004-3702.doi:10.1016/S0004-3702(01)00077-7.url:https://www. sciencedirect.com/science/article/pii/S000...

    2001 doi

  70. [78]

    The effect of false-name bids in combinatorial auctions: new fraud in internet auctions

    Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara. “The effect of false-name bids in combinatorial auctions: new fraud in internet auctions”. In:Games and Eco- nomic Behavior46.1 (2004), pp. 174–188.issn: 0899-8256.doi:10.1016/S0899- 8256(03)00045- 9.url:https://www.sciencedire...

    2004 doi

  71. [79]

    2021.doi: 10.48550/arXiv.2106.07371

    Liyi Zhou, Kaihua Qin, and Arthur Gervais.A2MM: Mitigating Frontrunning, Trans- action Reordering and Consensus Instability in Decentralized Exchanges. 2021.doi: 10.48550/arXiv.2106.07371. 22 A Computational Complexity We consider an encoding induced by finite-precision implem...

    2021 doi arXiv

  72. [80]

    Corollary I.8.Under independent types, every interim ISFPAε-BNE satisfiesE[SWIS]≥ 1− 1 e E[SW∗]−nε

    Applying the approximate-equilibrium part of Proposition I.4 to the IA mecha- nism yieldsE[SW IA]≥ 1 2 E[SW∗]−nε. Corollary I.8.Under independent types, every interim ISFPAε-BNE satisfiesE[SWIS]≥ 1− 1 e E[SW∗]−nε. Proof.The proof of Theorem 6.2 establishes the corresponding in...

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.