MARC

 008260126s2024        us                              c    eng  d
■001000017358687
■00520260202104737
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798290649269
■035    ▼a(MiAaPQ)AAI32149666
■035    ▼a(MiAaPQ)Stanfordjb690vg6095
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a519.2
■1001  ▼aNuti,  Pranav.
■24510▼aSecretary  Problems,  Prophet  Inequalities,  and  Contention  Resolution  Schemes
■260    ▼a[Sl]▼bStanford  University▼c2024
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2024
■300    ▼a165  p
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  87-03,  Section:  B.
■500    ▼aAdvisor:  Vondrak,  Jan.
■5021  ▼aThesis  (Ph.D.)--Stanford  University,  2024.
■520    ▼aIn  this  thesis,  we  study  online  selection  problems,  focusing  on  variants  of  secretary  problems,  prophet  inequalities,  and  contention  resolution  schemes.In  chapter  2,  we  study  variants  of  the  secretary  problem  where  the  observations  Xj  are  draws  from  distributions  Dj,  and  we  wish  to  find  algorithms  which  maximize  the  probability  of  selecting  the  largest  draw.  In  case  we  have  access  to  the  distributions  and  the  draws  are  randomly  ordered,  we  give  an  optimal  algorithm  with  success  probability  0.5801,  matching  the  case  where  the  distributions  are  identical,  and  establishing  a  conjecture  of  Esfandiari  et  al.  We  then  study  variants  where  we  only  have  sample  access  to  the  distributions.  Our  main  results  in  the  context  are:  (i)  an  algorithm  with  success  probability  0.5009  in  the  single  sample  random  order  case  (nearly  matching  the  upper  bound  of  ≃  0.5024);  (ii)  an  optimal  algorithm  with  success  probability  0.25  in  the  single  sample  adversarial  order  case.In  chapter  3,  we  study  prophet  inequalities  with  cancellation  costs.  Most  of  the  literature  on  online  selection  problems  focuses  on  settings  with  irrevocable  decisions.  In  contrast,  we  consider  a  model  in  which  after  deciding  to  select  some  variable  Xj,  we  may  still  choose  to  discard  it  and  accept  another  variable  Xj  at  a  buyback  cost  of  f  X₁.  The  goal  is  to  maximize  the  expected  value  of  the  final  accepted  variable  minus  the  cost  of  discarding  all  the  other  accepted  variables.  Our  main  results  are:  (i)  in  case  f≥  1.  an  optimal  prophet  inequality  with  competitive  ratio  1+f/1+2f;  (ii)  in  case  f→  0.  an  asymptotically  optimal  prophet  inequality  with  competitive  ratio  1  −  Θ  (  f  log(  1/f  )  )  .In  chapter  4,  we  study  contention  resolution  schemes  (CRSs)  for  matchings  focusing  on  the  regime  with  vanishing  edge  probabilities.  Our  main  results  in  this  regime  are:  (i)  an  optimal  ≃  0.544-selectable  CRS  in  the  offline  case;  (ii)  a  conjecturally  optimal  ≃  0.382-selectable  OCRS  in  the  adversarial  order  case,  along  with  an  upper  bound  of  0.390  on  the  selectability;  (iii)  an  optimal  0.5-selectable  RCRS  in  the  random  order  case;  and  (iv)  a  ≃0.510-selectable  CRS  in  the  free  order  case.  In  the  non-vanishing  regime,  we  construct  a  0.509-selectable  contention  resolution  scheme  for  bipartite  matchings,  establishing  for  the  first  time,  a  separation  between  offline  and  random  order  online  contention  resolution  schemes.
■590    ▼aSchool  code:  0212.
■650  4▼aProbability
■650  4▼aLinear  programming
■650  4▼aSuccess
■650  4▼aBids
■650  4▼aDecision  making
■650  4▼aApplied  mathematics
■653    ▼aSecretary  problems
■690    ▼a0364
■71020▼aStanford  University.
■7730  ▼tDissertations  Abstracts  International▼g87-03B.
■790    ▼a0212
■791    ▼aPh.D.
■792    ▼a2024
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17358687▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.

Preview

Export

ChatGPT Discussion

AI Recommended Related Books