Mechanisms that play a game, not toss a coin

• URL: http://arxiv.org/abs/2308.10413v2
• Date: Tue, 14 May 2024 20:34:27 GMT
• Title: Mechanisms that play a game, not toss a coin
• Authors: Toby Walsh,
• Abstract summary: We propose to derandomize randomized mechanisms by having agents play a game instead of tossing a coin. This derandomization retains many of the good normative properties of the original mechanism but gives a mechanism that is deterministic and easy to audit.
• Score: 18.168659230989384
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Randomized mechanisms can have good normative properties compared to their deterministic counterparts. However, randomized mechanisms are problematic in several ways such as in their verifiability. We propose here to derandomize such mechanisms by having agents play a game instead of tossing a coin. The game is designed so an agent's best action is to play randomly, and this play then injects ``randomness'' into the mechanism. This derandomization retains many of the good normative properties of the original randomized mechanism but gives a mechanism that is deterministic and easy, for instance, to audit. We consider three related methods to derandomize randomized mechanism in six different domains: voting, facility location, task allocation, school choice, peer selection, and resource allocation. We propose a number of novel derandomized mechanisms for these six domains with good normative properties. Each mechanism has a mixed Nash equilibrium in which agents play a modular arithmetic game with an uniform mixed strategy. In all but one mixed Nash equilibrium, agents report their preferences over the original problem sincerely. The derandomized methods are thus ``quasi-strategy proof''. In one domain, we additionally show that a new and desirable normative property emerges as a result of derandomization.

Related papers

• Correcting Subverted Random Oracles [55.4766447972367]
  We prove that a simple construction can transform a "subverted" random oracle which disagrees with the original one at a small fraction of inputs into an object that is indifferentiable from a random function. Our results permit future designers of cryptographic primitives in typical kleptographic settings to use random oracles as a trusted black box.
  arXiv  Detail & Related papers  (2024-04-15T04:01:50Z)
• A Game-theoretic Approach for Provably-Uniform Random Number Generation in Decentralized Networks [0.6216023343793144]
  We provide a protocol for distributed generation of randomness. It is trustless and generates unbiased random numbers. It is also tamper-proof and no party can change the output or affect its distribution.
  arXiv  Detail & Related papers  (2023-09-20T12:21:39Z)
• Strategic Resource Selection with Homophilic Agents [48.83208975886834]
  We propose Resource Selection Games with heterogeneous agents that strive for joint resource usage with similar agents. Our model considers agents with different types and the decisive feature is the fraction of same-type agents among the users. We show that this type of bounded rationality yields favorable game-theoretic properties.
  arXiv  Detail & Related papers  (2023-05-01T14:14:58Z)
• Randomness: what is it and why does it matter? [0.0]
  A widely accepted definition of randomness lacks scientific rigor and its results are questionable. I propose an information-theory-based definition of randomness which focuses on the physical process of random number generation itself. A new quantity named "randomness deviation" allows for a practical measure of quality of a random number generating process or a device.
  arXiv  Detail & Related papers  (2023-03-14T16:38:16Z)
• Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location Mechanism [103.36492220921109]
  We show that although Strong Proportionality is a well-motivated and basic axiom, there is no deterministic strategyproof mechanism satisfying the property. We then identify a randomized mechanism called Random Rank which satisfies Strong Proportionality in expectation. Our main characterizes Random Rank as the unique mechanism that achieves universal truthfulness, universal anonymity, and Strong Proportionality in expectation.
  arXiv  Detail & Related papers  (2022-05-30T00:51:57Z)
• Using Non-Stationary Bandits for Learning in Repeated Cournot Games with Non-Stationary Demand [11.935419090901524]
  In this paper, we model repeated Cournot games with non-stationary demand. The set of arms/actions that an agent can choose from represents discrete production quantities. We propose a novel algorithm 'Adaptive with Weighted Exploration (AWE) $epsilon$-greedy' which is remotely based on the well-known $epsilon$-greedy approach.
  arXiv  Detail & Related papers  (2022-01-03T05:51:47Z)
• Towards General Function Approximation in Zero-Sum Markov Games [126.58493169301012]
  This paper considers two-player zero-sum finite-horizon Markov games with simultaneous moves. Provably efficient algorithms for both decoupled and coordinated settings are developed.
  arXiv  Detail & Related papers  (2021-07-30T15:25:13Z)
• Rational Verification for Probabilistic Systems [2.4254101826561847]
  We develop the theory and algorithms for rational verification in probabilistic systems. We focus on concurrent games (CSGs), which can be used to model uncertainty and randomness in complex multi-agent environments.
  arXiv  Detail & Related papers  (2021-07-19T19:24:16Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values. We first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism. Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets.
  arXiv  Detail & Related papers  (2020-04-19T18:00:58Z)
• Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
  We introduce a theory for multi-armed bandits where the values are the modes of the reward distributions instead of the mean. We show in simulations that our algorithms are robust to perturbation of the arms by adversarial noise sequences.
  arXiv  Detail & Related papers  (2020-03-05T21:29:27Z)

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.