MARC

 008250123s2024        us                              c    eng  d
■001000017162461
■00520250211152015
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798383194386
■035    ▼a(MiAaPQ)AAI31331685
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a621.3
■1001  ▼aKumar,  Rachitesh.
■24510▼aBudget  Management  in  Auctions:  Bidding  Algorithms  and  Equilibrium  Analysis
■260    ▼a[Sl]▼bColumbia  University▼c2024
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2024
■300    ▼a306  p
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  86-01,  Section:  A.
■500    ▼aAdvisor:  Balseiro,  Santiago;Kroer,  Christian.
■5021  ▼aThesis  (Ph.D.)--Columbia  University,  2024.
■520    ▼aAdvertising  is  the  economic  engine  of  the  internet.  It  allows  online  platforms  to  fund  services  that  are  free  at  the  point  of  use,  while  providing  businesses  the  opportunity  to  target  their  ads  at  relevant  users.  The  mechanism  of  choice  for  selling  these  advertising  opportunities  is  real-time  auctions:  whenever  a  user  visits  the  platform,  an  auction  is  run  among  interested  advertisers,  and  the  winner  gets  to  display  their  ad  to  the  user.  The  entire  process  runs  in  milliseconds  and  is  implemented  via  automated  algorithms  which  bid  on  behalf  of  the  advertisers  in  every  auction.  These  automated  bidders  take  as  input  the  high-level  objectives  of  the  advertiser  like  value-per-click  and  budget,  and  then  participate  in  the  auctions  with  the  goal  of  maximizing  the  utility  of  the  advertiser  subject  to  budget  constraints.  Thus  motivated,  this  thesis  develops  a  theory  of  bidding  in  auctions  under  budget  constraints,  with  the  goal  of  informing  the  design  of  automated  bidding  algorithms  and  analyzing  the  market-level  outcomes  that  emerge  from  their  simultaneous  use.First,  we  take  the  perspective  of  an  individual  advertiser  and  tackle  algorithm-design  questions.  How  should  one  bid  in  repeated  second-price  auctions  subject  to  a  global  budget  constraint?  What  is  the  optimal  way  to  incorporate  data  into  bidding  decisions?  Can  data  be  incorporated  in  a  way  that  is  robust  to  common  forms  of  variability  in  the  market?  As  we  analyze  these  questions,  we  go  beyond  the  problem  of  bidding  under  budget  constraints  and  develop  algorithms  for  more  general  online  resource  allocation  problems.  In  Chapter  2,  we  study  a  non-stationary  stochastic  model  of  sequential  auctions,  which  despite  immense  practical  importance  has  received  little  attention,  and  propose  a  natural  algorithm  for  it.  With  access  to  just  one  historical  sample  per  auction/distribution,  we  show  that  our  algorithm  attains  (nearly)  the  same  performance  as  that  possible  under  full  knowledge  of  the  distributions,  while  also  being  robust  to  distribution  shifts  which  typically  occur  between  the  sampling  and  true  distributions.  Chapter  3  investigates  the  impact  of  uncertainty  about  the  total  number  of  auctions  on  the  performance  of  bidding  algorithms.  We  prove  upper  bounds  on  the  best-possible  performance  that  can  be  achieved  in  the  face  of  such  uncertainty,  and  propose  an  algorithm  that  (nearly)  achieves  this  optimal  performance  guarantee.  We  also  provide  a  fast  method  for  incorporating  predictions  about  the  total  number  of  auctions  into  our  algorithm.  All  of  our  proposed  algorithms  implement  some  version  of  FTRL/Mirror-Descent  in  the  dual  space,  making  them  ideal  for  large-scale  low-latency  markets  like  online  advertising.Next,  we  look  at  the  market  as  a  whole  and  analyze  the  equilibria  which  emerge  from  the  simultaneous  use  of  automated  bidding  algorithms.  For  example,  we  address  questions  like:  Does  an  equilibrium  always  exist?  How  does  the  auction  format  (first-price  vs  second-price)  impact  the  structure  of  the  equilibria?  Do  automated  bidding  algorithms  always  efficiently  converge  to  some  equilibrium?  What  are  the  social  welfare  properties  of  these  equilibrium  outcomes?  We  systematically  examine  such  questions  using  a  variety  of  tools,  ranging  from  infinite-dimensional  fixed-point  arguments  for  proving  existence  of  structured  equilibria,  to  computational  complexity  results  about  finding  them.  In  Chapter  4,  we  start  by  establishing  the  existence  of  equilibria  based  on  pacing-a  practically-popular  and  theoretically-optimal  budget  management  strategy-for  all  standard  auctions,  including  first-price  and  second-price  auctions.  We  then  leverage  its  structure  to  establish  a  revenue  equivalence  result  and  bound  the  price  of  anarchy  of  liquid  welfare.  Chapter  5  looks  at  the  market  from  a  computational  lens  and  investigates  the  complexity  of  finding  pacing-based  equilibria.  We  show  that  the  problem  is  PPAD  complete,  which  in  turn  implies  the  impossibility  of  polynomial-time  convergence  of  any  pacing-based  automated  bidding  algorithms  (under  standard  complexity-theoretic  assumptions).  Finally,  in  Chapter  6,  we  move  beyond  pacing-based  strategies  and  investigate  throttling,  which  is  another  popular  method  for  managing  budgets  in  practice.  Here,  we  describe  a  simple  tatonnement-style  algorithm  which  efficiently  converges  to  an  equilibrium  in  first-price  auctions,  and  show  that  no  such  algorithm  exists  for  second-price  auctions  (under  standard  complexity-theoretic  assumptions).  Furthermore,  we  prove  tight  bounds  on  the  price  of  anarchy  for  liquid  welfare,  and  compare  platform  revenue  under  throttling  and  pacing.
■590    ▼aSchool  code:  0054.
■650  4▼aComputer  engineering
■650  4▼aWeb  studies
■653    ▼aAuctions
■653    ▼aBudget  management
■653    ▼aData-driven  algorithms
■653    ▼aOnline  resource  allocation
■653    ▼aEconomic  engine
■690    ▼a0796
■690    ▼a0464
■690    ▼a0646
■71020▼aColumbia  University▼bOperations  Research.
■7730  ▼tDissertations  Abstracts  International▼g86-01A.
■790    ▼a0054
■791    ▼aPh.D.
■792    ▼a2024
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17162461▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.

미리보기

내보내기

chatGPT토론

Ai 추천 관련 도서