Various embodiments are directed to multi-user resource allocation capable of significantly reducing MAC header overhead and scheduling delay for small payload applications, such as Voice over Internet Protocol (VoIP) and interactive gaming and to increase the capacity of such applications. In various implementations, multi-user resource allocation may be used in mobile Worldwide Interoperability for Microwave Access (WiMAX) systems designed to operate in accordance with the Institute for Electronic and Electrical Engineers (IEEE) standards such as the 802.16e-2005 standard and/or the evolving IEEE 802.16m standard as well as Third Generation Partnership Project (3GPP), 3GPP Long Term Evolution (LTE), and/or 3GPP2 Ultra Mobile Broadband (UMB) standards.