Distributed Random Access Scheduling

We consider a network of wireless routers. The routers that are close together can interfere if they transmit simultaneously. So schedules need to avoid such collisions. We want each each wireless node to achieve a transmission rates that equals its arrival rate. One might want to implement a policy like MaxWeight or simply estimate the vector of arrival rates and accordingly choose the correct transmission rate. However, this is complicated by the fact that the routers do not know the arrival and transmission rates of their neighbors; all they can do is sense if their neighbors are transmitting or not.

Continue reading “Distributed Random Access Scheduling”

Blackwell Approachability

Sequentially a player decides to play \{p_t\}_{t=1}^\infty and his adversary decides \{q_t\}_{t=1}^\infty. At time t, a decision (p_t,q_t) results in a vector payoff A(p_t,q_t)\in {\mathbb R}^k. Given a_t is the average vector payoff at time t, Blackwell’s Approachability Theorem is a necessary and sufficient condition so that, regardless of the adversary’s decisions, the player makes the sequence of vectors \{a_t\}_{t=1}^\infty approach a convex set {\mathcal A}.

Continue reading “Blackwell Approachability”