Chenghan Zhou

Mark Braverman, Jingyi Liu, Eric Xue et al.

In this paper, we investigate the computational hardness of finding fractional allocations to unit-demand players using competitive equilibria from equal incomes (CEEI), where we allow a small constant error in players' response to market prices (also known as an approximate Hylland-Zeckhauser equilibrium). We show that assuming the $\mathbf{(\varepsilon,δ)}$-Generalized Circuits problem is PPAD-hard (the "PCP for PPAD" conjecture), finding an approximate HZ equilibrium is also PPAD-hard. This result provides additional motivation for trying to prove the PCP for PPAD conjecture as a tool for obtaining robust computational hardness results about markets. Further, we introduce a natural restriction on approximate HZ equilibria, where players' bundles may still only be approximately optimal given the prices, but may not contain positive-price items for which the player has zero utility. We show unconditionally that there exists a constant $ε$ such that finding a restricted $ε$-HZ equilibrium is PPAD-hard.

Mark Braverman, Jingyi Liu, Eric Xue et al.

We study one-sided matchings with endowments in the absence of money. It is well-known that a competitive equilibrium may not always exist and that the strong core may be empty in this setting [Hylland and Zeckhauser, 1979]. We propose a generalization of competitive equilibria that associates each item with a multi-dimensional price. We show that this solution concept always exists and resides within the rejective core [Konovalov, 2005]. Rejective core stability is strictly stronger than weak core stability: allocations in the rejective core are elements of the weak core, but the opposite is not true. Moreover, we show that the rejective core always converges to the set of competitive equilibria with multi-dimensional prices as the economy grows, demonstrating core convergence in a setting without non-satiation.

Chenghan Zhou, Thanh H. Nguyen, Haifeng Xu

Most algorithmic studies on multi-agent information design so far have focused on the restricted situation with no inter-agent externalities; a few exceptions investigated truly strategic games such as zero-sum games and second-price auctions but have all focused only on optimal public signaling. This paper initiates the algorithmic information design of both \emph{public} and \emph{private} signaling in a fundamental class of games with negative externalities, i.e., singleton congestion games, with wide application in today's digital economy, machine scheduling, routing, etc. For both public and private signaling, we show that the optimal information design can be efficiently computed when the number of resources is a constant. To our knowledge, this is the first set of efficient \emph{exact} algorithms for information design in succinctly representable many-player games. Our results hinge on novel techniques such as developing certain "reduced forms" to compactly characterize equilibria in public signaling or to represent players' marginal beliefs in private signaling. When there are many resources, we show computational intractability results. To overcome the issue of multiple equilibria, here we introduce a new notion of equilibrium-\emph{oblivious} hardness, which rules out any possibility of computing a good signaling scheme, irrespective of the equilibrium selection rule.