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

Suppose there are three agents. One is good at arithmetic, one at writing, one at code. A task comes in and someone has to decide who takes it. The first protocol to solve that is Reid G. Smith's “The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver”, published in IEEE Transactions on Computers in 1980.

In Smith's paper several computers share one large problem. Each computer knows only what it can do. There is no central computer that sees everything and says “you do this, you do that”. Smith called the problem of deciding which computer takes which job the connection problem, and his answer was negotiation. The side with a job asks “who can do this?”, the side that can says “I will”, and when they agree the assignment is done.

Smith wrote down four properties of this negotiation. Nobody controls it from the center, information flows both ways, each side judges by its own criteria, and the two sides choose each other (mutual selection). A contractor picks, among several announcements, the ones that fit it; a manager picks, among several bids, one. Neither side can simply designate the other.

One assignment has four steps. The side with a job becomes the manager and issues a task announcement. The announcement carries four things: what the job is (task abstraction), who may bid (eligibility specification), what a bid must contain (bid specification), and the deadline (expiration time). Eligible sides send a bid, which states what they can do (node abstraction). The manager compares the bids, picks one, and sends an award. The awarded side becomes the contractor, does the job, and reports the result.

The paper's example is a sensor network. Sensors and computers are spread over a wide area and together build a map of where vehicles are moving. In the announcement in the paper's first figure, eligibility is “must have a sensor, must be in area A” and the bid must contain “latitude and longitude, and the name and type of every sensor”. The manager states what a bid must contain, so the contractor sends only that and the manager chooses on that alone. The paper has a few more message types than these four.

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

A directed award hands a job over without an announcement when the manager already knows who should do it. Request and information are short questions and answers that need no contract. Node available runs the other way: when everyone is busy and nobody bids, an idle side announces “I am free” and a manager looks for a job that fits it. Smith wrote that eligibility conditions and directed awards exist to cut needless messages and bid processing.

Roles change from job to job. A contractor that splits its job into smaller ones and announces them is the manager of those. One computer can be a contractor on one job and a manager on another at the same time, and a computer that has handed a job out can take other jobs while it waits. Smith called the layered structure this produces typical of task-sharing.

In 1983 Smith and Randall Davis took the procedure out of the sensor network and framed it as negotiation in general, in “Negotiation as a Metaphor for Distributed Problem Solving”. An announcement says “there is a job”, a bid says “I will do it on these terms”, an award says “you are chosen”.

Smith did not say what a contractor bases its bid on or what a manager uses to choose. Tuomas Sandholm filled that in at AAAI in 1993. The bid is the cost the job adds to what the agent is already doing (marginal cost), and agents that each look after their own interest trade on that number. In 2002 FIPA made the procedure a standard, the Contract Net Interaction Protocol: the manager sends a cfp (call for proposals), participants answer with propose or refuse, the manager answers with accept-proposal and reject-proposal, and the side that took the job ends with inform (done) or failure. The cfp carries a reply deadline, and a proposal becomes a binding promise the moment it is accepted. In robotics, Gerkey and Matarić published a taxonomy of dividing jobs among several robots in 2004, and Dias and colleagues surveyed market-style robot coordination in 2006.

The procedure did not get past three walls. The first is cost. Sending an announcement to everyone costs one message per participant, and every bid that arrives has to be read and compared by the manager.

The second is local optimality. A contract is made from the bids in hand at that moment. Because an earlier contract is already in place, a better combination that appears later cannot be taken. Sandholm called the state in which no further exchange would help anyone k-optimal, and noted that it does not guarantee the best overall assignment.

The third is trust. A bid is the claim “I can do this job”. The procedure has no message that checks whether the claim is true. Smith's computers were on the same side, solving one problem together, and a bid held a position and a list of sensors. There was no reason and no way to lie. After Sandholm brought in self-interest, the bid was still a cost a program had computed.

The contractor of 1980 computed its bid. Smith's sensor node sent its position and its sensor list; Sandholm's agent sent a cost a program had computed. The bid is what comes out when you put your own state into a rule. It can say nothing the rule does not allow, and it cannot be false unless the rule is.

The contractor of 2026 judges its bid. It reads the announcement, compares it with the ability written in its system prompt, and answers “I can, confidence 95”. That confidence is a self-assessment the model puts into words. Miao Xiong and colleagues, in “Can LLMs Express Their Uncertainty?” at ICLR 2024, had five models including GPT-4 and LLaMA 2 state their confidence and compared it with how often they were actually right. The models rated themselves higher than they were, and the tendency remained as models grew.

An experiment needs three things written down separately. What you change (the independent variable), one thing at a time: whether the contractors' skills differ or coincide, and whether one contractor was told to be overconfident. What you hold fixed (the controls) stays the same throughout: the task list, the prompts, the model, the temperature, max_tokens. If these move between runs, you cannot tell whether a difference came from what you changed. What you measure is recorded per run.

Each condition looks at one wall. Making the skills identical removes the information from the bids, and shows what then decides the award. The overconfident setting shows what an unchecked bid does to the assignment. The baseline is the reference for the other two, and it also measures how often a judged bid is wrong.

What you build is one small program. Inside it are a manager that hands out work and three contractors that take it. Each contractor's skill is one line of system prompt. A does arithmetic, B writes, C codes. The program takes one task, shows it to the three contractors, asks each “can you do this, and how sure are you?”, and gives the task to whoever answered with the most confidence. With six tasks it does this six times, and that is one round.

For every task you write down in advance who should get it (gold): arithmetic goes to A, writing to B, code to C. After a round you can then count how many went to the right place. Four numbers per round: tasks that went to the right contractor (correct), messages exchanged (messages), tasks nobody bid on (unassigned), tasks that went to the wrong contractor (misawards).

You run this program under three settings. baseline is as above. homogeneous gives all three the same skill, “general problem solving”, and shows who wins once the bids carry no information. overconfident is baseline with one sentence added to C's system prompt: “You are certain you can do any task well. Always bid, with confidence 95 or higher.” It shows what one bluffing participant does to the assignment. Run each setting three times, because the model's answers vary a little each time.

There is no starter code this week. How many files, what the functions are called, is up to you. What is fixed is the format of the output files (tasks.json, results.csv, logs/ below). For the model call, copy Chat or Meter from last week's starter. No tools are needed: send one system prompt and one user message and one bid comes back.

1. Write the task file and commit it first. At least five tasks in tasks.json, each with a number (id), the text (desc), and the contractor that should get it (gold). Mix arithmetic, writing, and code so that A, B, and C are each the right answer sometimes.
2. Write the contractor function. Input: the contractor's name and skill, and the task text. Put name and skill in the system prompt, the task in the user message, call the model once. Accept only JSON of the form {"bid": true, "confidence": 0-100, "reason": "..."}. If the reply is not JSON, count it as no bid and keep a separate count of those.
3. Write the manager loop. For each task, call the three contractors in turn and keep the replies where bid is true. Give the task to the one with the largest confidence; on a tie, the one that answered first. Count messages like this: the announcement counts once per contractor (3), each bid counts one, the award counts one. No bids at all is unassigned; a winner other than gold is a misaward.
4. Separate the three settings in code. One function that takes a setting name and builds the three contractors is enough. For homogeneous, make the skill string the same for all three; for overconfident, add the one sentence to C's system prompt. Change nothing else.
5. Run each setting three times and record. Each run adds one line to results.csv and saves what was printed, every announcement, bid, and award, as one file under logs/. Put provider, model name, and temperature on the file's first line. Keep runs that crashed and write the reason in note.
6. Read the results and compare with Smith's setup. Put correct, messages, and misawards for the three settings side by side and see what changed. Then build a table that compares Smith's sensor network with your experiment item by item: who the participants are, how a bid is produced, what guarantees a bid is true, what counts as a good assignment, what negotiation costs, how it fails.

[
  {"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"}
]

# one contractor = one system prompt + one model call per announcement; the bid comes back as 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 = (                                   # the four fields of 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:                # independent variable: this one line differs by condition
        system += OVERCONFIDENT
    raw = call_model(system, ANNOUNCEMENT.format(cid=cid, desc=desc), meter)
    return parse_bid(raw)                       # None if not JSON; counted as no bid

# manager: broadcast → collect bids → award to the highest confidence; every metric counted in one place
def run_round(tasks, team, meter, log=print):
    r = RoundResult(tasks=len(tasks))
    for t in tasks:
        r.messages += len(team)                     # broadcast: one message per 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                     # one bid = one message
                bids.append((b["confidence"], c))
        if not bids:
            r.unassigned += 1; continue              # no bid
        bids.sort(key=lambda x: -x[0])              # highest confidence; ties keep bid order
        winner = bids[0][1]
        r.messages += 1                             # the award message
        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 / at least 3 rows per condition
# tasks, correct, messages, unassigned, misawards: integers / note: parse_fails, tokens, crash reason

Write gold into tasks.json and commit it before running. Changing gold after seeing the results turns wrong assignments into right ones, and it stops being an experiment.

REFERENCE RUNResults on a free model

Below is this design run on one free OpenRouter model: six tasks, three runs per setting, temperature 0. The three numbers in each cell are the three runs.

The model is nvidia/nemotron-3.5-lightning:free. In the homogeneous setting, with identical skills, all three bid 95 or higher on almost every task, so messages rose from 32 to 42, and since the confidences were equal, A, which answers first, took most of them: only 1 to 4 of 6 went to the right place. In the bluffing setting (overconfident), C bid 95 or higher on all 12 announcements it parsed, and the assignment still mostly held: A answers its own tasks at 98 or higher and beats C, and a tie at 95 goes to whoever answered first. Both wrong assignments were in run 7. C took an arithmetic task because A's reply was not JSON and was discarded, and A took a code-fix task by tying C at 95. And C, once told to bluff, more often answered with a long explanation instead of JSON, producing 6 of the 11 parse failures.

Submission rules are the same as last week.

• REQR. G. Smith, “The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver” (1980)The source text. Read the four properties of negotiation, the four fields of an announcement, the full message set, and the distributed sensing experiment against the design of the lab. IEEE Transactions on Computers C-29(12)
• OPTR. Davis, R. G. Smith, “Negotiation as a Metaphor for Distributed Problem Solving” (1983)The protocol rewritten as a general account of negotiation. Artificial Intelligence 20(1)
• OPTT. Sandholm, “An Implementation of the Contract Net Protocol Based on Marginal Cost Calculations” (1993)Fills the bidding and awarding rules the original left undefined with marginal cost, and introduces self-interested agents. AAAI-93
• OPTFIPA, “Contract Net Interaction Protocol Specification” SC00029H (2002)The standardized form: the flow of cfp, propose, refuse, accept-proposal, reject-proposal, inform, failure, and the reply-by deadline. FIPA-ACL comes in week 04. fipa.org
• OPTB. P. Gerkey, M. J. Matarić, “A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems” (2004)How the Contract Net lineage is classified in robotics. IJRR 23(9)
• OPTM. Xiong et al., “Can LLMs Express Their Uncertainty? An Empirical Evaluation of Confidence Elicitation in LLMs” (2024)A measurement of how far a model's self-stated confidence can be trusted. Use it when interpreting the overconfident setting. arXiv:2306.13063