It has become the default in markets such as ad auctions for participants to bid in an auction through automated bidding agents (autobidders) which adjust bids over time to satisfy return-over-spend constraints. Despite the prominence of such systems for the internet economy, their resulting dynamical behavior is still not well understood. Although one might hope that such relatively simple systems would typically converge to the equilibria of their underlying auctions, we provide a plethora of results that show the emergence of complex behavior, such as bi-stability, periodic orbits and quasi periodicity. We empirically observe how the market structure (expressed as motifs) qualitatively affects the behavior of the dynamics. We complement it with theoretical results showing that autobidding systems can simulate both linear dynamical systems as well logical boolean gates.

The interplay between exploration and exploitation in competitive multi-agent learning is still far from being well understood. Motivated by this, we study smooth Q-learning, a prototypical learning model that explicitly captures the balance between game rewards and exploration costs. We show that Q-learning always converges to the unique quantal-response equilibrium (QRE), the standard solution concept for games under bounded rationality, in weighted zero-sum polymatrix games with heterogeneous learning agents using positive exploration rates. Complementing recent results about convergence in weighted potential games [16,34], we show that fast convergence of Q-learning in competitive settings obtains regardless of the number of agents and without any need for parameter fine-tuning. As showcased by our experiments in network zero-sum games, these theoretical results provide the necessary guarantees for an algorithmic approach to the currently open problem of equilibrium selection in competitive multi-agent settings.

While extending the lifetime of a wireless sensor network (WSN) with full coverage has been extensively studied, it was found recently that the lifetime of a WSN can be prolonged significantly if partial covers are used instead. In this paper, we formally define the problem of extending the lifetime of a WSN using partial covers. (Throughout this paper, we assume that each point of the given target region is covered at least k times by the input sensors.) We first present a centralized algorithm using an optimal subroutine which computes the densest strip with width 2r, where r is the minimum sensing radius of all sensors. By using a known 1-D algorithm, we can cover the center of the strip with k full covers and the remaining subproblems can be solved recursively to have the eventual k partial covers. We then introduce a distributed algorithm without any assumption on the coordinates and directions of sensors, as long as each sensor knows the presence of other sensors within its sensing region. Finally, we present some experimental results comparing the performance of these algorithms with the previous homological partial cover solution. In all small instances the results generated by our algorithms are significantly better than those generated by the homological method. For two larger instances (a larger domain with n around 1000), the homological method cannot finish while both of our algorithms generate promising results.