Schedule, Notes/Handouts & Videos

We introduce two extensions of the Walrasian mechanism for quasilinear economies to allow agents to report non-concave values and non-convex costs. The extended mechanisms, which always deliver feasible, near-efficient allocations with no budget deficit, are computationally undemanding and nearly incentive-compatible. We also introduce an extension of the First Welfare Theorem allowing us to upper bound the welfare losses from these mechanisms.

Product-mix auctions are sealed-bid mechanisms for trading multiple units of multiple differentiated goods. They implement competitive-equilibrium allocations based on the preferences that participants express in a geometric language. Versions we have implemented are easy to use and understand. All concave substitutes (respectively, strong substitutes) preferences can be uniquely represented, and no other preferences can be represented, by appropriate sets of permitted bids in the corresponding version of this language. These languages thus also provide new characterizations of ordinary substitutes, and of strong substitutes. We discuss implementation of the auctions, and extensions and variants of the language, e.g., allowing for budget constraints.

Socio economic forces, development in generation technologies and environmental considerations have led over two decades ago to restructuring of the electric power systems in the US and in many systems worldwide, transforming them from vertically integrated regulated monopolies to competitive market based systems. This talk will review the basic structure and elements of the prevailing Standard Market Design adopted in the US under FERC guidance. I will also sketch the theoretical foundation underlying this design, which is based on strong convexity assumption that do not hold in practice. I will then describe alternative approaches and recent developments focusing on price formation that attempt to address distortions due to non convexities. These distortion have become more prominent and problematic due to the increased share of intermittent renewable resources in the electricity supply mix.

An obstacle to using market mechanisms to allocate indivisible goods (such as courses to students) is the non-existence of competitive equilibria (CE). To surmount this, Arrow and Hahn proposed the notion of social-approximate equilibria: a price vector and corresponding excess demands that are `small'. We identify a class of preferences called $\Delta$-substitutes, and show that social approximate equilibria where the bound on excess demand, good-by-good, is $2(\Delta-1)$ independent of the size of the economy. When $\Delta=1$ existence of CE is guaranteed even in the presence of income effects. This sufficient condition strictly generalizes prior conditions.

These results rely on a new type of Shapley-Folkman-Starr Lemma which could be of independent interest.

This is joint work with Thanh Nguyen.

The Fisher market is one of the most fundamental models for resource allocation. However, classical Fisher markets (i) only consider two types of constraints, i.e., budgets of individual buyers and capacities of goods, and (ii) involve a complete information setting wherein buyers' utilities are known, and all the transactions happen in a static market. In this talk, we present generalizations of classical Fisher markets to settings when agents have additional linear constraints and when buyers arrive at the market sequentially with utilities and budgets that are not known a priori to the market designer.

We first introduce Fisher markets with additional linear constraints and study the properties of the resulting equilibria. Notably, the addition of linear constraints introduces non-convexities into Fisher markets as the equilibrium price set may be non-convex, and computing equilibria is, in general, PPAD-hard. Yet, to set equilibrium prices, we introduce a budget-adjusted social optimization problem (BA-SOP), whose optimal dual variables correspond to the equilibrium prices. Further, since solving BA-SOP can be computationally intensive and requires centralized knowledge of all agents' utilities, we propose a new class of distributed algorithms based on the Alternating Direction Method of Multipliers (ADMM) to compute equilibrium prices.

Next, we extend the above-mentioned distributed implementation to the online setting when agents arrive sequentially at the market with privately known utility and budget parameters drawn i.i.d. from some distribution. In this setting, we study the performance limitations of static pricing approaches, which set the same prices for all users, and develop two adaptive pricing algorithms, one with knowledge of the distribution and another that solely relies on past observations of user consumption, i.e., revealed preference feedback, with improved performance guarantees. 

Over the last two decades we have developed good understanding how to quantify the impact of strategic user behavior on outcomes in many games (including traffic routing and online auctions) and showed that the resulting bounds extend to repeated games assuming players use a form of no-regret learning to adapt to the environment. We will review how this area evolved since its early days, and also discuss some of the new frontiers, including when repeated interactions have carry-over effects between rounds: when outcomes in one round effect the game in the future, as is the case in many applications. In this talk, we study this phenomenon in the context of a game modeling repeated auction with budgets and queuing systems: routers compete for servers, where packets that do not get served need to be resent, resulting in a system where the number of packets at each round depends on the success of the routers in the previous rounds. In joint work with Giannis Fikioris and Jason Gaitonde respectively, we analyze the resulting highly dependent random processes, and show bounds on the resulting budgeted welfare for auctions and the excess server capacity needed to guarantee that all packets get served in the queuing system despite the selfish (myopic) behavior of the participants.

Contract theory is the study of economic incentives when parties transact in the presence of information asymmetries.  We augment classical contract theory to incorporate a role for learning from data, where the overall goal of the adaptive mechanism is to obtain desired statistical behavior.  We consider applications of this framework to problems in federated learning, the delegation of data collection, and principal-agent regulatory mechanisms.

Equilibrium problems in Bayesian auction games can be described as systems of differential equations. Depending on the model assumptions, these equations might be such that we do not have a rigorous mathematical solution theory. The lack of analytical or numerical techniques with guaranteed convergence for the equilibrium problem has plagued the field and limited equilibrium analysis to rather simple auction models such as single-object auctions. Recent progress in equilibrium learning led to algorithms that find equilibrium under a wide variety of model assumptions. The talk will summarize empirical results and theoretical insights on the convergence of equilibrium learning algorithms.

In this talk, we will be focusing on learning in two-player games. We will provide a brief introduction on the possible behaviors of learning algorithms and will mention various techniques that have been heavily used and guarantee convergence to Nash equilibria in zero-sum games. Finally we will show how these techniques can be used to learn Nash equilibria in rank-1 games and what implications these techniques have for general-sum games.

I will present new results in four directions in how computer science can inform the design of economic mechanisms and systems. First, I will discuss automated mechanism design, with a focus on the number of samples one needs from the prior distribution, and also how flexible a mechanism class one should optimize over given a number of samples. Second, I will show that there are cases where the characterization of an optimal mechanism—e.g., optimal multi-item sales mechanism—requires an exponentially long description and that may explain why manual mechanism design has not been able to solve the problem for over 40 years. Third, I will describe AI mediators. Perhaps surprisingly, an optimal communication equilibrium (of which mechanism design and information design are special cases) can be computed in polynomial time, and the recent breakthroughs in two-player imperfect-information game solving can be leveraged for the problem. I will also discuss how the mediator can steer the agents to a good equilibrium. Fourth, I present a family of no-regret learning dynamics (including optimistic mirror descent (OMD)) that either reaches a Nash equilibrium or yields welfare greater than the robust price of anarchy. This yields the best approximation bound for welfare maximization under polynomial-time algorithms. I also show that when full efficiency is guaranteed via smoothness, Nash equilibrium finding is tractable via OMD. Finally, in 2-player games, when OMD does not converge to a Nash equilibrium, OMD converges to coarse correlated equilibrium with an infinite rate of convergence, i.e., in strongly polynomial time.