MARC

 008260203s2023        us                              c    eng  d
■001000017366037
■00520260209102932
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798291573983
■035    ▼a(MiAaPQ)AAI32272130
■035    ▼a(MiAaPQ)httphdlhandlenet2142122031
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a004
■1001  ▼aKulkarni,  Rucha.
■24510▼aFair  Division  of  Indivisibles  Through  the  Computational  Lens
■260    ▼a[Sl]▼bUniversity  of  Illinois  at  Urbana-Champaign▼c2023
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2023
■300    ▼a141  p
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  87-03,  Section:  B.
■500    ▼aAdvisor:  Mehta,  Ruta.
■5021  ▼aThesis  (Ph.D.)--University  of  Illinois  at  Urbana-Champaign,  2023.
■520    ▼aThis  thesis  studies  the  computational  problem  of  fairly  dividing  a  set  of  indivisible  and  non-shareable  items  among  n  agents  with  heterogeneous  preferences.  The  focus  of  this  work  is  on  three  fairness  notions  -  the  Nash  social  welfare  (NSW),  Maximin  share  (MMS),  and  relaxations  of  envy-freeness.  The  thesis  thus  has  three  natural  parts,  one  corresponding  to  each  of  these.  Extensive  work  on  these  notions  were  mainly  focused  on  allocating  goods,  i.e.,  positively  valued  items,  among  agents  with  additive  valuations.  Our  work  in  the  first  two  parts  extends  state-of-the-art  on  NSW  and  MMS  respectively  to  valuations  beyond  additive  and  to  bads,  i.e.,  negatively  valued  items.  The  third  part  models  a  real-world  setting  on  network  routing  as  a  fairness  problem,  defines  relaxations  of  envy-freeness  applicable  here  and  studies  their  computability.The  first  part  studies  the  problem  of  maximizing  Nash  welfare,  the  weighted  geometric  mean  of  agent's  utilities,  where  weights  are  agents'  entitlements.  This  notion  is  well-known  for  achieving  a  right  balance  between  fairness  and  efficiency.  Prior  work  had  mainly  focused  on  symmetric  weight  agents  with  additive  valuation  functions.  For  the  asymmetric  case,  a  trivial  O(m)  approximate  factor  algorithm  was  known,  where  m  is  the  number  of  goods  being  distributed.  We  initiate  the  study  of  the  case  where  the  agents  can  have  submodular  valuation  functions.  Along  with  submodular  valuations,  we  also  allow  the  agents  to  have  asymmetric  weights.  We  design  two  algorithms:  (i)  When  agents  have  additive  valuations  and  unequal  entitlements,  to  find  O(n)-approximate  NSW  allocation,  where  n  is  the  number  of  agents.  (ii)  When  agents  have  submodular  valuations  and  unequal  entitlements,  to  find  O(n  log(n))-approximate  NSW.  For  the  latter,  when  n  is  a  constant,  show  tight  lower-upper  bounds  of  (1  −  1/e)  ≈  1.5819-approximation,  and  thereby  resolving  this  case  completely.The  second  part  focuses  on  the  MMS  notion,  one  of  the  most  popular  share-based  notions.  Extensive  work  on  MMS  largely  focused  on  allocating  either  goods  or  bads,  but  not  both  together.  We  initiate  the  study  of  MMS  for  mixed-manna,  i.e.,  allocating  both  goods  and  bads  together,  under  additive  valuations.  We  first  show  non-existence  of  any  non-trival  approximation  in  general.  We  next  design  a  PTAS  to  find  an  α-MMS  allocation,  where  α  is  the  instance  specific  optimal  factor,  under  two  conditions:  (i)  constant  n,  and  (ii)  for  every  agent  i,  her  total  absolute  value  for  all  the  items  is  significantly  greater  than  the  minimum  of  her  total  value  for  goods  and  her  total  absolute  value  for  chores.  Both  of  these  conditions  are  unavoidable,  as  we  show  intractability  when  either  of  the  condition  is  dropped.  For  the  goods  allocation  case  when  the  agents  have  OXS  valuation  functions:  We  show  the  existence  of  a  1  3  (1  +  2/3  n−2/3  )-MMS  allocation  and  a  PTAS  for  the  same,  breaking  the  barrier  of  1/3-MMS  that  was  previously  known.  We  also  show  that  a  better  than  2/3-MMS  allocation  does  not  exist  for  all  instances  in  this  class.In  the  third  part  we  study  fairness  in  the  routing  problems.  also  known  as  congestion  games,  extending  the  classical  fairness  notion  of  envy  freeness  to  this  setting.  We  obtain  the  following  results.•  We  define  fairness  and  efficiency  notions  called  envy-free  ratio  and  rank  approximation  for  this  setting.  Informally,  a  path  has  rank  k  if  its  among  the  k  best  paths  computed  according  to  some  optimal  algorithm.•  When  the  cost  functions  are  linear,  we  present  4  approximately  fair  and  2  approximately  efficient  algorithm.•  For  the  more  general  setting  where  the  network  may  dynamically  change  over  time,  we  preassign  alternates,  that  is  a  set  of  paths  to  each  of  the  n  users.  We  show  an  algorithm  that  pre-assigns  O(log  n)  paths  such  that  the  assignment  is  2  approximately  fair,  and  each  user  will  be  able  to  pick  a  path  that  has  (1  +  2/e)cn  approximate  rank.
■590    ▼aSchool  code:  0090.
■650  4▼aComputer  science
■650  4▼aComputer  engineering
■650  4▼aComputational  physics
■653    ▼aFair  division
■653    ▼aIndivisible  items
■653    ▼aNash  welfare
■653    ▼aMaximin  share
■653    ▼aEnvy-freeness
■690    ▼a0984
■690    ▼a0464
■690    ▼a0216
■71020▼aUniversity  of  Illinois  at  Urbana-Champaign▼bComputer  Science.
■7730  ▼tDissertations  Abstracts  International▼g87-03B.
■790    ▼a0090
■791    ▼aPh.D.
■792    ▼a2023
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17366037▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.

Preview

Export

ChatGPT Discussion

AI Recommended Related Books