摘要:不同于离线网络,占线网络具有实时性和不可逆性。因此对于占线网络设施选址问题,一方面为了快速而有效地响应客户,需要立即确定客户是否可以获得来自设施提供的服务。另一方面一旦客户获得服务,客户与设施之间的服务链接不能再更改。在占线网络设施中,每个客户随机到达后,对服务进行投标,作为获得服务而愿意支付的最大成本。每个设施的开启均有一定的成本。因此需要通过机制设计来明确哪些设施为哪些客户提供服务,并明确获得服务的客户应承担的成本,使得网络总成本最小。客户出于自身利益最大化的考虑,会非真实披露购买服务的投标。更为严重的是网络中的多个客户可能通过共谋而以低成本获得服务,而对其他客户造成伤害。为此,本文通过交叉单调成本函数和组策略一致的概念,利用原始对偶思想,设计占线网络设施选址机制。在最坏/最好情况下以计算复杂性O(m*n3)/O(m*n2),获得3一占线近似预算平衡和防止共谋的目标。其中m是设施的数目,n是客户的数目。