The Northwestern CS Theory group had three papers at the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2020), which was recently held virtually.

Northwestern Economics PhD student Modibo Camara, CS PhD student Aleck Johnsen, and Prof. Jason Hartline co-authored a paper “Mechanisms for a No-Regret Agent: Beyond the Common Prior“.  The paper analyzes a broad class of Principal-Agent games in economics that normally depend on common knowledge of a precise distribution over an unknown, payoff-relevant input, using instead online learning in repeated game play.  A key idea of the paper which describes (possibly externally-informed) Agents behaviorally with only a no-regret property is to extend previous definitions for “regret” to consider counterfactual sequences of the repeated play. Link to the talk.

Northwestern CS PhD students Yingkai Li and Aleck Johnsen, and Prof. Jason Hartline co-authored a paper “Benchmark Design and Prior Independent Optimization“.  The paper introduces a formal approach to the study of benchmark design, as a parameter of worst case algorithm design to be optimized.  Incorporating first economic properties to justify and measure benchmarks, the main result of the paper shows that benchmark design is equivalent to algorithm design when inputs are drawn independently from a common-but-unknown distribution.  Another main result solves a longstanding open question in 2-agent revenue auction design, which further serves as application for the benchmark design result. Link to the talk.

Prof. Aravindan Vijayaraghavan co-authored a paper “Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay” with Biswaroop Maiti (Northeastern), Rajmohan Rajaraman (Northeastern), David Stalfa (Northeastern), and Zoya Svitkina (Google). The paper studies the problem of scheduling n precedence-constrained jobs on m uniformly-related machines in the challenging setting where we have to account for communication delays. Communication delay is the amount of time that must pass between the completion of a job on one machine and the start of any successor of that job on a different machine. The paper shows both algorithmic results and lower bounds. This includes the first polylogarithmic factor approximation algorithm for this problem, superconstant integrality gaps, and bounding the advantage of duplication in these settings. Link to the talk.