MARC

 008260126s2025        us                              c    eng  d
■001000017360056
■00520260202105257
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798297993853
■035    ▼a(MiAaPQ)AAI32279375
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a519
■1001  ▼aVuorinen,  Aapeli.
■24510▼aTradeoffs  Between  Information,  Tractability,  and  Fairness  in  Large  Matching  Markets
■260    ▼a[Sl]▼bColumbia  University▼c2025
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2025
■300    ▼a202  p
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  87-05,  Section:  B.
■500    ▼aAdvisor:  Faenza,  Yuri.
■5021  ▼aThesis  (Ph.D.)--Columbia  University,  2025.
■520    ▼aMatching  theory  is  one  of  the  cornerstones  of  modern  algorithmic  market  design,  and  is  therefore  heavily  studied  by  communities  in  operations  research,  economics,  and  theoretical  computer  science.  Such  models  arise  whenever  a  central  planner  is  tasked  with  pairing  together  agents  of  two  distinct  types  but  cannot  use  money  to  clear  the  market;  and  where  each  agent  has  idiosyncratic  preferences  over  the  agents  of  the  other  type.  Natural  applications  of  matching  markets  are  found  in  the  allocation  of  indivisible  goods  such  as  school  assignment,  medical  residency  matching,  and  the  allocation  of  government  subsidized  housing.Matching  theory  and  in  particular  stable  matching  has  seen  significant  research  effort  since  seminal  work  by  Gale  and  Shapley  algorithmically  established  the  existence  of  a  condition  called  stability,  which  guarantees  that  a  matching  can  be  found  with  the  property  that  no  participant  is  incentivized  to  deviate  from  it.  Many  centralized  mechanisms  for  two-sided  matching  markets  have  since  been  shown  to  enjoy  strong  theoretical  properties,  which  ipso  facto,  justifies  their  use  in  the  real  world.However,  due  to  practical  constraints-commonly  due  to  the  size  and  complexity  of  the  market  at  hand-real  world  applications  often  resort  to  simplified  models  that  do  not  faithfully  capture  reality.  These  simplifications  lead  to  the  central  planner  operating  without  perfect  information  about  the  participants  or  their  preferences.In  this  thesis,  we  present  three  interconnected  branches  of  research  exploring  tradeoffs  between  information,  tractability,  and  fairness  in  large  matching  markets.  We  investigate  how  various  limitations  on  information  acquisition  and  exchange  affect  the  mechanisms,  outcomes,  and  fairness  of  matching  markets.We  are  motivated  by  the  matching  mechanism  that  assigns  students  to  public  schools  in  New  York  City.  The  unified  school  district-which  encompasses  all  five  boroughs-  has  since  2003  employed  the  theory  of  stable  matching  to  perform  this  assignment,  with  students  as  one  side  of  the  market  and  schools  as  the  other.  Consisting  of  over  1.1  million  students,  the  size  and  diversity  of  the  market  presents  a  massively  interesting  real-world  object  of  study.In  the  first  chapter,  we  investigate  a  model  where  students  are  restricted  in  the  length  of  preference  lists  that  they  may  submit  to  the  market  operator.  In  particular,  we  study  such  random  instances  of  the  Serial  Dictatorship  mechanism  where  students  choose  \uD835\uDC51  schools  uniformly  at  random  from  \uD835\uDC5B  schools  as  their  preference  list,  and  each  school  has  exactly  one  seat.  Our  main  result  is  that  if  the  students  primarily  care  about  being  matched  to  any  school  of  their  list  (as  opposed  to  ending  up  unmatched),  then  all  students  in  position  \uD835\uDC56  ≤  \uD835\uDC5B  will  prefer  markets  with  longer  lists  when  \uD835\uDC5B  is  large  enough,  whereas  students  after  some  cutoff  \uD835\uDC50    \uD835\uDC5B  (that  quickly  approaches  \uD835\uDC5B  as  the  list  length  grows)  prefer  markets  with  shorter  lists.  This  suggests  that  markets  that  are  well-approximated  by  our  hypothesis  and  where  the  demand  of  schools  does  not  exceed  supply,  should  be  designed  with  preference  lists  as  long  as  reasonable.In  the  second  chapter,  we  study  the  impact  of  systemic  bias  in  school  matching  by  investigating  the  admissions  process  to  the  eight  elite  public  schools  (called  the  Specialized  High  Schools)  in  New  York  City.  These  schools  admit  students  solely  based  on  their  score  on  a  standardized  test,  but  we  observe  a  clear  distributional  shift  in  the  test  scores  of  disadvantaged  students  (as  defined  by  the  city).  To  study  this  shift,  we  present  a  stylized  model  where  all  students  have  a  true  potential  (representing  their  innate  ability)  sampled  independently  from  the  same  distribution.  While  non-disadvantaged  students  always  perform  at  their  true  potential,  disadvantaged  students  appear  at  a  perceived  potential  strictly  below  their  innate  ability  due  to  some  systemic  bias.  We  investigate  both  theoretically  and  empirically  the  impact  of  such  bias  on  the  admissions  process,  then  turn  to  studying  interventions  to  counter  it.  These  interventions  are  in  the  form  of  vouchers  targeted  at  certain  disadvantaged  students,  which  we  assume  give  that  student  the  resources  they  need  to  perform  at  their  true  potential.  We  measure  aggregate  mistreatment  under  various  metrics,  first  investigating  optimal  deterministic  voucher  distribution,  and  then  turning  to  randomized  voucher  distribution.  We  additionally  present  extensive  numerical  experiments  both  on  a  real  dataset  from  New  York,  as  well  as  on  simulated  data.  We  then  confirm  that  our  results  hold  under  various  relaxations  to  our  stylized  model,  including  moderate  levels  of  model  misspecification.  Our  key  takeaway  is  that  resources  should  be  targeted  at  slightly  above  average  performers  instead  of  the  absolute  top  performers.In  the  third  chapter,  we  take  the  schools'  side.  Currently  the  city  allows  schools  to  only  specify  their  preferences  using  a  strict  preference  list  over  students.  While  this  leads  to  a  simple  algorithm,  stable  matching  models  may  be  extended  to  allow  schools  to  communicate  much  more  rich  preference  via  choice  functions.  We  discuss  the  impact  of  using  general  choice  functions  in  the  offline  model  of  stable  matching,  establishing  that  general  path-independent  and  quota-filling  choice  functions  are  too  large  a  class  to  be  used  in  this  setting.  We  propose  the  class  of  Kuhn  choice  functions,  that  arise  as  maximum-weight  matchings  in  an  auxiliary  bipartite  graph,  as  a  tractable  yet  rich  subclass.  We  show  that  such  choice  functions  are  amenable  to  use  in  the  offline  model  and  possess  many  desirable  properties.  We  further  discuss  the  hierarchy  of  choice  and  approximability  of  various  classes  of  choice  functions.  Theoretical  proofs  are  complemented  by  computational  results  and  a  discussion  on  various  practical  aspects  of  using  choice  functions  in  stable  matching.
■590    ▼aSchool  code:  0054.
■650  4▼aApplied  mathematics
■653    ▼aDifferential  equations
■653    ▼aFunctional  limit  theorems
■653    ▼aMatching  theory
■653    ▼aStable  matching
■653    ▼aStochastic  processes
■690    ▼a0796
■690    ▼a0364
■690    ▼a0501
■71020▼aColumbia  University▼bOperations  Research.
■7730  ▼tDissertations  Abstracts  International▼g87-05B.
■790    ▼a0054
■791    ▼aPh.D.
■792    ▼a2025
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17360056▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.

미리보기

내보내기

chatGPT토론

Ai 추천 관련 도서