Transcript Agents

Trading Agents Competition
Supply Chain Management Scenario
Wednesday, 17 March, Ross 201
HUJI’s Runner Team
{Leo Dorrendorf, Raphael Boussidan, Zweig Alon, Yaad Blum, Joyce Vogel}
Background and Motivation



Supply Chain – The entire network of suppliers,
factories, warehouses, distribution centers and retailers,
that participate in the process from raw materials to
finish products
Supply chain management is concerned with planning
and coordinating the activities of organizations across
the supply chain
While today’s supply chains are essentially static, relying
on long-term relationships among key trading partners,
more flexible and dynamic practices offer the prospect of
better matches between suppliers and customers as
market conditions change.
Background and Motivation

The TAC annual contest has been designed jointly by a
team of researchers from the e-Supply Chain
Management Lab at Carnegie Mellon University and
the Swedish Institute of Computer Science (SICS).
This year, there will be two games in the competition:

TAC-SCM, the Trading Agents Competition in a
Supply Chain Management scenario, was designed
to capture many of the challenges involved in
supporting dynamic supply chain practices.

TAC Classic - The software agents will represent
travel coordinators whose goal is to arrange travel
packages (flights, hotel rooms, and tickets to
entertainment events) for clients.
Background and Motivation



It is challenging in that it requires agents to concurrently
compete in multiple markets (markets for different
components on the supply side and markets for different
products on the customer side) with interdependencies
and incomplete information.
The final rounds of the competition will be held during
AAMAS (20-22 July), preceded by qualifying and
seeding rounds in June and July
Last year, Jeff's students, Nadav Wainshal and Nir
Sharony, built an automated, learning agent that
participated in TAC Classic. NNN placed sixth in the field
of nine finalists, the scores of the automated agents
were quite clustered
Game Overview



In TAC SCM, 6 software agents compete in a simulated
sector of a market economy, specifically the personal
computer (PC) manufacturing sector
Each agent can manufacture 16 different types of
computers
Building each PC requires a different combination of
components. 4 types of components are represented in
the game: CPUs, Motherboards, Memory, and Hard
drives. It features a variety of components of each type
(e.g. 300GB H.D and 500GB H.D. etc’).
Game Overview
Game Overview




Components are acquired from a common pool of
suppliers at costs that vary as a function of demand.
After assembly, each agent can sell its PCs to a common
pool of customers by underbidding the other agents.
The agents are ranked based on their profits over 220
days, each of which lasts 15 seconds.
To succeed, agents will have to:



React to variations in customer demand and availability of
supplies
Strategize (e.g. specializing in particular types of products,
stocking up components that are in low supply)
Adapt to the strategies adopted by other competing agents
A TAC Day

Each competing agent needs to bid for customer orders,
negotiate supply contracts, and manage assembly
activities - all of which on daily basis.

Bid for customer orders




customers send a set of requests for quotes (RFQs) to
the agents.
RFQ contains a SKU, a quantity, a due date, a penalty
rate (max 5 days), and a reserve price
Agents sends an offer to each customer for each
RFQ, bidding to satisfy entire order (date & quantity)
Customer selects the agent with the lowest-priced
offer and awards that agent with a purchase order
A TAC Day

Negotiate supply contracts





Agents send RFQs to suppliers, requesting a specific
quantity of a component to arrive on a particular day
Suppliers respond the next day with offers
If the supplier can satisfy the order entirely, a full offer
is sent
A partial offer is generated if the supplier can deliver
only part of the requested quantity on the due date
specified in the RFQ
An earliest complete offer is generated to reflect the
earliest day (if any) that the supplier can deliver the
entire quantity requested
A TAC Day
Supplier
20 CPU’s available, d + 5
50 CPU’s available, d + 6
Supplier’s process
order is crucial
RFQ:
15 CPU’s, d+5
Partial Offer:
5 CPU’s, d+5
Earliest Complete Offer:
15 CPU’s, d+6
Offer:
15 CPU’s, d+5
RFQ:
15 CPU’s, d+5
Agent 1
Agent 2
A TAC Day

Manage assembly activities



Each agent converts the components it acquired from
suppliers into SKUs according to a production
schedule it generates for its factory, that decides
which PC orders to assemble first.
Agents also report a delivery schedule assigning the
PCs in its inventory to customer orders.
Each agent is endowed with an identical PC factory
containing a bounded assembly cell (2000 ac/d)
capable of assembling any type of PC, and an
inventory storing both components and finished PCs,
at a given storage cost (15%-25% annually, fixed).
A TAC Day
A TAC Day
A TAC Day
Suppliers’ Agent Preference



In order to probe, and not swamp the supplier, each day
an agent is allowed to send a maximum of 10 RFQs to
each supplier, that are bundled to an order list
RFQBundle, with the highest priority RFQ at the start.
The supplier selects an RFQ bundle and considers the
next unprocessed RFQ in that bundle. Then the supplier
moves to another bundle, and continue in a loop until all
RFQ are processed
Let us denote S a supplier in the game, and A a
competing agent. Define QuantityRequested(A,S) as the
sum of the quantities in all RFQs A sent to S thus far,
and QuantityPurchased(A,S) is the total quantity that A
has purchased from the S thus far .
Suppliers’ Agent Preference
OrderRatio( A, S )  QuantityPurchased ( A, S )
Quantity Re quested ( A, S )
Weight( A, S )  Min[0.5, OrderRatio n( A, S )]
Likelihood ( A, S ) 
Weight ( A, S )
Weight (a, S )
aAgents



Agents should not be punished for requesting same
components from both suppliers
Likelihood(A,S) = 1 at the beginning of the game
Supplier selects the RFQBundle with highest likelihood.
Encourage genuinely interested agents
Suppliers Daily Production
C ( S , d  1)  rnd (0.05,0.05) * Cnomianl( S )  0.01*[Cno min al ( S )  C p ( S , d  1)]
C p ( S , d )  max  p
0

C p ( S ,0)  Cno min al ( S )





Cp(S,d) - The production capacity on day d, is
determined by a random walk with a lower bound
Cnominal(S) - The nominal capacity (500 C/D) is the
expected capacity of supplier S.
Delivery only of entire quantity. No inventory cost
charged by S for production of multiple day orders
If Cp(S,d)< Cnominal(S), missed orders are scheduled for
next possible day.
Excess capacity used to satisfy future orders, however
no early shipments are made.
Suppliers Available Capacity
C free ( S , d )  Cno min al ( S ) C ordered( S , d )
Cavilable( S , d , d  i ) 




j  d  i 1
C
j d
free
(S , j)
Suppliers operate in a make to order basis
Cfree(S,d) and Cordered(S,d) denote the free and ordered
capacity on day d.
On day d the available capacity forecast on d+i is some
of all free capacity between d and d+i
At day d, an order for delivery on day d+i for n
components will be responded with full offers, partial
offers and earliest complete offers according to available
capacity forecast
Supplier Pricing
C 'avialable ( S , d , d  i )  qty
P (d , d  i )  Pbase (Component)[1  (
) * 0.5]
Ccurrent ( S , d ) * i
S







In day d , P(d,d+i) is the offer price for component to be
delivered in d+I
Pbase(Component) – Base price of component
0.5 – Discount factor
qty – quantity requested by the order
Ccurernt(S,d) – the supplier capacity on day d
C’avilable is like Cavailable but calculated using Ccurernt not Cnominal
Lower prices in case of high margin between demand
and quantity, immediate orders, low production capacity
Customers

Customer demand is expressed as RFQs
RFQ ::= <Id,PC,Quantity,DueDate,Penalty,ReservePrice>





PC is randomly selected from available types
Quantity is chosen U[1,20]
DueDate is chosen U[3,12] from today
ReservePrice is chosen U[75%,125%] from base price
Daily penalty is chosen U[5%,15%] of ReservePrice
Customers


Customers are classified into three market segments:
High range, Mid range, and Low range
The number of RFQ issued per day in each market
segment is a random variable NRFQ with a distribution:
NRFQ = Poisson (average number of RFQ per day)

Average number of RFQ per day will be varied using a
trend that is updated by a random walk:
RFQavg(d) = RFQavg(d-1)*Trend(d), bounded in [25,100]
Trend(d)=Trend(d-1)+rnd(-0.01,0.01) bound [0.95,1/0.95]

For Mid range bounded in [30,120]
Bank

Agents start the game with no money in the account

A fixed annual interest rate is chosen uniformly in the
range [10% , 20%] at the start of game, and is either
charged if the balance is in debt or credited if the
balance is positive.

Customer will pay for PCs only on the agreed DueDate.
However, agents may ship an order to a customer earlier
than the agreed DueDate and save inventory cost
Periodic Reports of Market State


All agents will be informed about the price interval (min,
max) for each type of PC ordered the previous day.
Component supply reports are made available every 20
TAC days:



Aggregate quantities produced by all suppliers
Aggregate quantities sold by all suppliers
Insight into supply procuring practices of other agents!
Customer demand report


Average sold PC price of each PC type requested
Average sold volume of each PC type requested
Detect lack of availability of a particular PC type
TAC-SCM-03 Results
Position
Agent
Average Score Games Played
1
RedAgent
11.61M
16
2
DeepMaize
9.473M
16
3
TacTex
5.017M
16
4
Botticelli
3.330M
16
5
PackaTAC
- 1.680M
16
6
WhiteBear
- 3.453M
16
TAC-SCM-03 Participants



RedAgent is based on a distributed architecture:
it is composed of simple agents, with markets
serving as means of communication and
exchange among them
DeepMaize is based on distributed architecture,
but relies on feedback control for coordination
TacTex and Botticelli are similar, traditional TAC
agent designs: build models of the environment
and attempt to optimize with respect to those
models
RedAgent-2003
Average Score: 11.61 M (1st)
Precup D., Keller P., Wahab M., Duguay, F.-O.
Reasoning and Learning Laboratory
McGill University's, CANADA
RedAgent Architecture




Redagent is centered around the idea of using an
internal market in order to determine what products to
focus on and how to allocate the existing resources
Create a highly distributed architecture, in which simple,
heuristic-based agents are assigned to deal with
individual aspects of the game
Agents communicate through a market mechanism in
order to determine, collectively, which components to
purchase, which types of PCs to produce, how to
allocate the available components and production
cycles, and what offers to send to customers.
Resulted in an efficient and flexible decision making
RedAgent Architecture

Uses 5 types of agents:
 Order Agents (OA)


10 Component Agents (CA)


Provide production cycles available to Assemblers
16 Assembler Agents (AA)



Purchase components from suppliers
Production Agent (PA)


Obtain PCs needed to fill orders and delivers them
Assemble components into PCs
Buy from PAs & CAs and sells to OAs
Bidder

Bid on customer RFQs
RedAgent Architecture


Communication and exchanges through Markets
 A market for each component type
 A market for each PC type
 Production cycles market
Markets help determine:

Which orders to fill with available SKUs
 What to build with available components
 What components to buy
 How much components and systems are worth
RedAgent Architecture
RedAgent Markets

Sealed-bid double auction variant
Secret bids from buyers and sellers
 Order bids according to price to obtain offer/demand
profiles
 Match up heads of both profiles
 Market price: midpoint between highest offer & lowest
demand
Resource markets hold several rounds of auctions each
day, in order to allow the participating agents to adjust
their valuations, based on current prices and on
availability of other necessary resources


RedAgent Markets



Same price for all transactions
Lowest demand bids and highest offer bids not
exchanged, though they could have been
Goal: Maximize overall gain in utility. That is justified
since in the internal market agents share a common
goal.
Buy-to-Build / Build-to-Order





buy-to-build strategy, an agent stocks up on
components, and starts producing PCs without
necessarily having orders for all the production
build-to-order strategy, the first concern of a PC maker is
to secure orders from customers; then, PCs are mostly
built in order to deliver these existing orders
Redagent adopted buy-to-build because of the absence
of inventory cost in TAC-SCM-03.
Maintained a large stock, and obtained high profit margin
when other competing manufacturers had low stocks
On the other hand, in a low-demand market, profits may
not be high enough to cover the cost of the unsold PCs.
Order Agent Heuristics





One agent per order
Greedy - Always tries to buy enough to fill
order
Always offers all inventory for sale
Same price for purchase or sale
Never ships early, always ships on/after due
date when possible
Order Agent Heuristics

Consequences for SKU Markets:



If SKU are plentiful

OAs buy early at low price (- Greedy)
 Market closing price ~ sum cost of components
If backlog
 Order agents buy later (Everybody’s greedy)
 Market closing price increases
 Bidder bids higher
Remember: market prices used by bidder
Assembler Agents
Assembler Agents


One for each SKU
AA Must determine






Offer prices for SKU market
Offer prices for production cycles market
Demand prices for component & production cycles
markets
Construct bids with the goal of maintaining a
target inventory, a “buffer”, to avoid spikes
Buffer is estimated as number of PCs needed for
10 days of operation, according to last 20 days
average
Also, generate production schedule & liquidation
Assembler Offers

Base price, Ba, is sum of estimated component
and production costs

PC inventory is divided into three batches:

PC’s in batch-1 priced linearly between Ba and 1.3Ba

PC’s in batch-2 priced linearly between 0.7Ba and Ba
PC’s in batch-3 priced 0.7Ba


Higher prices if inventory is low – selling buffer
Component market


Recall: sealed double auction
Sequential auctions, known order:







1. Production cycles: usually the most contention
2. CPUs: most expensive
3. Motherboards
4. Memory
5. Hard drives
Repeated N times each day
Used to find good resource allocation
between assemblers
Assembler Demand

First, determine total bid for an assembled SKU:


Use Demand profile from last SKU auction
Modify demand profile:




Compensate for highest bids with inventory
Add “fake” demand in order to build cheap SKUs for the
future
Now determine bids for each component/cycle:
 Use last relative prices from all the markets
 Multiply relative price by prices in demand profile to
obtain individual bids
Use the N auctions to try and match quantity of all
components, lowering risk in each round
Assembler Demand
Assembler Demand
Component Agent
Component Agent


One for each component
Determines



Based on




purchases (e.g H.D)
offer price of components (from probing)
Inventory
Expected component deliveries
Average demand of components by AA
Goal: always keep “buffer” of components

Size depends on day of game and avg. demand,
estimated from the components market
Bidder

Adaptive margin bidder



price offers are running average of the closing price
from the PC market + a margin for each necessary
production cycle
margin is decreased when a lot of production cycles
are available, and increased if production is at
capacity
maximize the profit per cycle since production
cycles are fixed and form the main bottleneck in
the system.
RedAgent

More details on :
Assembler agents
 Component agents
 Production agent
 Learning Bidder agent
 Delivery scheduale
Can be found in the submitted article:

KELLER, P. W., DUGUAY, F.-O., AND PRECUP, D. 2004.
Redagent-2003: An autonomous, market-based supply-chain
management agent. In Submitted.
Competition Performance –
PC Inventory
rank
Competition Performance –RFQ Sat’
Competition Performance
PC Price
Competition PerformanceParts Price
Competition Performance –
Parts inventory