Upgrade to Pro — share decks privately, control downloads, hide ads and more …

論文紹介 Budget Management Strategies in Repeated A...

論文紹介 Budget Management Strategies in Repeated Auctions (公開版)

社内論文読み会の発表資料

Balseiro, Santiago, et al. "Budget Management Strategies in Repeated Auctions."
Proceedings of the 26th International Conference on World Wide Web. 2017.
https://dl.acm.org/doi/abs/10.1145/3038912.3052682

Takashi Nishibayashi

July 20, 2021
Tweet

More Decks by Takashi Nishibayashi

Other Decks in Science

Transcript

  1. ࿦จ঺հ Budget Management Strategies in Repeated Auctions Balseiro, Santiago, et

    al. "Budget Management Strategies in Repeated Auctions." Proceedings of the 26th International Conference on World Wide Web. 2017. https://dl.acm.org/doi/abs/10.1145/3038912.3052682 %4࿦จಡΈձ! ੢ྛ޹ 5BLBTIJ/JTIJCBZBTIJIBHJOP 1
  2. ֓ཁ w 888࠾୒ w Πϯλʔωοτ޿ࠂͷ܁Γฦ͠ΦʔΫγϣϯʹ͓͚Δ༧ࢉ؅ཧઓུʹ͍ͭͯ w ഑৴ϓϥοτϑΥʔϜ͕༧ࢉ؅ཧઓུΛఏڙ͢Δͱ͖ʹ w ͭͷઓུʹγεςϜۉߧͷଘࡏΛূ໌ w

    ͜ΕΒͷઓུ͕ചΓखͷརӹͱങ͍खͷޮ༻ͷτϨʔυΦϑʹͲΜͳӨڹ ͕͋Δͷ͔Λ໌Β͔ʹͨ͠ w ࣮ݧ w ϦεςΟϯά޿ࠂͷΦʔΫγϣϯͷ࣮σʔλͰ࣮ূΛߦͳͬͨ
  3. ิ଍ͳͥۉߧͷ෼ੳΛ͢Δͷ͔ w ܦࡁֶͰ͸ࢢ৔ͷΞ΢τϓοτ͸ࢢ৔ͷϧʔϧɾϝΧχζϜʹΑͬͯมΘΔࣄ ͕஌ΒΕ͍ͯΔ w ചΓखͷརӹɺങ͍खͷޮ༻ɺ8FMGBSFʜ w ϓϨΠϠʔ͸ࣗ༝ʹ߹ཧతͳߦಈ͕ͱΕΔ͕ɺ৚͕݅ἧ͑͹ۉߧঢ়ଶʹ޲͏ w ۉߧ͸ϝΧχζϜ͕΋ͨΒ͢ӨڹΛಛ௃͚ͮͨ΋ͷͱ͍͑Δ

    w ۉߧΛൺֱ͢ΔࣄͰ༷ʑͳ؍఺ʹ͓͍ͯϝΧχζϜͷ༏ྼ͕Θ͔Δ w ചΓख͕ಘ͔ങ͍ख͕ಘ͔ɺޮ཰ੑɺެฏੑɺӕΛ͍ͭͨํ͕ಘ͔ͳͲ w ϝΧχζϜͷྫΦʔΫγϣϯํࣜ w ࢢ৔͸݁ࠗࢢ৔΍ब৬ࢢ৔ͱ͍ͬͨՁ֨Λ͚ͭͳ͍औҾࢢ৔΋ؚΉ
  4. ޿ࠂϓϥοτϑΥʔϜ͕޿ࠂओʹఏڙ͢Δ ༧ࢉ؅ཧػೳ w ೔༧ࢉΛઃఆ͓͚ͯ͠͹ͦΕҎ্࢖Θͳ͍ w ํࡦͷྫ w  ࢖͍Ռͨͨ͠ΒࢭΊΔ͚ͩ w

     ֬཰తʹεϩοτϦϯάͯ͠೔͔͚ͯ࢖͏ w  ΦʔΫγϣϯೖࡳֹۚΛԼ͛Δ উ཰ΛԼ͛Δ  w ͜ΕΒ͸ϓϥοτϑΥʔϜ͓Αͼ޿ࠂओʹҟͳΔ݁ՌΛಋ͘ w طଘݚڀ͸༧ࢉ؅ཧͷ֬཰త࠷దԽͷςΫχοΫ΍ͦͷઃఆʹ͓͚ ΔήʔϜཧ࿦తͳۉߧͷ෼ੳͩͬͨ
  5. ܁Γฦ͠ΦʔΫγϣϯઃఆ w ਓͷങ͍ख w ചΓख͸ ճɺػձίετ ͰࡒΛചΔ w ങ͍ख ͸༧ࢉ

    Λͭ w ങ͍ख ͷධՁֹ ͷ୆͸ ͱ͠ɺධՁֹ͸֬཰ີ౓෼෍ ͔ΒಠཱʹҾ͘ɻ ͜ͷ෼෍ͷྦྷੵؔ਺Λ ɺ ͱ͢Δɻ w ͷԾఆʹ͍͔ͭ͘ͷ৚݅Λ͓͘ SFHVMBS  w WJSUVBMWBMVFGVODUJPO ͕୯ௐ૿Ճ w ചΓखʹͱͬͯͷ࠷ద஋ Λղ͘ͱ͖ʹͰͯ͘Δ n T c > 0 i Bi i x χi fi Fi ¯ Fi (x) := 1 − Fi (x) fi ψi (x) := x − ¯ Fi (x) f(x) p = argmaxv v ⋅ (1 − F(v))
  6. ༧ࢉ؅ཧϝΧχζϜͷఆࣜԽ w ങ͍खͷධՁֹۭؒ  w ങ͍ख ͷϓϥοτϑΥʔϜύϥϝʔλ  w Λύϥϝʔλۭؒ

    w ༧ࢉ؅ཧϝΧχζϜ͸ׂΓ౰ͯϧʔϧ ͱ੥ٻϧʔϧ ͰදΘ͢ w  ͸֤ങ͍ख΁ͷׂΓ౰ͯ֬཰  w  w ͷݩͰͷങ͍ख ͷظ଴ࢧग़  w ͷݩͰͷങ͍ख ͷ֫ಘՁ஋ χ = χ1 × χ2 × ⋯ × χn i 𝒮i ∈ [s i , ¯ si ] 𝒮 = 𝒮1 × 𝒮2 × ⋯ × 𝒮n Q M Q : χ × 𝒮 → Δn Δn M : χ × 𝒮 → ℝn s i Gi (s) = T𝔼x [Mi (x; s)] s i Vi (s) = T𝔼x [xi Qi (x; s)]
  7. γεςϜۉߧ w ങ͍खશһͷϓϥοτϑΥʔϜύϥϝʔλͷ૊߹ͤ w  w ֤ങ͍खͷύϥϝʔλ ͸ങ͍खͷظ଴ޮ༻ Λ࠷େʹͭͭ͠ɺظ ଴ࢧग़ΛͦΕҎ্૿΍ͤͳ͍஋

    w γεςϜۉߧʹ͓͚Δརӹͱޮ༻ͷൺֱͷҙٛ w ͋Δ༧ࢉ؅ཧϝΧχζϜͷݩͰɺങ͍ख͕ͦΕͧΕ࠷΋߹ཧతͳߦಈΛऔͬͨ ͱ͖ͷചΓखͷརӹɾങ͍खͷޮ༻ΛϝΧχζϜؒͰൺֱ͢Δ͜ͱʹ૬౰͢Δ s* = (s* i )n i=1 ∈ 𝒮 s Vi (s) − Gi (s)
  8. ݕ౼͢Δ༧ࢉ؅ཧϝΧχζϜ ࠷௿མࡳՁ֨༗ΓηΧϯυϓϥΠεΦʔΫγϣϯΛগ͠վม͢Δɻ ϓϥοτϑΥʔϜ͸ങ͍खຖͷ༧ࢉ؅ཧϝΧχζϜͷύϥϝʔλTΛܾΊΔɻT͕େ͖͍ͱࢧग़͕ݮΔɻ #JE4IBEJOH 4 ೖࡳֹۚΛׂΓҾ͘ɻׂΓҾֹ͍ͨۚͰΦʔΫγϣϯΛߦͳ͏ɻ ങ͍खຖʹׂΓҾ͘౓߹͍Λઃఆ͢Δ .VMUJQMJDBUJWF#PPTUJOH .# উར৚݅ʹೋҐՁ֨ͱͷՁ֨ࠩΛ෇༩͢Δ

    ങ͍खຖʹՁ֨ࠩͷେ͖͞Λઃఆ͢Δ 3FTFSWF1SJDJOH 3 ങ͍खຖʹϑϩΞϓϥΠεΛઃఆ͢Δ 5ISFTIPMEJOH 5 ങ͍खຖʹΦʔΫγϣϯࢀՃᮢ஋ͱͳΔධՁֹΛઃఆ͢Δ 5ISPUUMJOH 50 ങ͍खຖʹΦʔΫγϣϯࢀՃ֬཰Λઃఆ͢Δ 1SPpU0QUJNBM 10 རӹ࠷େԽ ϕϯνϚʔΫ 6UJMJUZ0QUJNBM 60 ޿ࠂओޮ༻࠷େԽ ϕϯνϚʔΫ
  9. γεςϜۉߧ͕ଘࡏ͢Δ͜ͱͷূ໌ w ങ͍खͷධՁ͕ങ͍खຖʹҟͳΔઃఆ BTZNNFUSJDTFUUJOH  w l#JETIBEJOH 4 NVMUJQMJDBUJWFCPPTUJOH .#

    UISFTIPMEJOH 5 BOEUISPUUMJOH 50 BENJUBTZTUFNFRVJMJCSJVNz w 3FTFSWFQSJDJOH 3 BENJUTBTZTUFNFRVJMJCSJVNXIFOUIF SBOHFTPGSFTFSWFQSJDFTBSFTVJUBCMZSFTUSJDUFE BOECJE EJTUSJCVUJPOTIBWFTUSJDUMZJODSFBTJOH('3Tz w 3 ʹ͍ͭͯ͸3FTFSWFQSJDFͱධՁֹͷ෼෍ʹ੍໿͕͋Δ w ূ໌͸ϑϧόʔδϣϯ<>Λࢀর <>#BMTFJSP 43 ",JN ..BIEJBO BOE7.JSSPLOJ#VEHFUNBOBHFNFOUTUSBUFHJFTJO SFQFBUFEBVDUJPOT  0DUPCFS "WBJMBCMFBU443/IUUQTTTSODPN BCTUSBDU
  10. ิ଍ࢧ഑ؔ܎ %PNJOBODF3FMBUJPOT w ઓུͷൺֱؔ܎ w ͋Δઓུ"͕૬खͷઓུʹ͔͔ΘΒͣઓུ#ΑΓ΋େ͖ͳརಘΛ΋ͨΒ ͢৔߹ɺઓུ#͸ઓུ"ʹࢧ഑͞Ε͍ͯΔͱ͍͏ w नਓͷδϨϯϚͷྫ w

    φογϡۉߧ w ࣗനઓུ͕໧ൿઓུΛࢧ഑͍ͯ͠Δˠ߹ཧతͳनਓ͸ࣗന͢Δ w ৗʹ"Λ΍͓͚ͬͯ͹͍͍ͳΒ"͕ࢧ഑ઓུ w ηΧϯυϓϥΠεΦʔΫγϣϯͰ͸ධՁֹͰೖࡳ͢Δͷ͕ऑࢧ഑ઓུ
  11. ઓུಉ࢜ͷൺֱ w ࢧ഑ؔ܎ͷهड़ʹ ͱʚΛ࢖͍ͬͯ͘Α w ༧ࢉ؅ཧϝΧχζϜ ͕ Λࢧ഑͢Δͱ͖ɺ  ͸

    ͷγεςϜۉߧΑΓ΋େ͖ͳ໨తՁ஋Λಋ͘ w ͜ΕΛ  w ඇࢧ഑ؔ܎ʹ͋Δ৔߹͸ʚ w ൺֱΛਤࣔͰ͖ΔΑ͏ʹੑೳۂઢΛಋೖ͢Δˠ w ͷੑೳۂઢ͕ৗʹ ͷ্ʹ͋ΔͳΒ  w ަࠩ͢Δ৔߹͸ઃఆʹΑͬͯ༏ྼؔ܎͕มΘΔͷͰ  ≥ (Qπ, Mπ) (Qπ′ , Mπ′ ) (Qπ, Mπ) (Qπ′ , Mπ′ ) π ≥ π′ π π′ π ≥ π′ π||π′
  12. ചΓखͷརӹ؍఺Ͱͷൺֱ w ఆཧ w 1SPpU0QUJNBM3FTFSWF1SJDJOH≥5ISFTIPMEJOH≥ 5ISPUUMJOH≥*'#JE4IBEJOH≥6UJMJUZ0QUJNBM w 3FTFSWF1SJDJOH≥6.VMUJ#PPTUJOH≥6#JE4IBEJOH w .VMU#PPTUJOHcc5ISFTIPMEJOH.VMUJ#PPTUJOHcc

    5ISPUUMJOH w ചΓख͸*NQຖʹػձίετΛ࣋ͭͷͰগͳ͍ൢച਺ͰചΓखͷ ༧ࢉΛ࢖͍Ռ͢ํ͕རӹ͕େ͖͘ͳΔ w *NQͷࢧ෷ֹ͍ۚΛߴ͘Ͱ͖Δ3FTFSWF1SJDJOH͕ޮՌత
  13. ചΓखͷརӹ؍఺Ͱͷൺֱ ଓ͖ w ൢച*NQ਺Λ ͱ͢ΔͱചΓखͷརӹ ͸ ͳͷͰফԽֹۚͱ*NQ਺ ͕ಉ͡Ͱ͋Ε͹Ͳͷઓུ΋ಉ݁͡Ռʹͳ Δ w

    આ໌͸ແ͍͚Ͳ6UJMJUZ0QUJNBM͸ೖࡳஊ ߹ঢ়ଶʹͳ͍ͬͯΔɻશһ͕ݩͷ 3FTFSWF1SJDF ͜ͷ࿦จͰ͸ػձί ετ ΪϦΪϦͰೖࡳ͢ΔͱചΓखͷར ӹ͸ͳ͘ͳΔ I P = nG − cI
  14. ങ͍खͷޮ༻؍఺Ͱͷൺֱ w ޮ༻  w ఆཧ w 6UJMJUZ0QUJNBM≥#JE4IBEJOH≥5ISFTIPMEJOH≥3FTFSWF1SJDJOH 1SPpU0QUJNBM w

    #JE4IBEJOH≥6.VMUJ#PPTUJOH≥63FTFSWF1SJDJOH w 5ISPUUMJOHcc5ISFTIPMEJOH5ISPUUMJOHcc.VMU#PPTUJOH w ചΓखͷརӹͷ؍఺͔ΒΈͨ༏Ґੑͱٯస͍ͯ͠ΔɻചΓखͷརӹ͸ങ͍ खͷޮ༻Λ٘ਜ਼ʹ͢Δ͔Βࣗવɻ w #JE4IBEJOH͸5ISFTIPMEJOHΑΓ΋ߴ͍ޮ༻Λ΋ͨΒ͢͜ͱ͔Β*NQͷ ਺͕ଟ͍ͱޮ༻͸্͕Δ U = nV − nG
  15. ݁Ռ w 'JHVSFʹࣔ݁͢Ռ͸ཧ࿦తʹূ໌ͨ݁͠Ռͱ౳͘͠ͳͬͨ w ചΓखࢹ఺ w 3FTFSWF1SJDF͕࠷ྑ #JE4IBEJOH͕࠷ѱ w ങ͍खࢹ఺

    w #JE4IBEJOH͕࠷ྑ 3FTFSWF1SJDF͕࠷ѱ w 8FMGBSFࢹ఺ w #JE4IBEJOH͕࠷ྑ 3FTFSWF1SJDF͕࠷ѱ