The field of computational complexity and fairness is moving towards a deeper understanding of the interplay between randomized and pseudodeterministic communication protocols. Recent work has shown an exponential separation between these two models, highlighting the importance of pseudodeterminism in achieving efficient communication. Furthermore, researchers are exploring new approaches to fair division, including the allocation of indivisible items and the consideration of social impact. Notable papers in this area include 'Pseudodeterministic Communication Complexity', which exhibits a partial function with randomized communication complexity O(log n) but requires randomized communication complexity n^Ω(1) for any completion of this function into a total one. Another noteworthy paper is 'Fair Multi-agent Persuasion with Submodular Constraints', which presents a signaling policy that achieves a logarithmically approximate majorized policy in the setting of Bayesian persuasion with submodular constraints.
Advances in Fairness and Computation
Sources
Pseudodeterministic Communication Complexity
Dynamic Allocation of Public Goods with Approximate Core Equilibria
Persuading Stable Matching
Optimal Selection Using Algorithmic Rankings with Side Information
Fair Division with Indivisible Goods, Chores, and Cake
Confidentiality in a Card-Based Protocol Under Repeated Biased Shuffles
Leveraging the Power of AI and Social Interactions to Restore Trust in Public Polls
Centralized Group Equitability and Individual Envy-Freeness in the Allocation of Indivisible Items
Dividing Indivisible Items for the Benefit of All: It is Hard to Be Fair Without Social Awareness
Classification in Equilibrium: Structure of Optimal Decision Rules
Fair Multi-agent Persuasion with Submodular Constraints
Formal Verification of Diffusion Auctions
Random Permutations in Computational Complexity
Minimal Regret Walras Equilibria for Combinatorial Markets
Understanding the Impact of Proportionality in Approval-Based Multiwinner Elections
Minimal Regret Walras Equilibria for Combinatorial Markets via Duality, Integrality, and Sensitivity Gaps