-
Natural Language Mechanisms via Self-Resolution with Foundation Models
Authors:
Nicolas Della Penna
Abstract:
Practical mechanisms often limit agent reports to constrained formats like trades or orderings, potentially limiting the information agents can express. We propose a novel class of mechanisms that elicit agent reports in natural language and leverage the world-modeling capabilities of large language models (LLMs) to select outcomes and assign payoffs. We identify sufficient conditions for these me…
▽ More
Practical mechanisms often limit agent reports to constrained formats like trades or orderings, potentially limiting the information agents can express. We propose a novel class of mechanisms that elicit agent reports in natural language and leverage the world-modeling capabilities of large language models (LLMs) to select outcomes and assign payoffs. We identify sufficient conditions for these mechanisms to be incentive-compatible and efficient as the LLM being a good enough world model and a strong inter-agent information over-determination condition. We show situations where these LM-based mechanisms can successfully aggregate information in signal structures on which prediction markets fail.
△ Less
Submitted 10 July, 2024;
originally announced July 2024.
-
Towards Optimal Prior-Free Permissionless Rebate Mechanisms, with applications to Automated Market Makers & Combinatorial Orderflow Auctions
Authors:
Bruno Mazorra,
Nicolás Della Penna
Abstract:
Maximal Extractable Value (MEV) has become a critical issue for blockchain ecosystems, as it enables validators or block proposers to extract value by ordering, including or censoring users' transactions. This paper aims to present a formal approach for determining the appropriate compensation for users whose transactions are executed in bundles, as opposed to individually. We explore the impact o…
▽ More
Maximal Extractable Value (MEV) has become a critical issue for blockchain ecosystems, as it enables validators or block proposers to extract value by ordering, including or censoring users' transactions. This paper aims to present a formal approach for determining the appropriate compensation for users whose transactions are executed in bundles, as opposed to individually. We explore the impact of MEV on users, discuss the Shapley value as a solution for fair compensation, and delve into the mechanisms of MEV rebates and auctions as a means to undermine the power of the block producer.
△ Less
Submitted 29 June, 2023;
originally announced June 2023.
-
The Cost of Sybils, Credible Commitments, and False-Name Proof Mechanisms
Authors:
Bruno Mazorra,
Nicolás Della Penna
Abstract:
Consider a mechanism that cannot observe how many players there are directly, but instead must rely on their self-reports to know how many are participating. Suppose the players can create new identities to report to the auctioneer at some cost $c$. The usual mechanism design paradigm is equivalent to implicitly assuming that $c$ is infinity for all players, while the usual Sybil attacks literatur…
▽ More
Consider a mechanism that cannot observe how many players there are directly, but instead must rely on their self-reports to know how many are participating. Suppose the players can create new identities to report to the auctioneer at some cost $c$. The usual mechanism design paradigm is equivalent to implicitly assuming that $c$ is infinity for all players, while the usual Sybil attacks literature is that it is zero or finite for one player (the attacker) and infinity for everyone else (the 'honest' players). The false-name proof literature largely assumes the cost to be 0. We consider a model with variable costs that unifies these disparate streams.
A paradigmatic normal form game can be extended into a Sybil game by having the action space by the product of the feasible set of identities to create action where each player chooses how many players to present as in the game and their actions in the original normal form game. A mechanism is (dominant) false-name proof if it is (dominant) incentive-compatible for all the players to self-report as at most one identity. We study mechanisms proposed in the literature motivated by settings where anonymity and self-identification are the norms, and show conditions under which they are not Sybil-proof. We characterize a class of dominant Sybil-proof mechanisms for reward sharing and show that they achieve the efficiency upper bound. We consider the extension when agents can credibly commit to the strategy of their sybils and show how this can break mechanisms that would otherwise be false-name proof.
△ Less
Submitted 29 June, 2023; v1 submitted 30 January, 2023;
originally announced January 2023.
-
Constant Function Market Making, Social Welfare and Maximal Extractable Value
Authors:
Bruno Mazorra,
Nicolás Della Penna
Abstract:
We consider the social welfare that can be facilitated by a constant function market maker (CFMM). When there is sufficient liquidity available to the CFMM, it can approximate the optimal social welfare when all users transactions are executed. When one of the agent has the role of proposing the block, and blockspace is scarce, they can obtain higher expected utility than otherwise identical agent…
▽ More
We consider the social welfare that can be facilitated by a constant function market maker (CFMM). When there is sufficient liquidity available to the CFMM, it can approximate the optimal social welfare when all users transactions are executed. When one of the agent has the role of proposing the block, and blockspace is scarce, they can obtain higher expected utility than otherwise identical agents. This gives a lower bound on the maximal extractable value exposed when blockspace is scarce.
△ Less
Submitted 23 November, 2022; v1 submitted 14 November, 2022;
originally announced November 2022.
-
Towards Prior-Free Approximately Truthful One-Shot Auction Learning via Differential Privacy
Authors:
Daniel Reusche,
Nicolás Della Penna
Abstract:
Designing truthful, revenue maximizing auctions is a core problem of auction design. Multi-item settings have long been elusive. Recent work (arXiv:1706.03459) introduces effective deep learning techniques to find such auctions for the prior-dependent setting, in which distributions about bidder preferences are known. One remaining problem is to obtain priors in a way that excludes the possibility…
▽ More
Designing truthful, revenue maximizing auctions is a core problem of auction design. Multi-item settings have long been elusive. Recent work (arXiv:1706.03459) introduces effective deep learning techniques to find such auctions for the prior-dependent setting, in which distributions about bidder preferences are known. One remaining problem is to obtain priors in a way that excludes the possibility of manipulating the resulting auctions. Using techniques from differential privacy for the construction of approximately truthful mechanisms, we modify the RegretNet approach to be applicable to the prior-free setting. In this more general setting, no distributional information is assumed, but we trade this property for worse performance. We present preliminary empirical results and qualitative analysis for this work in progress.
△ Less
Submitted 31 March, 2021;
originally announced April 2021.
-
An Experimental Study of Cryptocurrency Market Dynamics
Authors:
Peter M Krafft,
Nicolás Della Penna,
Alex Pentland
Abstract:
As cryptocurrencies gain popularity and credibility, marketplaces for cryptocurrencies are growing in importance. Understanding the dynamics of these markets can help to assess how viable the cryptocurrnency ecosystem is and how design choices affect market behavior. One existential threat to cryptocurrencies is dramatic fluctuations in traders' willingness to buy or sell. Using a novel experiment…
▽ More
As cryptocurrencies gain popularity and credibility, marketplaces for cryptocurrencies are growing in importance. Understanding the dynamics of these markets can help to assess how viable the cryptocurrnency ecosystem is and how design choices affect market behavior. One existential threat to cryptocurrencies is dramatic fluctuations in traders' willingness to buy or sell. Using a novel experimental methodology, we conducted an online experiment to study how susceptible traders in these markets are to peer influence from trading behavior. We created bots that executed over one hundred thousand trades costing less than a penny each in 217 cryptocurrencies over the course of six months. We find that individual "buy" actions led to short-term increases in subsequent buy-side activity hundreds of times the size of our interventions. From a design perspective, we note that the design choices of the exchange we study may have promoted this and other peer influence effects, which highlights the potential social and economic impact of HCI in the design of digital institutions.
△ Less
Submitted 24 April, 2018; v1 submitted 17 January, 2018;
originally announced January 2018.
-
Human collective intelligence as distributed Bayesian inference
Authors:
Peter M. Krafft,
Julia Zheng,
Wei Pan,
Nicolás Della Penna,
Yaniv Altshuler,
Erez Shmueli,
Joshua B. Tenenbaum,
Alex Pentland
Abstract:
Collective intelligence is believed to underly the remarkable success of human society. The formation of accurate shared beliefs is one of the key components of human collective intelligence. How are accurate shared beliefs formed in groups of fallible individuals? Answering this question requires a multiscale analysis. We must understand both the individual decision mechanisms people use, and the…
▽ More
Collective intelligence is believed to underly the remarkable success of human society. The formation of accurate shared beliefs is one of the key components of human collective intelligence. How are accurate shared beliefs formed in groups of fallible individuals? Answering this question requires a multiscale analysis. We must understand both the individual decision mechanisms people use, and the properties and dynamics of those mechanisms in the aggregate. As of yet, mathematical tools for such an approach have been lacking. To address this gap, we introduce a new analytical framework: We propose that groups arrive at accurate shared beliefs via distributed Bayesian inference. Distributed inference occurs through information processing at the individual level, and yields rational belief formation at the group level. We instantiate this framework in a new model of human social decision-making, which we validate using a dataset we collected of over 50,000 users of an online social trading platform where investors mimic each others' trades using real money in foreign exchange and other asset markets. We find that in this setting people use a decision mechanism in which popularity is treated as a prior distribution for which decisions are best to make. This mechanism is boundedly rational at the individual level, but we prove that in the aggregate implements a type of approximate "Thompson sampling"---a well-known and highly effective single-agent Bayesian machine learning algorithm for sequential decision-making. The perspective of distributed Bayesian inference therefore reveals how collective rationality emerges from the boundedly rational decision mechanisms people use.
△ Less
Submitted 5 August, 2016;
originally announced August 2016.
-
Compliance-Aware Bandits
Authors:
Nicolás Della Penna,
Mark D. Reid,
David Balduzzi
Abstract:
Motivated by clinical trials, we study bandits with observable non-compliance. At each step, the learner chooses an arm, after, instead of observing only the reward, it also observes the action that took place. We show that such noncompliance can be helpful or hurtful to the learner in general. Unfortunately, naively incorporating compliance information into bandit algorithms loses guarantees on s…
▽ More
Motivated by clinical trials, we study bandits with observable non-compliance. At each step, the learner chooses an arm, after, instead of observing only the reward, it also observes the action that took place. We show that such noncompliance can be helpful or hurtful to the learner in general. Unfortunately, naively incorporating compliance information into bandit algorithms loses guarantees on sublinear regret. We present hybrid algorithms that maintain regret bounds up to a multiplicative factor and can incorporate compliance information. Simulations based on real data from the International Stoke Trial show the practical potential of these algorithms.
△ Less
Submitted 8 February, 2016;
originally announced February 2016.
-
Popularity and Performance: A Large-Scale Study
Authors:
Peter Krafft,
Julia Zheng,
Erez Shmueli,
Nicolás Della Penna,
Josh Tenenbaum,
Sandy Pentland
Abstract:
Social scientists have long sought to understand why certain people, items, or options become more popular than others. One seemingly intuitive theory is that inherent value drives popularity. An alternative theory claims that popularity is driven by the rich-get-richer effect of cumulative advantage---certain options become more popular, not because they are higher quality, but because they are a…
▽ More
Social scientists have long sought to understand why certain people, items, or options become more popular than others. One seemingly intuitive theory is that inherent value drives popularity. An alternative theory claims that popularity is driven by the rich-get-richer effect of cumulative advantage---certain options become more popular, not because they are higher quality, but because they are already relatively popular. Realistically, it seems likely that popularity is driven by neither one of these forces alone but rather both together. Recently, researchers have begun using large-scale online experiments to study the effect of cumulative advantage in realistic scenarios, but there have been no large-scale studies of the combination of these two effects. We are interested in studying a case where decision-makers observe explicit signals of both the popularity and the quality of various options. We derive a model for change in popularity as a function of past popularity and past perceived quality. Our model implies that we should expect an interaction between these two forces---popularity should amplify the effect of quality, so that the more popular an option is, the faster we expect it to increase in popularity with better perceived quality. We use a data set from eToro.com, an online social investment platform, to support this hypothesis.
△ Less
Submitted 30 June, 2014;
originally announced June 2014.
-
Crowd & Prejudice: An Impossibility Theorem for Crowd Labelling without a Gold Standard
Authors:
Nicolás Della Penna,
Mark D. Reid
Abstract:
A common use of crowd sourcing is to obtain labels for a dataset. Several algorithms have been proposed to identify uninformative members of the crowd so that their labels can be disregarded and the cost of paying them avoided. One common motivation of these algorithms is to try and do without any initial set of trusted labeled data. We analyse this class of algorithms as mechanisms in a game-theo…
▽ More
A common use of crowd sourcing is to obtain labels for a dataset. Several algorithms have been proposed to identify uninformative members of the crowd so that their labels can be disregarded and the cost of paying them avoided. One common motivation of these algorithms is to try and do without any initial set of trusted labeled data. We analyse this class of algorithms as mechanisms in a game-theoretic setting to understand the incentives they create for workers. We find an impossibility result that without any ground truth, and when workers have access to commonly shared 'prejudices' upon which they agree but are not informative of true labels, there is always equilibria where all agents report the prejudice. A small amount amount of gold standard data is found to be sufficient to rule out these equilibria.
△ Less
Submitted 16 April, 2012;
originally announced April 2012.
-
Bandit Market Makers
Authors:
Nicolas Della Penna,
Mark D. Reid
Abstract:
We introduce a modular framework for market making. It combines cost-function based automated market makers with bandit algorithms. We obtain worst-case profits guarantee's relative to the best in hindsight within a class of natural "overround" cost functions . This combination allow us to have distribution-free guarantees on the regret of profits while preserving the bounded worst-case losses and…
▽ More
We introduce a modular framework for market making. It combines cost-function based automated market makers with bandit algorithms. We obtain worst-case profits guarantee's relative to the best in hindsight within a class of natural "overround" cost functions . This combination allow us to have distribution-free guarantees on the regret of profits while preserving the bounded worst-case losses and computational tractability over combinatorial spaces of the cost function based approach. We present simulation results to better understand the practical behaviour of market makers from the framework.
△ Less
Submitted 1 August, 2013; v1 submitted 30 November, 2011;
originally announced December 2011.
