Éva Tardos

Robert Kleinberg, Erald Sinanaj, Éva Tardos

Several recent works investigate the effects of monoculture, the ever increasing phenomenon of (possibly) self-interested actors in a society relying on one common source of advice for decision making, with an archetypal driving example being the growing adoption and predictive power of machine learning models in matching markets, e.g. in hiring. Kleinberg and Raghavan (PNAS, 2021) introduced a model that captures the effects of monoculture in a one-sided matching market with advice, demonstrating that a higher accuracy common signal (such as an algorithmic vendor) might incentivize society as a whole to rationally adopt it, but as a collective it would be better off if each instead adopted less accurate, but private advice. We generalize their model and address the open question of their work in quantifying the social welfare loss. We find that monoculture and more generally decentralized optimization is close to optimal: we show a tight constant bound of 2 on the price of anarchy (and more general notions) for the induced game.

Giannis Fikioris, Balasubramanian Sivan, Éva Tardos

The study of repeated interactions between a learner and a utility-maximizing optimizer has yielded deep insights into the manipulability of learning algorithms. However, existing literature primarily focuses on independent, unlinked rounds, largely ignoring the ubiquitous practical reality of budget constraints. In this paper, we study this interaction in repeated second-price auctions in a Bayesian setting between a learning agent and a strategic agent, both subject to strict budget constraints, showing that such cross-round constraints fundamentally alter the strategic landscape. First, we generalize the classic Stackelberg equilibrium to the Budgeted Stackelberg Equilibrium. We prove that an optimizer's optimal strategy in a budgeted setting requires time-multiplexing; for a $k$-dimensional budget constraint, the optimal strategy strictly decomposes into up to $k+1$ distinct phases, with each phase employing a possibly unique mixed strategy (the case of $k=0$ recovers the classic Stackelberg equilibrium where the optimizer repeatedly uses a single mixed strategy). Second, we address the intriguing question of non-manipulability. We prove that when the learner employs a standard Proportional controller (the "P" of the PID-controller) to pace their bids, the optimizer's utility is upper bounded by their objective value in the Budgeted Stackelberg Equilibrium baseline. By bounding the dynamics of the PID controller via a novel analysis, our results establish that this widely used control-theoretic heuristic is actually strategically robust.