More Like this

1. Algorithmic Cheap Talk

   Babichenko, Yakov; Talgam-Cohen, Inbal; Xu, Haifeng; Zabarnyi, Konstantin (July 2024, Proceedings of 25th ACM Conference on Economics and Computation, EC 2024)

   The literature on strategic communication originated with the influential cheap talk model, which precedes the Bayesian persuasion model by three decades. This model describes an interaction between two agents: sender and receiver. The sender knows some state of the world which the receiver does not know, and tries to influence the receiver’s action by communicating a cheap talk message to the receiver. This paper initiates the algorithmic study of cheap talk in a finite environment (i.e., a finite number of states and receiver’s possible actions). We first prove that approximating the sender-optimal or the welfare-maximizing cheap talk equilibrium up to a certain additive constant or multiplicative factor is NP-hard. Fortunately, we identify three naturally-restricted cases that admit efficient algorithms for finding a sender-optimal equilibrium. These include a state-independent sender’s utility structure, a constant number of states or a receiver having only two actions. 

   more » « less
2. Implementing Mediators with Asynchronous Cheap Talk

   https://doi.org/10.1145/3293611.3331623  

   Abraham, Ittai; Dolev, Danny; Geffner, Ivan; Halpern, Joseph Y. (July 2019, Proceedings of the 38th Annual ACM Symposium on Principles of Distributed Computing)

   A mediator can help non-cooperative agents obtain an equilibrium that may otherwise not be possible. We study the ability of players to obtain the same equilibrium without a mediator, using only cheap talk, that is, nonbinding pre-play communication. Previous work has considered this problem in a synchronous setting. Here we consider the effect of asynchrony on the problem, and provide upper bounds for implementing mediators. Considering asynchronous environments introduces new subtleties, including exactly what solution concept is most appropriate and determining what move is played if the cheap talk goes on forever. Different results are obtained depending on whether the move after such ``infinite play'' is under the control of the players or part of the description of the game. 

   more » « less
3. The development of randomization and deceptive behavior in mixed strategy games

   https://doi.org/10.3982/QE1769  

   Brocas, Isabelle; Carrillo, Juan D. (January 2022, Quantitative Economics)

   We study the foundations for the development of optimal randomization in mixed strategy games. We consider a population of children and adolescents (7 to 16 years old) and study in the laboratory their behavior in a nonzero sum, hide‐and‐seek game with a unique interior mixed strategy equilibrium where each location has a known but different value. The vast majority of participants favor the high‐value location not only as seekers (as predicted by theory) but also as hiders (in contradiction with theory). The behavior is extremely similar across all ages, and also similar to that of the college students control adult group. We also study the use of cheap talk (potentially deceptive) messages in this game. Hiders are excessively truthful in the messages they send while seekers have a slight tendency to (correctly) believe hiders. In general, however, messages have a small impact on outcomes. The results point to a powerful (erroneous) heuristic thinking in two‐person randomization settings that does not get corrected, even partially, with age. 

   more » « less
4. Explaining the Bag Gain in Batch Steganography

   Eli Dworetzky; Jessica Fridrich (December 2022, IEEE transactions on information forensics and security)

   In batch steganography, the sender distributes the secret payload among multiple images from a “bag” to decrease the chance of being caught. Recent work on this topic described an experimentally discovered phenomenon, which we call the “bag gain”: for fixed communication rate, pooled detectors experience a decrease in statistical detectability for initially increasing bag sizes, providing an opportunity for the sender to gain in security. The bag gain phenomenon is universal in the sense of manifesting under a wide spectrum of conditions. In this paper, we explain this experimental observation by adopting a statistical model of detector response. Despite the simplicity of the model, it does capture observed trends in detectability as a function of the bag size, the rate, and cover source properties. Additionally, and surprisingly, the model predicts that in certain cover sources the sender should avoid bag sizes that are too small as this can lead to a bag loss. 

   more » « less
5. A Formal Analysis of Karn’s Algorithm

   Max von Hippel, Kenneth L. (May 2023, Lecture notes in computer science)

   David Mohaisen, Thomas Wies (Ed.)

   The stability of the Internet relies on timeouts. The timeout value, known as the Retransmission TimeOut (RTO), is constantly updated, based on sampling the Round Trip Time (RTT) of each packet as measured by its sender -- that is, the time between when the sender transmits a packet and receives a corresponding acknowledgement. Many of the Internet protocols compute those samples via the same sampling mechanism, known as Karn's Algorithm. We present a formal description of the algorithm, and study its properties. We prove the computed samples reflect the RTT of some packets, but it is not always possible to determine which. We then study some of the properties of RTO computations as described in the commonly used RFC6298. All properties are mechanically verified. 

   more » « less