TechTalk – Speeding Up Fairness: The Science of Fast Convergence in Markets and Graphs
April 3, 2025 (Thursday) 4:30-5:30pm
Achieving fairness in resource allocation can be modeled as a graph-based optimization problem, with many efficient algorithms available. This talk explores the connection between market equilibrium and graph density decomposition, showing how fast convergence can be achieved in large-scale systems. We present a unified framework linking hypergraph density decomposition and Fisher market equilibrium through locally verifiable optimality conditions. This symmetry allows repurposing algorithms between domains, significantly accelerating convergence.
We focus on iterative gradient-based methods, including the iterative proportional response process and its momentum-enhanced extensions. Our novel exponential momentum approach refines traditional techniques, delivering near-optimal solutions in distributed settings. Empirical results show these methods outperform existing algorithms, achieving speedups by several orders of magnitude in large-scale graphs.
By integrating graph theory, market dynamics, and optimization, this talk offers new insights into efficient computation to achieve fairness in networked systems. These methods deepen our understanding of algorithmic principles and open new applications in algorithm design, social networks, and economic modeling.