Aleck C. Johnsen

FOCS Conference 2020 Conference Paper

Benchmark Design and Prior-independent Optimization

• Jason D. Hartline
• Aleck C. 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 online algorithm to an offline benchmark in worst-case over inputs, and prior-independent mechanism design compares the expected performance of a mechanism on an unknown distribution (of inputs, i. e. , agent values) to the optimal mechanism for the distribution in worst case over distributions. For competitive analysis, a critical concern is the choice of benchmark. This paper gives a method for selecting a good benchmark. We show that optimal algorithm/mechanism for the optimal benchmark is equal to the prior-independent optimal algorithm/mechanism. We solve a central open question in prior-independent mechanism design, namely we identify the prior-independent revenue-optimal mechanism for selling a single item to two agents with i. i. d. and regularly distributed values. We use this solution to solve the corresponding benchmark design problem. Via this solution and the above equivalence of prior-independent mechanism design and competitive analysis (a. k. a. prior-free mechanism design) we show that the standard method for lower bounds of prior-free mechanisms is not generally tight for the benchmark design program. 1 1 For the full version of this work, see https: //arxiv. org/abs/2001. 10157.

SODA Conference 2020 Conference Paper

Inference from Auction Prices

• Jason D. Hartline
• Aleck C. Johnsen
• Denis Nekipelov
• Zihe Wang 0001

FOCS Conference 2020 Conference Paper

Mechanisms for a No-Regret Agent: Beyond the Common Prior

• Modibo K. Camara
• Jason D. Hartline
• Aleck C. 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 determined by an unknown state of the world. Traditionally, these models require strong and often-impractical assumptions about beliefs (a common prior over the state). In this paper, we dispense with the common prior. Instead, we consider a repeated interaction where both the principal and the agent may learn over time from the state history. We reformulate mechanism design as a reinforcement learning problem and develop mechanisms that attain natural benchmarks without any assumptions on the state-generating process. Our results make use of novel behavioral assumptions for the agent - based on counterfactual internal regret - that capture the spirit of rationality without relying on beliefs. 1 1 For the full version of this paper, see https: //arxiv. org/abs/2009. 05518.