本論文では,インターネットオークションで深刻な問題となり得る架空名義入札に対して,頑健性が保証される組合せオークションプロトコルの実現方法について検討する.インターネットを利用することにより低コストで大規模なオークションが可能となった一方で,ネットワークでの匿名性を利用した新しいタイプの不正行為が問題となる.このような不正行為の1つとして,単一のエージェントが,複数の名義を用いて入札を行う架空名義入札が存在する.複数種類の商品を扱う組合せオークションにおいて,架空名義入札に対して頑健なプロトコルとして,レベル付き分割セットプロトコル(LDSプロトコル)が提案されている.しかしながら,LDSプロトコルではオークションの主催者がレベル付き分割セットと呼ばれる一連の財のバンドルの組合せを決定しなければならない.良い社会的余剰を得られるようにレベル付き分割セットを設計することは,組合せオークションにおける勝者決定問題よりもはるかに複雑な最適化問題となる.本論文では良い社会的余剰を得ることができるレベル付き分割セットを設計するためのヒューリスティックな手法を提案する.この手法は勝者決定アルゴリズムを主要な構成要素として,目的とするバンドルの組合せを元に,レベル付き分割セットを構成する.計算機シミュレーションを用いて,提案手法により,パレート効率的な社会的余剰に非常に近い結果が得られることを示す.