We study the complexity of the classic Hylland-Zeckhauser scheme [HZ79] for one-sided matching markets. We show that the problem of finding an $epsilon$-approximate equilibrium in the HZ scheme is PPAD-hard, and this holds even when $epsilon$ is poly
nomially small and when each agent has no more than four distinct utility values. Our hardness result, when combined with the PPAD membership result of [VY21], resolves the approximation complexity of the HZ scheme. We also show that the problem of approximating the optimal social welfare (the weight of the matching) achievable by HZ equilibria within a certain constant factor is NP-hard.
We provide a new analysis of the Boltzmann equation with constant collision kernel in two space dimensions. The scaling-critical Lebesgue space is $L^2_{x,v}$; we prove global well-posedness and a version of scattering, assuming that the data $f_0$ i
s sufficiently smooth and localized, and the $L^2_{x,v}$ norm of $f_0$ is sufficiently small. The proof relies upon a new scaling-critical bilinear spacetime estimate for the collision gain term in Boltzmanns equation, combined with a novel application of the Kaniel-Shinbrot iteration.
In this paper, we continue our study of the Boltzmann equation by use of tools originating from the analysis of dispersive equations in quantum dynamics. Specifically, we focus on properties of solutions to the Boltzmann equation with collision kerne
l equal to a constant in the spatial domain $mathbb{R}^d$, $dgeq 2$, which we use as a model in this paper. Local well-posedness for this equation has been proven using the Wigner transform when $left< v right>^beta f_0 in L^2_v H^alpha_x$ for $min (alpha,beta) > frac{d-1}{2}$. We prove that if $alpha,beta$ are large enough, then it is possible to propagate moments in $x$ and derivatives in $v$ (for instance, $left< x right>^k left< abla_v right>^ell f in L^infty_T L^2_{x,v}$ if $f_0$ is nice enough). The mechanism is an exchange of regularity in return for moments of the (inverse) Wigner transform of $f$. We also prove a persistence of regularity result for the scale of Sobolev spaces $H^{alpha,beta}$; and, continuity of the solution map in $H^{alpha,beta}$. Altogether, these results allow us to conclude non-negativity of solutions, conservation of energy, and the $H$-theorem for sufficiently regular solutions constructed via the Wigner transform. Non-negativity in particular is proven to hold in $H^{alpha,beta}$ for any $alpha,beta > frac{d-1}{2}$, without any additional regularity or decay assumptions.
We use the dispersive properties of the linear Schr{o}dinger equation to prove local well-posedness results for the Boltzmann equation and the related Boltzmann hierarchy, set in the spatial domain $mathbb{R}^d$ for $dgeq 2$. The proofs are based on
the use of the (inverse) Wigner transform along with the spacetime Fourier transform. The norms for the initial data $f_0$ are weight
We prove the existence of scattering states for the defocusing cubic Gross-Pitaevskii (GP) hierarchy in ${mathbb R}^3$. Moreover, we show that an energy growth condition commonly used in the well-posedness theory of the GP hierarchy is, in a specific
sense, necessary. In fact, we prove that without the latter, there exist initial data for the focusing cubic GP hierarchy for which instantaneous blowup occurs.
We present a new, simpler proof of the unconditional uniqueness of solutions to the cubic Gross-Pitaevskii hierarchy in $R^3$. One of the main tools in our analysis is the quantum de Finetti theorem. Our uniqueness result is equivalent to the one est
ablished in the celebrated works of Erdos, Schlein and Yau, cite{esy1,esy2,esy3,esy4}.
