고전 MAS 1: Contract Net Classical MAS 1: Contract Net

계산, 글쓰기, 코드를 각각 담당하는 에이전트가 있다면 작업에 맞는 에이전트를 골라야 한다. Reid G. Smith는 1980년 IEEE Transactions on Computers에 발표한 “The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver”에서 협상을 통한 작업 배정 절차를 제안했다.

Smith의 논문에서는 컴퓨터 여러 대가 하나의 큰 문제를 나눠 푼다. 각 컴퓨터는 자기가 무엇을 할 수 있는지만 안다. 전체 작업을 배정하는 중앙 컴퓨터는 없다. Smith는 어떤 일을 어떤 컴퓨터가 맡을지 정하는 문제를 connection problem이라 불렀고, 답으로 협상을 택했다.

중앙에서 통제하지 않고, 정보가 양쪽으로 오가며, 각자가 자기 기준으로 판단하고, 양쪽이 서로 고른다(mutual selection). contractor는 여러 공고 중 자기에게 맞는 것을 고르고, manager는 여러 입찰 중 하나를 고른다.

일을 가진 쪽이 manager가 되어 공고(task announcement)를 낸다. 공고에는 작업 내용(task abstraction), 입찰 자격(eligibility specification), 입찰서 항목(bid specification), 입찰 마감(expiration time)을 적는다. 자격이 되는 쪽이 입찰(bid)을 보낸다. 입찰서에는 자기가 할 수 있는 것을 적는다(node abstraction). manager가 입찰을 비교해 하나를 고르고 낙찰(award)한다. 낙찰받은 쪽이 contractor가 되어 일을 하고, 결과를 보고(report)한다.

논문의 예는 센서 네트워크다. 넓은 지역에 센서와 컴퓨터가 흩어져 있고, 함께 차량이 어디로 움직이는지 지도를 만든다. 논문 첫 그림의 공고에서 자격은 “센서가 있을 것, 구역 A에 있을 것”이고, 입찰서에 적을 것은 “위도와 경도, 센서마다 이름과 종류”다. manager가 입찰서에 적을 항목을 정하므로 contractor는 그 항목만 보내고, manager는 그 항목만 보고 고른다.

TASK-ANNOUNCEMENT [name] {task-abstraction} {eligibility-specification} {bid-specification} [expiration-time]
BID               [name] {node-abstraction}
ANNOUNCED-AWARD   [name] {task-specification}
DIRECTED-AWARD    [name] {task-abstraction} {eligibility-specification} {task-specification}
ACCEPTANCE | REFUSAL [name] {refusal-justification}
INTERIM-REPORT | FINAL-REPORT [name] {result-description}
TERMINATION       [name]
NODE-AVAILABLE    {eligibility-specification} {node-abstraction} [expiration-time]
REQUEST | INFORMATION

directed award는 manager가 적임자를 이미 알 때 공고 없이 바로 맡기는 메시지다. request와 information은 계약까지 갈 필요 없는 짧은 질문과 답이다. node available은 작업을 받을 수 있는 노드가 가용 상태를 알리는 메시지이다. manager는 이 알림을 받아 해당 노드에 맞는 작업을 찾는다. Smith는 자격 조건과 directed award를 두는 이유를 쓸데없는 메시지와 입찰 처리 부담을 줄이기 위해서라고 적었다.

역할은 일마다 바뀐다. 낙찰받은 contractor가 일을 더 잘게 쪼개 다시 공고하면, 그 작은 일들의 manager다. 한 컴퓨터가 어떤 일에서는 contractor이면서 다른 일에서는 manager일 수 있고, 일을 남에게 맡긴 컴퓨터는 결과를 기다리는 동안 다른 일을 받을 수 있다. Smith는 이렇게 층이 겹치는 구조가 task-sharing의 기본 모양이라고 적었다.

Smith와 Randall Davis는 1983년 “Negotiation as a Metaphor for Distributed Problem Solving”에서 이 절차를 분산 문제 해결에 적용할 수 있는 협상 방식으로 정리했다.

Smith는 contractor가 무엇을 근거로 입찰하고 manager가 무엇을 기준으로 고르는지는 정하지 않았다. Tuomas Sandholm이 1993년 AAAI 논문에서 이 부분을 채웠다. 입찰가는 그 일을 지금 하는 일에 더했을 때 늘어나는 비용(marginal cost)이고, 각자 자기 이익만 따지는 에이전트들이 이 값으로 거래한다. 2002년 FIPA는 이 절차를 Contract Net Interaction Protocol이라는 표준으로 만들었다. manager가 cfp(제안 요청)를 보내고, 참여자는 propose(제안) 또는 refuse(거절)로 답하고, manager는 accept-proposal과 reject-proposal로 결과를 알리고, 일을 맡은 쪽은 inform(완료) 또는 failure(실패)로 끝낸다. cfp에는 답장 마감이 있고, 제안은 수락되는 순간 지켜야 하는 약속이 된다. 로봇 연구에서는 Gerkey와 Matarić이 2004년 여러 로봇에게 일을 나누는 문제의 분류 체계를 세웠고, Dias 등이 2006년 시장 방식의 로봇 협업 연구를 정리했다.

첫째 한계는 통신과 입찰 처리 비용이다. 공고를 모두에게 보내면 참여자 수만큼 메시지가 나가고, 입찰이 들어오면 manager가 전부 읽고 비교해야 한다.

둘째는 국소 최적(local optimum)이다. 계약은 그 순간 들어온 입찰만 보고 맺는다. 개별 계약에서 유리한 선택이 전체 작업의 최적 배정을 보장하지는 않는다. Sandholm은 “지금 상태에서 더 이득이 되는 교환이 없다”는 상태를 k-optimal이라 부르고, 이것이 전체 최적을 보장하지는 않는다고 적었다.

셋째는 신뢰다. 입찰은 “내가 이 일을 할 수 있다”는 주장이다. 이 주장이 참인지 확인하는 메시지가 절차에 없다. Smith의 시스템은 노드들이 공동의 문제를 해결하는 설정이었고, 입찰 정보는 위치와 센서 목록이었다. Sandholm의 self-interested agent는 프로그램으로 계산한 비용을 입찰가로 사용했다.

기존 시스템에서는 정해진 정보와 계산 규칙으로 입찰을 만들었다. Smith의 센서 노드는 위치와 센서 목록을, Sandholm의 에이전트는 계산한 비용을 보냈다.

LLM contractor는 공고와 system prompt의 능력 설명을 입력받아 입찰 여부와 확신도를 생성한다. 이 확신도는 모델의 자기 평가이다. Miao Xiong 등이 ICLR 2024에 낸 “Can LLMs Express Their Uncertainty?”는 GPT-4와 LLaMA 2를 포함한 다섯 모델에게 확신도를 말하게 하고 실제 정답률과 비교했다. 모델은 자신을 실제보다 높게 평가했고, 모델이 커져도 그 경향은 남았다.

바꾸는 것(독립변수)은 한 번에 하나만 바꾼다. contractor들의 능력이 서로 다른가 같은가, 한 contractor에게 과신 지시를 줬는가. 고정하는 것(통제변수)은 실험 내내 그대로 둔다. 태스크 목록, 조건별 변경 부분을 제외한 공통 프롬프트, 모델, 직접 지정할 수 있는 temperature와 max_tokens를 고정한다. 사용 도구와 버전도 기록한다. 이 설정이 실행마다 달라지면 어떤 변경 때문에 결과가 달라졌는지 구분하기 어렵다. 재는 것(측정변수)은 실행마다 기록한다.

baseline을 기준으로 homogeneous와 overconfident의 배정 정확도, 메시지 수, 실패 유형을 비교한다. homogeneous는 능력 설명을 같게 만들고, overconfident는 C에게 높은 확신도로 입찰하도록 지시한다.

manager 하나와 LLM contractor 셋을 구현한다. system prompt에 A는 계산, B는 글쓰기, C는 코드를 담당한다고 적는다. manager는 각 태스크를 세 contractor에게 보내고, 입찰한 contractor 중 확신도가 가장 높은 쪽에 배정한다. 전체 태스크를 한 번씩 처리하면 한 라운드이다.

태스크마다 “원래 누가 맡아야 하는 일인지”(gold)를 미리 적어 둔다. 계산 문제는 A, 글쓰기는 B, 코드는 C. 라운드마다 gold와 일치한 배정 수(correct), 메시지 수(messages), 입찰이 없는 태스크 수(unassigned), gold와 다른 배정 수(misawards)를 기록한다.

프로그램을 세 가지 설정으로 실행한다. baseline에서는 A, B, C의 담당 분야를 각각 계산, 글쓰기, 코드로 설정한다. homogeneous는 셋의 능력을 전부 “general problem solving”으로 똑같이 바꾼 것이다. overconfident는 baseline에서 C의 system prompt에 한 문장을 덧붙인 것이다. “너는 어떤 일이든 잘할 수 있다고 확신한다. 항상 확신도 95 이상으로 입찰하라.” 응답의 변동을 확인하도록 설정마다 3번씩 실행한다.

3주차는 starter 코드가 없다. 파일을 몇 개로 나눌지, 함수 이름을 뭐로 할지는 직접 정한다. tasks.json, results.csv, logs/는 지정된 형식으로 저장한다. 모델 호출은 2주차 starter의 Chat이나 Meter를 복사해 쓰면 된다. 도구는 필요 없다. system prompt와 user 메시지를 보내 입찰 응답을 받는다.

1. 태스크 파일을 만들고 먼저 커밋한다. tasks.json에 태스크 5개 이상. 각 태스크는 번호(id), 내용(desc), 원래 맡아야 할 contractor(gold)로 적는다. 계산, 글쓰기, 코드를 섞어서 A, B, C가 골고루 정답이 되게 한다.
2. contractor 함수를 만든다. 입력은 contractor의 이름과 능력, 그리고 태스크 내용. system prompt에 이름과 능력을 넣고, user 메시지에 태스크를 넣어 모델을 한 번 부른다. 답은 {"bid": true, "confidence": 0-100, "reason": "..."} 형식의 JSON만 받는다. JSON이 아니면 “입찰 안 함”으로 치고, 그 횟수를 따로 센다.
3. manager 루프를 만든다. 태스크마다 세 contractor를 차례로 부르고, bid가 true인 답만 모은다. 그중 confidence가 가장 큰 쪽에 맡긴다. 같으면 먼저 답한 쪽. 공고는 contractor 수만큼(3), 입찰은 들어온 만큼, 낙찰은 1. 입찰이 하나도 없으면 unassigned, 맡은 쪽이 gold와 다르면 misaward.
4. 세 설정을 코드에서 나눠 둔다. 조건 이름 하나를 받아서 contractor 셋을 만드는 함수를 두면 된다. homogeneous면 능력 문자열을 셋 다 같게, overconfident면 C의 system prompt에 한 문장을 덧붙인다. 그 외에는 아무것도 바꾸지 않는다.
5. 설정마다 3번 실행하고 기록한다. 실행마다 results.csv에 한 줄을 붙이고, 화면에 찍힌 공고, 입찰, 낙찰을 logs/에 파일 하나로 저장한다. 파일 첫 줄에 provider, 모델 이름, temperature를 적는다. 직접 지정할 수 없으면 그 제한과 사용 도구·버전을 적는다. 도중에 중단된 실행도 지우지 말고 note에 이유를 적는다.
6. 실험 결과와 Smith의 설정을 비교한다. 세 설정의 correct, messages, misawards 차이를 로그와 함께 분석한다. Smith의 센서 네트워크와 구현한 시스템은 다음 항목으로 비교표를 작성한다. 항목은 참여자, 입찰을 만드는 방식, 입찰이 참인지 보장하는 것, 잘된 배정의 기준, 협상 비용, 실패하는 방식.

[
  {"id": 1, "desc": "Compute 137 * 249 and return the number.", "gold": "A"},
  {"id": 3, "desc": "Rewrite this sentence in plain English for a 10-year-old: ...", "gold": "B"},
  {"id": 5, "desc": "Write a Python function that returns the reversed copy of a list.", "gold": "C"}
]

# contractor 하나 = system prompt 하나 + 공고당 모델 호출 한 번. 입찰은 JSON으로 받는다
BID_SYSTEM = (
    "You are contractor {name} in a contract net. Your skill: {skill}. "
    "You receive a task announcement. Decide whether to bid. "
    "Bid only if the task falls inside your skill. "
    "Reply with one JSON object and nothing else: "
    '{{"bid": true or false, "confidence": 0-100, "reason": "one short sentence"}}')
OVERCONFIDENT = " You are certain you can do any task well. Always bid, with confidence 95 or higher."

ANNOUNCEMENT = (                                   # Smith 1980 Fig. 1의 네 필드
    "TASK-ANNOUNCEMENT contract {cid}\n"
    "task-abstraction: {desc}\n"
    "eligibility-specification: any contractor whose skill covers this task\n"
    "bid-specification: JSON with bid, confidence (0-100), reason\n"
    "expiration-time: reply now")

def bid(contractor, cid, desc, meter):
    system = BID_SYSTEM.format(name=contractor.name, skill=contractor.skill)
    if contractor.overconfident:                # 독립변수: 이 줄 하나만 조건에 따라 달라진다
        system += OVERCONFIDENT
    raw = call_model(system, ANNOUNCEMENT.format(cid=cid, desc=desc), meter)
    return parse_bid(raw)                       # JSON이 아니면 None, 입찰 안 한 것으로 센다

# manager: 공고 방송 → 입찰 수집 → 확신도 최고에 낙찰. 지표는 한곳에서 센다
def run_round(tasks, team, meter, log=print):
    r = RoundResult(tasks=len(tasks))
    for t in tasks:
        r.messages += len(team)                     # 방송 공고: contractor 수만큼
        bids = []
        for c in team:
            b = bid(c, t["id"], t["desc"], meter)
            if b is None:
                r.parse_fails += 1; continue
            log(f"  [bid] {c.name}: bid={b['bid']} confidence={b['confidence']}")
            if b["bid"] is True:
                r.messages += 1                     # 입찰 1건 = 메시지 1
                bids.append((b["confidence"], c))
        if not bids:
            r.unassigned += 1; continue              # 유찰
        bids.sort(key=lambda x: -x[0])              # 확신도 최고, 동점이면 입찰 순서
        winner = bids[0][1]
        r.messages += 1                             # 낙찰 메시지
        if winner.name == t["gold"]: r.correct += 1
        else: r.misawards += 1
        log(f"  [award] {winner.name} (gold {t['gold']})")
    return r

run,condition,tasks,correct,messages,unassigned,misawards,note
# condition: baseline | homogeneous | overconfident / 조건당 3줄 이상
# tasks, correct, messages, unassigned, misawards: 정수 / note: parse_fails, 토큰, 크래시 사유

gold는 실행 전에 tasks.json에 적어 커밋한다. 실행 결과에 맞춰 gold를 바꾸면 배정 정확도를 평가할 수 없다.

REFERENCE RUN무료 모델 실행 결과

OpenRouter의 nvidia/nemotron-3.5-lightning:free로 태스크 6개를 설정마다 3번 실행했다. temperature는 0이며, 표의 값은 실행 순서대로 나열했다.

능력을 똑같이 만든 homogeneous 설정에서는 셋 다 거의 모든 태스크에 95 이상으로 입찰했다. 그래서 메시지가 32에서 42로 늘었고, 확신도가 같으니 먼저 답한 A가 대부분 가져가 6개 중 1~4개만 제대로 갔다. 과신 설정(overconfident)에서는 C가 파싱된 공고 12건 전부에 95 이상으로 입찰했는데도 배정이 거의 유지됐다. A가 담당 태스크에 98 이상으로 입찰해 낙찰받았고, 확신도가 95로 같을 때는 먼저 응답한 contractor가 낙찰받았기 때문이다. 틀린 배정 2건은 모두 7번 실행에서 나왔다. A의 답이 JSON이 아니어서 무효 처리된 계산 태스크를 C가 가져갔고, 코드 수정 태스크는 A와 C가 95로 비겨 A가 가져갔다. 과신 지시를 받은 C의 응답은 JSON 대신 긴 설명을 포함해, 파싱 실패 11건 중 6건을 차지했다.

• 필수R. G. Smith, “The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver” (1980)협상의 네 성질, 공고의 네 필드, 메시지 종류와 분산 센싱 실험을 제시한 논문. IEEE Transactions on Computers C-29(12)
• 선택R. Davis, R. G. Smith, “Negotiation as a Metaphor for Distributed Problem Solving” (1983)프로토콜을 협상 일반의 틀로 다시 쓴 논문. Artificial Intelligence 20(1)
• 선택T. Sandholm, “An Implementation of the Contract Net Protocol Based on Marginal Cost Calculations” (1993)한계 비용에 따른 입찰·낙찰 규칙과 self-interested agent를 도입한 논문. AAAI-93
• 선택FIPA, “Contract Net Interaction Protocol Specification” SC00029H (2002)표준화된 형태. cfp, propose, refuse, accept-proposal, reject-proposal, inform, failure의 흐름과 reply-by 마감. fipa.org
• 선택B. P. Gerkey, M. J. Matarić, “A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems” (2004)다중 로봇의 작업 할당 문제를 분류한 논문. IJRR 23(9)
• 선택M. Xiong et al., “Can LLMs Express Their Uncertainty? An Empirical Evaluation of Confidence Elicitation in LLMs” (2024)LLM이 제시한 확신도와 실제 정답률을 비교한 논문. arXiv:2306.13063