Author

Aviad Rubinstein

3 papers indexed here

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Oct 2026

Improved Combinatorial Auctions with and without Samples

We give new mechanisms for combinatorial auctions in the offline, secretary, and prophet-with-samples models. Specifically, we obtain the following guarantees for social welfare maximization with $m$ items and $n$ XOS buyers: * In the prophet-with-samples version, buyers arrive in adversarial order and draw their value...

Aviad Rubinstein, Sahil Singla · 0 citations

Preprint Oct 2026

Tarski Fixed Points in Quasi-FPT Queries

We study the query complexity of finding a Tarski fixed point over $[n]^k$. Previous work has left a large gap between $\smash{{\Omega}(\log^2 n)}$ and $\smash{\log^{O(k)}n}$. We show that both of the previous upper and lower bounds were far from tight: for every $k\geq 3$, \[ \Omega\left((\log n)^{\frac{1}{2}\lceil \l...

Xi Chen, Rui-Quan Gao, Yu-Hao Li et al. · 0 citations

Preprint Sep 2026

Approximately Efficient Multidimensional Bilateral Trade

A central challenge in mechanism design is to develop truthful trade mechanisms that maximize the expected gains-from-trade (GFT) in two-sided markets. Because achieving the full GFT is generally impossible, the literature has focused on constant-factor approximations---a notoriously difficult problem even in simple se...

Aviad Rubinstein, Xi-Zhi Tan, Zi-Xin Zhou · 6 citations