単一財逐次複数ユニットオークションにおける財の割り当てに関する考察

(1)

修士論文の和文要旨研究科・専攻大学院情報理工学研究科情報・ネットワーク工学専攻博士前期課程氏名森本智貴学籍番号 1931147 論文題目単一財逐次複数ユニットオークションにおける財の割り当てに関する考察要旨近年，環境問題への対応の一つとしてCO2 排出量の削減がある．解決作の一つが輸送の電化であり，世界的に電気自動車の普及が進んでいる．一方で電気自動車には，充電時間が長いことや充電できる場所が少ないという問題がある．この問題によって，電気自動車の増加に伴い，すべての電気自動車を満足に充電することができない可能性がある．充電を行う電気自動車を決定する方法としてオークションやスケジュール作成などが考えられている．本研究では，動的に到着・出発する買い手へ，エネルギーなどの貯めておくことができない財を割り当てる方法を考える．貯めておくことができないので，時間が経過すると財は廃棄される．風力や太陽光などの再生可能エネルギーを使用して充電することを想定し，時刻毎に市場に供給される財の量が変化するモデルを考える．また，買い手はコストを払うことで，市場から出発する時刻を延長できるものとする．オークションの割り当ての決定方法として，すべての買い手と売り手の利得の和である社会的総余剰を最大化するように割り当てを決定するものが存在する．また，買い手の利得を割り当てられた財の単位数と買い手が市場に滞在する時間の二つで定義し，その利得を用いて充電施設から送られてきた充電スケジュールの提案を受け入れるかどうかを決定するような研究が存在する．本研究では，社会的総余剰に加え，買い手の需要の満足度を考慮した割り当てルールを提案し，数値実験により評価を行った．モデルより複数のインスタンスを作成し，提案した割り当てルールを用いて割り当てを求めた．この割り当てと既存の割り当てルールの割り当てを，社会的総余剰，買い手の需要の満足度，延長した買い手の人数とその時間，廃棄された財の数，必要な量の財を獲得できた買い手の人数の5 つの観点で比較した．提案した割り当てルールを用いると，既存の割り当て方法と比べ，社会的総余剰と満足度の和が大きくなる良い割り当てを求めることができた．延長人数は，買い手の滞在時間が短いインスタンスや，買い手が集中して市場に来るインスタンスで多くなり，またこのときの延長時間も他のインスタンスよりも長いことがわかる．廃棄された財は買い手が集中するインスタンス以外では，1 単位程度であり，それほど多くないこともわかる．本研究で用いたインスタンスでは，需要過多で競争が激しいものが多く，需要を満たした買い手が少なくなる傾向にある．今後，被験者実験などを行い現実に近い環境での割り当て結果を確認する必要がある．

(2)

電気通信大学大学院情報理工学研究科情報・ネットワーク工学専攻情報数理工学プログラム修士論文

単一財逐次複数ユニットオークションにおける

財の割り当てに関する考察

令和 3 年 2 月 25 日

情報数理工学プログラム

学籍番号

1931147

森本智貴

指導教員高橋里司村松正和

(3)

1 はじめに 3 2 準備 3 2.1 オークションとメカニズム . . . . 3 2.2 限界評価 . . . . 4 2.3 単一財複数ユニットオークション . . . . 4 2.4 整数線形計画問題 [6] . . . . 5 3 単一財逐次複数ユニットオークション 5 4 メカニズム 6 4.1 割り当てルール . . . . 6 4.1.1 社会的総余剰 . . . . 7 4.1.2 満足度 . . . . 8 4.2 支払いルール . . . . 9 5 先行研究 9 5.1 Fair Online Allocation of Perishable Goods and its Application to Electric Vehicle Charging [2] . . . . 9

5.1.1 [2] のモデル . . . 10

5.1.2 割り当てルール . . . 10

5.1.3 割り当てを求める問題の計算複雑性 . . . 11

5.2 An Agent-based Negotiation Scheme for the Distribution of Electric Vehicles Across a Set of Charging Stations [3] . . . 14

5.2.1 [3] のモデル . . . 14 5.2.2 電気自動車の所有者の利得 . . . 15 5.3 提案モデルと先行研究との違い . . . 16 6 提案手法 16 6.1 社会的総余剰を最大化する割り当て . . . 17 6.2 満足度を最大化する割り当て . . . 17 6.3 社会的総余剰と満足度を最大化する割り当て . . . 18 7 計算機実験 19 7.1 インスタンスの生成 . . . 19 7.2 実験環境 . . . 22 7.3 実験結果 . . . 22 8 考察 23 9 おわりに 28

(4)

1 はじめに

近年，環境問題への対応の一つとして，CO2 排出量の削減がある．解決策の一つが輸送の電化であり，世界的に電気自動車の普及が進んでいる．我が国でも電気自動車の購入費に対する補助金制度により [1]，今後電気自動車の台数は増加すると考えられる．一方で電気自動車には，充電時間が長いことや充電できる場所が少ないという問題がある．この問題によって，電気自動車の増加に伴い，すべての電気自動車を満足に充電することができなくなる可能性がある．このような状況では何らかの方法でどの電気自動車を充電するか決定する必要がある．充電を行う電気自動車を決定する方法としてオークションやエネルギー量などの制約を満たすスケジュールの作成などが考えられている [2, 3]．本研究では，動的に到着・出発する買い手へ，エネルギーなどの貯めておくことができない財を割り当てる方法を考える．貯めておくことができないので，時間が経過すると財は廃棄される．風力や太陽光などの再生可能エネルギーを使用して充電することを想定し，時刻毎に割り当てることができる財の量が変化するモデルを考える．また，買い手は市場からの出発時刻を遅らせることができるものとする．ただし，遅らせることに対してはコストが発生する．本研究の目的は，このような環境のもとで，一般的なオークションで用いられている社会的総余剰に加え，買い手の需要の充足度を考慮した割り当てルールを提案し，数値実験によって評価を行うことである．提案手法によって求めた割り当てを，既存の割り当てルールで求めた割り当てと比較し，買い手と売り手の利益の和，買い手への財の割り当て数と買い手が市場に滞在する時間に対する満足度，延長した買い手の人数とその時間，廃棄してしまった財の数，必要な量の財を獲得できた買い手の人数の評価を行う．本章では，研究背景と研究目的を述べた．2 章では，本研究で用いる用語の説明を行う．3 章では，時間毎に市場に供給される財の単位数が変化する単一財を動的に到着する買い手に割り当てるモデルについて述べる．4 章では，割り当てを求めるにあたって必要な知識を述べる．5 章で似たようなモデルの先行研究を二つ紹介し，本研究との違いを述べる．6 章では，4 章で説明した割り当てを求めるために用いた整数線形計画問題について述べる．7 章では，提案した割り当てルールについて，行った計算機実験と結果を記述し，8 章で考察を行う．最後に 9 章で，まとめと今後の課題について述べる．

2 準備

2.1 オークションとメカニズム

オークションとは，価格の定まっていない財を、その財を需要する買い手が購入したい価格を提示して競い，購入する買い手と財の価格を決定する経済取引手法の 1 つである．一般には，買い手全員の入札額を入力とし，財の割り当てと価格を出力する．このとき誰に財を割り当てるかを決める割り当てルールと買い手がいくら支払うかを決める支払いルールの組をメカニズムと呼び，メカニズムにしたがって

(5)

オークションが分類されている．例えば，最高入札額を入札した買い手が財を獲得し，その入札額を支払いとすると，第一価格オークションと呼ばれ，Yahoo!オークションや e-Bay のようなインターネットオークションサイトに用いられている [4, 5]．

2.2 限界評価

ある単一財を複数単位購入したいと考えている買い手について考える．その買い 手は，k− 1(≥ 0) 単位の財に対しての評価 ¯vk−1を持っている．買い手に財をもう 1 単位割り当てたときに，財に対しての評価がどのくらい変化するかを考える．この 変化量を k 単位目の財への限界評価と呼び，¯vk− ¯vk−1で定義される．

2.3 単一財複数ユニットオークション

本節では，本研究のモデルの説明の前に一般的な単一財複数ユニットオークションについて述べる．本研究のモデルは，単一財複数ユニットオークションを拡張したものである． 財の売り手が 1 人，買い手が 2 人以上のオークションを考え，買い手の集合を B と する．売り手は，1 単位以下には分割不可な s 単位の単一財を市場に供給する．それ ぞれの買い手は，複数需要であるとする．買い手 b∈ B は必要な財の単位数 nb ∈ N， 獲得する財に対しての限界評価ベクトル vb = (vb,0 = 0, vb,1, vb,2,· · · , vb,s) を持つ． vb,kは，k 単位目の財に対しての限界評価を表し，1 ≤ k ≤ s に対して vb,k ≥ 0 か つ vb,k ≥ vb,k+1であるとする．買い手 b∈ B が k 単位の財を獲得したときの評価を ¯ vb,k = ∑k m=0vb,mで表す．また，買い手 b ∈ B へ k(0 ≤ k ≤ s) 単位の財が割り当て られているかどうかを xb,k ∈ {0, 1} で表し， xb,k = { 1 (if 買い手 b ∈ B へ k 単位の財が割り当てられている) 0 (o.w.) である．例として，市場へ財の供給単位数が s = 2 であり，買い手 b に財が 1 単位割 り当てられている状況を考えると，xb,0 = 0, xb,1 = 1, xb,2 = 0 となる．単一財複数ユニットオークションは次の手順で行われる． step1 (i) s = 0 のとき， オークション終了． (ii) それ以外のとき， 時刻 t に市場に供給される財の単位数 s が売り手から買い手に発表される． 買い手 b∈ B の財への評価ベクトル vbを集める． step2 メカニズムに従って割り当てと価格を決定する．

(6)

2.4 整数線形計画問題

[6]

線形計画問題とは，「与えられた有限個の線形等式または線形不等式を満たす条件の もとで，与えられた線形関数を最大化 (または最小化) するような実変数 (x1, x2,· · · , xn) の値を求めよ，またはそのようなものが存在しないことを示せ」という問題であり，次のように表す．最大化 c1x1+ c2x2+· · · cnxn 制約条件 α11x1+· · · + α1nxn= b1 .. . αm1x1+· · · + αmnxn= bm β11x1+· · · + β1nxn ≤ b′1 .. . βm1x1+· · · + βmnxn ≤ b′m γ11x1+· · · + γ1nxn≥ b′′1 .. . γm1x1 +· · · + γmnxn≥ b′′m 最大化の対象になる関数 c1x1 + c2x2+· · · cnxnを目的関数と呼ぶ．線形等式 (不等 式) や線形関数を具体的に決める係数 c1, α11, β11, γ11, b1, b′1, b′′1などは，すでに値が決 定されている実定数である．これに対し x1, x2,· · · , xnは実変数である．整数線形計画問題 (ILP) とは，目的関数と制約式が線形等式または線形不等式であるという条件，変数の一部またはすべてが整数であるという条件二つを満たす問題である [7]．

3 単一財逐次複数ユニットオークション

本研究では，時間毎に市場に供給される財の単位数が変化する単一財を動的に到着する買い手に割り当てるオークションモデルを考える．これは，2 章 2.3 節の単一財複数ユニットオークションに時間軸を追加したモデルである．買い手は，市場に滞在している時間に制限があり，時刻毎にオークションに参加している買い手が変化する．また，保存ができない財を想定し，買い手に割り当てられない財は廃棄することとする．財の売り手が 1 人，買い手が 2 人以上のオークションを考え，買い手の集合を B(|B| ≥ 2) とする．時刻の集合を T とし，時刻の集合 T の最後の時刻を tmaxとす る．財は 1 単位以下には分割不可能な単一財を想定する．時刻 t _{∈ T に市場にある} 財が，時刻 t のうちに買い手に割り当てられない場合，その財は時刻 t 終了時に廃 棄されてしまうとする．その際廃棄コストは発生しない．時刻 t∈ T に市場に供給

(7)

される財の単位数を st∈ N とする．買い手 b ∈ B は市場へ到着する時刻 ab ∈ T ，市 場から出発する時刻 db ∈ T (ab ≤ db)，必要な財の単位数 nb ∈ N，時刻 t ∈ T に獲 得する財に対しての限界評価ベクトル vbt = (vbt,0 = 0, vbt,1, vbt,2,· · · , vbt,st) を持つ． vbt,kは，時刻 t ∈ T の k 単位目の財に対しての限界評価を表し，1 ≤ k ≤ stに対し て vbt,k ≥ 0 かつ vbt,k ≥ vbt,k+1であるとする．買い手 b ∈ B が時刻 t ∈ T に k 単位 の財を獲得したときの評価を ¯vbt,k = ∑k m=0vbt,mで表す．また，買い手 b∈ B へ時刻 t ∈ T に k(0 ≤ k ≤ st) 単位の財が割り当てられているかどうかを xbt,k ∈ {0, 1} で 表し， xbt,k = { 1 (if 買い手 b∈ B へ時刻 t ∈ T に k 単位の財が割り当てられている) 0 (o.w.) である． 例として，ある時刻 t の市場へ財の供給単位数が st = 2 であり，買い手 b に財が 1 単位割り当てられている状況を考えると，xbt,0 = 0, xbt,1 = 1, xbt,2 = 0 となる．単一財逐次複数ユニットオークションは次の手順で行われる． step1 現在の時刻 t = 1 とする．

step2 (i) t > tmaxのとき，

オークション終了． (ii) それ以外のとき， 時刻 t に市場に供給される財の単位数 stが売り手から買い手に発表される． 時刻 t に市場にいる買い手 (ab ≤ t ≤ dbを満たす買い手) の集合 Bt ⊆ B を作成する． Bt ⊆ B に含まれている買い手の時刻 t の財への評価ベクトル vbtを集める． step3 メカニズムに従って割り当てと価格を決定する． step4 t← t + 1 とし，step2 へ どのようなメカニズムを用いるかは次の章で述べる．本研究では，出発時刻になった買い手は割り当てられた財の単位数に満足できなかった場合，コストを払い出発時刻を延長することができるということを想定する．

4 メカニズム

4.1 割り当てルール

本研究では，以下の三つの割り当てルールを考える． • 割り当てルール 1 社会的総余剰の最大化

(8)

• 割り当てルール 2 財の獲得単位数に基づく買い手の満足度の最大化 • 割り当てルール 3 社会的総余剰+満足度の最大化本研究で用いる社会的総余剰と満足度について以下で述べる． 4.1.1 社会的総余剰本研究では，買い手は準線形 [8, 9] の効用を持つと仮定する．これは，財を落札した場合の利得は，財の価値と支払額の差額で与えられるというものである．買い 手 b ∈ B の利得は，買い手 b に割り当てられた財への評価と支払額の差分として定 義されるので， db ∑ t=ab st ∑ k=0 ¯ vbt,k · xbt,k − 買い手 b の支払額 と表すことができる．よって買い手の利得の総和は， ∑ b∈B ( _d b ∑ t=ab st ∑ k=0 ¯ vbt,k · xbt,k− 買い手 b の支払額 ) = ∑ b∈B db ∑ t=ab st ∑ k=0 ¯ vbt,k· xbt,k − ∑ b∈B 買い手 b の支払額となる．売り手は財の廃棄にコストがかからないので，売り手の利得は買い手の支払額の合計であり， ∑ b∈B 買い手 b の支払額となる．すべての買い手と売り手の利得の総和を社会的総余剰と呼ぶ．社会的総余 剰 SW は， SW = 買い手の利得の総和 + 売り手の利得 = ∑ b∈B db ∑ t=ab st ∑ k=0 ¯ vbt,k · xbt,k − ∑ b∈B 買い手 b の支払額 +∑ b∈B 買い手 b の支払額 = ∑ b∈B db ∑ t=ab st ∑ k=0 ¯ vbt,k · xbt,k と表すことができる．SW を最大化するような割り当てをするのが割り当てルール 1 である．この割り当てルールを満たすような割り当ては，複数存在する可能性がある．複数存在する場合は，割り当てを求める方法によってどの割り当てかが決定される．

(9)

メカニズムが持っていて欲しい性質の一つとして割り当て結果がパレート効率的な状態であるということがある [10]．パレート効率的な状態とは，いずれかの参加者の利得を犠牲にすることなしには，他の参加者の利得を向上することができない状態のことを意味する．オークションにおいて，割り当て結果がパレート効率的な状態であるのは，最も高い評価を持つ買い手に財を割り当てるときである．本研究のように買い手に利得が準線形である場合には，参加者の間でお金を用いて効用がやりとりできるため，パレート効率的な割り当てでは社会的総余剰は最大化される． 4.1.2 満足度買い手が，オークションの結果に対して満足したかしていないかを考える．本研究では，財の割り当て数に対する満足度と時間に関する満足度の二つを考える． • 財の割り当て数に関する満足度 買い手に自身の財の必要単位数分財が割り当てられているとき，買い手の財の 割り当て数に関する満足度が最も高くなる．買い手 b の財の必要単位数 nbまでは，財の割り当て数が増えれば増えるほど買い手の満足度は高くなる．本研究では，財が必要以上に割り当てられると，その財を持て余してしまい満足度は 0 になるとする．過充電は，バッテリーの発火や劣化を引き起こす可能性があるため，必要以上に財を欲しがる買い手は存在しないと考えられるためであ る．買い手 b∈ B に割り当てられた財の総単位数 xb(0≤ xb ≤ nb) に対する買 い手 b の満足度を ub(xb) とする．ub(xb) は，0≤ xb ≤ nbの範囲で単調増加し，それ以外では 0 となる関数とする．例えば以下のような関数を考えることができる． ub(xb) = { 8xb (if 0≤ xb ≤ nb) 0 (o.w.). ub(xb) = { 5× ln(xb+ 1) (if 0≤ xb ≤ nb) 0 (o.w.). • 時間に関する満足度 買い手が最初に申告した到着時刻と出発時刻の間で財の取引が終了するとき，時間に関する満足度が最も高くなると考える．本研究では，最初に申告した出発時刻を超えてオークションに参加するとその時間に応じてコストがかかると する．買い手 b∈ B が出発時刻を延長した時間を lb ∈ Z+とする．また，買い 手 b∈ B が出発時刻を延長することでかかるコスト関数を cb(lb) とする．コス ト関数 cb(lb) は，単調増加関数であるとする．例えば以下ような関数を考えることができる． cb(lb) = lb.

(10)

cb(lb) = l2b. 時間厳守しなければならない買い手は，コスト関数の値が大きくなるように設定する． 上記の二つを用いて，買い手 b∈ B の満足度 Satbを Satb = ub(xb)− cb(lb) で表す．すべての買い手の満足度 Sat = ∑_b_∈BSatbの総和を最大化するような割り当てをするのが割り当てルール 2 である．割り当てルール 2 も割り当てルール 1 と同様にルールを満たす割り当てが複数存在する可能性がある．

4.2 支払いルール

本研究では，以下の二つの支払いルールを考える．買い手は，以下の支払いのルー ルに従って, 時刻 t 終了時に支払いを行う． • 支払いルール 1 : 買い手の評価値と同じ額支払う． 時刻 t ∈ T に k 単位の財が割り当てられた買い手は，¯vbt,k支払う． • 支払いルール 2 : (∑b∈B ∑st k=0xbt,k· k + 1) 番目に高い限界評価分を支払う． 時刻 t に買い手に割り当てられた財の単位数は，∑_b_∈B∑st k=0xbt,k·k である．時 刻 t に市場にいる買い手の財への限界評価を大きい順に並べ，(∑_b_∈B∑st k=0xbt,k· k + 1) 番目に大きい限界評価 v′を取り出す．市場に滞在している買い手が少なく，(∑_b_∈B∑st k=0xbt,k · k + 1) 番目に大きい限界評価が存在しない場合は 0 と する．時刻 t に財を割り当てられた買い手は，獲得した財一単位に対して v′支払う．

5 先行研究

本章では，時間毎に市場に供給される財の単位数が変化する単一財を動的に到着する買い手に割り当てるモデルの先行研究を述べる．

5.1 Fair Online Allocation of Perishable Goods and its

Ap-plication to Electric Vehicle Charging [2]

この論文では，多くの買い手が保存ができない財を求めて競合し，公平な割り当てを見つける必要があるオンラインスケジューリング問題について述べている．このモデルでは，金銭の支払いがなく，買い手が評価関数を指定せず，必要な財の量や期限などの要件のみを指定する．買い手は動的に到着し，到着時に出発時刻を発表すると想定している．主な用途は，時間の経過とともに買い手が出入りする場所での電気自動車の充電である．

(11)

5.1.1 [2] のモデル 買い手の集合を B とする．時刻の集合を T とする．財は分割不可能な単一財を想 定する．時刻 t ∈ T に市場にある財が，時刻 t のうちに買い手に割り当てられない 場合，その財は時刻 t 終了時に廃棄されてしまうとする．その際廃棄コストは発生 しない．時刻 t_{∈ T に市場に供給される財の単位数を s}t ∈ N とする．買い手 b ∈ B は市場へ到着する時刻 ab ∈ T ，市場から出発する時刻 db ∈ T (ab ≤ db)，必要な財の 単位数 nb ∈ N を持つ．買い手 b ∈ B へ時刻 t ∈ T に財が k 単位ちょうど割り当てら れている時 xbt,k = 1，そうでないとき xbt,k = 0 となる．買い手は，1 単位時間で受け取ることができる財の単位数 ¯rb ∈ Z+を持つ．これは買い手の中に，1 単位時間で 2 単位分の財を受け取ることができる人もいれば，1 単位分の財しか受け取ることができない人もいることを表している．買い手の必要 な財の単位数より多く財を割り当てることは考慮しない．よって買い手 b ∈ B の時 刻 t∈ T での ¯rbの値は，¯rb,t = min(¯rb, nb− ∑t−1 t=ai ∑st k=0xbt,k · k) となる． モデルより，検討する割り当てに対して以下の問題制約が生じる． • ∀b ∈ B, ∀t < ai : xbt,0= 1. すべての買い手は，到着時刻より前に財が割り当てられることはない． • ∀b ∈ B, ∀t > di : xbt,0= 1. すべての買い手は，出発時刻より後に財が割り当てられることはない． • ∀b ∈ B, ab ≤ t ≤ db : ∑st k=0xbt,k· k ≤ ¯rb. すべての買い手は，市場に滞在している間，1 単位時間で受け取ることができる財の単位数以上の財を受け取ることはない． • ∀b ∈ B : ∑db t=ab ∑st k=0xbt,k· k ≤ nb. すべての買い手は，必要な財の単位数より多く財を割り当てられることはない． • ∀t ∈ T :∑b∈B ∑st k=0xbt,k · k ≤ st. すべての時刻で，その時刻に割り当てられる財は，その時刻の供給量を超えない． 5.1.2 割り当てルール著者らは，買い手の財への評価が容易に取得できないことから，社会的総余剰を最大化する割り当てなどに代わりに，別の割り当てルールを検討している．検討されている割り当てルールは以下の通りである． • 割り当てられる財の単位数を最大化する割り当て 割り当てられる財の単位数∑_b_∈B∑db t=ab ∑st k=0xbt,k· k を最大にするように割り 当てを決める．すべての買い手が同一の財への評価を持ち，これらが割り当てられた財の単位数に線形である場合は社会的総余剰の最大化と同等である．

(12)

• 満足する買い手の人数の最大化する割り当て 買い手が∑db t=ab ∑st k=0xbt,k· k = nbを満たすとき，買い手は満足しているという．必要な単位数の財を割り当てられた買い手の人数が最大化されるように割り当てを決める． 5.1.3 割り当てを求める問題の計算複雑性著者らは，買い手の到着時刻，出発時刻，時刻毎の割り当て可能数が事前にすべてのわかっているオフライン環境で問題を解決する複雑さを検討している． • 割り当てられる財の単位数を最大化する割り当て 割り当てられる財の単位数を最大化する割り当ては，頂点に容量制約がある有向グラフの最大フローを計算することで多項式時間で割り当てを計算できる．このとき，有向グラフの頂点集合は次のように構成する．

{start, terminal} ∪ {buyerb|b ∈ B} ∪ {buyerbt|t ∈ T, b ∈ B} ∪ {timet|t ∈ T }

また，有向辺は次のような規則で構成する． – 始点 start から，各買い手の点 buyerbに辺を張る．これら辺の容量は nb である． – 各買い手の点 buyerbから，すべての t の点 buyerbtに辺を張る．これら辺 の容量は stである． – 点 buyert bから買い手が b が市場いる時刻 t の点 timetに辺を張る．これら の辺の容量は stである． – 点 timetから終点 terminal に辺を張る．これらの辺の容量は stである．頂点の容量を以下のように決定する． – buyerbの点は容量 nb. – timetの点は容量 st. 買い手が二人いる例を用いて実際にグラフ作成する．時刻の集合を T ={1, 2, 3} であるとする．買い手 1 は a1 = 1, d1 = 3, n1 = 3 であり，買い手 2 は a2 = 2, d2 = 3, n2 = 2 であるとする．また時刻毎の割り当て可能な財の単位数を s1 = 1, s2 = 1, s3 = 1 とする．この例を用いて実際にグラフを作成すると図 1 のようになる．始点 start から各買い手の点 buyerbに辺があり，各買い手の

点 buyerbからすべての t の buyertbに辺があり，点 timetから終点 terminal に

辺があることが確認できる．また買い手 1 はすべての時刻で市場にいるので 点 buyert

1から点 timetへ辺がある．買い手 2 は時刻 1 に市場にいないので点 buyer1₁から点 time1への辺がないことが確認できる．

(13)

𝑠tart 𝑏𝑢𝑦𝑒𝑟1 𝑏𝑢𝑦𝑒𝑟2 𝑡𝑖𝑚𝑒₁ 𝑡𝑖𝑚𝑒2 𝑡𝑖𝑚𝑒3 𝑏𝑢𝑦𝑒𝑟₁1 𝑏𝑢𝑦𝑒𝑟₁2 𝑏𝑢𝑦𝑒𝑟₁3 𝑏𝑢𝑦𝑒𝑟21 𝑏𝑢𝑦𝑒𝑟₂3 𝑏𝑢𝑦𝑒𝑟₂2 𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙 上限容量 𝑛₁= 3 上限容量 𝑛2= 2 上限容量 𝑠₁= 1

頂点の集合

{𝑠𝑡𝑎𝑟𝑡, 𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙} ∪ 𝑏𝑢𝑦𝑒𝑟

_𝑏

𝑏 ∈ 𝐵

∪ 𝑏𝑢𝑦𝑒𝑟

_𝑏𝑡

𝑏 ∈ 𝐵, 𝑡 ∈ 𝑇 ∪ 𝑡𝑖𝑚𝑒

_𝑡

𝑡 ∈ 𝑇}

上限容量 𝑠2= 1 上限容量 𝑠₃= 1 図 1: 有向グラフ作成例このグラフの最大フローを計算する．一例が図 2 である．フローを調べることで，実際の割り当てを読み取ることができる．図 2 を見るとすべての時刻で買い手 1 に財が割り当てられており，割り当て可能なすべての財を割り当てていることが確認できる． • 満足する買い手の数の最大化する割り当て 筆者らは，すべての時刻で st= 1 であり，かつ∀b ∈ B : ¯rb = 1 のとき，満足する買い手の人数を最大化する割り当ては多項式時間で計算できることを示し， すべての時刻で st= 2 であり，かつ∀b ∈ B : ¯rb = 1 のときは，NP 困難であることも示している．次に，著者らはすべての時刻でこれまでに到着した買い手の情報しかもっていないオンライン環境で割り当てを求めるアルゴリズムを提案し，問題の計算複雑性を検討している．オンライン環境で割り当てられる財の単位数を最大化する割り当てを求めるアルゴリズムと満足する買い手の人数の最大化する割り当てを求めるアルゴリズムを提案し，それらの計算の複雑さがそれぞれ多項式および NP 困難であることを示している．

(14)

𝑠tart 𝑏𝑢𝑦𝑒𝑟1 𝑏𝑢𝑦𝑒𝑟2 𝑡𝑖𝑚𝑒1 𝑡𝑖𝑚𝑒₂ 𝑡𝑖𝑚𝑒3 𝑏𝑢𝑦𝑒𝑟₁1 𝑏𝑢𝑦𝑒𝑟₁2 𝑏𝑢𝑦𝑒𝑟₁3 𝑏𝑢𝑦𝑒𝑟₂1 𝑏𝑢𝑦𝑒𝑟₂3 𝑏𝑢𝑦𝑒𝑟₂2 𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙 上限容量 𝑛₁= 3 上限容量 𝑛₂= 2 上限容量 𝑠₁= 1 上限容量 𝑠2= 1 上限容量 𝑠3= 1 3 1 1 1 1 1 1 1 1 1 図 2: 最大フロー例

(15)

5.2 An Agent-based Negotiation Scheme for the

Distribu-tion of Electric Vehicles Across a Set of Charging

Sta-tions [3]

この論文では，複数の電気自動車が時間の経過とともに複数の充電施設に充電要求を行うモデルを検討しており，どの電気自動車がどの充電施設でどの程度の充電を行うかを決定するアルゴリズムを提案している．充電施設は，限られた数しか充電器所持しておらず，利用可能なエネルギーの量は限られている．財は，電気自動車の充電権である． 5.2.1 [3] のモデル 充電施設の集合 F ，電気自動車の所有者の集合 B とする．時刻の集合を T とす る．財は分割不可能な財を想定する．時刻 t ∈ T に買い手に割り当て可能な財があ り，この財が時刻 t に割り当てが行われない場合，その財は時刻 t 終了時に誰にも割 り当てないまま消費されてしまうとする．充電施設が財を廃棄するためのコストは 0 であるとする．施設 f ∈ F が持つ充電装置の集合を CDfとし，各時刻で充電装置 cd∈ CDf が使用可能な充電量を ecd ∈ N とする．電気自動車の所有者は，充電リク エストを送る時刻 reqb ∈ T ，到着時刻 ab ∈ T (reqb ≥ ab)，出発時刻 db ∈ T (ab ≥ db)， 必要な財の単位数 nb ∈ N，利得 ubを持つ．スケジュールは以下の手順で決定される． step1 電気自動車の所有者は，各施設に充電施設に送った到着時刻 ab ∈ T ，出発時 刻 db ∈ T ，必要な財の単位数 nb ∈ N の組を充電リクエストとして送信する． step2 各充電施設は，送られてきた充電リクエストを用いて整数線形計画問題を解き，充電スケジュールを決定する． 決定したスケジュールを用いて，電気自動車の所有者に提案 prop = (aprop b , d prop b , x prop b ) を送信するか，使用できないことを連絡する．

step3 電気自動車の所有者は，送られきた提案を評価し，以下のように Accept/W ait/Stop のいずれかを施設に返信する． – 提案の中で一番よい提案をした施設に Accept を返信し，残りの施設に Stop を返信する． – 提案を受け入れず，施設に W ait を送信し，代替案を提案してもらう． ただし，W ait を送信する回数に制限があり，その回数を超えると Stop を送信する． step4 充電施設は，返信に応じて対応する． Accept が返信されたとき．スケジュールを固定する． W ait が返信されたとき，割り当てられていない財を用いて整数線形計画問題 を解き，代替案を送信する．

(16)

Stop が返信されたとき．送信をやめる． すべての買い手から Accept または Stop どちらかの返信を受け取ったとき，現 在の時刻の操作を終了する．オフライン環境の場合，時刻 1 にすべての電気自動車の所有者が充電リクエストを送り，上記の手順でスケジュールを決定する．オンライン環境の場合，現在の時 刻 t に送られてきた充電リクエスト (reqb = t である充電リクエスト) を用いて上記 の手順でスケジュールを決定する．以降の時刻では，一度固定したスケジュールは変更しない．次の時刻になると，その時刻に送られてきた充電リクエストと割り当てられていない財を用いて，上記の手順でスケジュールを決定するという動作を繰り返す． また，オンライン環境では，Accept を返信した電気自動車の所有者が到着時刻に 遅れるということを想定する．到着時刻に間に合わない電気自動車の所有者は，新しく充電リクエストを充電施設に送信し，変更を充電施設に通知する．充電施設は，固定したスケジュールを削除する．その後，送られてきた充電リクエストは，その時刻に送られてきた他の充電リクエストと一緒に上記の手順で再度スケジュールを決定する．遅延した電気自動車の所有者は，優先されないため，変更により充電できなくなる可能性がある． 5.2.2 電気自動車の所有者の利得 電気自動車の所有者 b∈ B の利得は，充電施設に送った充電リクエストの到着時 刻 ab ∈ T ，出発時刻 db ∈ T ，必要な財の単位数 nb ∈ N の通りに充電するようにス ケジュールされているとき，ub = 1 となる．また，すべての充電施設の提案を断っ たとき，ub = 0 となる．代替案を受け入れた場合の所有者 b∈ B の利得を以下のよ うに計算する． ub = 1− ( w1 energyDif maxEnergyDif + w2 windowDif maxW indowDif ) . 財の割り当て数に対する利得を energyDif, maxEnergyDif を用いて計算する． energyDif は電気自動車の所有者が獲得できなかった財の単位数を表し，energyDif = nb− x prop b である．maxEnergyDif は、獲得できなかった財の単位数の最大値を表 す．要求されたエネルギーをすべて割り当てられない場合は，すべての施設から拒 否されている場合であり ub = 0 となる．上記の式を用いて利得を計算するとき，割 り当てられた財の最低単位数は 1 単位なので，maxEnergyDif = nb− 1 である．

財の割り当てが発生する時刻に対する利得を windowDif, maxW indowDif を用 いて計算する．windowDif は、施設から提案された到着時刻と出発時刻が充電リク エストからどの程度移動したかを表し，以下の式で求める．

(17)

する．w1, w2 は，必要な単位数分の財を獲得することと時間通りに充電されること のどちらを重視しているかを表す重みである． 以下で例を用いて計算する．時刻の集合を T ={1, 2, 3, 4, 5} とする．電気自動車 の所有者 b ∈ B の充電リクエストが (ab = 2, db = 3, nb = 2) であるとする．施設か ら提案 prop = (aprop b = 1, d prop b = 2, x prop b = 2) が送られてきて，b は提案を受け入れ たとする．このときの電気自動車の所有者 b∈ B の利得を計算する．電気自動車の 所有者は財をを必要単位分獲得しているため，energyDif = 2_{− 2 = 0 である．ま} た，獲得できなかった財の単位数の最大値は，maxEnergyDif = 2− 1 = 1 である． ab = 2, db = 3, aprop_b = 1, dprop_b = 2 であるので， windowDif = min(|1 − 2|, |1 − 3|) +

min(|2−2|, |2−3|) = 1である，windowDifが最も大きくなるのは，aprop_b = 4, dprop_b = 5 の時であるので，maxW indowDif = min(|4 − 2|, |4 − 3|) + min(|5 − 2|, |5 − 3|) = 3

である，必要な単位数分の財を獲得することと時間通りに充電されることを同じ重みで計算すると ui = 1− ( 0.5· 0 1 + 0.5· 1 3 ) = 0.85 となる．

5.3 提案モデルと先行研究との違い

本研究と先行研究はどれも買い手が動的に市場に到着するというモデルであり，割り当てる財は分割不可な単一財で，次の時刻に持ち越すことができないという性質を持っている．検討する割り当てが持つ問題制約は，先行研究 [2] が持つ制約と同様のものが多い．また，本研究の満足度の計算方法は，先行研究 [3] の利得の計算方法と同様で，財の割り当て単位数に対する満足度，時間に対する満足度の二つを考慮して作成されている．本研究と先行研究の大きな違いは，割り当て決定の際に社会的総余剰も考慮するという点である．オークションの分野では，社会的総余剰を最大化する割り当てが以前から考えられている．先行研究で財への評価を収集せずに割り当てを決定する方法が述べられている．その両方を用いて，社会的総余剰の観点からも買い手の満足度の観点からもよい割り当てを求めようと考えたのが本研究である．先行研究 [3] で考慮していた買い手が到着時刻に遅れるという点は考慮していない．買い手が出発時刻を延長できるという仮定は，先行研究のモデルには含まれていない．

6 提案手法

本章では，3 章の「単一財逐次複数ユニットオークション」に対して，割り当てルールに従った割り当てをどのように求めるかを述べる．すべての買い手の到着時刻，出発時刻，財の必要数，評価額と時刻毎の割り当て可能数が事前にすべてわかっているオフライン環境で割り当てを求める方法を述べる．整数線形計画問題を用いて割り当てを求める．

(18)

6.1 社会的総余剰を最大化する割り当て

社会的総余剰を最大化する割り当ては，以下の ILP1 を解いて求める．目的関数 は SW であり，変数は xbt,kである． ILP1 最大化 SW = ∑ b∈B db ∑ t=ab st ∑ k=0 ¯ vbt,k· xbt,k 制約条件 _{∀b ∈ B, ∀t < a}_b : xbt,0= 1. (1) ∀b ∈ B, ∀t > db : xbt,0= 1. (2) ∀b ∈ B : db ∑ t=ab st ∑ k=0 xbt,k · k ≤ nb. (3) ∀t ∈ T :∑ b∈B st ∑ k=0 xbt,k· k ≤ st. (4) ∀b ∈ B, ∀t ∈ T : st ∑ k=0 xbt,k = 1. (5) ∀b ∈ B, ∀t ∈ T, ∀k(0 ≤ k ≤ st) : xbt,k ∈ {0, 1} (6) それぞれの制約条件について以下で述べる．制約条件 (1)(2) は，すべての買い手は市場にいない間に財が割り当てられることはないという条件を表す．制約条件 (1) で到着時刻より前の時刻についての制約，制約条件 (2) で出発時刻より後の時刻についての制約を表す．制約条件 (3) は，すべての買い手はその買い手の財の必要単位数以上に財を割り当てられることがないという条件を表す．制約条件 (4) は，すべての時刻で，割り当てられる財が現在の時刻に割り当て可能である単位数以上にならないという条件を表す．制約条件 (5)(6) は， 割り当て xbt,kに関係する制約である．制約条件 (5) は，すべての買い手，すべての 時刻について，割り当て xbt,kの定義を満たすという条件を表す．制約条件 (6) は，割 り当て xbt,kには，0 か 1 が入力されるという条件を表す．

6.2 満足度を最大化する割り当て

買い手 b に財が割り当てられた最後の時刻を tlast b ∈ Z+とする． 満足度を最大化する割り当ては，以下の ILP2 を解いて求める．目的関数は Sat で あり，変数は xbt,k, lb, tlastb である．

(19)

ILP2 最大化 Sat =∑ b∈B (ub(xb)− cb(lb)) 制約条件 _{∀b ∈ B, ∀t < a}_b : xbt,0= 1. (7) ∀b ∈ B : tmax ∑ t=ab st ∑ k=0 xbt,k· k ≤ nb. (8) ∀t ∈ T :∑ b∈B st ∑ k=0 xbt,k· k ≤ st. (9) ∀b ∈ B, ∀t ∈ T : st ∑ k=0 xbt,k = 1. (10) ∀b ∈ B, ∀t ∈ T, ∀k(0 ≤ k ≤ st) : xbt,k ∈ {0, 1} (11) ∀b ∈ B : lb ≥ tlastb − db. (12) ∀b ∈ B, ∀t ∈ T : st ∑ k=1 xbt,k · t ≤ tlastb . (13) ∀b ∈ B : lb ∈ Z+ (14) ∀b ∈ B : tlast b ∈ Z+ (15) それぞれの制約条件について以下で述べる．制約条件 (7) は，すべての買い手は市場に到着する前に財が割り当てられることはないという条件を表す．本モデルでは，出発時刻を延長できるので満足度を考える際には，制約条件 (2) の条件はない．制約条件 (8) は，ILP1 の制約条件 (3) と同様 の条件を表しているが，出発時刻が延長できるので到着時刻 ab から tmaxまでを考える．制約条件 (9)(10)(11) は，ILP1 の制約条件 (4)(5)(6) と同様の条件である．制 約条件 (12)(13)(14)(15) は，延長時間 lbと最終割り当て時刻 tlastb に関する制約である，制約条件 (12) は，延長時間が最終割り当て時刻から出発時刻を引いた値以上であることを表す．制約条件 (13) は，財が 1 単位以上割り当てられている時刻は，最終割り当て時刻以下であることを表す．制約条件 (14)(15) は，延長時間と最終割り当て時刻が 0 以上の整数であることを表す．

6.3 社会的総余剰と満足度を最大化する割り当て

社会的総余剰と満足度を最大化する割り当ては，以下の ILP3 を解いて求める．目 的関数は SW + Sat であり，変数は xbt,k, lb, tlastb である．

(20)

ILP3 最大化 SW + Sat 制約条件 _{∀b ∈ B, ∀t < a}_b : xbt,0= 1. ∀b ∈ B : tmax ∑ t=ab st ∑ k=0 xbt,k· k ≤ nb. ∀t ∈ T :∑ b∈B st ∑ k=0 xbt,k· k ≤ st. ∀b ∈ B, ∀t ∈ T : st ∑ k=0 xbt,k = 1. ∀b ∈ B, ∀t ∈ T, ∀k(0 ≤ k ≤ st) : xbt,k ∈ {0, 1} ∀b ∈ B : lb ≥ tlastb − db. ∀b ∈ B, ∀t ∈ T : st ∑ k=1 xbt,k · t ≤ tlastb . ∀b ∈ B : lb ∈ Z+ ∀b ∈ B : tlast b ∈ Z+ 制約条件は，ILP2 と同様の条件である．

7 計算機実験

7.1 インスタンスの生成

実験を行うにあたり，入力として与えるデータをどのように生成するか述べる．こ こで閉区間 [l, u] の中で一様乱数を用いて，整数値を生成する確率分布を U [l, u] と する． • インスタンスタイプ 1 ：完全ランダムデータ 買い手の集合のサイズを_{|B| = 100，時刻の集合のサイズを |T | = 30 とする．} 買い手の定数 ab, db, nb, vbtと時刻の定数 stを以下の表 1 のように選択する． また，すべての買い手 b∈ B の割り当てられた財に対する満足度を ub(xb) = { 8xb (if 0≤ xb ≤ nb) 0 (o.w.) (16) とする． すべての買い手 b∈ B のコスト関数を cb(lb) = lb (17) とする．

(21)

表 1: インスタンスタイプ 1 作成方法 ad U [1, 30] db U [ab, 30] nb U [1, 5] vbt,0 0 vbt,1 U [0, 10] vbt,k(k≥ 2) U[0, vbt,k−1] st U [1, 5] • インスタンスタイプ 2 ：買い手の到着時刻出発時刻にピークがあるデータ 買い手の到着時刻 ab，出発時刻 dbを以下のように生成する． 1 平均 15 分散 5 の正規分布を用いて値を二つ選び，その値の小数点第 1 位を四捨五入し，整数にする． 2 選んだ値が 1 以下であった場合は 1 に変更し，30 以上であった場合は 30 に変更する． 3 二つの値の大小を比べ，小さい方を到着時刻 abに，大きい方を出発時刻 dbとする． nb, vbt, stは，完全ランダムデータと同様の方法で生成する．割り当てられた財に対する満足度とコスト関数も，完全ランダムデータと同様の関数を用いる．ピークの時刻 15 周辺に市場にいる買い手の人数が多くなり，時刻 1 や時刻 30 などは市場にいる買い手の人数は少なくなるようなインスタンスを生成する． • インスタンスタイプ 3 ：短い期間しか市場に滞在できない買い手のデータ 買い手の出発時刻 dbを U [ab, ab+ 3] で生成する． ab, nb, vbt, stは，完全ランダムデータと同様の方法で生成する．割り当てられた財に対する満足度とコスト関数も，完全ランダムデータと同様の関数を用いる．買い手が市場にいる時間が最大でも 3 であるようなインスタンスを生成する． • インスタンスタイプ 4 ：財への評価が低い買い手のデータ 1 単位目の財への限界評価 vbt,1を U [0, 5] で生成する． ab, db, nb, vbt,0, vbt,k(k≥ 2), stは，完全ランダムデータと同様の方法で生成する．割り当てられた財に対する満足度とコスト関数も，完全ランダムデータと同様の関数を用いる．買い手の財への評価が完全ランダムデータ生成時に比べて小さいインスタンスを生成する． • インスタンスタイプ 5 ：財が大量に欲しい買い手のデータ 必要な財の単位数 nbを U [5, 10] で生成する．

(22)

ab, db, vbt, stは，完全ランダムデータと同様の方法で生成する．割り当てられた財に対する満足度とコスト関数も，完全ランダムデータと同様の関数を用いる．買い手が必要な財の単位数が完全ランダムデータ生成時に比べて大きいインスタンスを生成する． • インスタンスタイプ 6 ：市場に供給される財の単位数にピークがあるデータ 時間毎の市場に供給される財の単位数 stを以下の方法で生成する． – 1 ≤ t ≤ 10 または 21 ≤ t ≤ 30 のとき，平均 3 分散 1 の正規分布を用いて 値を一つ選ぶ．その値の小数点第 1 位をを四捨五入して整数にする．もし 1 以下の整数が得られた場合 1 に変更する． – 11≤ t ≤ 20 のとき，平均 5 分散 1 の正規分布を用いて値を一つ選ぶ．そ の値の小数点第 1 位をを四捨五入して整数にする．もし 1 以下の整数が得られた場合 1 に変更する． ab, db, nb, vbtは，完全ランダムデータと同様の方法で生成する．割り当てられた財に対する満足度とコスト関数も，完全ランダムデータと同様の関数を用いる．時刻 1≤ t ≤ 10 または 21 ≤ t ≤ 30 では財の割り当て可能単位数が 3 単位程度であり，時刻 11≤ t ≤ 20 では財の割り当て可能単位数が 5 単位程度となる．財が多く供給される時間帯があるようなインスタンスを生成する． • インスタンスタイプ 7 : 買い手のコスト関数が大きいデータ すべての買い手 b∈ B のコスト関数を cb(lb) = lb2 (18) とする．ab, db, nb, vbt, stは，完全ランダムデータと同様の方法で生成する．割り当てられた財に対する満足度は，完全ランダムデータと同様の関数を用いる． • インスタンスタイプ 8 : 買い手の割り当てられた財に対する満足度が小さい データ すべての買い手 b∈ B の割り当てられた財に対する満足度を ub(xb) = { 3xb (if 0≤ xb ≤ nb) 0 (o.w.) (19) とする．ab, db, nb, vbt, stは，完全ランダムデータと同様の方法で生成する．コスト関数は，完全ランダムデータと同様の関数を用いる． • インスタンスタイプ 9 : 買い手の財の必要量が小さいデータ 必要な財の単位数 nbを U [1, 2] で生成する． ab, db, vbt, stは，完全ランダムデータと同様の方法で生成する．割り当てられた財に対する満足度とコスト関数も，完全ランダムデータと同様の関数を用いる．買い手が必要な財の単位数が完全ランダムデータ生成時に比べて小さいインスタンスを生成する．

(23)

• インスタンスタイプ 10 : 財が大量に供給されるデータ 時間毎の市場に供給される財の単位数 stを U [5, 10] で生成する． ab, db, nb, vbtは，完全ランダムデータと同様の方法で生成する．割り当てられた財に対する満足度とコスト関数も，完全ランダムデータと同様の関数を用いる． • インスタンスタイプ 11 : 買い手の 1 単位の財への満足度が徐々に小さくなる データ すべての買い手 b_{∈ B の割り当てられた財に対する満足度を} ub(xb) = { 5× ln(xb+ 1) (if 0≤ xb ≤ nb) 0 (o.w.) (20) とする．ab, db, nb, vbt, stは，完全ランダムデータと同様の方法で生成する．コスト関数は，完全ランダムデータと同様の関数を用いる．

7.2 実験環境

前節で述べた方法で，それぞれのインスタンスタイプのパラメータを 50 セットずつ生成し，実験を行う．実験環境は以下の表 2 の通りである．言語は Python3.6.3 を用いる．整数線形計画問題は，CPLEX12.10 を用いて解く．表 2: 実験環境

CPU Memory CPU

3.2 GHz Intel Core i5 8 GB 1867 MHz DDR3 macOS Mojave 10.14.6

7.3 実験結果

生成したパラメータ 50 セットを用いて整数線形計画問題 1,2,3 をそれぞれ 50 回ず つ解いた．生成したパラメータの買い手が市場にいる時間 db− abの平均と分散を有 効数字二桁で表 3 にまとめる．SW, Sat, SW + Sat の値，延長した人数，延長した 時間の平均，割り当てられずに廃棄された財の単位数，満足した買い手の人数を平 均した値を有効数字二桁で表 4 から表 14 にまとめる．SW + Sat を最大化する割り 当てルールで求めた割り当てで，支払いルール 1,2 に従って求めたすべて買い手の支払額の総和を有効数字二桁で表 15 にまとめる．

(24)

表 3: 買い手が市場にいる時間の平均分散平均分散インスタンスタイプ 1 7.24 44.43 インスタンスタイプ 2 5.69 18.20 インスタンスタイプ 3 1.41 1.26 インスタンスタイプ 4 7.39 44.71 インスタンスタイプ 5 7.19 43.25 インスタンスタイプ 6 7.29 45.41 インスタンスタイプ 7 7.19 43.32 インスタンスタイプ 8 7.40 46.30 インスタンスタイプ 9 7.24 43.62 インスタンスタイプ 10 7.14 44.01 インスタンスタイプ 11 7.03 43.54 表 4: インスタンスタイプ 1

ILP1 ILP2 ILP3 SW 817.68 363.70 825.00 Sat 708.48 711.84 707.04 SW + Sat 1526.16 1075.54 1532.04 延長した人数 – 0 3.62 延長時間の平均 – 0 1.22 廃棄された財 0.66 0.20 0.40 満足した買い手の人数 20.90 20.28 21.28 表 5: インスタンスタイプ 2

ILP1 ILP2 ILP3 SW 624.30 284.42 749.98 Sat 578.56 661.18 630.30 SW + Sat 1202.86 945.60 1380.28 延長した人数 – 3.08 10.84 延長時間の平均 – 2.82 3.71 廃棄された財 17.04 5.58 7.28 満足した買い手の人数 17.40 20.08 19.02

8 考察

SW + Sat の値から，すべてのインスタンスタイプで SW と Sat を両方考慮する割 り当てルールは，片方のみを考慮する割り当てルールより社会的総余剰と満足度の

(25)

表 6: インスタンスタイプ 3

ILP1 ILP2 ILP3 SW 684.30 346.96 800.16 Sat 717.28 724.68 677.58 SW + Sat 1401.58 1071.64 1477.74 延長した人数 – 0.10 21.64 延長時間の平均 – 0.09 2.20 廃棄された財 1.42 0.36 3.44 満足した買い手の人数 20.46 19.48 20.00 表 7: インスタンスタイプ 4

ILP1 ILP2 ILP3 SW 843.68 343.38 851.56 Sat 724.96 727.36 722.68 SW + Sat 1568.64 1070.74 1574.24 延長した人数 – 0 3.40 延長時間の平均 – 0 1.34 廃棄された財 0.58 0.14 0.34 満足した買い手の人数 0.46 2.2 0.74 観点でよい割り当てを得ることできるということがわかる．買い手が出発時刻を延 長し，財を獲得できる潜在機会が高くなるため，SW の値が増加していると考えら れる．どのインスタンスタイプでも SW を考慮せずに割り当てを決定している ILP2 の SW の値はとても低いが，廃棄された財の単位数は少ない．廃棄された財は買い 手が集中するインスタンスや財が市場に大量に供給されるインスタンス以外では，1 単位程度であり，それほど多くないこともわかる．また，必要な量の財を獲得できた買い手の人数は少ないインスタンスが多い．本研究で用いたインスタンスは，需要過多で競争の激しいものが多く，需要を満たした買い手が少なくなる傾向にある．

(26)

ILP1 ILP2 ILP3 SW 809.82 349.10 817.20 Sat 701.92 706.54 701.88 SW + Sat 1511.74 1055.64 1519.08 延長した人数 – 0.02 4.12 延長時間の平均 – 0.02 1.03 廃棄された財 1.20 0.44 0.74 満足した買い手の人数 20.58 18.68 20.68 表 11: インスタンスタイプ 8

ILP1 ILP2 ILP3 SW 827.10 349.90 836.08 Sat 268.32 269.62 264.10 SW + Sat 1095.42 619.52 1100.18 延長した人数 – 0.02 3.70 延長時間の平均 – 0.02 1.33 廃棄された財 0.52 0.08 0.38 満足した買い手の人数 23.14 20.68 22.36 表 5 では，他のインスタンスと比較して，買い手に割り当てられずに廃棄された財が多いことが確認できる．これは買い手が時刻 15 付近に集中するようにインスタンスを作成したためだと考えられる．財がどの時刻で廃棄されたかを実験の出力から確認すると，ILP1 はオークション開始付近と終了付近で廃棄され，ILP2 はオークションは開始付近で廃棄され，ILP3 はオークション開始付近がもっとも多く，オークション終了付近でも少し廃棄されていた．時間の延長ができる ILP2 と ILP3 では，オークション終了付近の時間に延長する買い手が存在し，買い手が少なくなる時間帯に割り当て可能な財を獲得したのだと考えられる．また，表 3 からも買い手の市

(27)

ILP1 ILP2 ILP3 SW 835.84 453.46 836.34 Sat 254.98 311.41 278.09 SW + Sat 1090.82 764.86 1114.42 延長した人数 – 0.10 6.30 延長時間の平均 – 0.06 1.29 廃棄された財 0.90 1.02 1.72 満足した買い手の人数 22.30 19.58 20.30 場にいる時間の平均と分散の値が完全ランダムデータより小さくなっていることが確認できる．表 6 では，他のインスタンスと比較して，延長した買い手の人数が多いことが確認できる．これは買い手が短い期間しか市場にいれないインスタンスであるためではないかと考えられる．表 3 より，他のインスタンスと比べ，買い手の市場にいる時間の平均と分散の値がとても小さいことが確認できる．表 4 と表 7 を比較すると ILP3 で，延長した買い手の人数と延長時間が少なくなっ ているのが確認できる．これは，SW と Sat を単純に足し合わせているため評価が

(28)

表 15: すべて買い手の支払額の総和支払いルール 1 支払いルール 2 インスタンスタイプ 1 825.00 753.44 インスタンスタイプ 2 749.98 551.02 インスタンスタイプ 3 800.16 525.18 インスタンスタイプ 4 433.52 405.80 インスタンスタイプ 5 851.56 762.00 インスタンスタイプ 6 1013.94 924.44 インスタンスタイプ 7 817.20 745.98 インスタンスタイプ 8 836.08 763.70 インスタンスタイプ 9 812.52 765.14 インスタンスタイプ 10 1805.82 1025.88 インスタンスタイプ 11 836.34 766.60 低い買い手が集まると延長コストを受け入れることができず，延長しなくなっているからだと考えられる．表 8 では，他のインスタンスと比較して，満足した買い手の人数が少ないことを確認できる．買い手が大量の財を必要としているインスタンスには，本研究の割り当てルールは，買い手が満足するということに関して効果を期待できないと考えられる．表 9 では，他のインスタンスと比較して満足した買い手の人数が多いことが確認できるが，割り当て可能な財の数が増えたことにより，満足する買い手の人数が増えているだけであると考えられる．表 10 では，表 4 と比べて，延長時間の平均が低い値となっている．これは，コスト関数の変化の影響だと考えられる．延長時間が 2 を超えると大きなコストを支払う必要があるので，延長した買い手のほとんどが 1 時刻分しか出発時刻を延長していないと考えられ，実験の出力からこのことが正しいと確認できた． 表 11 では，割り当て数に対する満足度の変化により Sat が小さくなっている．し かし，延長人数やその時間，廃棄された財の数，満足した買い手の人数は，完全ランダムデータと大差ないことがわかる．表 12 では，買い手の財の必要量を減らしたインスタンスであるため，他のインスタンスに比べ，満足した買い手の人数が多い．表 13 では，ILP3 の延長人数が多いことが確認できる．財が大量にあることによって，延長しても財を獲得できないという事象が起こる可能性が他のインスタンスに比べて少なく，延長しやすい環境になっているためだと考えられる．また，ILP3 の満足した買い手の人数は，ILP1,2 と比べ少しだけ増加している． 表 14 は，表 11 と同様で満足度の変更により Sat の値は減少しているが，その他 のデータは完全ランダムデータと大差ないことがわかる．支払いルール 1 に従って買い手の支払額を決定するとき，買い手の利得は常に 0 と なる．よって SW の値は，すべての買い手の支払額の総和と一致する．支払いルー

(29)

ル 2 に従って買い手の支払額を決定するとき，買い手の利得は正の値をとる．SW の値は割り当てを変更していないので変化しない．SW の一部が買い手の利得にな り，残りが売り手の利得となる．表 15 より，買い手の利得が大きいのはインスタンスタイプ 2,3,10 であり，買い手の利得が小さいのはインスタンスタイプ 4 である．インスタンスタイプ 2,3 は，買い手の到着時間や滞在時間を変化させたインスタンスであり，買い手の人数が少ない時刻で財の競合が発生せず，無料で財を獲得している買い手が存在するためだと考えられる．インスタンスタイプ 10 は，財の供給量を増加させたインスタンスであり，財が大量にあるために財の競合が少なくなり，無料で財を獲得している買い手が存在するためだと考えられる．インスタンスタイプ 4 は，買い手の財への評価が低いインスタンスであるため，利得の値も小さくなっていると考えられる．

9 おわりに

本研究では，時間毎に割り当て可能数が変わる単一財を動的に到着する買い手に割り当てるモデルで，社会的総余剰と買い手の満足度両方を考慮する割り当てルールを提案し，割り当てをオフライン環境で整数線形計画問題を用いて求めた．この割り当てルールを用いると，本研究で考慮した環境のもとで，社会的総余剰か買い手の満足度のうち一方のみを考慮する割り当てルールより，社会的総余剰と満足度の点でよい割り当てを得ることができることを確認した．今後の課題として，割り当て数に対する満足度やコスト関数を変更したインスタンスなど，新たなインスタンスを作成し，追加で実験を行う必要がある．また，買い手の到着時刻などがわからないオンライン環境で社会的総余剰と買い手の満足度の両方を考慮する割り当てを求めるアルゴリズムの作成とそのときの支払いルールの作成が考えられる．実データでの検証のため，被験者実験を行うことも考えられる．

謝辞

本研究を進めるにあたり，多くのご指導を賜りました高橋里司准教授に深く感謝致します．研究以外にも三年間大学生活で大変お世話になりました．本当にありがとうございました．最適化ゼミや研究室で助言を頂きました村松正和教授に感謝いたします．また，研究室での生活など高橋研究室と村松研究室の保木研究室の学生の皆様に大変お世話になりました．心から感謝致します．

参考文献

[1] 経済産業省/ニュースリリース/ニュースアーカイブ/2020 年度 12 月一覧/令和 2 年度第 3 次補正予算案に「災害時にも活用可能なクリーンエネルギー自動車導入事業費補助金」等が盛り込まれました https://www.meti.go.jp/press/2020/12/20201222006/20201222006.html

(30)

(2021/1/13 最終アクセス)

[2] Enrico H. Gerding, Alvaro Perez-Diaz, Haris Aziz, Serge Gaspers, Antonia Marcu, Nicholas Mattei and Toby Walsh,「Fair Online Allocation of Perishable Goods and its Application to Electric Vehicle Charging」 In Proceedings of the Twenty-Eigth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19). 7 pp . (In Press)

[3] Andreas Seitaridisa, Emmanouil S. Rigasa, Nick Bassiliadesa, Sarvapali D. Ram-churnb「An Agent-based Negotiation Scheme for the Distribution of Electric Vehicles Across a Set of Charging Stations」Simulation Modelling Practice and Theory Volume 100, April 2020, 102040

[4] ヤフオク！ヘルプ/入札のしくみ https://support.yahoo-net.jp/PccAuctions/s/article/H000005267(2021/1/18 最終アクセス) [5] e-Bay https://www.ebay.com(2021/1/18 最終アクセス) [6] 並木誠 (著),「線形計画法」朝倉書店 (2008) [7] 藤江哲也 (2012), ’ 整数計画法による定式化入門’ ，オペレーションズ・リサーチ 2012 年 4 月号 191-197 [8] ポール・ミルグロム (著)，川又邦夫・奧野正寛 (監訳), 計盛英一郎・馬場弓子 (訳): 「オークション理論とデザイン」, 東洋経済新報社 (2007) p81 3.3 利得関数が準線形の場合 [9] ハル・R・ヴァリアン (著)，佐藤降三 (監訳): 「入門ミクロ経済学 [原著第 7 版]」勁草書房 (2007)p65 [10] 横尾真 (著)「オークション理論の基礎ーゲーム理論と情報化学の先端領域ー」東京電機大学出版局 (2006)

単一財逐次複数ユニットオークションにおける財の割り当てに関する考察

単一財逐次複数ユニットオークションにおける

財の割り当てに関する考察

情報数理工学プログラム

学籍番号

1931147

森本 智貴

目 次

1

はじめに

2

準備

2.1

オークションとメカニズム

2.2

限界評価

2.3

単一財複数ユニットオークション

2.4

整数線形計画問題

[6]

3

単一財逐次複数ユニットオークション

4

メカニズム

4.1

割り当てルール

4.2

支払いルール

5

先行研究

5.1

Fair Online Allocation of Perishable Goods and its

Ap-plication to Electric Vehicle Charging [2]

頂点の集合

{𝑠𝑡𝑎𝑟𝑡, 𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙} ∪ 𝑏𝑢𝑦𝑒𝑟

𝑏 ∈ 𝐵

∪ 𝑏𝑢𝑦𝑒𝑟

𝑏 ∈ 𝐵, 𝑡 ∈ 𝑇 ∪ 𝑡𝑖𝑚𝑒

𝑡 ∈ 𝑇}

5.2

An Agent-based Negotiation Scheme for the

Distribu-tion of Electric Vehicles Across a Set of Charging

Sta-tions [3]

5.3

提案モデルと先行研究との違い

6

提案手法

6.1

社会的総余剰を最大化する割り当て

6.2

満足度を最大化する割り当て

6.3

社会的総余剰と満足度を最大化する割り当て

7

計算機実験

7.1

インスタンスの生成

7.2

実験環境

7.3

実験結果

8

考察

9

おわりに

謝辞

参考文献

森本智貴

目次