More Like this

1. One Hot Garbling

   https://doi.org/10.1145/3460120.3484764  

   Heath, David ; Kolesnikov, Vladimir ( November 2021 , One Hot Garbling)
2. 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)
3. 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))
4. 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
5. It Takes Two to Lie: One to Lie, and One to Listen

   Denis Peskov, Benny Cheng ( January 2020 , Proceedings of ACL)

   Trust is implicit in many online text conversations—striking up new friendships, or asking for tech support. But trust can be betrayed through deception. We study the language and dynamics of deception in the negotiation-based game Diplomacy, where seven players compete for world domination by forging and breaking alliances with each other. Our study with players from the Diplomacy community gathers 17,289 messages annotated by the sender for their intended truthfulness and by the receiver for their perceived truthfulness. Unlike existing datasets, this captures deception in long-lasting relationships, where the interlocutors strategically combine truth with lies to advance objectives. A model that uses power dynamics and conversational contexts can predict when a lie occurs nearly as well as human players. 

   more » « less