MARC

 008260126s2025        us                              c    eng  d
■001000017358662
■00520260202104733
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798290648934
■035    ▼a(MiAaPQ)AAI32149625
■035    ▼a(MiAaPQ)Stanfordbq150gy8422
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a001
■1001  ▼aJiang,  Zhihao.
■24510▼aMulti-Selection  in  Voting  and  Recommendation:  Approximation  Algorithms  and  Convex  Programming
■260    ▼a[Sl]▼bStanford  University▼c2025
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2025
■300    ▼a133  p
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  87-03,  Section:  B.
■500    ▼aAdvisor:  Goel,  Ashish.
■5021  ▼aThesis  (Ph.D.)--Stanford  University,  2025.
■520    ▼aThis  thesis  investigates  algorithmic  frameworks  for  multi-selection-selecting  a  small  subset  of  alternatives  to  serve  a  population-across  applications  in  multi-winner  voting  and  differential  privacy.  The  first  two  chapters  focus  on  electing  representative  or  stable  committees  in  approval-based  multi-winner  voting,  while  the  third  leverages  multi-selection  to  improve  accuracy  under  input  perturbation  in  a  privacy-aware  environment.  All  three  contributions  build  on  convex  programming  techniques  to  find  principled,  tractable  solutions  to  these  selection  problems.In  the  first  part,  we  study  approximation  algorithms  for  optimizing  cost  and  welfare  objectives  under  justified  representation  (JR)  and  its  strengthened  variants  EJR+  and  BJR.  Prior  work  established  that  optimizing  over  JR  committees  is  NP-hard,  even  for  simple  objectives.  We  design  linear  programming  relaxations  that  capture  JR  constraints  via  carefully  constructed  variables,  and  develop  randomized  rounding  techniques  to  obtain  near-optimal  committees.  Specifically,  we  show  that  by  relaxing  JR  slightly,  allowing  an  approximate  form  of  proportionality,  we  can  achieve  an  O(log  n)  approximation  to  the  minimum  cost.  Our  methods  extend  naturally  to  stronger  notions  such  as  EJR+  and  BJR,  where  we  design  specialized  LP  formulations  that  maintain  proportionality  guarantees  under  fractional  voter-to-candidate  assignments.  These  results  match  hardness  lower  bounds  under  standard  complexity  assumptions.  Furthermore,  we  establish  that  under  natural  relaxations  of  committee  size,  simple  greedy  algorithms  achieve  nearly  optimal  welfare,  and  prove  tight  hardness  of  approximation  results  based  on  reductions  from  hypergraph  problems.  This  chapter  thus  provides  both  algorithmic  techniques  and  structural  insights  into  the  trade-off  between  fairness  and  quality  in  multi-selection  problems.In  the  second  part,  we  extend  the  notion  of  fairness  to  coalition  stability  by  studying  core  outcomes  in  approval-based  multi-selection.  We  introduce  the  concept  of  the  Nash  core,  where  voters  are  matched  to  candidates  with  proportional  payments,  and  committees  are  selected  to  maximize  a  candidate-weighted  Nash  social  welfare  objective.  We  first  show  that  in  the  fractional  setting,  there  always  exists  a  Nash-core  solution,  and  we  further  design  a  proportional  payment  rule  that  assigns  prices  to  candidates  based  on  their  approval  ballots,  ensuring  that  voters  fairly  contribute  to  committee  members  they  support.  Preliminary  results  for  the  discrete  setting  are  also  presented,  where  we  define  the  discrete  Nash  core  and  propose  heuristic  algorithms  for  finding  core-stable  committees  in  practice.  Empirical  experiments  on  real  voting  data  confirm  that  the  Nash  core  approach  leads  to  stable  outcomes.  By  combining  proportionality,  coalition  stability,  and  computational  tractability,  this  chapter  offers  new  directions  for  fair  group  decision  making  beyond  traditional  voting  rules.In  the  third  part,  we  incorporate  privacy  considerations  into  multi-selection  by  introducing  a  new  system  architecture  for  differentially  private  selection  with  multiple  responses.  Under  this  framework,  users  first  perturb  their  private  query  values  using  local  differential  privacy  mechanisms,  and  servers  respond  by  sending  back  a  small  set  of  candidate  results.  We  rigorously  characterize  the  optimal  mechanism  under  this  architecture  when  the  user  feature  space  is  one-dimensional  and  the  utility  loss  is  distance-based.  Remarkably,  we  prove  that  adding  Laplace  noise  to  the  user  query,  combined  with  a  carefully  optimized  selection  of  k  results  from  the  server,  minimizes  expected  disutility  under  privacy  constraints.  Our  proof  techniques  involve  developing  a  novel  duality  theory  for  differential-integral  linear  programs,  which  allows  us  to  analyze  infinite-dimensional  optimization  problems  with  both  derivative  and  integral  constraints.  This  duality  framework  may  be  of  independent  interest  beyond  privacy  applications.  Additionally,  we  show  that  the  user's  error  decreases  inversely  with  the  number  of  returned  results,  achieving  an  O(1/k)  trade-off  between  privacy  and  accuracy.  This  chapter  blends  ideas  from  differential  privacy  and  optimization  to  design  systems  that  respect  both  individual  privacy  and  social  utility.
■590    ▼aSchool  code:  0212.
■650  4▼aSoftware
■650  4▼aLinear  programming
■650  4▼aPrivacy
■650  4▼aVoters
■650  4▼aPublic  good
■650  4▼aPolitical  advertising
■650  4▼aElections
■653    ▼aJustified  representation
■653    ▼aVoting
■653    ▼aConvex  programming
■690    ▼a0796
■690    ▼a0454
■71020▼aStanford  University.
■7730  ▼tDissertations  Abstracts  International▼g87-03B.
■790    ▼a0212
■791    ▼aPh.D.
■792    ▼a2025
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17358662▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.

미리보기

내보내기

chatGPT토론

Ai 추천 관련 도서