2025-12-12 | | Total: 7
Simple Clock Auctions (SCA) are a mechanism commonly used in spectrum auctions to sell lots of frequency bandwidths. We study such an auction with one player having access to perfect information against straightforward bidders. When the opponents' valuations satisfy the ordinary substitutes condition, we show that it is optimal to bid on a fixed lot overtime. In this setting, we consider a continuous-time version of the SCA auction in which the prices follow a differential inclusion with a piecewise-constant dynamics. We show that there exists a unique solution in the sense of Filippov. This guarantees that the continuous-time model coincides with the limit of the discrete-time auction when price increments tend to zero. Moreover, we show that the value function of this limit auction is piecewise linear (though possibly discontinuous). Finally, we illustrate these results by analyzing a simplified version of the multiband Australian spectrum auction of 2017.
The rapid advancement of large language models (LLMs) necessitates novel monetization strategies, among which LLM-native advertising has emerged as a promising paradigm by naturally integrating advertisement within LLM-generated responses. However, this paradigm fundamentally shifts the auction object from discrete ad slots to the distribution over LLM outputs, posing new challenges for designing auction mechanisms. Existing mechanisms for LLM-native advertising adopt frameworks that decouple auction and generation, which either ignore externalities or require multiple LLM inferences for ad allocation, rendering them impractical for industrial scenarios. To address these challenges, we propose LLM-Auction, which to the best of our knowledge is the first learning-based generative auction mechanism that integrates auction and LLM generation for LLM-native advertising. By formulating the allocation optimization as a preference alignment problem between LLM outputs and the mechanism's objective which reflects both advertisers' expected value and user experience, we introduce Iterative Reward-Preference Optimization (IRPO) algorithm that alternately optimizes the reward model and the LLM. This approach enables the LLM to inherently model allocation externalities without any extra inference cost. We further identify the allocation monotonicity and continuity of LLM-Auction, which allows us to prove that a simple first-price payment rule exhibits favorable incentive properties. Additionally, we design an LLM-as-a-judge simulation environment to facilitate large-scale data construction and enable comprehensive quantitative evaluation of the mechanism's performance. Extensive quantitative and qualitative experiments demonstrate that LLM-Auction significantly outperforms existing baselines in allocation efficiency, while achieving the desired mechanism properties.
A partially parallel dynamical noisy binary choice (Ising) game in discrete time of $N$ players on complete graphs with $k$ players having a possibility of changing their strategies at each time moment called $k$-flip Ising game is considered. Analytical calculation of the transition matrix of game as well as the first two moments of the distribution of $\varphi=N^+/N$, where $N^+$ is a number of players adhering to one of the two strategies, is presented. First two moments of the first hitting time distribution for sample trajectories corresponding to transition from a metastable and unstable states to a stable one are considered. A nontrivial dependence of these moments on $k$ for the decay of a metastable state is discussed. A presence of the minima at certain $k^*$ is attributed to a competition between $k$-dependent diffusion and restoring forces.
Concavity and its refinements underpin tractability in multiplayer games, where players independently choose actions to maximize their own payoffs which depend on other players' actions. In concave games, where players' strategy sets are compact and convex, and their payoffs are concave in their own actions, strong guarantees follow: Nash equilibria always exist and decentralized algorithms converge to equilibria. If the game is furthermore monotone, an even stronger guarantee holds: Nash equilibria are unique under strictness assumptions. Unfortunately, we show that certifying concavity or monotonicity is NP-hard, already for games where utilities are multivariate polynomials and compact, convex basic semialgebraic strategy sets -- an expressive class that captures extensive-form games with imperfect recall. On the positive side, we develop two hierarchies of sum-of-squares programs that certify concavity and monotonicity of a given game, and each level of the hierarchies can be solved in polynomial time. We show that almost all concave/monotone games are certified at some finite level of the hierarchies. Subsequently, we introduce SOS-concave/monotone games, which globally approximate concave/monotone games, and show that for any given game we can compute the closest SOS-concave/monotone game in polynomial time. Finally, we apply our techniques to canonical examples of imperfect recall extensive-form games.
We present an algorithm for computing evolutionarily stable strategies (ESSs) in symmetric perfect-recall extensive-form games of imperfect information. Our main algorithm is for two-player games, and we describe how it can be extended to multiplayer games. The algorithm is sound and computes all ESSs in nondegenerate games and a subset of them in degenerate games which contain an infinite continuum of symmetric Nash equilibria. The algorithm is anytime and can be stopped early to find one or more ESSs. We experiment on an imperfect-information cancer signaling game as well as random games to demonstrate scalability.
Maximal extractable value opportunities often induce spam in Layer-2 blockchains: many identical transactions are submitted near simultaneously, most of which revert, wasting blockspace. We study Timeboost, a mechanism on Arbitrum that auctions a timestamp advantage, crucial under first-come first-served sequencing rules. We develop a game-theoretic model in which users choose the number of transaction copies to submit, and extend upon the baseline setting by modeling the Timeboost auction and subsequent transaction submission behavior. We show that Timeboost reduces spam and increases sequencer/DAO revenue in equilibrium relative to the baseline, transferring user payments from revert costs to auction bids. Empirically, we assemble mempool data from multiple Layer-2 networks, measuring spam via identical transactions submitted in narrow time intervals, and conduct an event study around Timeboost adoption on Arbitrum using other L2s as contemporaneous benchmarks. We find a decline in MEV-related spam and an increase in revenue on Arbitrum post-adoption, consistent with model predictions.
This paper introduces the formulation of a distributionally robust Markov game (DR-MG) with average rewards, a crucial framework for multi-agent decision-making under uncertainty over extended horizons. Unlike finite-horizon or discounted models, the average-reward criterion naturally captures long-term performance for systems designed for continuous operation, where sustained reliability is paramount. We account for uncertainty in transition kernels, with players aiming to optimize their worst-case average reward. We first establish a connection between the multi-agent and single agent settings, and derive the solvability of the robust Bellman equation under the average-reward formulation. We then rigorously prove the existence of a robust Nash Equilibrium (NE), offering essential theoretical guarantees for system stability. We further develop and analyze an algorithm named robust Nash-Iteration to compute the robust Nash Equilibria among all agents, providing practical tools for identifying optimal strategies in complex, uncertain, and long-running multi-player environments. Finally, we demonstrate the connection between the average-reward NE and the well-studied discounted NEs, showing that the former can be approximated as the discount factor approaches one. Together, these contributions provide a comprehensive theoretical and algorithmic foundation for identifying optimal strategies in complex, uncertain, and long-running multi-player environments, which allow for the future extension of robust average-reward single-agent problems to the multi-agent setting.