An official website of the United States government
Non-monetary mechanisms for repeated resource allocation are gaining widespread use in many real-world settings. Our aim in this work is to study the allocative efficiency and incentive properties of simple repeated mechanisms based on artificial currencies. Within this framework, we make three main contributions: We provide a general black-box technique to convert any static monetary mechanism to a dynamic mechanism with artificial currency, that simultaneously guarantees vanishing loss in efficiency, and vanishing gains from non-truthful bidding over time. On a computational front, we show how such a mechanism can be implemented using only sample-access to the agents' type distributions, and requires roughly twice the amount of computation as needed to run the monetary mechanism alone. For settings with two agents, we show that a particular artificial currency mechanism also results in a vanishing price of anarchy. This provides additional justification for the use of artificial currency mechanisms in practice. Moreover, we show how to leverage this result to demonstrate the existence of a Bayesian incentive-compatible mechanism with vanishing efficiency loss in this setting. Our work takes a significant step towards bridging the gap between monetary and non-monetary mechanisms, and also points to several open problems.
more »
« less
From Monetary to Nonmonetary Mechanism Design via Artificial Currencies
Nonmonetary mechanisms for repeated allocation and decision making are gaining widespread use in many real-world settings. Our aim in this work is to study the performance and incentive properties of simple mechanisms based on artificial currencies in such settings. To this end, we make the following contributions: For a general allocation setting, we provide two black-box approaches to convert any one-shot monetary mechanism to a dynamic nonmonetary mechanism using an artificial currency that simultaneously guarantees vanishing gains from nontruthful reporting over time and vanishing losses in performance. The two mechanisms trade off between their applicability and their computational and informational requirements. Furthermore, for settings with two agents, we show that a particular artificial currency mechanism also results in a vanishing price of anarchy.
more »
« less
- PAR ID:
- 10240307
- Date Published:
- Journal Name:
- Mathematics of Operations Research
- ISSN:
- 0364-765X
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)Public goods are often either over-consumed in the absence of regulatory mechanisms, or remain completely unused, as in the Covid-19 pandemic, where social distance constraints are enforced to limit the number of people who can share public spaces. In this work, we plug this gap through market based mechanisms designed to efficiently allocate capacity constrained public goods. To design these mechanisms, we leverage the theory of Fisher markets, wherein each agent in the economy is endowed with an artificial currency budget that they can spend to avail public goods. While Fisher markets provide a strong methodological backbone to model resource allocation problems, their applicability is limited to settings involving two types of constraints - budgets of individual buyers and capacities of goods. Thus, we introduce a modified Fisher market, where each individual may have additional physical constraints, characterize its solution properties and establish the existence of a market equilibrium. Furthermore, to account for additional constraints we introduce a social convex optimization problem where we perturb the budgets of agents such that the KKT conditions of the perturbed social problem establishes equilibrium prices. Finally, to compute the budget perturbations we present a fixed point scheme and illustrate convergence guarantees through numerical experiments. Thus, our mechanism, both theoretically and computationally, overcomes a fundamental limitation of classical Fisher markets, which only consider capacity and budget constraints.more » « less
-
To facilitate dynamic spectrum sharing, the FCC has designated certified SAS administrators to implement their own spectrum access systems (SASs) that manage the shared spectrum usage in the novel CBRS band. As a premise, different SAS servers must conduct periodic inter-SAS coordination to synchronize service states and avoid allocation conflicts. However, SAS servers may inevitably stop service for regular upgrades, crash down, or even perform maliciously that deviate from the normal routines, posing a fundamental operation security problem — the system shall be robust against these faults to guarantee secure and efficient spectrum sharing service. Unfortunately, the incumbent inter-SAS coordination mechanism, CPAS, is prone to SAS failures and does not support real-time allocation. Recent proposals that rely on blockchain smart contracts or state machine replication mechanisms to realize fault-tolerant inter-SAS coordination require all SASs to follow a unified allocation algorithm. They however face performance bottlenecks and cannot accommodate the current fact that different SASs hold their own proprietary allocation algorithms. In this work, we propose TriSAS—a novel inter-SAS coordination mechanism to facilitate secure, efficient, and dependable spectrum allocation that is fully compatible with the existing SAS infrastructure. TriSAS decomposes the coordination process into two phases including input synchronization and decision finalization. The firstphase ensures participants share a common input set while the second one fulfills a fair and verifiable spectrum allocation selec- tion, which is generated efficiently via SAS proposers’ proprietary allocation algorithms and evaluated by a customized designed allocation evaluation algorithm (AEA), in the face of no more than one-third of malicious participants. We implemented a prototype of TriSAS on the AWS cloud computing platform and evaluated its throughput and latency performance. The results show that TriSAS achieves high transaction throughput and low latency under various practical settings.more » « less
-
Advanced Air Mobility (AAM) operations are expected to transform air transportation while challenging current air traffic management practices. By introducing a novel market-based mechanism, we address the problem of on-demand allocation of capacity-constrained airspace to AAM vehicles with heterogeneous and private valuations. We model airspace and air infrastructure as a collection of contiguous regions (or sectors) with constraints on the number of vehicles that simultaneously enter, stay, or exit each region. Vehicles request access to airspace with trajectories spanning multiple regions at different times. We use the graph structure of our airspace model to formulate the allocation problem as a path allocation problem on a time-extended graph. To ensure that the cost information of AAM vehicles remains private, we introduce a novel mechanism that allocates each vehicle a budget of “air-credits” (an artificial currency) and anonymously charges prices for traversing the edges of the time-extended graph. We seek to compute a competitive equilibrium that ensures that: (i) capacity constraints are satisfied, (ii) a strictly positive resource price implies that the sector capacity is fully utilized, and (iii) the allocation is integral and optimal for each AAM vehicle given current prices, without requiring access to individual vehicle utilities. However, a competitive equilibrium with integral allocations may not always exist. We provide sufficient conditions for the existence and computation of a fractional-competitive equilibrium, where allocations can be fractional. Building on these theoretical insights, we propose a distributed, iterative, two-step algorithm that: (1) computes a fractional competitive equilibrium, and (2) derives an integral allocation from this equilibrium. We validate the effectiveness of our approach in allocating trajectories for the emerging urban air mobility service of drone delivery.more » « less
-
In recent decades, the design of budget feasible mechanisms for a wide range of procurement auction settings has received significant attention in the Artificial Intelligence (AI) community. These procurement auction settings have practical applications in various domains such as federated learning, crowdsensing, edge computing, and resource allocation. In a basic procurement auction setting of these domains, a buyer with a limited budget is tasked with procuring items (\eg, goods or services) from strategic sellers, who have private information on the true costs of their items and incentives to misrepresent their items' true costs. The primary goal of budget feasible mechanisms is to elicit the true costs from sellers and determine items to procure from sellers to maximize the buyer valuation function for the items and ensure that the total payment to the sellers is no more than the budget. In this survey, we provide a comprehensive overview of key procurement auction settings and results of budget feasible mechanisms. We provide several promising future research directions.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1287/moor.2020.1098
