NeurIPS 2026 论文列表

We consider linear equations with min and max operators~(LEMMs) that contain many subproblems ranging from optimization, learning, to games. Recently, Chatterjee et al. [2025] gave a systematic study of the complexity of different subclasses. Three key subclasses--(I) halting branching process, (II) absolutely halting LEMMs, and (III) halting LEMMs--are proved to be in UP $\cap$ coUP while generalizing stochastic games (SSGs). In this work, we study the classic algorithms of Policy Iteration (PI) and Value Iteration (VI) for these general subclasses. First, we simplify the problem hierarchy by showing the equivalence between halting branching process and SSGs. Then, we show that while PI diverges for absolutely halting LEMMs due to the loss of monotonicity, VI remains convergent, a result we establish via diagonal rescaling. Finally, we show that neither PI nor VI converges for general halting LEMMs and, to this end, propose variants of simple policy iteration that ensure convergence across all subclasses.

The rise of generative AI and autonomous agents is creating ecosystems in which stakeholders strategically choose which agents to deploy on their behalf. These design choices--such as model backbone, prompting strategy, tool access, and fine-tuning pipeline--are often strategically interdependent, as the performance of a deployed agent depends on the agents chosen by others. This position paper argues that this agent design stage should itself be a target for mediation. This perspective shifts attention from mediating only the \emph{downstream} interaction among deployed agents to mediating the \emph{upstream} stakeholder game that determines which agents enter that interaction in the first place. We formalize this agent design stage as a \emph{meta-game}, show how its equilibria can be collectively harmful, and discuss how various forms of mediation can realign incentives toward socially beneficial outcomes. We demonstrate these mediation approaches using both stylized examples and a real-world case study constructed from empirical LLM-agent interaction data. We outline concrete research directions for developing mediators that steer agentic design choices toward socially desirable outcomes.

Large language models successfully solve classic theory-of-mind tasks adapted from cognitive science, but the mechanisms underlying this ability remain unclear. Do they deploy circuitry specialized for reasoning about other minds, memorize common false-belief vignette structures and outputs, or rely on more domain-general computations? We investigate this question in Qwen2.5-14B-Instruct using causal mediation and representational similarity analyses across matched prompt sets that systematically vary an agent’s beliefs, the state of the physical world, and the correct answer. We identify a population of mid-layer attention heads that tracks divergence between an initial representation and the current state of the world. These heads are causally relevant regardless of whether the initial representation is an agent’s belief or a photograph, despite the photograph condition involving no agent or perspective-taking. A distinct population of later-layer heads retrieves the answer token. The two populations are functionally dissociable yet combine compositionally. Together, these findings argue against both mentalizing-specific and memorization accounts, suggesting instead that LLMs solve classic false-belief problems by reusing a domain-general mechanism for detecting divergence between representations and reality.