We prove that attempts to formalize machine intelligence measures (MIMs) in an agent-environment framework suffer from the consequences of Arrow’s Impossibility Theorem; there does not exist an agent-environment-based MIM that satisfies analogs of Arrow’s fairness conditions (Pareto Efficiency, Independence of Irrelevant Alternatives, and Non-Oligarchy) for machine intelligence. We prove that this issue is faced by a large class of MIMs, including two of the most well known: Legg-Hutter Intelligence and Chollet’s Intelligence Measure.