More Like this

1. From Monetary to Nonmonetary Mechanism Design via Artificial Currencies

   https://doi.org/10.1287/moor.2020.1098  

   Gorokh, Artur; Banerjee, Siddhartha; Iyer, Krishnamurthy (April 2021, Mathematics of Operations Research)

   null (Ed.)

   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
2. Mechanism Design for Demand Management in Energy Communities

   https://doi.org/10.3390/g12030061  

   Wei, Xupeng; Anastasopoulos, Achilleas (September 2021, Games)

   null (Ed.)

   We consider a demand management problem in an energy community, in which several users obtain energy from an external organization such as an energy company and pay for the energy according to pre-specified prices that consist of a time-dependent price per unit of energy as well as a separate price for peak demand. Since users’ utilities are their private information, which they may not be willing to share, a mediator, known as the planner, is introduced to help optimize the overall satisfaction of the community (total utility minus total payments) by mechanism design. A mechanism consists of a message space, a tax/subsidy, and an allocation function for each user. Each user reports a message chosen from her own message space, then receives some amount of energy determined by the allocation function, and pays the tax specified by the tax function. A desirable mechanism induces a game, the Nash equilibria (NE), of which results in an allocation that coincides with the optimal allocation for the community. As a starting point, we design a mechanism for the energy community with desirable properties such as full implementation, strong budget balance and individual rationality for both users and the planner. We then modify this baseline mechanism for communities where message exchanges are allowed only within neighborhoods, and consequently, the tax/subsidy and allocation functions of each user are only determined by the messages from their neighbors. All of the desirable properties of the baseline mechanism are preserved in the distributed mechanism. Finally, we present a learning algorithm for the baseline mechanism, based on projected gradient descent, that is guaranteed to converge to the NE of the induced game. 

   more » « less
3. Large-Scale Dynamic Spectrum Access with IEEE 1900.5.2 Spectrum Consumption Models

   https://doi.org/10.1109/WCNC55385.2023.10118670  

   Netalkar, Prasad; Zahabee, Azhaan; Caicedo Bastidas, Carlos E.; Kadota, Igor; Stojadinovic, Dragoslav; Zussman, Gil; Seskar, Ivan; Raychaudhuri, Dipankar (March 2023, in Proc. IEEE WCNC’23, Mar. 2023)

   Next generation wireless services and applications, including Augmented Reality, Internet-of-Things, and Smart- Cities, will increasingly rely on Dynamic Spectrum Access (DSA) methods that can manage spectrum resources rapidly and efficiently. Advances in regulatory policies, standardization, networking, and wireless technology are enabling DSA methods on a more granular basis in terms of time, frequency, and geographical location which are key for the operation of 5G and beyond-5G networks. In this context, this paper proposes a novel DSA algorithm that leverages IEEE 1900.5.2 Spectrum Consumption Models (SCMs) which offer a mechanism for RF devices to: (i) “announce” or “declare” their intention to use the spectrum and their needs in terms of interference protection; and (ii) determine compatibility (i.e., non-interference) with existing devices. In this paper, we develop an SCM-based DSA algorithm for spectrum deconfliction in large-scale wireless network environments and evaluate this algorithm in terms of computation time, efficiency of spectrum allocation, and number of device reconfigurations due to interference using a custom simulation platform. The results demonstrate the benefits of using SCMs and their capabilities to perform fine grained spectrum assignments in dynamic and dense communication environments. 

   more » « less
4. Privacy-Preserving Mechanisms for Coordinating Airspace Usage in Advanced Air Mobility

   https://doi.org/10.1145/3732290  

   Maheshwari, Chinmay; Mendoza, Maria G; Tuck, Victoria; Su, Pan-Yang; Qin, Victor L; Seshia, Sanjit; Balakrishnan, Hamsa; Sastry, Shankar (June 2025, ACM Journal on Autonomous Transportation Systems)

   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
5. Markets Beyond Nash Welfare for Leontief Utilities

   Goel, Ashish; Hulett, Reyna; Plaut, Benjamin (December 2019, Web and Internet Economics)

   We study the allocation of divisible goods to competing agents via a market mechanism, focusing on agents with Leontief utilities. The majority of the economics and mechanism design literature has focused on \emph{linear} prices, meaning that the cost of a good is proportional to the quantity purchased. Equilibria for linear prices are known to be exactly the maximum Nash welfare allocations. \emph{Price curves} allow the cost of a good to be any (increasing) function of the quantity purchased. We show that price curve equilibria are not limited to maximum Nash welfare allocations with two main results. First, we show that an allocation can be supported by strictly increasing price curves if and only if it is \emph{group-domination-free}. A similarly characterization holds for weakly increasing price curves. We use this to show that given any allocation, we can compute strictly (or weakly) increasing price curves that support it (or show that none exist) in polynomial time. These results involve a connection to the \emph{agent-order matrix} of an allocation, which may have other applications. Second, we use duality to show that in the bandwidth allocation setting, any allocation maximizing a CES welfare function can be supported by price curves. 

   more » « less