Optimal Reward Allocation via Proportional Splitting

• URL: http://arxiv.org/abs/2503.10185v1
• Date: Thu, 13 Mar 2025 09:14:29 GMT
• Title: Optimal Reward Allocation via Proportional Splitting
• Authors: Lukas Aumayr, Zeta Avarikioti, Dimitris Karakostas, Karl Kreder, Shreekara Shastry,
• Abstract summary: We introduce a reward allocation mechanism, called Proportional Splitting (PRS), which outperforms existing state of the art.<n>On the theoretical side, we show that our protocol combined with PRS is an equilibrium and guarantees fairness, similar to FruitChains.
• Score: 4.258375398293221
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Following the publication of Bitcoin's arguably most famous attack, selfish mining, various works have introduced mechanisms to enhance blockchain systems' game theoretic resilience. Some reward mechanisms, like FruitChains, have been shown to be equilibria in theory. However, their guarantees assume non-realistic parameters and their performance degrades significantly in a practical deployment setting. In this work we introduce a reward allocation mechanism, called Proportional Splitting (PRS), which outperforms existing state of the art. We show that, for large enough parameters, PRS is an equilibrium, offering the same theoretical guarantees as the state of the art. In addition, for practical, realistically small, parameters, PRS outperforms all existing reward mechanisms across an array of metrics. We implement PRS on top of a variant of PoEM, a Proof-of-Work (PoW) protocol that enables a more accurate estimation of each party's mining power compared to e.g., Bitcoin. We then evaluate PRS both theoretically and in practice. On the theoretical side, we show that our protocol combined with PRS is an equilibrium and guarantees fairness, similar to FruitChains. In practice, we compare PRS with an array of existing reward mechanisms and show that, assuming an accurate estimation of the mining power distribution, it outperforms them across various well-established metrics. Finally, we realize this assumption by approximating the power distribution via low-work objects called "workshares" and quantify the tradeoff between the approximation's accuracy and storage overhead.

Related papers

• Unveil Sources of Uncertainty: Feature Contribution to Conformal Prediction Intervals [0.3495246564946556]
  We propose a novel, model-agnostic uncertainty attribution (UA) method grounded in conformal prediction (CP)<n>We define cooperative games where CP interval properties-such as width and bounds-serve as value functions, we attribute predictive uncertainty to input features.<n>Our experiments on synthetic benchmarks and real-world datasets demonstrate the practical utility and interpretative depth of our approach.
  arXiv  Detail & Related papers  (2025-05-19T13:49:05Z)
• Fully Automated Selfish Mining Analysis in Efficient Proof Systems Blockchains [5.864854777864723]
  We study selfish mining attacks in longest-chain blockchains like Bitcoin, but where the proof of work is replaced with efficient proof systems. We propose a novel selfish mining attack that aims to maximize expected relative revenue of the adversary. We present a formal analysis procedure which computes an $epsilon$-tight lower bound on the optimal expected relative revenue in the MDP.
  arXiv  Detail & Related papers  (2024-05-07T15:44:39Z)
• Pairwise Ranking Losses of Click-Through Rates Prediction for Welfare Maximization in Ad Auctions [12.67468905841272]
  We study the design of loss functions for click-through rates (CTR) to optimize (social) welfare in advertising auctions. We propose a novel weighted rankloss to train the CTR model. We demonstrate the advantages of the proposed loss on synthetic and real-world data.
  arXiv  Detail & Related papers  (2023-06-01T15:42:50Z)
• Distributional Reinforcement Learning with Dual Expectile-Quantile Regression [51.87411935256015]
  quantile regression approach to distributional RL provides flexible and effective way of learning arbitrary return distributions. We show that distributional guarantees vanish, and we empirically observe that the estimated distribution rapidly collapses to its mean estimation. Motivated by the efficiency of $L$-based learning, we propose to jointly learn expectiles and quantiles of the return distribution in a way that allows efficient learning while keeping an estimate of the full distribution of returns.
  arXiv  Detail & Related papers  (2023-05-26T12:30:05Z)
• Distributional Reward Estimation for Effective Multi-Agent Deep Reinforcement Learning [19.788336796981685]
  We propose a novel Distributional Reward Estimation framework for effective Multi-Agent Reinforcement Learning (DRE-MARL) Our main idea is to design the multi-action-branch reward estimation and policy-weighted reward aggregation for stabilized training. The superiority of the DRE-MARL is demonstrated using benchmark multi-agent scenarios, compared with the SOTA baselines in terms of both effectiveness and robustness.
  arXiv  Detail & Related papers  (2022-10-14T08:31:45Z)
• Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward [66.81579829897392]
  We propose a novel offline reinforcement learning algorithm called Pessimistic vAlue iteRaTion with rEward Decomposition (PARTED) PARTED decomposes the trajectory return into per-step proxy rewards via least-squares-based reward redistribution, and then performs pessimistic value based on the learned proxy reward. To the best of our knowledge, PARTED is the first offline RL algorithm that is provably efficient in general MDP with trajectory-wise reward.
  arXiv  Detail & Related papers  (2022-06-13T19:11:22Z)
• On Scheduling Mechanisms Beyond the Worst Case [17.281501828240877]
  We find that mechanism K achieves a smaller social cost than mechanism P on every input. We also find that the average-case approximation ratio of mechanism P converges to the same constant.
  arXiv  Detail & Related papers  (2022-04-14T20:57:50Z)
• Monotonic Improvement Guarantees under Non-stationarity for Decentralized PPO [66.5384483339413]
  We present a new monotonic improvement guarantee for optimizing decentralized policies in cooperative Multi-Agent Reinforcement Learning (MARL) We show that a trust region constraint can be effectively enforced in a principled way by bounding independent ratios based on the number of agents in training.
  arXiv  Detail & Related papers  (2022-01-31T20:39:48Z)
• Top $K$ Ranking for Multi-Armed Bandit with Noisy Evaluations [102.32996053572144]
  We consider a multi-armed bandit setting where, at the beginning of each round, the learner receives noisy independent evaluations of the true reward of each arm. We derive different algorithmic approaches and theoretical guarantees depending on how the evaluations are generated.
  arXiv  Detail & Related papers  (2021-12-13T09:48:54Z)
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization [68.8204255655161]
  We show that the MARINA method of Gorbunov et al (2021) can be considered as a state-of-the-art method in terms of theoretical communication complexity. Theory of MARINA to support the theory of potentially em correlated compressors, extends to the method beyond the classical independent compressors setting.
  arXiv  Detail & Related papers  (2021-10-07T09:38:15Z)
• Forecasting Bitcoin closing price series using linear regression and neural networks models [4.17510581764131]
  We study how to forecast daily closing price series of Bitcoin using data prices and volumes of prior days. We followed different approaches in parallel, implementing both statistical techniques and machine learning algorithms.
  arXiv  Detail & Related papers  (2020-01-04T21:04:05Z)
• Generalization Guarantees for Multi-item Profit Maximization: Pricing, Auctions, and Randomized Mechanisms [86.81403511861788]
  We study multi-item profit when there is an underlying distribution over buyers' values. For any set of buyers' values, profit is piecewise linear in the mechanism's parameters. We prove new bounds for mechanism classes not yet in the sample-based mechanism design literature.
  arXiv  Detail & Related papers  (2017-04-29T22:02:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.