More Like this

1. Learning From Strategic Agents: Accuracy, Improvement, and Causality, ICML

   Shavit, Yonadav; Edelman, Benjamin; Axelrod, Brian (July 2020, Proceedings of Machine Learning Research)

   In many predictive decision-making scenarios, such as credit scoring and academic testing, a decision-maker must construct a model that accounts for agents' incentives to ``game'' their features in order to receive better decisions. Whereas the strategic classification literature generally assumes that agents' outcomes are not causally dependent on their features (and thus strategic behavior is a form of lying), we join concurrent work in modeling agents' outcomes as a function of their changeable attributes. Our formulation is the first to incorporate a crucial phenomenon: when agents act to change observable features, they may as a side effect perturb unobserved features that causally affect their true outcomes. We consider three distinct desiderata for a decision-maker's model: accurately predicting agents' post-gaming outcomes (accuracy), incentivizing agents to improve these outcomes (improvement), and, in the linear setting, estimating the visible coefficients of the true causal model (causal precision). As our main contribution, we provide the first algorithms for learning accuracy-optimizing, improvement-optimizing, and causal-precision-optimizing linear regression models directly from data, without prior knowledge of agents' possible actions. These algorithms circumvent the hardness result of Miller et al. (2019) by allowing the decision maker to observe agents' responses to a sequence of decision rules, in effect inducing agents to perform causal interventions for free. 

   more » « less
2. Algorithmic Decision-Making under Agents with Persistent Improvement

   Xie, Tian; Tan, Xuwei; Zhang, Xueru (August 2024, 7th AAAI Conference on AI, Ethics, and Society)

   This paper studies algorithmic decision-making under human's strategic behavior, where a decision maker uses an algorithm to make decisions about human agents, and the latter with information about the algorithm may exert effort strategically and improve to receive favorable decisions. Unlike prior works that assume agents benefit from their efforts immediately, we consider realistic scenarios where the impacts of these efforts are persistent and agents benefit from efforts by making improvements gradually. We first develop a dynamic model to characterize persistent improvements and based on this construct a Stackelberg game to model the interplay between agents and the decision-maker. We analytically characterize the equilibrium strategies and identify conditions under which agents have incentives to improve. With the dynamics, we then study how the decision-maker can design an optimal policy to incentivize the largest improvements inside the agent population. We also extend the model to settings where 1) agents may be dishonest and game the algorithm into making favorable but erroneous decisions; 2) honest efforts are forgettable and not sufficient to guarantee persistent improvements. With the extended models, we further examine conditions under which agents prefer honest efforts over dishonest behavior and the impacts of forgettable efforts. 

   more » « less
3. Fair and Efficient Memory Sharing: Confronting Free Riders

   Friedman, Eric J.; Gkatzelis, Vasilis; Psomas, Christos-Alexandros; Shenker, Scott (January 2019, Proceedings of the ... AAAI Conference on Artificial Intelligence)

   A cache memory unit needs to be shared among n strategic agents. Each agent has different preferences over the files to be brought into memory. The goal is to design a mechanism that elicits these preferences in a truthful manner and outputs a fair and efficient memory allocation. A trivially truthful and fair solution would isolate each agent to a 1/n fraction of the memory. However, this could be very inefficient if the agents have similar preferences and, thus, there is room for cooperation. On the other hand, if the agents are not isolated, unless the mechanism is carefully designed, they have incentives to misreport their preferences and free ride on the files that others bring into memory. In this paper we explore the power and limitations of truthful mechanisms in this setting.We demonstrate that mechanisms blocking agents from accessing parts of the memory can achieve improved efficiency guarantees, despite the inherent inefficiencies of blocking. 

   more » « less
4. Scalable Mechanism Design for Multi-Agent Path Finding

   https://doi.org/10.24963/ijcai.2024/7  

   Friedrich, Paul; Zhang, Yulun; Curry, Michael; Dierks, Ludwig; McAleer, Stephen; Li, Jiaoyang; Sandholm, Tuomas; Seuken, Sven (August 2024, International Joint Conferences on Artificial Intelligence Organization)

   Multi-Agent Path Finding (MAPF) involves determining paths for multiple agents to travel simultaneously and collision-free through a shared area toward given goal locations. This problem is computationally complex, especially when dealing with large numbers of agents, as is common in realistic applications like autonomous vehicle coordination. Finding an optimal solution is often computationally infeasible, making the use of approximate, suboptimal algorithms essential. Adding to the complexity, agents might act in a self-interested and strategic way, possibly misrepresenting their goals to the MAPF algorithm if it benefits them. Although the field of mechanism design offers tools to align incentives, using these tools without careful consideration can fail when only having access to approximately optimal outcomes. In this work, we introduce the problem of scalable mechanism design for MAPF and propose three strategyproof mechanisms, two of which even use approximate MAPF algorithms. We test our mechanisms on realistic MAPF domains with problem sizes ranging from dozens to hundreds of agents. We find that they improve welfare beyond a simple baseline. 

   more » « less
5. Earth stewardship: Shaping a sustainable future through interacting policy and norm shifts

   https://doi.org/10.1007/s13280-022-01721-3  

   Chapin, F. Stuart; Weber, Elke U.; Bennett, Elena M.; Biggs, Reinette; van den Bergh, Jeroen; Adger, W. Neil; Crépin, Anne-Sophie; Polasky, Stephen; Folke, Carl; Scheffer, Marten; et al (September 2022, Ambio)

   Abstract Transformation toward a sustainable future requires an earth stewardship approach to shift society from its current goal of increasing material wealth to a vision of sustaining built, natural, human, and social capital—equitably distributed across society, within and among nations. Widespread concern about earth’s current trajectory and support for actions that would foster more sustainable pathways suggests potential social tipping points in public demand for an earth stewardship vision. Here, we draw on empirical studies and theory to show that movement toward a stewardship vision can be facilitated by changes in either policy incentives or social norms. Our novel contribution is to point out that both norms and incentives must change and can do so interactively. This can be facilitated through leverage points and complementarities across policy areas, based on values, system design, and agency. Potential catalysts include novel democratic institutions and engagement of non-governmental actors, such as businesses, civic leaders, and social movements as agents for redistribution of power. Because no single intervention will transform the world, a key challenge is to align actions to be synergistic, persistent, and scalable. 

   more » « less