Other Computer Science · Tue, Nov 10, 2026

Distributed computing, game theory, information theory and more.

RSS feed
arXiv cs.DC

Contention Resolution with a Fast-but-Fickle Channel

In briefContention resolution on a fast but unreliable channel: a randomized method for sharing a wireless link

SummaryThe paper studies how n devices share a communication channel without central coordination, using a reliable slow channel and a faster channel that can be intermittently disabled. It presents RACE, a randomized algorithm that uses the fast channel when available and keeps progress on the slow channel during disruptions. The authors give competitive-ratio bounds for expected latency and switching cost relative to offline algorithms, along with matching lower bounds.

Umesh Biswas, Vini Chaudhary, Shafqat Hasan et al.

★★★★☆ Notable
arXiv cs.GT · cs.DS

Computing EF1 Allocations under Budget Constraints in Polynomial Time

In briefComputing fair item allocations within budget limits in polynomial time

SummaryThis paper studies dividing indivisible items fairly among agents with budget constraints and additive valuations, requiring envy-freeness up to one item (EF1) between agents and toward a charity holding unallocated items. The authors give a polynomial-time algorithm for computing EF1 allocations under heterogeneous valuations. They also prove that detecting an EF1 violation is NP-complete and provide polynomial-time algorithms for EFX in two special valuation settings.

WhyThe authors resolve an open problem by giving a polynomial-time EF1 algorithm under budget constraints, plus NP-completeness and approximation results.

Tingwei Hu, Lili Mei, Guochuan Zhang

arXiv cs.GT

Learning Global Equilibria in Non-Concave Prospect Theoretic Games

In briefLearning Global Equilibria in Non-Concave Prospect Theory Games

SummaryThis paper studies non-cooperative games in which agents behave non-rationally, modeled with prospect theory, which makes utility functions non-concave and non-convex and equilibrium computation hard. It proposes a minorization-maximization learning algorithm and proves global convergence to a potential-maximizing Nash equilibrium under a proximal Polyak-Lojasiewicz condition on the potential function. The paper also shows how the MM minorizer's structure enables distributed implementation.

Ashok Krishnan K.S., Lilou Malfoy, Helene Le Cadre et al.