Workshop

Abstract: The existence of EFX allocations is a central open problem in discrete fair division. An allocation is EFX (envy-free up to any good) if no agent envies another agent after the removal of any single good from the other agent's bundle. We resolve this longstanding question by providing the first-ever counterexample to the existence of EFX allocations for agents with monotone valuations, which in turn immediately implies a counterexample for submodular valuations.

Specifically, we show that EFX allocations need not exist for instances with n>2  agents and m > n+4 goods. In contrast, we prove that every instance with three agents and seven goods admits an EFX allocation. Both results are obtained via SAT solving. We encode the negation of EFX existence as a SAT instance: satisfiability yields a counterexample, while unsatisfiability establishes universal existence. The correctness of the encoding is formally verified in Lean.

Finally, we establish positive guarantees for fair allocations with three agents and an arbitrary number of goods. Although EFX allocations may fail to exist, we prove that every instance with three agents and monotone valuations admits at least one of two natural relaxations of EFX: tEFX, or EF1 and EEFX.

Abstract : A decision-maker (DM) repeatedly makes choices under uncertainty in a bandit environment, where only the realization of the chosen arm is observed. Another competing agent, the adviser (AD), repeatedly provides recommendations, but the realizations of these recommendations are unobserved unless they coincide with the DM’s choice. Both agents possess partial information about the arms’ realizations. The central question we focus on is whether, in the long run, an outside observer can identify which agent is more informed based solely on the observed decisions, recommendations, and arm realizations. A test selects one of the agents based on the observed data. We focus primarily on the class of scoring tests, which assign a numerical score to each observation and select the agent according to the average score. We study strategic agents whose objective is to be selected by the test. For simultaneous arm choices, we show that there exists a scoring test that successfully identifies the more-informed agent. For sequential arm choices, however, no such scoring test exists. Finally, we explore the tension between identifying the more-informed agent and maximizing welfare. A DM whose objective is to pass the test may not necessarily make welfare-maximizing decisions. In a binary-arm environment, we show that no scoring test can simultaneously identify the more informed agent and achieve more than half of the welfare attained by welfare-maximizing decisions.

Abstract : We characterize correlated equilibrium in finite normal-form games. Interpreting correlated strategies as action recommendations, we show that correlated equilibrium is the unique solution concept that never recommends a pure-strategy dominated action, treats payoff-equivalent actions interchangeably, and respects the sure-thing principle under uncertainty about payoffs and the correlation device. A parallel characterization identifies coarse correlated equilibrium among solution concepts that recommend dominant actions whenever they exist and treat payoff-equivalent actions as strongly interchangeable.

Abstract: We analyze the performance of Krasnosel’ski--Mann's fixed point iteration when applied to a strict contraction. This iteration is ubiquitous across many fields, including convex optimization,  monotone inclusions, Markov decision processes, under-relaxed methods for PDEs, and more.

Drawing on a remarkable connection with a Markov chain on the lattice $\mathbb{Z}^2$, and  using counting arguments from enumerative combinatorics, we derive explicit estimates for the  distance between iterates and error bounds for the fixed point residuals. 

In the nearly non-expansive regime, these estimates provide better guarantees than the classical  Banach-Picard iteration. As the contraction parameter approaches one, we smoothly recover the  vanishing bounds already known for nonexpansive maps.  

Building upon these estimates, we further derive error bounds for inexact iterations.

Abstract: We study communication by an informed sender to many heterogeneous receivers. Receivers differ in state-dependent preferences and outside options, and accept when their posterior expected payoff exceeds their outside option. We compare public and targeted versions of persuasion, mediation, and cheap talk. Targeting alone has no value without commitment: discriminatory cheap talk is equivalent to public cheap talk. Commitment alone is also limited: public mediation reaches public persuasion only when public cheap talk already does. In contrast, targeted mediation can strictly improve on cheap talk, because a mediator can balance the sender’s reporting incentives across different receivers. In some environments, targeted mediation attains the full-commitment benchmark. The model applies naturally to platform-mediated communication between sellers and consumers.

Abstract : Equilibria in nonatomic congestion games model how traffic distributes across resources when independent agents seek to minimize their own delays. While one might expect increased demand to uniformly increase resource usage, paradoxical non-monotone behavior is a well-documented phenomenon. In this talk, we investigate the monotonicity of equilibrium loads and costs as functions of total demand.

In the classic case of single-commodity routing, it is known that network topology alone dictates these paradoxes. However, with multiple commodities, the combinatorial structure of strategy sets also plays an important role. We first show that singleton congestion games maintain monotone equilibrium loads with respect to any demand. We then extend this result to a broader class of multi-commodity games, which we define as Constrained Series-Parallel (CSP) games. Finally, we show that CSP games can be represented as a variant of multi-commodity routing games on series-parallel networks, bridging the gap between abstract strategy sets and physical network topology. 

Abstract : We establish a revelation principle for interim correlated rationalizability. A direct representation based only on terminal rationalizable action sets generally fails: revealing these sets may discard the lower-order information that generated them and thereby change the rationalizable outcomes. The appropriate direct object is the full hierarchy of action sets surviving the iterative rationalizability procedure. For games whose exact best-response regions are convex, every information structure is outcome-equivalent to the distribution it induces over states and rationalizability hierarchies. These distributions are characterized by level-by-level obedience constraints and implement themselves under interim correlated rationalizability. This class includes all finite binary-action games and a class of ordered games with interval best-response sets. For arbitrary finite games, exact best-response regions need not be convex. We restore the revelation principle by partitioning them into finitely many convex cells and augmenting each level of the hierarchy with a finite cell tag. The resulting tagged hierarchies satisfy an analogous obedience characterization, and projecting away the tags recovers the original interim correlated rationalizability hierarchy. Thus, for every finite game, strategically relevant information admits a countable, game-dependent direct representation.

Abstract : We study a reputational cheap-talk environment in which a judge, who is privately and imperfectly informed about a state, must choose between two speakers of unknown reliability. Exactly one speaker is an expert who perfectly observes the state, while the other is a quack with no information. Both speakers seek to be selected, while the judge wishes to identify the expert. We show that, quite generally, there is an equilibrium in which the expert is honest, yet the judge favors more extreme signals. This bias toward extremism does not induce exaggeration by the expert, but instead sustains truthful communication. The quack strategically mimics the expert's speech, and sometimes panders to the judge's prior. We show that learning in this environment exhibits an ``information begets information'' property: judges with more precise private information are more likely to identify the expert and learn the true state, implying that exposure to competing sources of uncertain reliability may amplify informational inequality across audiences.

Abstract : A significant challenge in managing large-scale engineering systems, such as energy and transportation networks, lies in enabling autonomous decision-making among interacting agents. Game theory offers a framework for modeling and analyzing these types of problems. In many practical applications, like power markets, each player only has partial information about the cost functions and actions of others. Therefore, a decentralized learning approach is essential to devise optimal strategies for each player.

Abstract : We propose a new solution concept for normal-form games with incomplete information. In our baseline model, players’ beliefs take the form of opponent-specific moments of marginal action distributions; there is no common prior. We prove the existence of moment equilibrium, in which players act optimally given their moment beliefs and those beliefs are consistent with the distribution of play. Moment equilibrium exists when each player’s value function is measurable in type and continuous in moment beliefs. It nests Bayes-Nash equilibrium when every player’s moments identify each opponent’s marginal action distribution, while allowing strategic uncertainty when they do not.

Abstract : We consider multi-agent combinatorial contracts, where a principal must incentivize a team of agents who are each capable of executing multiple actions. The goal is to choose a contract that approximately maximizes the principal's utility. We propose an approximation algorithm that achieves a constant-factor approximation. The guarantee compares the worst equilibrium of our contract to the best one of the best contract. This holds even for all mixed Nash and coarse-correlated equilibria. 

Abstract : We study competition between firms that contract with consumers before the consumers fully learn their product preferences. In a Hotelling duopoly, firms screen consumers by offering menus of option contracts. We characterize the unique equilibrium. Consumers select contracts from both firms. Each consumer is endogenously locked into the firm from which he chooses an option with a lower strike price. Lock-in yields inefficient consumption. Yet earlier contracting stiffens competition because less informed consumers are more homogeneous. Sufficiently early contracting raises consumer surplus relative to spot pricing -- reversing the ranking under monopoly. Exclusive contracting further increases consumer surplus by intensifying competition.

Abstract : We introduce a concept of stability of a Nash equilibrium, or of a set of Nash equilibria, to the addition of small players, i.e., players who only have a small effect on the original players. We coin this concept 'small-player robustness' or 'uniform small-player robustness', depending on the specific condition required. We show that either of these conditions is equivalent to the essentiality condition of Govindan and Wilson (2005). The game constructions are related to techniques for representing functions as equilibrium correspondences of families of games that have previously been used in establishing the complexity of computing Nash equilibria, and combine these with semialgebraic geometry and new fixed-point theorems.

Abstract: We study convergence of decentralised dynamics in trading networks with bilateral contracts. Agents may be buyers, sellers, or both, and interact only through local offers or asynchronous demand reports. The first type of interaction is formalized in our trading network game, in which agents submit offers on their incident trades. Although arbitrary Nash equilibria can be inefficient, we show that tight Nash equilibria are equivalent to competitive equilibria of the underlying trading network market, and thus efficient. We prove that the best-response dynamic of Lock et al., [2025], a natural dynamic for the network game, converges for 3-sparse markets with fully substitutable agent preferences, extending the known 2-sparse result, and we disprove convergence for general k-sparse markets when k ≥ 4. We also develop high-probability last-iterate approximate convergence results for any k, where cycling remains close to competitive equilibrium prices. For the second type of interaction, we propose a stochastic clock-price dynamic in which agents report their demand (at current prices) asynchronously, in randomized order. We prove that fixed step sizes yield high-probability approximate last-iterate convergence, while decreasing step sizes yield convergence to competitive-equilibrium prices. Our analysis uses the structure and geometry of fully substitutable preferences and connects local decentralised behaviour to competitive and Nash equilibrium.

Abstract : A network is called a global village if repeated local competition within it leads to globally efficient wealth allocation. We study the Erdös Rényi random graph process, in which connections between agents are added randomly over time. We prove that, with high probability, the emergence of a global village coincides exactly with the disappearance of the last leaf: the network becomes a global village at the moment its minimum degree reaches two.

Abstract : We examine a dynamic search game played between two players: the hider and the searcher. The hider chooses an initial vertex of a directed graph and hides there, and at any period travels along one of the outgoing arcs. The searcher at each period chooses an arbitrary vertex of the graph, and if the hider is there, then the hider is found and the game ends. The hider does not observe which vertex is searched by the searcher. The searcher's goal is to minimize the expected search time, whereas the hider's goal is to maximize it.

Abstract : A fundamental question in market design is how to maximize revenue in dynamic environments. We study a simple market model in which forward-looking buyers arrive over discrete time periods and a monopolist seller holds a limited supply of a single good. For i.i.d. and regular valuations, Board and Skrzypacz (2016) characterized the optimal mechanism and showed that posted prices are optimal in the continuous-time limit. We consider the limit of a continuum of buyers and show that, for arbitrary independent (not necessarily i.i.d. or regular) valuations, posted prices combined with capacity rationing implement the optimal anonymous mechanism. This departs from prior work along three dimensions: no regularity assumptions, general independent arrivals, and a mechanism that uses rationing alongside prices. If supply is unlimited, we show that the rationing effect vanishes, and the optimal mechanism can be implemented using posted prices only, à la Board [2008].

Abstract : Coalition formation is a widely studied problem in multi-agent systems, where the goal is to partition agents into groups according to their preferences. In many realistic settings, these preferences are private information, and agents may strategically misreport them to obtain more favorable outcomes. We aim to present recent advances in the design of manipulation-resistant mechanisms for coalition formation, focusing on two prominent models: Hedonic Games and the Group Activity Selection Problem.

The talk considers two notions of resistance to manipulation: strategyproofness, where truthful reporting is a dominant strategy, and non-obvious manipulability, a weaker notion that captures boundedly rational agents who may fail to recognize profitable deviations. For both notions, we discuss mechanisms that approximately maximize utilitarian social welfare while guaranteeing truthful reporting by the agents.

More broadly, with this talk, we aim at highlighting this research direction as a promising avenue for future work and to encourage a reconsideration of how resistance to manipulation should be defined, thereby opening the door to the future study of alternative notions that better capture strategic behavior in practice.

Abstract : Classical strategic queueing models predict simple and robust behavior: in the seminal model of Naor, rational agents follow a unique threshold rule. This prediction, however, relies crucially on agents interacting with the queue only once, making myopic behavior optimal. We study how equilibrium behavior changes when agents can repeatedly attempt to enter the queue over time.

We consider a queueing game with a finite population of rational agents who receive stochastic opportunities to join or balk and may be served multiple times, giving rise to an asynchronous stochastic game. We characterize stationary equilibria and identify conditions under which the classical Naor threshold remains valid. Outside this regime, strategic re-entry can generate substantially richer behavior, including equilibrium multiplicity, asymmetry, and randomization.

For general populations, we develop a reduction to a semi-Markov decision process that allows us to study symmetric threshold equilibria and their robustness. Our analysis shows that repeated entry opportunities can undermine both the uniqueness and the existence properties familiar from classical queueing games. More broadly, the results highlight how even a simple form of dynamic interaction can fundamentally alter strategic behavior in queues.