2 citations · 5 across the 7 of their papers we have counts for
12 papers
Scale-robust Auctions
Jason Hartline, Aleck Johnsen, Yingkai Li
We study auctions that are robust at any scale, i.e., they can be applied to sell both expensive and cheap items and achieve the best multiplicative approximation of the optimal re…
Subgame Optimal and Prior-Independent Online Algorithms
Jason Hartline, Aleck Johnsen, Anant Shah
This paper takes a game theoretic approach to the design and analysis of online algorithms and illustrates the approach on the finite-horizon ski-rental problem. This approach allo…
Extension of Minimax for Algorithmic Lower Bounds
Jason Hartline, Aleck Johnsen
This paper considers the use of Yao's Minimax Theorem in robust algorithm design, e.g., for online algorithms, where the algorithm designer aims to minimize the ratio of the algori…
Screening with Disadvantaged Agents
Hedyeh Beyhaghi, Modibo K. Camara, Jason Hartline +2
Motivated by school admissions, this paper studies screening in a population with both advantaged and disadvantaged agents. A school is interested in admitting the most skilled stu…
Lower Bounds for Prior Independent Algorithms
Jason Hartline, Aleck Johnsen
The prior independent framework for algorithm design considers how well an algorithm that does not know the distribution of its inputs approximates the expected performance of the…
Mechanisms for a No-Regret Agent: Beyond the Common Prior
Modibo Camara, Jason Hartline, Aleck Johnsen
A rich class of mechanism design problems can be understood as incomplete-information games between a principal who commits to a policy and an agent who responds, with payoffs dete…
Benchmark Design and Prior-independent Optimization
Jason Hartline, Aleck Johnsen, Yingkai Li
This paper compares two leading approaches for robust optimization in the models of online algorithms and mechanism design. Competitive analysis compares the performance of an onli…
Bias-Variance Games
Yiding Feng, Ronen Gradwohl, Jason Hartline +2
Firms engaged in electronic commerce increasingly rely on predictive analytics via machine-learning algorithms to drive a wide array of managerial decisions. The tuning of many sta…
Dashboard Mechanisms for Online Marketplaces
Jason Hartline, Aleck Johnsen, Denis Nekipelov +1
This paper gives a theoretical model for design and analysis of mechanisms for online marketplaces where a bidding dashboard enables the bid-optimization of long-lived agents. We a…
Inference from Auction Prices
Jason Hartline, Aleck Johnsen, Denis Nekipelov +1
Econometric inference allows an analyst to back out the values of agents in a mechanism from the rules of the mechanism and bids of the agents. This paper gives an algorithm to sol…
A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tile set synthesis
Aleck Johnsen, Ming-Yang Kao, Shinnosuke Seki
Patterned self-assembly tile set synthesis (PATS) aims at finding a minimum tile set to uniquely self-assemble a given rectangular (color) pattern. For k >= 1, k-PATS is a variant…
Computing Minimum Tile Sets to Self-Assemble Colors Patterns
Aleck C. Johnsen, Ming-Yang Kao, Shinnosuke Seki
Patterned self-assembly tile set synthesis (PATS) aims at finding a minimum tile set to uniquely self-assemble a given rectangular color pattern. For , -PATS is a varia…