More Like this

1. One-Layer Transformer Provably Learns One-Nearest Neighbor In Context

   Li, Zihao; Cao, Yuan; Gao, Cheng; He, Yihan; Liu, Han; Klusowski, Jason M; Fan, Jianqing; Wang, Mengdi (December 2024, Neural Information Processing Systems (NeurIPS))
2. One Hot Garbling

   https://doi.org/10.1145/3460120.3484764  

   Heath, David; Kolesnikov, Vladimir (November 2021, One Hot Garbling)
3. Five-list-coloring graphs on surfaces III. One list of size one and one list of size two

   https://doi.org/10.1016/j.jctb.2017.06.004  

   Postle, Luke; Thomas, Robin (January 2018, Journal of Combinatorial Theory, Series B)
4. VIGOR: Cross-View Image Geo-localization beyond One-to-one Retrieval

   https://doi.org/10.1109/CVPR46437.2021.00364  

   Zhu, Sijie; Yang, Taojiannan; Chen, Chen (June 2021, 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR))
5. Two for One & One for All: Two-Sided Manipulation in Matching Markets

   https://doi.org/10.24963/ijcai.2022/46  

   Hosseini, Hadi; Umar, Fatima; Vaish, Rohit (July 2022, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence Main Track.)

   Strategic behavior in two-sided matching markets has been traditionally studied in a one-sided manipulation setting where the agent who misreports is also the intended beneficiary. Our work investigates two-sided manipulation of the deferred acceptance algorithm where the misreporting agent and the manipulator (or beneficiary) are on different sides. Specifically, we generalize the recently proposed accomplice manipulation model (where a man misreports on behalf of a woman) along two complementary dimensions: (a) the two for one model, with a pair of misreporting agents (man and woman) and a single beneficiary (the misreporting woman), and (b) the one for all model, with one misreporting agent (man) and a coalition of beneficiaries (all women). Our main contribution is to develop polynomial-time algorithms for finding an optimal manipulation in both settings. We obtain these results despite the fact that an optimal one for all strategy fails to be inconspicuous, while it is unclear whether an optimal two for one strategy satisfies the inconspicuousness property. We also study the conditions under which stability of the resulting matching is preserved. Experimentally, we show that two-sided manipulations are more frequently available and offer better quality matches than their one-sided counterparts. 

   more » « less