随着通信网络的发展,信息论的研究开始由点对点的简单场景向多用户的场景演进,多用户信息论成为信息论领域内的研究热点。传统的多用户信息论重点关注消息在网络中的存储和传输。但网络中还存在一大类不以恢复消息为目的,而是旨在通过用户间的信息交互实现特定任务的问题,例如分布式计算、用户关系的协调等。这些特定任务的执行,有赖于节点之间显式或隐式的通信过程,但却无需传递节点完整的状态信息。此类与任务结构有关的通信与传统多用户信息论的研究有显著区别,近年来受到了广泛关注。本文从应用中抽象出了一类以建立和识别用户协作关系为目的的多用户通信问题,并在多址接入二进制信道环境下,基于信息论的研究范式,开展了为建立和识别用户协作关系所需的通信开销界限的理论研究。主要工作包含三部分:第一,根据多址接入中多用户冲突的分布式协调机制,建模了一类用户划分关系的建立问题,并提出了一种图论表达方法,将用户及其状态建模成超图,划分的目标可看作对超图的强着色,通信过程可看作对该超图的一系列删边操作。该方法揭示了信息在划分关系建立中所起的作用。进而,在理想多址接入二进制信道下,利用信源编码导出的穷举法、随机编码两种方法,给出了建立划分关系所需通信开销的可达界,其开销比以消息传输为目的的通信开销小;第二,在有噪声多址接入二进制信道下,提出了一种基于强典型集的联合边构造方法,以及解决噪声导致的删边错误问题。并在随机编码框架下,利用问题的Markov结构给出了建立划分关系所需通信开销的可达界,其开销比以消息传输为目的的通信开销小;第三,建模了一类多址接入二进制信道下用户协作模式的主动识别问题。将用户及其通信关系用加权图表达,则系统可能的协作模式可看作是一组先验已知的加权图,我们的目标是利用用户间的通信,对该组加权图进行区分。在随机化编码的框架下,提出了可使用图的内部连通性指标作为识别特征,并对一类互补Paley图给出了最小通信开销的解析解,揭示了该问题与图的独立集、Discrepancy性质的联系。