TCS Prof. Anindya De had a joint paper with Michael Saks (Rutgers) and Sijian Tang (Rutgers) in 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 16). The paper “Noisy population recovery in polynomial time” addresses the problem of recovering an unknown distribution on binary strings under noise. This problem is related to well-studied problems in learning such as learning mixtures of spherical Gaussians and product distributions. A manuscript of the paper can be found here.
Theory PhD students Abhratanu Dutta and Yiding Feng along with their teammate Ruohong Zhang finished first at the ACM-ICPC Midcentral Regional Programming Contest this year. They finished in 1st place out of 156 teams representing 56 different schools in total and have advanced to the ACM-ICPC World Finals in Rapid City, South Dakota from May 20-25, 2017.
The ACM-ICPC (Association for Computing Machinery – International Collegiate Programming Contest) is a multi-tier, team-based, programming competition. Headquartered at Baylor University, Texas, it operates according to the rules and regulations formulated by the ACM. The contest participants come from over 2,000 universities that are spread across 80 countries and six continents.
Details can be found here.
The 2016 ACM Conference on Economics and Computation and the World Congress of the Game Theory Society (GAMES 2016) were colocated at Maastricht University in the medieval town of Maastricht, Netherlands in late July. The Northwestern theory group had an especially strong showing with seven papers presented and a public lecture! Brief summaries are given below.
Ph.D. student Manolis Pountourakis presented two papers. At GAMES, he presented his paper Optimal Auctions vs. Anonymous Pricing (joint with with coauthors Saeed Alaei, Northwestern Prof. Jason Hartline, Rad Niazadeh, and Yang Yuan). The paper proves that eBay’s Auctions and Buy-It-Now (posted pricings) are within at least an e = 2.718 factor of the revenue optimal auction (which may be asymmetric and very complicated). This is a worst-case bound that is quite difficult to prove; in practice the eBay’s sales mechanisms likely do much better. This paper previously appeared in FOCS 2015 and with this video of the talk. At EC, he presented Procrastination with Variable Present Bias (joint with coauthors Nick Gravin, Nicole Immorlica, and Brendan Lucier). Individuals attempting to complete a task often procrastinate, making plans and then failing to follow through. One well-known model of such behavioral anomalies is present-bias discounting: individuals over-weight present costs by a bias factor. This paper introduces a variant of this model where the bias factor varies across time, identifies a connection between the planning problem with variable present bias and optimal pricing, and uses this connection to bound the cost of procrastination.
Nima Haghpanah, a former Ph.D. student and now faculty member in the Economics Department at Penn State, presented two papers. At GAMES he presented Multi-dimensional Virtual Values and Second-degree Price Discrimination (joint with Northwestern Prof. Jason Hartline). This paper studies multi-dimensional mechanism design. It develops a method for solving for multi-dimensional virtual values, the pointwise optimization of which gives the optimal mechanism. It uses these virtual values to characterize the family of distributions where second-degree price discrimination (e.g., with a high- and low-quality version of a product) is not profitable. At EC he presented Sequential Mechanisms with ex-post Participation Guarantees (joint with Profs. Itai Ashlagi of Stanford and Constantinos Daskalakis). The paper identifies optimal and approximately optimal mechanisms in dynamic setting in which a seller and a buyer interact repeatedly. In contrast to standard settings, in this paper the outcomes of a mechanism must be acceptable to the buyer even after all uncertainty is resolved.
At the second Workshop on Algorithmic Game Theory and Data Science (a part of the EC program), Ph.D. student Sam Taggart presented Non-revelation Mechanism Design (joint with Northwestern Prof. Jason Hartline). This paper shows how to better design Bayes-Nash mechanisms, e.g., with winner-pays-bid or all-pay semantics, in a repeated environment by “linking decisions” across the repetitions. The designed mechanisms are asymptotically optimal with the number of repetitions that are linked.
At EC, Prof. Jason Hartline presented A/B Testing of Auctions (joint with Shuchi Chawla and Denis Nekipelov). This paper shows how the counter factual revenue of a mechanism B can be estimated from the equilibrium bids in a mechanism C which is the convex combination of mechanism A and B. For example, an auctioneer with multiple units can determine whether selling one unit or two units gives higher revenue by running the auction that probabilistically sells one or two units. The methods applies generally to position auctions to both winner-pays-bid and all-pay semantics.
Adjunct Northwestern Prof. Nicole Immorlica presented two papers. At the Workshop on Economics of Cloud Computing she presented On-demand or Spot? Selling the Cloud to Risk-averse Customers (joint with former Ph.D. student Darrell Hoy and Nikhil Devanur). In Amazon EC2, cloud resources are sold through a combination of the on-demand market, in which customers buy resources at a fixed price, and the spot market, in which customers bid for an uncertain supply of excess resources. This paper showed that such a dual market system improves upon key objectives when customers have heterogeneous risk attitudes: the welfare and revenue of its unique equilibrium is larger than that of spot markets alone and the efficiency is larger than only on-demand markets.
A slide from “Market Design without Money”
At a GAMES affiliated evening soirée with the Brightlands Young Professionals network Prof. Immorlica gave a Roy-Lichtenstein-themed public lecture entitled “Market Design without Money”. As a market-designer, a primary goal is to allocate resources to individuals in a way that maximizes the total value of the community for the allocation. Selling the resources is a great way to achieve this: if someone is willing to pay a high price for something, then they must have a high value for it as well. However, in many settings of interest, payments are infeasible. This could be due to repugnance, as in the assignment of public schools to children or cadaver kidneys to patients. Or perhaps the market technologies can not support financial transactions, e.g., users of an online review system like TripAdvisor may not have bank accounts linked to their user accounts. This talk explored using alternative incentives including risk, waiting time, and social status, in place of money to help optimize markets in such scenarios.
Great work to the presenters and coauthors of these papers!
Sam Taggart won the 2016 Northwestern EECS Best TA award for his work TAing EECS 336: Design and Analysis of Algorithms this Fall. The class tripped in size over the last couple years and Sam taught all 150 students in six discussion sessions. Even with this overwhelming workload he received incredibly high scores on the teaching evaluations with rave comments. Great work Sam!!
Talk videos are online from the 2015 Symposium on Foundations of Computer Science (FOCS). The CS Theory group had two papers at the conference.
Northwestern CS Theory and Economics Ph.D. student Manolis Pountourakis did a really fantastic job of presenting his paper Optimal Auctions vs. Anonymous Pricing (joint with with coauthors Saeed Alaei, Rad Niazadeh, Yang Yuan, and me). The paper proves that eBay’s Auctions and Buy-It-Now (posted pricings) are within at least an e = 2.718 factor of the revenue optimal auction (which may be asymmetric and very complicated). This is a worst-case bound that is quite difficult to prove; in practice the eBay’s sales mechanisms likely do much better. Watch the video!
TCS Prof. Anindya De presented his paper Beyond the central limit theorem: Asymptotic expansions and pseudorandomness for combinatorial sums. This paper extends the central limit theorem to achieve faster convergence rates by using information about a large number of moments of the sum (as opposed to just the mean and variance). This result also has applications in space bounded derandomization, a central question in complexity theory. Watch the video!
The Northwestern CS Theory Group hosted its First Quarterly Theory Workshop last month on the theme of Algorithmic Game Theory and Data Science. Fantastic talks were given by workshop speakers Tim Roughgarden (Stanford), Avrim Blum (CMU), and Eva Tardos (Cornell). Videos of the talks are available on the workshop webpage.
The goal of this new quarterly theory workshop format is to facilitate a deep discussion of the workshop theme and enable broad participation from theoretical computer science faculty and students in the greater Chicago area. For this first workshop, we were especially delighted to have attendees coming from the Toyota Technology Institute, University of Illinois at Chicago, the University of Chicago, and the University of Wisconsin at Madison. A colleague wrote afterward: “Thank you so much for inviting my students to attend the workshop yesterday! They were all blown away by the experience.”
The Second Quarterly Theory Workshop will be held on the morning of May 17 (Tuesday) on the theme of semidefinite programming hierarchies and sum-of-squares. The speakers are Boaz Barak (Harvard), David Steurer (Cornell), and Prasad Raghavendra (UC-Berkeley). The workshop will be preceded, on the morning of May 16 (Monday), by a tutorial on sum-of-squares by Madhur Tulsiani (TTI-Chicago). Individual meetings with the speakers are available on Monday and Tuesday afternoon.
Thanks to everyone who came and made the first workshop a success, we hope to see you all again for the second!
Congratulations to former Northwestern CS Economics and Theory Ph.D. student Nima Haghpanah for accepting a tenure track assistant professorship at the Economics Department at Pennsylvania State! Nima’s Ph.D. dissertation, titled Optimal Multi-parameter Auction Design, won Northwestern’s CS dissertation award in 2015. It revisits four of the main conclusions of Roger Myerson’s 1981 paper, also award winning, and extends or approximately extends them to environments where the bidders have multi-dimensional preferences. Multi-dimensional auction design is well regarded as one of the most impenetrable areas for economic analysis. Nima made progress on this problem by deftly combining analysis methods from both economics and theoretical computer science.
When I joined Northwestern in 2008, at the time with Lance Fortnow and Nicole Immorlica, our goal was to create a program where the next generation of Ph.D.s in algorithmic game theory could train to become equal parts economists and computer scientists. In addition to the usual courses taken by theoretical computer scientists, the first-year students in the program take the introductory Ph.D. course sequences in microeconomics, game theory, and optimization that are taught in Northwestern’s Economics Department and Kellogg School of Management. The most important part of the program, however, is the outstanding students who have joined us, made it a fantastic and collegial environment, and have done really amazing research. Thanks, Nima, for helping us all achieve our goals. We look forward to seeing even more amazing things come from you at Penn State!
© 2024 Northwestern CS Theory Group
Theme by Anders Noren — Up ↑
Recent Comments