Smoothed Arrovian Impossibility: Approximate Axioms under Computation and Communication Constraints

Hall (2023) surveys Mihara’s striking computability results: under standard axioms, the only voting systems that are in any sense computable are dictatorial, deflating the infinite-voter “possibility” loophole. This project flips the lens from exact, total computability to resource-bounded and approximate guarantees. We formalize epsilon-IIA, delta-transitivity, and probably-approximately-strategyproofness under randomness, profile noise, or communication limits (e.g., streaming or sublinear models). The aim is a smoothed impossibility/possibility theory: prove lower bounds showing that any polynomial-time, pairwise-computable (Hall) aggregator must be “epsilon-dictatorial” in worst case, but also prove average-case possibility theorems that exhibit non-dictatorial randomized social welfare functions whose axiom violations occur with vanishing probability on reasonable profile distributions (connecting to Penn, 2011, on paradox modeling). This reframes Arrow/GS as sharp worst-case barriers but identifies practical “safe zones” for platforms with millions of voters and bounded computation (with implications for alignment pipelines like RLHF; cf. Mishra, 2023). The innovation is to import smoothed-analysis style guarantees to social choice, quantifying how computational constraints interact with impossibility—something not addressed in Mihara/Hall’s exact computability framing.

References:

1. Arrow's Impossibility Theorem: Computability in Social Choice Theory. Alex Hall (2023).
2. Impossibility Theorems And Voting Paradoxes In Collective Choice Theory. E. M. Penn (2011).
3. AI Alignment and Social Choice: Fundamental Limitations and Policy Implications. Abhilash Mishra (2023). Social Science Research Network.