More Like this

1. Multi-Item Mechanisms without Item-Independence: Learnability via Robustness

   https://doi.org/10.1145/3391403.3399541  

   Brustle, Johannes; Cai, Yang; Daskalakis, Constantinos (July 2020, 21st ACM Conference on Economics and Computation)

   We study the sample complexity of learning revenue-optimal multi-item auctions. We obtain the first set of positive results that go beyond the standard but unrealistic setting of item-independence. In particular, we consider settings where bidders' valuations are drawn from correlated distributions that can be captured by Markov Random Fields or Bayesian Networks -- two of the most prominent graphical models. We establish parametrized sample complexity bounds for learning an up-to-ε optimal mechanism in both models, which scale polynomially in the size of the model, i.e. the number of items and bidders, and only exponential in the natural complexity measure of the model, namely either the largest in-degree (for Bayesian Networks) or the size of the largest hyper-edge (for Markov Random Fields). We obtain our learnability results through a novel and modular framework that involves first proving a robustness theorem. We show that, given only "approximate distributions" for bidder valuations, we can learn a mechanism whose revenue is nearly optimal simultaneously for all "true distributions" that are close to the ones we were given in Prokhorov distance. Thus, to learn a good mechanism, it suffices to learn approximate distributions. When item values are independent, learning in Prokhorov distance is immediate, hence our framework directly implies the main result of Gonczarowski and Weinberg. When item values are sampled from more general graphical models, we combine our robustness theorem with novel sample complexity results for learning Markov Random Fields or Bayesian Networks in Prokhorov distance, which may be of independent interest. Finally, in the single-item case, our robustness result can be strengthened to hold under an even weaker distribution distance, the Levy distance. 

   more » « less
2. Serial order depends on item-dependent and item-independent contexts.

   https://doi.org/10.1037/rev0000422  

   Logan, Gordon D.; Cox, Gregory E. (March 2023, Psychological Review)
3. Investigating Item Bias in a CS1 Exam with Differential Item Functioning

   https://doi.org/10.1145/3408877.3432397  

   Davidson, Matt J.; Wortzman, Brett; Ko, Amy J.; Li, Min (March 2021, ACM Technical Symposium on Computer Science Education (SIGCSE))

   null (Ed.)
4. Controllable Gradient Item Retrieval

   https://doi.org/10.1145/3442381.3449963  

   Wang, Haonan; Zhou, Chang; Yang, Carl; Yang, Hongxia; He, Jingrui (April 2021, The Web Conference 2021)

   null (Ed.)
5. Streaming algorithms for the missing item finding problem

   Stoeckl, Manuel (January 2023, SODA 2023)

   Many problems on data streams have been studied at two extremes of difficulty: either allowing randomized algorithms, in the static setting (where they should err with bounded probability on the worst case stream); or when only deterministic and infallible algorithms are required. Some recent works have considered the adversarial setting, in which a randomized streaming algorithm must succeed even on data streams provided by an adaptive adversary that can see the intermediate outputs of the algorithm. In order to better understand the differences between these models, we study a streaming task called “Missing Item Finding”. In this problem, for r < n, one is given a data stream a1 , . . . , ar of elements in [n], (possibly with repetitions), and must output some x ∈ [n] which does not equal any of the ai. We prove that, for r = nΘ(1) and δ = 1/poly(n), the space required for randomized algorithms that solve this problem in the static setting with error δ is Θ(polylog(n)); for algorithms in the adversarial setting with error δ, Θ((1 + r2/n)polylog(n)); and for deterministic algorithms, Θ(r/polylog(n)). Because our adversarially robust algorithm relies on free access to a string of O(r log n) random bits, we investigate a “random start” model of streaming algorithms where all random bits used are included in the space cost. Here we find a conditional lower bound on the space usage, which depends on the space that would be needed for a pseudo-deterministic algorithm to solve the problem. We also prove an Ω(r/polylog(n)) lower bound for the space needed by a streaming algorithm with < 1/2polylog(n) error against “white-box” adversaries that can see the internal state of the algorithm, but not predict its future random decisions. 

   more » « less