More Like this

1. Markets for Efficient Public Good Allocation with Social Distancing

   Jalota, Devansh; Pavone, Marco; Qi, Qi; Ye, Yinyu (December 2020, Conference of Web and Internet Economics)

   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
2. A Market Mechanism for Truthful Bidding with Energy Storage

   Bansal, Rajni K; You, Pengcheng; Gayme, Dennice F; Mallada, Enrique (January 2022, Power Systems Computation Conference (PSCC))

   This paper proposes a market mechanism for multi-interval electricity markets with generator and storage participants. Drawing ideas from supply function bidding, we introduce a novel bid structure for storage participation that allows storage units to communicate their cost to the market using energy cycling functions that map prices to cycle depths. The resulting market-clearing process--implemented via convex programming--yields corresponding schedules and payments based on traditional energy prices for power supply and per-cycle prices for storage utilization. We illustrate the benefits of our solution by comparing the competitive equilibrium of the resulting mechanism to that of an alternative solution that uses prosumer-based bids. Our solution shows several advantages over the prosumer-based approach. It does not require a priori price estimation. It also incentivizes participants to reveal their truthful costs, thus leading to an efficient, competitive equilibrium. Numerical experiments using New York Independent System Operator (NYISO) data validate our findings. 

   more » « less
3. Markets for Public Decision-Making

   Garg, Nikhil; Goel, Ashish; Plaut, Benjamin (December 2018, Web and Internet Economics - 14th International Conference)

   A public decision-making problem consists of a set of issues, each with multiple possible alternatives, and a set of competing agents, each with a preferred alternative for each issue. We study adaptations of market economies to this setting, focusing on binary issues. Issues have prices, and each agent is endowed with artificial currency that she can use to purchase probability for her preferred alternatives (we allow randomized outcomes). We first show that when each issue has a single price that is common to all agents, market equilibria can be arbitrarily bad. This negative result motivates a different approach. We present a novel technique called "pairwise issue expansion", which transforms any public decision-making instance into an equivalent Fisher market, the simplest type of private goods market. This is done by expanding each issue into many goods: one for each pair of agents who disagree on that issue. We show that the equilibrium prices in the constructed Fisher market yield a "pairwise pricing equilibrium" in the original public decision-making problem which maximizes Nash welfare. More broadly, pairwise issue expansion uncovers a powerful connection between the public decision-making and private goods settings; this immediately yields several interesting results about public decisions markets, and furthers the hope that we will be able to find a simple iterative voting protocol that leads to near-optimum decisions. 

   more » « less
4. Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances

   Can, Bugra; Gurbuzbalaban, Mert; Zhu, Lingjiong (July 2019, Proceedings of Machine Learning Research)

   Momentum methods such as Polyak's heavy ball (HB) method, Nesterov's accelerated gradient (AG) as well as accelerated projected gradient (APG) method have been commonly used in machine learning practice, but their performance is quite sensitive to noise in the gradients. We study these methods under a first-order stochastic oracle model where noisy estimates of the gradients are available. For strongly convex problems, we show that the distribution of the iterates of AG converges with the accelerated linear rate to a ball of radius " centered at a unique invariant distribution in the 1-Wasserstein metric where  is the condition number as long as the noise variance is smaller than an explicit upper bound we can provide. Our analysis also certifies linear convergence rates as a function of the stepsize, momentum parameter and the noise variance; recovering the accelerated rates in the noiseless case and quantifying the level of noise that can be tolerated to achieve a given performance. To the best of our knowledge, these are the first linear convergence results for stochastic momentum methods under the stochastic oracle model. We also develop finer results for the special case of quadratic objectives, extend our results to the APG method and weakly convex functions showing accelerated rates when the noise magnitude is sufficiently small. 

   more » « less
5. Solving Non-smooth Constrained Programs with Lower Complexity than O(1/ε): A Primal-Dual Homotopy Smoothing Approach

   Wei, Xiaohan; Yu, Hao; Ling, Qing; Neely, Michael J. (December 2018, 32nd Conference on Neural Information Processing Systems (NeurIPS 2018), Montréal, Canada.)

   We propose a new primal-dual homotopy smoothing algorithm for a linearly constrained convex program, where neither the primal nor the dual function has to be smooth or strongly convex. The best known iteration complexity solving such a non-smooth problem is O(ε−1). In this paper, we show that by leveraging a local error bound condition on the dual function, the proposed algorithm can achieve a better primal convergence time of O 􏰕ε−2/(2+β) log2(ε−1)􏰖, where β ∈ (0, 1] is a local error bound parameter. As an example application of the general algorithm, we show that the distributed geometric median problem, which can be formulated as a constrained convex program, has its dual function non-smooth but satisfying the aforementioned local error bound condition with β = 1/2, therefore enjoying a convergence time of O 􏰕ε−4/5 log2(ε−1)􏰖. This result improves upon the O(ε−1) convergence time bound achieved by existing distributed optimization algorithms. Simulation experiments also demonstrate the performance of our proposed algorithm. 

   more » « less