# ANAC SCML Oneshot Trackについて

[KatHub](https://hackmd.io/@yh/kathub#KatHub)
[研究関連](https://hackmd.io/@yh/kathub-research#%E7%A0%94%E7%A9%B6%E5%88%86%E9%87%8E)
[エージェント](https://hackmd.io/@yh/agent)

ANAC・SCML(Supply Chain Management League)のOneshot Trackについて記載します．

[SCML2021のルール](http://www.yasserm.com/scml/scml2021oneshot.pdf)をもとに書いているため，**現在のルールとは異なる点があるかも**しれません．
間違いがあった場合は清水に教えてください．無断で修正していただいても構いません．(@arakawaと書いてある部分は荒川が勝手に追記しています．)

SCMLの公式なウェブサイトは[こちら](https://scml.cs.brown.edu/)になります（全てのTrackで共通）．

## 概要
SCMLには3つのTrackがあり，それぞれで少しずつルールが異なります．Standard TrackおよびCollusion Trackについては，[ANAC SCMLについて](https://hackmd.io/@KazukiKomori/rJUxbEEBd)を見てください．

Oneshot Trackでは，交渉に重点をおいた特殊な環境を想定しているため，ルールが他2つと異なる点がいくつかあります．
* 2層（固定）のサプライチェーンネットワーク
* 製品の製造や運搬の時間は考慮しない（0とみなす）
* 1日の終わりに売れ残った製品は廃棄コストを支払って，廃棄する（消滅する）

それぞれの詳しい説明は後述します．

### サプライチェーンネットワークについて
エージェントは，次の3つの製品を使って生産および取引を行います．

* 原材料：売り手エージェントがシステムエージェントから入荷する製品
* 中間製品：売り手エージェントと買い手エージェントが交渉によって取引する製品
* 完成品：買い手エージェントがシステムエージェントに出荷する製品

ここで，製品を生産するのにコストは製品が**完成に近づくほど高くなる**ため，買い手のエージェントの方が生産コストが高く設定されています．

Oneshot Trackでは，サプライチェーンネットワークの構造が他のTrackと大きく異なります．その他のTrackでは層数が決まっていないのに対し，Oneshot Trackでは次の図のように**2層のサプライチェーンネットワーク**でシミュレーションが行われます．


第1層のエージェントが**売り手**，第2層のエージェントが**買い手**となります．各層のエージェント数はシミュレーションにより異なります．両端にいるのは**システムエージェント**であり，売り手および買い手のエージェントと製品を売買します．その際，取引価格と取引量はシステムによって決定されます．

競技会の参加者が作成したエージェントはサプライチェーン内の工場のうち1つを担当し，他のエージェントとの交渉や製品の生産などを行います．各エージェントは自分の利益を最大化するように行動します．

## Oneshot Trackのルール
ここでは，Oneshot Trackのルールについて少し詳しく説明します．

全エージェントは，結構多めの所持金と0個の在庫を持ってスタートします．
次の**1日**を50日〜200日の間繰り返します．

### 1日の流れ
1. exogenous contractを行う．
システムエージェントとの取引を行い，原材料および完成品の契約を結びます．
2. 他のエージェントとの交渉
売り手エージェントと買い手エージェントの交渉を行い，中間製品の契約を結びます．
3. 製品の生産
生産コストを支払って，材料を製品に変換します．
4. 契約の実行
その日結んだ契約に基づいて，製品とお金が移動します．

### exogenous contract
システムエージェントとの取引は，exogenous contractと呼ばれ，売り手エージェントは原材料の契約を，買い手エージェントは完成品の契約を結びます．


**exogenous contractにおける取引価格および取引量については，システムにより決定されます**．1日の初めにこの契約が結ばれるため，エージェントはこの価格や量に基づいて中間製品の交渉を行います．

### 交渉について
エージェントは他のエージェントと交渉することにより，中間製品の契約を結びます．


Oneshot Trackでは交渉プロトコルとして**Alternating Offers Protocol**（Geniusで使うやつ）を並列交渉に拡張したものを用います．2者間の交渉を同時に行うイメージです．
まず，２体のエージェントの両方が最初のオファーを決定します．システムによりそのどちらかが1ラウンド目のオファーとして相手に届けられることで，交渉が開始されます．これはどちらが先攻あるいは後攻なのかを秘密にするためです．オファーを受け取ったエージェントは次のいずれかの行動を取ります．

* Accept：相手のオファーを受け入れる．
* Offer：相手のオファーを拒否し，代わりにこちらからオファーする．
* EndNegotiation：合意せずに交渉を終了する．

このプロセスを合意に達するか**20ラウンド**や時間の期限に達するまで繰り返します．時間の期限はかなり長いので，あまり気にする必要はないと思います．

次に，エージェントは次の2つの事柄について交渉します．

* 取引価格：5〜30（ドル）
* 取引量：0〜10（個）

取引価格については後述する**trading price**により，日によって上限や下限が異なります．一方，取引量は各工場の生産上限が10個であるため，こちらは上限や下限は変化しません．ただし，==上限や下限を超えた価格や量でオファーすることが可能な点に注意してください． 特に戦略を作成する際は，現実的な取引価格・取引量であるかどうかを確認しましょう．==
Oneshot Trackでは**運搬にかかるコスト（時間やお金）は0とみなしているため，納期に関する交渉は行いません．**

交渉により結んだ契約には拘束力があり，**途中で破棄することはできません**．残高や在庫が足りない，他のエージェントの方が良い合意を得られるなどの理由で，契約を破棄することはできません．

### 製品の生産および取引
エージェントは量に応じた生産コストを支払うことで，製品を生産します．生産コストは工場や日によっても異なります．また，生産上限は10個となっており，これに伴いexogenous contractの取引量も10個以下となります．

次に，**1日の取引で売れ残った商品については，コストを支払って廃棄しなければなりません．** これによりエージェントは在庫管理をする必要がなくなり，在庫を常に0になる（売り尽くす）ように交渉を行うようになります．

また，取引するにあたり，仕入れた量よりも出荷する量が多い場合，在庫が足りなくなってしまいます．その際は，**足りない製品量に基づいて相手にペナルティを支払います．**

exogenous contractは常に5〜10個の取引を行うため，毎日決められた量を交渉によって仕入れる（出荷する）必要があります．==戦略を作成するにあたっては，毎日誰かしらと合意する方が良い結果になることが多いです．== 条件が悪いから合意しないようにすると，廃棄コストを支払うことになり帰って効用値が下がってしまうことが多いです．

### 契約の処理 (@arakawa)

結んだ契約が全て履行されるとは限りません．自エージェントが保有している資金，工場のライン数による制約などで変化します．

(ソース: http://www.yasserm.com/scml/scml2021oneshot.pdf 4章)

#### 購入先の決定

the set of satisfiable input contracts $C^{*in}_{a}$ は次のように求められます．

1. input contractsを単価の昇順でソートする．
2. input contractsを順番に見て，自エージェントの保有資金が足りる限り$C^{*in}_{a}$に追加する．

保有資金が足りるかどうかは**生産コストも含めて**判定されます．

最後に見たinput contract$(p, q)$について，実際の購入個数$q^*$が$q$より小さくなる場合があります．(保有資金が足りる限り商品を*1つずつ*買うので)

#### 売却先の決定

購入先の決定方法とほぼ同じです．the set of satisfiable output contracts $C^{*out}_{a}$ は次のように求められます．

1. output contractsを単価の降順でソートする．
2. output contractsを順番に見て，条件を満たす限り$C^{*out}_{a}$に追加する．

条件は次のとおりです．
- 生産数 <= 自分の工場の生産ライン数
- 生産数 <= 購入可能な原料の数

最後に見たoutput contract$(p, q)$について，実際の売却個数$q^*$が$q$より小さくなる場合があります．(条件を満たす限り商品を*1つずつ*売るので)

### 効用関数
Oneshot Trackでは，交渉と契約の実行が1日で完結するため，効用関数を定義できます．効用関数は合意案候補（取引価格と取引量のセット）を入力として，その日得られる効用値（利益・損失）を計算します．具体的には，次に示す全収入から全支出を引いた金額を計算します．

* 全収入
* 　製品の販売総額
* 　全支出
* 　製品の購入総額
* 　生産コスト
* 　廃棄コスト
* 　ペナルティ

各種コストやペナルティを計算する際に，trading priceと呼ばれる指標を用います．これは製品の過去の取引価格を加重平均して求められる指標であり，より新しい取引価格であるほど計算する際の重みが大きくなります．

1日の終わりに効用関数を用いてその日の取引により得られた利益または損失を計算し，残高を更新します．

効用関数を利用することで，自分や相手のオファーがどのくらい良いのかを判断することができます．積極的に活用しましょう！

以下@arakawa なお，廃棄コスト・ペナルティ(shortfall penalty)の計算式は次のとおりです．

- 廃棄コスト: $\alpha_a \mathrm{tp}(\rho_a^{in}, d)Q_{a}^{excess}$
- $\mathrm{tp}(\rho_a^{in}, d)$: 商品$\rho_a^{in}$の$d$日目におけるtrading price
- $Q_{a}^{excess}$: エージェント$a$が廃棄する個数 (=max{0, $Q^{in}-Q^{*out}$})
- $\alpha_a$: エージェント$a$の廃棄コスト定数
- シミュレーションごとに平均値$\mu_a^{\alpha}$を[0.0, 0.2]の一様分布から決めて，1日ごとに平均$\mu_a^{\alpha}$の正規分布から実際の$\alpha_a$を決めているようです．(ルールpdf P14 Table3より)
- shortfall penalty: $\beta_a \mathrm{tp}(\rho_a^{out}, d)Q_{a}^{shortfall}$
- $Q_{a}^{shortfall}$: エージェント$a$の不足数 (=max{0, $Q^{out}-Q^{*out}$})
- $\beta_a$: エージェント$a$のペナルティ
- シミュレーションごとに平均値$\mu_a^{\beta}$を[0.2, 1.0]の一様分布から決めて，1日ごとに平均$\mu_a^{\beta}$の正規分布から実際の$\beta_a$を決めているようです．(ルールpdf P14 Table3より)

*大抵の場合は*廃棄コストよりshortfall penaltyの方が重くなるように設定されています．

また，「購入先の決定」の項では「購入資金+生産コストが足りるだけ買う」としていますが，効用関数の計算では次のように変化します．

- 全ての購入を(**購入資金が足りなくても**)行う
- 実際に売却する数だけ生産コストを支払う

### 公開情報
自分のエージェントがアクセスできる情報は次のようなものです．
* 自分の入荷・出荷品が何なのか
* 自分の各種コスト
* 生産コスト
* 廃棄コスト
* ペナルティ
* シミュレーションの日数
* 全製品の消費者・生産者リスト
* 全製品のtrading price(取引の目安になる値段)
* 契約違反者リスト
* 全工場の財務状況(残高，在庫，契約違反率，違反レベル)
* 自分と相手の交渉履歴(いつどちらがどんな提案をしたか)
* exogenous contractについて
* 取引量の合計値
* 取引価格の平均値

### 非公開情報
自分のエージェントがアクセスできない情報は，例えば次のようなものです．

* 第三者同士の交渉・取引内容
* 他人の各種コスト(コストは人によって違う値)

また，**シミュレーションごとにサプライチェーンの配置やエージェントが持っていた情報はリセットされます．** 過去のシミュレーションでの情報にアクセスすることはできません．（10日目に1日目の情報を得ることはできるが，1日目に別世界の1日目の情報は得られない）

### ペナルティ (@arakawa)

#### bankrupt

1日の終わりに資金がマイナスになった場合は**bankrupt**(破産)を宣告されます．bankruptとなったエージェントは*それ以降の交渉に参加することができません．*

#### breach

生産数より多くの商品を売却する契約をしてしまった場合は**breach**(不履行)となり，shortfall penalty を課せられます．

## エージェントの評価
競技会の順位を決定する評価値についてです．

1回のシミュレーションについて，エージェントは**初期の所持金の何倍になったか**で評価されます．
複数回シミュレーションが繰り返され，**全シミュレーションでの平均値**が最終的な評価値となります．ただし，上位と下位の数%を除外して算出されます．これは，外れ値が全体の平均に影響を与えることへの対策です．

## その他お役立ち情報
筆者が役立つかなと思った情報をいろいろ書いていきます．

### 2021年のOneshot Trackに参加したエージェント
2021年のOneshot Trackでは，過去の合意価格の平均値を用いたエージェントが好成績を収めていました．合意価格の平均値を用いることで，その時の市場の相場を掴むことができたと考えられます．

また，全体的に頑固な（譲歩しにくい）エージェントほど高い効用値を得ていることが多かったです．==ほとんどのエージェントが最終ラウンドで合意することを想定しているため，早めに譲歩するとかえって搾取されてしまうと考えられます．==

中にはオファーを受け取ってから返すまでの時間をできるだけ短くすることを試みたエージェントもいました．ルールには書かれていませんでしたが，応答を早くすることで良い提案をしてくる相手と早めに合意することができるかもしれません．

### サンプルエージェント
SCMLにはとても丁寧な[チュートリアル](http://www.yasserm.com/scml/scml2020docs/index.html)があるので参加する方は必ず見ておきましょう．その中に，説明のための簡単な戦略のサンプルエージェントがいくつか存在します．2021年のサンプルエージェントは，時間依存の譲歩関数に従ってオファーや受け入れ方法を決定するものでした．
ほとんどの参加者は，このサンプルエージェントを少し改良したもので勝負して来ます．そのため，==これに勝てるような（弱点をついた）戦略を考えるのが良いと思います．==

### 最新の情報を確認しよう
SCMLの情報は，基本的にはウェブサイトをみることで把握できます．ただし，細かいプログラムの変更などについては，[Github](https://github.com/yasserfarouk/scml)やSCMLに登録すると配信されるメールを確認する必要があります．
==主にバグ修正や便利な関数の追加などが行われますが，中には環境が大きく変わる（大きな順位変動が起こる）ほどの変更がなされる場合があるので，注意してください．==~~筆者のエージェントはそれで優勝を逃したと言っても過言ではありません...~~