We examine fixed-price mechanisms in bilateral trade through the lens of regret minimization. Our main results are twofold. (i) For independent values, a near-optimal $\widetildeΘ(T^{2/3})$ tight bound for $\textsf{Global Budget Balance}$ fixed-price mechanisms with two-bit/one-bit feedback. (ii) For correlated/adversarial values, a near-optimal $Ω(T^{3/4})$ lower bound for $\textsf{Global Budget Balance}$ fixed-price mechanisms with two-bit/one-bit feedback, which improves the best known $Ω(T^{5/7})$ lower bound obtained in the work [BCCF24] and, up to polylogarithmic factors, matches the $\widetilde{\mathcal{O}}(T^{3 / 4})$ upper bound obtained in the same work. Our work in combination with the previous works [CCCFL24mor, CCCFL24jmlr, AFF24, BCCF24] (essentially) gives a thorough understanding of regret minimization for fixed-price bilateral trade. En route, we have developed two technical ingredients that might be of independent interest: (i) A novel algorithmic paradigm, called $\textit{fractal elimination}$, to address one-bit feedback and independent values. (ii) A new $\textit{lower-bound construction}$ with novel proof techniques, to address the $\textsf{Global Budget Balance}$ constraint and correlated values.

We propose the first local search algorithm for Euclidean clustering that attains an \(O(1)\)-approximation in almost-linear time. Specifically, for Euclidean \(k\)-Means, our algorithm achieves an \(O(c)\)-approximation in \(\tilde O(n^{1+1/c})\) time, for any constant \(c \ge 1\), maintaining the same running time as the previous (non-local-search-based) approach [la Tour and Saulpic, arXiv’2407.11217] while improving the approximation factor from \(O(c^6)\) to \(O(c)\). The algorithm generalizes to any metric space with sparse spanners, delivering efficient constant approximation in \(\ell_p\) metrics, doubling metrics, Jaccard metrics, etc.

Real-world pricing mechanisms are typically optimized using training data, a setting corresponding to the pricing query complexity problem in Mechanism Design. The previous work [11] studies the single-distribution case1, with tight bounds of ~Θ (ε-3 ) for a general distribution and ~Θ (ε-2 ) for either a regular or monotone-hazard-rate (MHR) distribution, where ε ∈ (0, 1) denotes the (additive) revenue loss of a learned uniform price relative to the Bayesian-optimal uniform price.

A large proportion of the Bayesian mechanism design literature is restricted to the family of regular distributions $\mathbb{F}_{\text {reg }}$ [Mye81] or the family of monotone hazard rate (MHR) distributions $\mathbb{F}_{M H R}$ [BMP63], which has overshadowed this rich and well-developed theory. We (re-)introduce two generalized families: quasi-regular distributions $\mathbb{F}_{Q-r e g}$ and quasi-MHR distributions $\mathbb{F}_{Q-M H R}$. Altogether, these four families form the following hierarchy: $\mathbb{F}_{\mathrm{MHR}} \subsetneq\left(\mathbb{F}_{\mathrm{reg}} \cap \mathbb{F}_{Q-\mathrm{MHR}}\right) \subsetneq \mathbb{F}_{\mathrm{reg}}, \mathbb{F}_{Q-\mathrm{MHR}} \subsetneq\left(\mathbb{F}_{\mathrm{reg}} \cup \mathbb{F}_{Q-\mathrm{MHR}}\right) \subsetneq \mathbb{F}_{Q-\mathrm{reg}}$ Likewise, the parameterized families of $\lambda$-regular (a.k.a. $\alpha$ strongly regular) distributions [CR14], [SS19], which smoothly interpolate $\mathbb{F}_{\text {reg }}$ and $\mathbb{F}_{\text {MHR }}$, generalize to $\lambda$-quasi-regular distributions. The significance of our new families is manifold. Firstly, their defining conditions are immediate “economic” relaxations of the original defining conditions (e.g., regularity as monotonicity of the virtual value functions), capturing key economic intuitions. Secondly, they satisfy natural mathematical properties (about order statistics) failed for the original families, thus technically more tractable. Thirdly, numerous results (by [BK96], [HR09a], [CD15], [DRY15], [HR14], [AHN ${ }^{+}$19], [JLTX20], [JLQ ${ }^{+}$19b], [FLR19], [GHZ19b], [JLX23], [LM24] etc) known merely for the original families now can extend to our new families. Many of these extensions incur no quantitative loss, or even improve the state of the art for the original families. Finally, beyond the third point, our new families guide us to entirely new perspectives and thus entirely unknown results. For example, regarding revenue maximization for symmetric versus asymmetric regular buyers, we acquire $\frac{1}{2}$ - versus 0.1908 -approximations for the (less-than-)one-sample prophet inequalities, respectively. To the best of our knowledge, such results are blank in the literature, despite their widely-studied welfare maximization counterparts [CDFS22], [RWW20], [CCES20], [CDF ${ }^{+}$21], [CCES24].

We study revenue maximization in the unit-demand single-buyer setting. Our main result is that Uniform-Ironed-Virtual-Value Item Pricing guarantees a tight 3-approximation to the Duality Relaxation Benchmark [Chawla-Malec-Sivan, EC’10/GEB’15; Cai-Devanur-Weinberg, STOC’16/ SICOMP’21], breaking the barrier of 4 since [Chawla-Hartline-Malec-Sivan, STOC’10; Chawla-Malec-Sivan, EC’10/GEB’15]. To our knowledge, this is the first benchmark-tight revenue guarantee of any simple multi-item mechanism. Technically, all previous works employ Myerson Auction as an intermediary. The barrier of 4 follows as Uniform-Ironed-Virtual-Value Item Pricing achieves a tight 2-approximation to Myerson Auction, which then achieves a tight 2-approximation to Duality Relaxation Benchmark. Instead, our new approach avoids Myerson Auction, thus enabling the improvement. Central to our work are a benchmark-based 3-competitive prophet inequality and its fully constructive proof. Such variant prophet inequalities shall find future applications, e.g., to Multi-Item Mechanism Design where optimal revenues are relaxed to various more accessible benchmarks. We complement our benchmark-tight ratio with an impossibility result. All previous works and ours follow the single-dimensional representative approach introduced by [Chawla-Hartline-Kleinberg, EC'07]. Against Duality Relaxation Benchmark, it turns out that this approach cannot beat our bound of 3 for a large class of Item Pricing's.

A major goal in the area of exact exponential algorithms is to give an algorithm for the (worst-case) $n$-input Subset Sum problem that runs in time $2^{(1/2 - c)n}$ for some constant $c>0$. In this paper we give a Subset Sum algorithm with worst-case running time $O(2^{n/2} \cdot n^{-γ})$ for a constant $γ> 0.5023$ in standard word RAM or circuit RAM models. To the best of our knowledge, this is the first improvement on the classical ``meet-in-the-middle'' algorithm for worst-case Subset Sum, due to Horowitz and Sahni, which can be implemented in time $O(2^{n/2})$ in these memory models. Our algorithm combines a number of different techniques, including the ``representation method'' introduced by Howgrave-Graham and Joux and subsequent adaptations of the method in Austrin, Kaski, Koivisto, and Nederlof, and Nederlof and Wegrzycki, and ``bit-packing'' techniques used in the work of Baran, Demaine, and Patrascu on subquadratic algorithms for 3SUM.

This paper proves the tight sample complexity of Second-Price Auction with Anonymous Reserve, up to a logarithmic factor, for each of all the value distribution families studied in the literature: [0,1]-bounded, [1,H]-bounded, regular, and monotone hazard rate (MHR). Remarkably, the setting-specific tight sample complexity poly(ε^{-1}) depends on the precision ε ∈ (0, 1), but not on the number of bidders n ≥ 1. Further, in the two bounded-support settings, our learning algorithm allows correlated value distributions. In contrast, the tight sample complexity Θ̃(n) ⋅ poly(ε^{-1}) of Myerson Auction proved by Guo, Huang and Zhang (STOC 2019) has a nearly-linear dependence on n ≥ 1, and holds only for independent value distributions in every setting. We follow a similar framework as the Guo-Huang-Zhang work, but replace their information theoretical arguments with a direct proof.

The ability to resolve detail in the object that is being imaged, named by resolution, is the core parameter of an imaging system. Super-resolution is a class of techniques that can enhance the resolution of an imaging system and even transcend the diffraction limit of systems. Despite huge success in the application, super-resolution is not well understood on the theoretical side, especially for any dimension d ≥ 2. In particular, in order to recover a k-sparse signal, all previous results suffer from either/both poly(k) samples or running time. We design robust algorithms for any (constant) dimension under a strong noise model based on developing some new techniques in Sparse Fourier transform (Sparse FT), such as inverting a robust linear system, “eggshell” sampling schemes, and partition and voting methods in high dimension. These algorithms are the first to achieve running time and sample complexity (nearly) linear in the number of source points and logarithmic in bandwidth for any constant dimension, and we believe the techniques developed in the work can find their further applications on the Super-resolution and Sparse FT problem. * The full version of the paper can be accessed at https://arxiv.org/abs/2005.06156

This paper establishes the Price of Stability (PoS) for First Price Auctions, for all equilibrium concepts that have been studied in the literature: Bayesian Nash Equilibrium ⊊ Bayesian Correlated Equilibrium ⊊ Bayesian Coarse Correlated Equilibrium. • Bayesian Nash Equilibrium: For independent valuations, the tight PoS is 1 − 1/e2 ≈ 0.8647, matching the counterpart Price of Anarchy (PoA) bound [JL22]. For correlated valuations, the tight PoS is 1 − 1/e ≈ 0.6321, matching the counterpart PoA bound [ST13, Syr14]. This result indicates that, in the worst cases, efficiency degradation depends not on different selections among Bayesian Nash Equilibria. • Bayesian (Coarse) Correlated Equilibrium: For independent or correlated valuations, the tight PoS is always 1 = 100%, i.e., no efficiency degradation. This result indicates that First Price Auctions can be fully efficient when we allow the more general equilibrium concepts. * The full version of the paper can be accessed at https://arxiv.org/abs/2207.04455

We prove that the PoA of First Price Auctions is 1-1/ e 2 ≈ 0.8647, closing the gap between the best known bounds [0.7430, 0.8689].

We prove that the PoA of First Price Auctions is 1-1/$ e^{2}\approx$0.8647, closing the gap between the best known bounds [0.7430, 0.8689].

Given a set of n input integers, the Equal Subset Sum problem asks us to find two distinct subsets with the same sum. In this paper we present an algorithm that runs in time O∗(30.387n) in the average case, significantly improving over the O∗(30.488n) running time of the best known worst-case algorithm [MNPW19] and the Meet-in-the-Middle benchmark of O∗(30.5n). Our algorithm generalizes to a number of related problems, such as the “Generalized Equal Subset Sum” problem, which asks us to assign a coefficient ci from a set C to each input number xi such that Σi cixi = 0. Our algorithm for the average-case version of this problem runs in time for some positive constant c0, whenever C = {0, ± 1, …, ± d} or {±1, …,±d} for some positive integer d (with runtime O∗(|C|0.45n) when |C| < 10). Our results extend to the problem of finding “nearly balanced” solutions in which the target is a not-too-large nonzero offset τ. Our approach relies on new structural results that characterize the probability that Σi cixi = τ has a solution c ∊ Cn when xi's are chosen randomly; these results may be of independent interest. Our algorithm is inspired by the “representation technique” introduced by Howgrave-Graham and Joux [HGJ10]. This requires several new ideas to overcome preprocessing hurdles that arise in the representation framework, as well as a novel application of dynamic programming in the solution recovery phase of the algorithm.

Abstract. This paper considers Bayesian revenue maximization in the [Formula: see text]-unit setting, where a monopolist seller has [Formula: see text] copies of an indivisible item and faces [Formula: see text] unit-demand buyers (whose value distributions can be nonidentical). Four basic mechanisms among others have been widely employed in practice and widely studied in the literature: Myerson auction, sequential posted-pricing, [Formula: see text]-th price auction with anonymous reserve, and anonymous pricing. Regarding a pair of mechanisms, we investigate the largest possible ratio between the two revenues (also known as the revenue gap), over all possible value distributions of the buyers. Divide these four mechanisms into two groups: (i) the discriminating mechanism group, Myerson auction and sequential posted-pricing, and (ii) the anonymous mechanism group, anonymous reserve and anonymous pricing. Within one group, the involved two mechanisms have an asymptotically tight revenue gap of [Formula: see text]. In contrast, any two mechanisms from the different groups have an asymptotically tight revenue gap of [Formula: see text].

This paper considers Bayesian revenue maximization in the k-unit setting, where a monopolist seller has k copies of an indivisible item and faces n unit-demand buyers (whose value distributions can be non-identical). Four basic mechanisms among others have been widely employed in practice and widely studied in the literature: Myerson Auction, Sequential Posted-Pricing, (k + 1)-th Price Auction with Anonymous Reserve, and Anonymous Pricing. Regarding a pair of mechanisms, we investigate the largest possible ratio between the two revenues (a.k.a. the revenue gap), over all possible value distributions of the buyers. Divide these four mechanisms into two groups: (i) the discriminating mechanism group, Myerson Auction and Sequential Posted-Pricing, and (ii) the anonymous mechanism group, Anonymous Reserve and Anonymous Pricing. Within one group, the involved two mechanisms have an asymptotically tight revenue gap of 1 + Θ(1 / √k). In contrast, any two mechanisms from the different groups have an asymptotically tight revenue gap of Θ(łog k).

We consider a fundamental problem in microeconomics: selling a single item to a number of potential buyers, whose values are drawn from known independent and regular (not necessarily identical) distributions. There are four widely used and widely studied mechanisms in the literature: Myerson Auction (OPT), Sequential Posted-Pricing (SPM), Second-Price Auction with Anonymous Reserve (AR), and Anonymous Pricing (AP). OPT is revenue-optimal but complicated and also experiences several issues in practice such as fairness; AP is the simplest mechanism but also generates the lowest revenue among these four mechanisms; SPM and AR are of intermediate complexity and revenue. We explore revenue gaps among these mechanisms, each of which is defined as the largest ratio between revenues from a pair of mechanisms. We establish two tight bounds and one tighter bound: 1. SPM vs. AP: this ratio studies the power of discrimination in pricing schemes. We obtain the tight ratio of constant ${\cal{C}}^* \approx {2.62}$, closing the gap between $[\frac{e}{e - 1}, e]$ left before. 2. AR vs. AP: this ratio measures the relative power of auction scheme vs. pricing scheme, when no discrimination is allowed. We attain the tight ratio of $\frac{\pi^2}{6} \approx 1.64$, closing the previously known bounds $[\frac{e}{e - 1}, e]$. 3. OPT vs. AR: this ratio quantifies the power of discrimination in auction schemes and is previously known to be somewhere between [2, e]. The lower bound of 2 was conjectured to be tight by Hartline and Roughgarden [ Proceedings of the 10th ACM Conference on Electronic Commerce, 2009, pp. 225--234] and Alaei et al. [ Games Econom. Behav., 118 (2019), pp. 494--510]. We acquire a better lower bound of 2.15 and thus disprove this conjecture.

We consider a fundamental problem in microeconomics: Selling a single item among a number of buyers whose values are drawn from known independent and regular distributions. There are four widely-used and widely-studied mechanisms in this literature: Anonymous Posted-Pricing (AP), Second-Price Auction with Anonymous Reserve (AR), Sequential Posted-Pricing (SPM), and Myerson Auction (OPT). Myerson Auction is optimal but complicated, which also suffers a few issues in practice such as fairness; AP is the simplest mechanism, but its revenue is also the lowest among these four; AR and SPM are of intermediate complexity and revenue. We study the revenue gaps among these four mechanisms, which is defined as the largest ratio between revenues from two mechanisms. We establish two tight ratios and one tighter bound: 1. SPM/AP. This ratio studies the power of discrimination in pricing schemes. We obtain the tight ratio of roughly 2.62, closing the previous known bounds [e/(e – 1), e]. 2. AR/AP. This ratio studies the relative power of auction vs. pricing schemes, when no discrimination is allowed. We get the tight ratio of π2/6 ≈ 1.64, closing the previous known bounds [e/(e – 1), e]. 3. OPT/AR. This ratio studies the power of discrimination in auctions. Previously, the revenue gap is known to be in interval [2, e], and the lower-bound of 2 is conjectured to be tight [38, 37, 4]. We disprove this conjecture by obtaining a better lower-bound of 2.15.

This paper considers two canonical Bayesian mechanism design settings. In the single-item setting, the tight approximation ratio of Anonymous Pricing is obtained: (1) compared to Myerson Auction, Anonymous Pricing always generates at least a 1/2.62-fraction of the revenue; (2) there is a matching lower-bound instance.