Welfare Guarantees from Data
Analysis of efficiency of outcomes in game theoretic settings has been a main item of study at the intersection of economics and computer science. The notion of the price of anarchy takes a worst-case stance to efficiency analysis, considering instance independent guarantees of efficiency. We propose a data-dependent analog of the price of anarchy that refines this worst-case assuming access to samples of strategic behavior. We focus on auction settings, where the latter is non-trivial due to the private information held by participants. Our approach to bounding the efficiency from data is robust to statistical errors and mis-specification. Unlike traditional econometrics, which seek to learn the private information of players from observed behavior and then analyze properties of the outcome, we directly quantify the inefficiency without going through the private information. We apply our approach to datasets from a sponsored search auction system and find empirical results that are a significant improvement over bounds from worst-case analysis.
This paper studies a non-worst-case notion of the price of anarchy (PoA). An auction A’s PoA is the worst-case ratio between the welfare of the optimal auction and the welfare in a Bayes-Nash equilibrium of A, taken over all value distributions and equilibria. The authors propose a non-worst case relaxation which they call the distributional PoA (DPoA), which is defined by a distribution D over bids. It measures the same ratio as the original PoA, but only over all value distributions and equilibria that could generate the bid distribution D. They bound the DPoA for single-dimensional settings and show that it can be estimated using samples from D.
In one example, the authors provide an upper bound on the DPoA for the single item first price auction (Lemma 1). There are a few things I couldn’t reproduce in the proof. In line 140, the authors write that 1/\mu*\int_0^{v_i(1 – e^{-\mu})} (1 – G_{-i}(z)) dz <= T_i. Isn’t it less than or equal to T_i/\mu? Also, it seems as though if I add 1/\mu*\int_0^{v_i(1 – e^{-\mu})} (1 – G_{-i}(z)) dz to the right-hand-side of Equation (8), I’ll get 1/\mu*\int_0^{v_i(1 – e^{-\mu})} (1 – G_{-i}(z) + G_{-i}(z)) dz = 1/\mu*\int_0^{v_i(1 – e^{-\mu})} dz = v_i(1 – e^{-\mu})/\mu. (The authors write that it’s just v_i(1 – e^{-\mu}).) Lastly, in line 145, the authors write that \sum_i T_i*x_i >= max_i T_i. Since this is a single-item auction, there’s exactly one x_i that equals 1 and the rest equal 0. Should the inequality be flipped? (\sum_i T_i*x_i <= max_i T_i.)
I would really like to see the proof of Lemma 5 written out. It’s not clear to me how it follows immediately from Lemma 9.9 in [5]. Rademacher complexity does have nice compositional properties. However, I’m not convinced, for example, that “multiplication of bid vectors with constants” is covered by Lemma 9.9 in [5]. Lemma 9.9 in [5] applies to function classes mapping some domain X to R. The function class defined by “multiplication of bid vectors with constants” maps from R^{n-1} to R^{n-1}. How exactly does Lemma 9.9 apply? Also, it seems like multiplication would have to be involved in the form of many payment functions. For example, in the first price auction, the payment function is b_i*x_i, where x_i can be written as {b_i > b_1}*…*{b_i > b_{i-1}}*{b_i > b_{i+1}}*…*{b_i > b_n}. Is there a way to write this without multiplication? The authors write that the conditions in Lemma 5 hold for sponsored search auctions. Is there no multiplication in that setting either?
I think this paper is currently better written for an economics community as opposed to a learning community. For example, it’s not clear to me what a pay-your-bid auction is. On line 187, the authors write that “For any auction, we can re-write the expected utility of a bid b: u_i(b, v_i) = x_i(b)(v_i – p_i(b)/x_i(b)).” What if x_i(b) = 0?
I think that overall, this is a really interesting contribution to beyond-worst-case analysis and the experiments seem to validate its practical relevance. However, I think the presentation could be improved to make it more understandable for an ICML audience. I’m also hesitant to recommend it for acceptance without a proof of Lemma 5.
======after rebuttal======
I'm willing to believe Lemma 5 if the authors are assuming that number of bidders is constant. I didn't realize that they were making this assumption. The authors should mention this explicitly in the preliminaries and/or the lemma statement.