Ariel Schvartzman

FOCS Conference 2019 Conference Paper

Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries

• Pravesh K. Kothari
• Sahil Singla 0001
• Divyarthi Mohan
• Ariel Schvartzman
• S. Matthew Weinberg

We consider a revenue-maximizing seller with n items facing a single buyer. We introduce the notion of symmetric menu complexity of a mechanism, which counts the number of distinct options the buyer may purchase, up to permutations of the items. Our main result is that a mechanism of quasi-polynomial symmetric menu complexity suffices to guarantee a (1 - epsilon )-approximation when the buyer is unit-demand over independent items, even when the value distribution is unbounded, and that this mechanism can be found in quasi-polynomial time. Our key technical result is a polynomial-time, (symmetric) menu-complexity-preserving black-box reduction from achieving a (1 - epsilon )-approximation for unbounded valuations that are subadditive over independent items to achieving a (1 - O(epsilon ))-approximation when the values are bounded (and still subadditive over independent items). We further apply this reduction to deduce approximation schemes for a suite of valuation classes beyond our main result. Finally, we show that selling separately (which has exponential menu complexity) can be approximated up to a (1 - epsilon ) factor with a menu of efficient-linear (f (epsilon) · n) symmetric menu complexity.

TCS Journal 2018 Journal Article

The fewest clues problem

• Erik D. Demaine
• Fermi Ma
• Ariel Schvartzman
• Erik Waingarten
• Scott Aaronson

When analyzing the computational complexity of well-known puzzles, most papers consider the algorithmic challenge of solving a given instance of (a generalized form of) the puzzle. We take a different approach by analyzing the computational complexity of designing a “good” puzzle. We assume a puzzle maker designs part of an instance, but before publishing it, wants to ensure that the puzzle has a unique solution. Given a puzzle, we introduce the FCP (fewest clues problem) version of the problem: Given an instance to a puzzle, what is the minimum number of clues we must add in order to make the instance uniquely solvable? We analyze this question for the Nikoli puzzles Sudoku, Shakashaka, and Akari. Solving these puzzles is NP-complete, and we show their FCP versions are Σ 2 P -complete. Along the way, we show that the FCP versions of Triangle Partition, Planar 1-in-3 SAT, and Latin Square are all Σ 2 P -complete. We show that even problems in P have difficult FCP versions, sometimes even Σ 2 P -complete, though “closed under cluing” problems are in the (presumably) smaller class NP; for example, FCP 2SAT is NP-complete.

SODA Conference 2018 Conference Paper

The menu complexity of "one-and-a-half-dimensional" mechanism design

• Raghuvansh R. Saxena
• Ariel Schvartzman
• S. Matthew Weinberg