Credible, Truthful, and Two-Round (Optimal) Auctions via Cryptographic Commitments

Authors

Matheus V. X. Ferreira, S. Matthew Weinberg

Type: Preprint

Publication Date: 2020-07-09

Citations: 14

DOI: https://doi.org/10.1145/3391403.3399495

Ask PDF

Abstract

We consider the sale of a single item to multiple buyers by a revenue-maximizing seller. Recent work of Akbarpour and Li formalizes \emph{credibility} as an auction desideratum, and prove that the only optimal, credible, strategyproof auction is the ascending price auction with reserves (Akbarpour and Li, 2019). In contrast, when buyers' valuations are MHR, we show that the mild additional assumption of a cryptographically secure commitment scheme suffices for a simple \emph{two-round} auction which is optimal, strategyproof, and credible (even when the number of bidders is only known by the auctioneer). We extend our analysis to the case when buyer valuations are $\alpha$-strongly regular for any $\alpha > 0$, up to arbitrary $\varepsilon$ in credibility. Interestingly, we also prove that this construction cannot be extended to regular distributions, nor can the $\varepsilon$ be removed with multiple bidders.

Locations

arXiv (Cornell University)
View PDF
DataCite API
View

Ask a Question About This Paper

Summary

Credible, Strategyproof, Optimal, and Bounded Expected-Round Single-Item Auctions for all Distributions

2022-01-01

Meryem Essaidi , Matheus V. X. Ferreira , S. Matthew Weinberg

We consider a revenue-maximizing seller with a single item for sale to multiple buyers with i.i.d. valuations. Akbarpour and Li (2020) show that the only optimal, credible, strategyproof auction is … We consider a revenue-maximizing seller with a single item for sale to multiple buyers with i.i.d. valuations. Akbarpour and Li (2020) show that the only optimal, credible, strategyproof auction is the ascending price auction with reserves which has unbounded communication complexity. Recent work of Ferreira and Weinberg (2020) circumvents their impossibility result assuming the existence of cryptographically secure commitment schemes, and designs a two-round credible, strategyproof, optimal auction. However, their auction is only credible when buyers' valuations are MHR or $\alpha$-strongly regular: they show their auction might not be credible even when there is a single buyer drawn from a non-MHR distribution. In this work, under the same cryptographic assumptions, we identify a new single-item auction that is credible, strategyproof, revenue optimal, and terminates in constant rounds in expectation for all distributions with finite monopoly price.

Credible, Optimal Auctions via Blockchains

2023-01-01

Tarun Chitra , Matheus V. X. Ferreira , Kshitij Kulkarni

Akbarpour and Li (2020) formalized credibility as an auction desideratum where the auctioneer cannot benefit by implementing undetectable deviations from the promised auction and showed that, in the plain model, … Akbarpour and Li (2020) formalized credibility as an auction desideratum where the auctioneer cannot benefit by implementing undetectable deviations from the promised auction and showed that, in the plain model, the ascending price auction with reserves is the only credible, strategyproof, revenue-optimal auction. Ferreira and Weinberg (2020) proposed the Deferred Revelation Auction (DRA) as a communication efficient auction that avoids the uniqueness results from Akbarpour and Li (2020) assuming the existence of cryptographic commitments and as long as bidder valuations are MHR. They also showed DRA is not credible in settings where bidder valuations are $\alpha$-strongly regular unless $\alpha > 1$. In this paper, we ask if blockchains allow us to design a larger class of credible auctions. We answer this question positively, by showing that DRA is credible even for $\alpha$-strongly regular distributions for all $\alpha > 0$ if implemented over a secure and censorship-resistant blockchain. We argue ledgers provide two properties that limit deviations from a self-interested auctioneer. First, the existence of smart contracts allows one to extend the concept of credibility to settings where the auctioneer does not have a reputation -- one of the main limitations for the definition of credibility from Akbarpour and Li (2020). Second, blockchains allow us to implement mechanisms over a public broadcast channel, removing the adaptive undetectable deviations driving the negative results of Ferreira and Weinberg (2020).

View PDF Chat

Stackelberg Attacks on Auctions and Blockchain Transaction Fee Mechanisms

2023-09-28

Daji Landis , Nikolaj I. Schwartzbach

We study a multi-unit single-demand auction in a setting where agents can arbitrarily commit to strategies that may depend on the commitments of other agents. Such commitments non-trivially change the … We study a multi-unit single-demand auction in a setting where agents can arbitrarily commit to strategies that may depend on the commitments of other agents. Such commitments non-trivially change the equilibria of the auction by inducing a metagame, in which agents commit to strategies. We demonstrate a strategy an attacker may commit to that ensures they receive one such item for free, while forcing the remaining agents to enter a lottery for the remaining items. The attack is detrimental to the auctioneer, who loses most of their revenue. We show that the strategy works as long as the agents have valuations that are somewhat concentrated. The attack is robust to a large fraction of the agents being either oblivious to the attack or having exceptionally high valuations. The attacker may coerce these agents into cooperating by promising them a free item. We show that the conditions for the attack to work hold with high probability when (1) the auction is not too congested, and (2) the valuations are sampled i.i.d. from either a uniform distribution or a Pareto distribution. The attack works for first-price auctions, second-price auctions, and the transaction fee mechanism EIP-1559 used by Ethereum.

View PDF Chat

Optimal commitments in auctions with incomplete information

2015-02-26

Zihe Wang , Pingzhong Tang

We are interested in the problem of optimal commitments in rank-and-bid based auctions, a general class of auctions that include first price and all-pay auctions as special cases. Our main … We are interested in the problem of optimal commitments in rank-and-bid based auctions, a general class of auctions that include first price and all-pay auctions as special cases. Our main contribution is a novel approach to solve for optimal commitment in this class of auctions, for any continuous type distributions. Applying our approach, we are able to solve optimal commitments for first-price and all-pay auctions in closed-form for fairly general distribution settings. The optimal commitments functions in these auctions reveal two surprisingly opposite insights: in the optimal commitment, the leader bids passively when he has a low type. We interpret this as a credible way to alleviate competition and to collude. In sharp contrast, when his type is high enough, the leader sometimes would go so far as to bid above his own value. We interpret this as a credible way to threat. Combing both insights, we show via concrete examples that the leader is indeed willing to do so to secure more utility when his type is in the middle. Our main approach consists of a series of nontrivial innovations. In particular we put forward a concept called equal-bid function that connects both players' strategies, as well as a concept called equal-utility curve that smooths any leader strategy into a continuous and differentiable strategy. We believe these techniques and insights are general and can be applied to similar problems.

Optimal commitments in auctions with incomplete information

2015-01-01

Zihe Wang , Pingzhong Tang

View PDF Chat

Simple, Credible, and Approximately-Optimal Auctions

2020-02-16

Constantinos Daskalakis , Maxwell Fishelson , Brendan Lucier +2 more

We identify the first static credible mechanism for multi-item additive auctions that achieves a constant factor of the optimal revenue. This is one instance of a more general framework for … We identify the first static credible mechanism for multi-item additive auctions that achieves a constant factor of the optimal revenue. This is one instance of a more general framework for designing two-part tariff auctions, adapting the duality framework of Cai et al [CDW16]. Given a (not necessarily incentive compatible) auction format $A$ satisfying certain technical conditions, our framework augments the auction with a personalized entry fee for each bidder, which must be paid before the auction can be accessed. These entry fees depend only on the prior distribution of bidder types, and in particular are independent of realized bids. Our framework can be used with many common auction formats, such as simultaneous first-price, simultaneous second-price, and simultaneous all-pay auctions. If all-pay auctions are used, we prove that the resulting mechanism is credible in the sense that the auctioneer cannot benefit by deviating from the stated mechanism after observing agent bids. If second-price auctions are used, we obtain a truthful $O(1)$-approximate mechanism with fixed entry fees that are amenable to tuning via online learning techniques. Our results for first price and all-pay are the first revenue guarantees of non-truthful mechanisms in multi-dimensional environments; an open question in the literature [RST17].

Zero-Knowledge Mechanisms

2023-01-01

Ran Canetti , Amos Fiat , Yannai A. Gonczarowski

A powerful feature in mechanism design is the ability to irrevocably commit to the rules of a mechanism. Commitment is achieved by public declaration, which enables players to verify incentive … A powerful feature in mechanism design is the ability to irrevocably commit to the rules of a mechanism. Commitment is achieved by public declaration, which enables players to verify incentive properties in advance and the outcome in retrospect. However, public declaration can reveal superfluous information that the mechanism designer might prefer not to disclose, such as her target function or private costs. Avoiding this may be possible via a trusted mediator; however, the availability of a trusted mediator, especially if mechanism secrecy must be maintained for years, might be unrealistic. We propose a new approach to commitment, and show how to commit to, and run, any given mechanism without disclosing it, while enabling the verification of incentive properties and the outcome -- all without the need for any mediators. Our framework is based on zero-knowledge proofs -- a cornerstone of modern cryptographic theory. Applications include non-mediated bargaining with hidden yet binding offers.

View PDF Chat

Cryptographic protocols for Vickrey auctions

1993-11-01

Hannu Nurmi , Arto Salomaa

Simple, Credible, and Approximately-Optimal Auctions

2020-07-09

Constantinos Daskalakis , Maxwell Fishelson , Brendan Lucier +2 more

We present a general framework for designing approximately revenue-optimal mechanisms for multi-item additive auctions. Our approach adapts the duality framework of Cai, Devanur and Weinberg (STOC 2016) and applies to … We present a general framework for designing approximately revenue-optimal mechanisms for multi-item additive auctions. Our approach adapts the duality framework of Cai, Devanur and Weinberg (STOC 2016) and applies to both truthful and non-truthful auctions. Given a (not necessarily truthful) single-item auction format 'A' satisfying certain technical conditions, we run simultaneous item auctions augmented with a personalized entry fee for each bidder that must be paid before the auction can be accessed. These entry fees depend only on the prior distribution of bidder types, and in particular are independent of realized bids. We bound the revenue of the resulting two-part tariff mechanism using a novel geometric technique that enables revenue guarantees for many common non-truthful auctions that previously had none. Our framework can be used with many common auction formats, such as simultaneous first-price, simultaneous second-price, and simultaneous all-pay auctions. Our results for first price and all-pay are the first revenue guarantees of non-truthful mechanisms in multi-dimensional environments, addressing an open question in the literature. If all-pay auctions are used, we prove that the resulting mechanism is also credible in the sense that the auctioneer cannot benefit by deviating from the stated mechanism after observing agent bids. This is the first static credible mechanism for multi-item additive auctions that achieves a constant factor of the optimal revenue. If second-price auctions are used, we obtain a truthful O(1)-approximate mechanism with fixed entry fees that are amenable to tuning via online learning techniques.

View PDF Chat

Stackelberg Attacks on Auctions and Blockchain Transaction Fee Mechanisms

2023-01-01

Daji Landis , Nikolaj I. Schwartzbach

We study an auction with $m$ identical items in a context where $n$ agents can arbitrarily commit to strategies. In general, such commitments non-trivially change the equilibria by inducing a … We study an auction with $m$ identical items in a context where $n$ agents can arbitrarily commit to strategies. In general, such commitments non-trivially change the equilibria by inducing a metagame of choosing which strategies to commit to. In this model, we demonstrate a strategy that an attacker may commit to that ensures they receive one such item for free, while forcing the remaining agents to enter into a lottery for the remaining items (albeit for free). The attack is thus detrimental to the auctioneer who loses most of their revenue. For various types of auctions that are not too congested, we show that the strategy works as long as the agents have valuations that are somewhat concentrated. In this case, all agents will voluntarily cooperate with the attacker to enter into the lottery, because doing so gives them a chance of receiving a free item that would have otherwise cost an amount commensurate with their valuation. The attack is robust to a large constant fraction of the agents being either oblivious to the attack or having exceptionally high valuations (thus reluctant to enter into the lottery). For these agents, the attacker may coerce them into cooperating by promising them a free item rather than entering in to the lottery. We show that the conditions for the attack to work hold with high probability when (1) the auction is not too congested, and (2) the valuations are sampled i.i.d. from either a uniform distribution or a Pareto distribution. The attack works for first-price auctions, second-price auctions and the transaction fee mechanism EIP-1559 used by the Ethereum blockchain.

View PDF Chat

Foundations of Platform-Assisted Auctions

2025-01-06

Hao Chung , Ke Wu , Elaine Shi

Today, many auctions are carried out with the help of intermediary platforms like Google and eBay. We refer to such auctions as platform-assisted auctions.Traditionally, the auction theory literature mainly focuses … Today, many auctions are carried out with the help of intermediary platforms like Google and eBay. We refer to such auctions as platform-assisted auctions.Traditionally, the auction theory literature mainly focuses on designing auctions that incentivize the buyers to bid truthfully,assuming that the platform always faithfully implements the auction. In practice, however, the platforms have been found to manipulate the auctions to earn more profit, resulting in high-profile anti-trust lawsuits. We propose a new model for studying platform-assisted auctions in the permissionless setting. We explore whether it is possible to design a dream auction in thisnew model, such that honest behavior is the utility-maximizing strategy for each individual buyer, the platform, the seller, as well as platform-seller or platform-buyer coalitions.Through a collection of feasibility and infeasibility results,we carefully characterize the mathematical landscape of platform-assisted auctions. We show how cryptography can lend to the design of an efficient platform-assisted auction with dream properties. Although a line of works have also used MPC or the blockchain to remove the reliance on a trusted auctioneer, our work is distinct in nature in several dimensions.First, we initiate a systematic exploration of the game theoretic implications when the service providers are strategic and can collude with sellers or buyers. Second, we observe that the full simulation paradigm is too stringent and leads to high asymptotical costs. Specifically, because every player has a different private outcomein an auction protocol, running any generic MPC protocol among the players would incur at least $n^2$ total cost. We propose a new notion of simulation calledutility-dominated emulation.Under this new notion, we showhow to design efficient auction protocols with quasilinear efficiency.

View PDF Chat

Revisiting the Primitives of Transaction Fee Mechanism Design

2024-07-08

Aadityan Ganesh , Clayton Thomas , S. Matthew Weinberg

Transaction Fee Mechanism Design 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, … Transaction Fee Mechanism Design 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, prior works posit that a 'good' auction should be 'simple for users', 'simple for miners', and 'resistant to collusion'.In this paper, we propose a novel desideratum for Transaction Fee Mechanisms.We say that a TFM is off-chain influence proof when the miner cannot achieve additional revenue by running a separate auction off-chain.While the previously-highlighted EIP-1559 is the goldstandard according to prior desiderata (satisfying simplicity for users and miners along with collusion resistance in the 'typical' case where supply is functionally unlimited), we show that it does not satisfy off-chain influence proofness.Intuitively, this holds because a Bayesian revenuemaximizing miner can strictly increase profits by persuasively threatening to censor any bids that do not transfer a tip directly to the miner off-chain.On the other hand, we reconsider the Cryptographic (multi-party computation assisted) Second Price Auction mechanism (Shi et al., 2023), which is technically not 'simple for miners' according to previous desiderata (since miners may wish to set a reserve by fabricating bids).We argue that the space of TFMs can be naturally expanded to solicit an input from the miner, for example by asking them to set the reserve price of the auction.We show that in this model, the Cryptographic Second Price Auction satisfies simplicity for users and miners, and off-chain influence proofness, since it allows a Bayesian miner to maximize their revenue by posting an optimal reserve price.Finally, we prove a strong impossibility result: no mechanism satisfies all previously-considered properties along with off-chain influence proofness, even with unlimited supply, and even after soliciting miner input.

View PDF Chat

A Sealed-bid Auction with Fund Binding: Preventing Maximum Bidding Price Leakage

2022-08-01

Kota Chin , Keita Emura , Kazumasa Omote +1 more

In an open-bid auction, a bidder can know the budgets of other bidders. Thus, a sealed-bid auction that hides bidding prices is desirable. However, in previous sealed-bid auction protocols, it … In an open-bid auction, a bidder can know the budgets of other bidders. Thus, a sealed-bid auction that hides bidding prices is desirable. However, in previous sealed-bid auction protocols, it has been difficult to provide a "fund binding" property, which would guarantee that a bidder has funds more than or equal to the bidding price and that the funds are forcibly withdrawn when the bidder wins. Thus, such protocols are vulnerable to false bidding. As a solution, many protocols employ a simple deposit method in which each bidder sends a deposit to a smart contract, which is greater than or equal to the bidding price, before the bidding phase. However, this deposit reveals the maximum bidding price, and it is preferable to hide this information. In this paper, we propose a sealed-bid auction protocol that provides a fund binding property. Our protocol not only hides the bidding price and a maximum bidding price, but also provides fund binding, simultaneously. For hiding the maximum bidding price, we pay attention to the fact that usual Ethereum transactions and transactions for sending funds to a one-time address have the same transaction structure, and it seems that they are indistinguishable. We discuss how much bidding transactions are hidden. We also employ DECO (Zhang et al,. CCS 2020) that proves the validity of the data to a verifier in which the data are taken from a source without showing the data itself. Finally, we give our implementation which shows transaction fees required and compare it to a sealed-bid auction protocol employing the simple deposit method.

View PDF Chat

A Practical Solution to Yao's Millionaires' Problem and Its Application in Designing Secure Combinatorial Auction

2019-01-01

Sankarshan Damle , Boi Faltings , Sujit Gujar

The emergence of e-commerce and e-voting platforms has resulted in the rise in the volume of sensitive information over the Internet. This has resulted in an increased demand for secure … The emergence of e-commerce and e-voting platforms has resulted in the rise in the volume of sensitive information over the Internet. This has resulted in an increased demand for secure and private means of information computation. Towards this, the Yao's Millionaires' problem, i.e., to determine the richer among two millionaires' securely, finds an application. In this work, we present a new solution to the Yao's Millionaires' problem namely, Privacy Preserving Comparison (PPC). We show that PPC achieves this comparison in constant time as well as in one execution. PPC uses semi-honest third parties for the comparison who do not learn any information about the values. Further, we show that PPC is collusion-resistance. To demonstrate the significance of PPC, we present a secure, approximate single-minded combinatorial auction, which we call TPACAS, i.e., Truthful, Privacy-preserving Approximate Combinatorial Auction for Single-minded bidders. We show that TPACAS, unlike previous works, preserves the following privacies relevant to an auction: agent privacy, the identities of the losing bidders must not be revealed to any other agent except the auctioneer (AU), bid privacy, the bid values must be hidden from the other agents as well as the AU and bid-topology privacy, the items for which the agents are bidding must be hidden from the other agents as well as the AU. We demonstrate the practicality of TPACAS through simulations. Lastly, we also look at TPACAS' implementation over a publicly distributed ledger, such as the Ethereum blockchain.

A Sealed-Bid Auction with Fund Binding: Preventing Maximum Bidding Price Leakage

2024-04-30

Kota Chin , Keita Emura , Shingo Sato +1 more

In an open-bid auction, a bidder can know the budgets of other bidders. Thus, a sealed-bid auction that hides bidding prices is desirable. However, in previous sealed-bid auction protocols, it … In an open-bid auction, a bidder can know the budgets of other bidders. Thus, a sealed-bid auction that hides bidding prices is desirable. However, in previous sealed-bid auction protocols, it has been difficult to provide a "fund binding" property, which would guarantee that a bidder has funds more than or equal to the bidding price and that the funds are forcibly withdrawn when the bidder wins. Thus, such protocols are vulnerable to a false bidding. As a solution, many protocols employ a simple deposit method in which each bidder sends a deposit to a smart contract, which is greater than or equal to the bidding price, before the bidding phase. However, this deposit reveals the maximum bidding price, and it is preferable to hide this information. In this paper, we propose a sealed-bid auction protocol that provides a fund binding property. Our protocol not only hides the bidding price and a maximum bidding price, but also provides a fund binding property, simultaneously. For hiding the maximum bidding price, we pay attention to the fact that usual Ethereum transactions and transactions for sending funds to a one-time address have the same transaction structure, and it seems that they are indistinguishable. We discuss how much bidding transactions are hidden. We also employ DECO (Zhang et al., CCS 2020) that proves the validity of the data to a verifier in which the data are taken from a source without showing the data itself. Finally, we give our implementation which shows transaction fees required and compare it to a sealed-bid auction protocol employing the simple deposit method.

View PDF Chat

Posted Price and a Knockout Auction: Revenue Maximization Under the Threat of Collusion

2025-01-01

Kan Wu

Strictly strategy-proof auctions

2020-07-17

Matteo Escudé , Ludvig Sinander

View PDF Chat

A Sealed-bid Auction with Fund Binding: Preventing Maximum Bidding Price Leakage

2022-01-01

Kota Chin , Keita Emura , Kazumasa Omote +1 more

In an open-bid auction, a bidder can know the budgets of other bidders. Thus, a sealed-bid auction that hides bidding prices is desirable. However, in previous sealed-bid auction protocols, it … In an open-bid auction, a bidder can know the budgets of other bidders. Thus, a sealed-bid auction that hides bidding prices is desirable. However, in previous sealed-bid auction protocols, it has been difficult to provide a ``fund binding'' property, which would guarantee that a bidder has funds more than or equal to the bidding price and that the funds are forcibly withdrawn when the bidder wins. Thus, such protocols are vulnerable to false bidding. As a solution, many protocols employ a simple deposit method in which each bidder sends a deposit to a smart contract, which is greater than or equal to the bidding price, before the bidding phase. However, this deposit reveals the maximum bidding price, and it is preferable to hide this information. In this paper, we propose a sealed-bid auction protocol that provides a fund binding property. Our protocol not only hides the bidding price and a maximum bidding price, but also provides fund binding, simultaneously. For hiding the maximum bidding price, we pay attention to the fact that usual Ethereum transactions and transactions for sending funds to a one-time address have the same transaction structure, and it seems that they are indistinguishable. We discuss how much bidding transactions are hidden. We also employ DECO (Zhang et al,. CCS 2020) that proves the validity of the data to a verifier in which the data are taken from a source without showing the data itself. Finally, we give our implementation which shows transaction fees required and compare it to a sealed-bid auction protocol employing the simple deposit method.

View PDF Chat

Learning against Non-credible Auctions

2023-01-01

Qian Wang , Xuanzhi Xia , Zongjun Yang +7 more

The standard framework of online bidding algorithm design assumes that the seller commits himself to faithfully implementing the rules of the adopted auction. However, the seller may attempt to cheat … The standard framework of online bidding algorithm design assumes that the seller commits himself to faithfully implementing the rules of the adopted auction. However, the seller may attempt to cheat in execution to increase his revenue if the auction belongs to the class of non-credible auctions. For example, in a second-price auction, the seller could create a fake bid between the highest bid and the second highest bid. This paper focuses on one such case of online bidding in repeated second-price auctions. At each time $t$, the winner with bid $b_t$ is charged not the highest competing bid $d_t$ but a manipulated price $p_t = \alpha_0 d_t + (1-\alpha_0) b_t$, where the parameter $\alpha_0 \in [0, 1]$ in essence measures the seller's credibility. Unlike classic repeated-auction settings where the bidder has access to samples $(d_s)_{s=1}^{t-1}$, she can only receive mixed signals of $(b_s)_{s=1}^{t-1}$, $(d_s)_{s=1}^{t-1}$ and $\alpha_0$ in this problem. The task for the bidder is to learn not only the bid distributions of her competitors but also the seller's credibility. We establish regret lower bounds in various information models and provide corresponding online bidding algorithms that can achieve near-optimal performance. Specifically, we consider three cases of prior information based on whether the credibility $\alpha_0$ and the distribution of the highest competing bids are known. Our goal is to characterize the landscape of online bidding in non-credible auctions and understand the impact of the seller's credibility on online bidding algorithm design under different information structures.

The Polyhedral Geometry of Truthful Auctions

2023-01-01

Michael Joswig , Max Klimm , Sylvain Spitz

View PDF Chat

Bayesian Mechanism Design for Blockchain Transaction Fee Allocation

2023-01-01

Xi Chen , David Simchi‐Levi , Zishuo Zhao +1 more

In blockchain systems, the design of transaction fee mechanisms is essential for stability and satisfaction for both miners and users. A recent work has proven the impossibility of collusion-proof mechanisms … In blockchain systems, the design of transaction fee mechanisms is essential for stability and satisfaction for both miners and users. A recent work has proven the impossibility of collusion-proof mechanisms that achieve both non-zero miner revenue and Dominating-Strategy-Incentive-Compatible (DSIC) for users. However, a positive miner revenue is important in practice to motivate miners. To address this challenge, we consider a \emph{Bayesian game} setting and relax the DSIC requirement for users to Bayesian-Nash-Incentive-Compatibility (BNIC). In particular, we propose an auxiliary mechanism method that makes connections between BNIC and DSIC mechanisms. With the auxiliary mechanism method, we design a transaction fee mechanism (TFM) based on the multinomial logit (MNL) choice model, and prove that the TFM has both BNIC and collusion-proof properties with an asymptotic constant-factor approximation of optimal miner revenue for \emph{i.i.d.} bounded valuations. Our result breaks the zero-revenue barrier while preserving truthfulness and collusion-proof properties.

View PDF Chat

Foundations of Transaction Fee Mechanism Design

2022-02-01

Hao Chung , Elaine Shi

In blockchains such as Bitcoin and Ethereum, users compete in a transaction fee auction to get their transactions confirmed in the next block. A line of recent works set forth … In blockchains such as Bitcoin and Ethereum, users compete in a transaction fee auction to get their transactions confirmed in the next block. A line of recent works set forth the desiderata for a transaction fee mechanism (TFM), and explored whether such a mechanism existed. A dream TFM should satisfy 1) user incentive compatibility (UIC), i.e., truthful bidding should be a user's dominant strategy; 2) miner incentive compatibility (MIC), i.e., the miner's dominant strategy is to faithfully implement the prescribed mechanism; and 3) miner-user side contract proofness (SCP), i.e., no coalition of the miner and one or more user(s) can increase their joint utility by deviating from the honest behavior. The weakest form of SCP is called 1-SCP, where we only aim to provide resilience against the collusion of the miner and a single user. Sadly, despite the various attempts, to the best of knowledge, no existing mechanism can satisfy all three properties in all situations. Since the TFM departs from classical mechanism design in modeling and assumptions, to date, our understanding of the design space is relatively little. In this paper, we further unravel the mathematical structure of transaction fee mechanism design by proving the following results: - Can we have a dream TFM? - Rethinking the incentive compatibility notions. - Do the new design elements make a difference?

View PDF Chat

Auctions without commitment in the auto-bidding world

2023-04-26

Andrés Perlroth , Aranyak Mehta

Advertisers in online ad auctions are increasingly using auto-bidding mechanisms to bid into auctions instead of directly bidding their value manually. One of the prominent auto-bidding formats is that of … Advertisers in online ad auctions are increasingly using auto-bidding mechanisms to bid into auctions instead of directly bidding their value manually. One of the prominent auto-bidding formats is that of target cost-per-acquisition (tCPA) which maximizes the volume of conversions subject to a return-of-investment constraint. From an auction theoretic perspective however, this trend seems to go against foundational results that postulate that for profit-maximizing (aka quasi-linear) bidders, it is optimal to use a classic bidding system like marginal CPA (mCPA) bidding rather than using strategies like tCPA.

View PDF Chat

Dynamic posted-price mechanisms for the blockchain transaction-fee market

2021-09-26

Matheus V. X. Ferreira , Daniel J. Moroz , David C. Parkes +1 more

View PDF Chat

Dynamic Posted-Price Mechanisms for the Blockchain Transaction-Fee Market

2021-03-25

Matheus V. X. Ferreira , Daniel J. Moroz , David C. Parkes +1 more

In recent years, prominent blockchain systems such as Bitcoin and Ethereum have experienced explosive growth in transaction volume, leading to frequent surges in demand for limited block space, causing transaction … In recent years, prominent blockchain systems such as Bitcoin and Ethereum have experienced explosive growth in transaction volume, leading to frequent surges in demand for limited block space, causing transaction fees to fluctuate by orders of magnitude. Under the standard first-price auction approach, users find it difficult to estimate how much they need to bid to get their transactions accepted (balancing the risk of delay with a preference to avoid paying more than is necessary). In light of these issues, new transaction fee mechanisms have been proposed, most notably EIP-1559. A problem with EIP-1559 is that under market instability, it again reduces to a first-price auction. Here, we propose dynamic posted-price mechanisms, which are ex post Nash incentive compatible for myopic bidders and dominant strategy incentive compatible for myopic miners. We give sufficient conditions for which our mechanisms are stable and approximately welfare optimal in the probabilistic setting where each time step, bidders are drawn i.i.d. from a static (but unknown) distribution. Under this setting, we show instances where our dynamic mechanisms are stable, but EIP-1559 is unstable. Our main technical contribution is an iterative algorithm that, given oracle access to a Lipschitz continuous and concave function $f$, converges to a fixed point of $f$.

Revisiting the Primitives of Transaction Fee Mechanism Design

2024-07-08

Aadityan Ganesh , Clayton Thomas , S. Matthew Weinberg

View PDF Chat

Credible Decentralized Exchange Design via Verifiable Sequencing Rules

2022-01-01

Matheus V. X. Ferreira , David C. Parkes

Trading on decentralized exchanges has been one of the primary use cases for permissionless blockchains with daily trading volume exceeding billions of U.S.~dollars. In the status quo, users broadcast transactions … Trading on decentralized exchanges has been one of the primary use cases for permissionless blockchains with daily trading volume exceeding billions of U.S.~dollars. In the status quo, users broadcast transactions and miners are responsible for composing a block of transactions and picking an execution ordering -- the order in which transactions execute in the exchange. Due to the lack of a regulatory framework, it is common to observe miners exploiting their privileged position by front-running transactions and obtaining risk-fee profits. In this work, we propose to modify the interaction between miners and users and initiate the study of {\em verifiable sequencing rules}. As in the status quo, miners can determine the content of a block; however, they commit to respecting a sequencing rule that constrains the execution ordering and is verifiable (there is a polynomial time algorithm that can verify if the execution ordering satisfies such constraints). Thus in the event a miner deviates from the sequencing rule, anyone can generate a proof of non-compliance. We ask if there are sequencing rules that limit price manipulation from miners in a two-token liquidity pool exchange. Our first result is an impossibility theorem: for any sequencing rule, there is an instance of user transactions where the miner can obtain non-zero risk-free profits. In light of this impossibility result, our main result is a verifiable sequencing rule that provides execution price guarantees for users. In particular, for any user transaction A, it ensures that either (1) the execution price of A is at least as good as if A was the only transaction in the block, or (2) the execution price of A is worse than this ``standalone'' price and the miner does not gain (or lose) when including A in the block.

View PDF Chat

Credible Decentralized Exchange Design via Verifiable Sequencing Rules

2023-05-16

Matheus V. X. Ferreira , David C. Parkes

Trading on decentralized exchanges has been one of the primary use cases for permissionless blockchains with daily trading volume exceeding billions of U.S. ‍dollars. In the status quo, users broadcast … Trading on decentralized exchanges has been one of the primary use cases for permissionless blockchains with daily trading volume exceeding billions of U.S. ‍dollars. In the status quo, users broadcast transactions they wish to execute in the exchange and miners are responsible for composing a block of transactions and picking an execution ordering — the order in which transactions execute in the exchange. Due to the lack of a regulatory framework, it is common to observe miners exploiting their privileged position by front-running transactions and obtaining risk-fee profits. Indeed, the Flashbots service institutionalizes this exploit, with miners auctioning the right to front-run transactions. In this work, we propose to modify the interaction between miners and users and initiate the study of verifiable sequencing rules. As in the status quo, miners can determine the content of a block; however, they commit to respecting a sequencing rule that constrains the execution ordering and is verifiable (there is a polynomial time algorithm that can verify if the execution ordering satisfies such constraints). Thus in the event a miner deviates from the sequencing rule, anyone can generate a proof of non-compliance.

View PDF Chat

Bayesian and Randomized Clock Auctions

2022-07-12

Michal Feldman , Vasilis Gkatzelis , Nick Gravin +1 more

In a single-parameter mechanism design problem, a provider is looking to sell some service to a group of potential buyers. Each buyer i has a private value vi for receiving … In a single-parameter mechanism design problem, a provider is looking to sell some service to a group of potential buyers. Each buyer i has a private value vi for receiving this service, and some feasibility constraint restricts which subsets of buyers can be served simultaneously. Recent work in economics introduced (deferred-acceptance) clock auctions as a superior class of auctions for this problem, due to their transparency, simplicity, and very strong incentive guarantees. Subsequent work in computer science focused on evaluating these auctions with respect to their social welfare approximation guarantees, leading to strong impossibility results: in the absence of prior information regarding the buyers' values, no deterministic clock auction can achieve a bounded approximation, even for simple feasibility constraints with only two maximal feasible sets.

View PDF Chat

Transaction Fee Mechanism Design for the Ethereum Blockchain: An Economic Analysis of EIP-1559

2020-12-01

Tim Roughgarden

EIP-1559 is a proposal to make several tightly coupled additions to Ethereum's transaction fee mechanism, including variable-size blocks and a burned base fee that rises and falls with demand. This … EIP-1559 is a proposal to make several tightly coupled additions to Ethereum's transaction fee mechanism, including variable-size blocks and a burned base fee that rises and falls with demand. This report assesses the game-theoretic strengths and weaknesses of the proposal and explores some alternative designs.

Ultra power and ultra exponential functions

2006-06-27

M. H. Hooshmand

Supposing that a is a positive real number, then for each natural number n, the notation a n is called a to the ultra power of n , and we … Supposing that a is a positive real number, then for each natural number n, the notation a n is called a to the ultra power of n , and we define by In the other words, , n times. In [Euler, L., De formulis exponentialibus replicatus, Acta Academiac Petropolitenae, 1, 38–60.] the necessary and sufficient condition for the convergence of lim n→∞ a n is proved by Euler and in [Baker, I.N. and Rippon, P.J., 1983 Baker, I. N. and Rippon, P. J. 1983. Convergence of infinite exponentials. Annales Academiac Scentiarium Fennicae. Mathematika. 8: 179–186. Series AI [Google Scholar], Convergence of infinite exponentials. Annales Academiac Scentiarium Fennicae Mathematika Series AI., 8, 179–186] it is studied for the case a∊ℂ. Also in Macdonnell, J. [1989, Some critical points on the hyperpower function n x = x x⋮ International Journal of Mathematical Education in Science and Technology, 20(2), 297–305.], by supposing a = x be variable, some property of the function f(x)=lim n→∞ x n is introduced. But, in this paper, we want to introduce and discuss a different topic, considering the following explanation: we can consider the serial operations as production, power and ultra power respectively. As we know, due to algebraic properties of power, it can be extended from natural to rational numbers (and then other numbers) but this cannot be done for ultra power, because it does not have any useful algebraic properties except . Perhaps this is the reason that ultra power is not extended so far. For removing this problem, we first introduce the following functional equation and then study some of its properties (If f be a function satisfying the equation, then f(n)=a n for all natural n). We state and prove a uniqueness theorem about the above functional equation and extend the definition of ultra power by it. Also, we introduce the new functions uxp a (ultra exponential functions) and study their properties.

Cryptographic protocols for Vickrey auctions

1993-11-01

Hannu Nurmi , Arto Salomaa

Extreme-Value Theorems for Optimal Multidimensional Pricing

2011-10-01

Yang Cai , Constantinos Daskalakis

We provide a Polynomial Time Approximation Scheme for the multi-dimensional unit-demand pricing problem, when the buyer's values are independent (but not necessarily identically distributed.) For all ϵ >; 0, we … We provide a Polynomial Time Approximation Scheme for the multi-dimensional unit-demand pricing problem, when the buyer's values are independent (but not necessarily identically distributed.) For all ϵ >; 0, we obtain a (1 + ϵ)-factor approximation to the optimal revenue in time polynomial, when the values are sampled from Monotone Hazard Rate (MHR) distributions, quasi-polynomial, when sampled from regular distributions, and polynomial in n poly(log r) when sampled from general distributions supported on a set [u min ,ru min ]. We also provide an additive PTAS for all bounded distributions. Our algorithms are based on novel extreme value theorems for MHR and regular distributions, and apply probabilistic techniques to understand the statistical properties of revenue distributions, as well as to reduce the size of the search space of the algorithm. As a byproduct of our techniques, we establish structural properties of optimal solutions. We show that, for all ϵ >; 0, g(1/ϵ) distinct prices suffice to obtain a (1 + ϵ)-factor approximation to the optimal revenue for MHR distributions, where g(1/ϵ) is a quasi-linear function of 1/ϵ that does not depend on the number of items. Similarly, for all ϵ >; 0 and n >; 0, g(1/ϵ · log n) distinct prices suffice for regular distributions, where n is the number of items and g(·) is a polynomial function. Finally, in the i.i.d. MHR case, we show that, as long as the number of items is a sufficiently large function of 1/ϵ, a single price suffices to achieve a (1 + ϵ)-factor approximation. Our results represent significant progress to the single-bidder case of the multidimensional optimal mechanism design problem, following Myerson's celebrated work on optimal mechanism design [Myerson 1981].

View PDF Chat

The sample complexity of revenue maximization

2014-05-31

Richard Cole , Tim Roughgarden

In the design and analysis of revenue-maximizing auctions, auction performance is typically measured with respect to a prior distribution over inputs. The most obvious source for such a distribution is … In the design and analysis of revenue-maximizing auctions, auction performance is typically measured with respect to a prior distribution over inputs. The most obvious source for such a distribution is past data. The goal of this paper is to understand how much data is necessary and sufficient to guarantee near-optimal expected revenue.

View PDF Chat