008131127s2009                                                eng  d
■001CHIMSIN00303349
■00520131127090623.5
■020    ▼a9781109666496
■040    ▼aUMI▼cUMI
■090    ▼aPh.D.
■1001  ▼aBalan,  Gabriel  Catalin.
■24510▼aComputational  issues  in  long-term  fairness  among  groups  of  agents▼h[e-book]
■260    ▼aFairfax▼bGeorge  Mason  University▼c2009.
■300    ▼a208  p.
■500    ▼aAdviser:  Sean  Luke.
■502    ▼aThesis  (Ph.D.)--George  Mason  University,  2009.
■520    ▼aFairness  within  groups  is  important  to  a  very  broad  range  of  problems,  from  policies  for  battery-operated  soccer  robots  to  distributed  traffic  control.  While  no  single  action  may  be  fair  to  everyone,  it  is  possible  to  achieve  long-term  optimal  fairness  for  everyone  through  choice  of  repeated  actions.  I  explore  the  issue  of  achieving  such  long-term  fairness  among  multiple  agents,  and  provide  a  unified  view  of  the  problem  and  solutions  to  it.  The  issue  of  constructing  long-term  fair  policies  among  multiple  agents  has  not  been  well  studied  in  the  literature.
■520    ▼aI  concentrate  on  the  “average  reward”  utility  model,  where  one’s  utility  is  defined  as  the  average  of  the  rewards  one  has  received  from  past  interactions.  Also,  I  focus  on  a  particular  definition  of  fairness,  called  “leximin”  fairness,  but  most  of  the  results  apply  to  other  measures  as  well.
■520    ▼aAfter  examination  of  fairness  through  an  infinite  series  of  repeated  actions,  I  extend  analysis  in  several  directions.  First,  I  consider  how  to  achieve  as  fair  a  result  as  possible  given  a  finite  series  of  actions,  where  the  length  of  the  series  is  not  precisely  known  beforehand  but  rather  is  chosen  from  an  unknown  or  stochastic  distribution  of  time  horizons.  My  solution  guarantees  the  beneficiaries  the  fairest  possible  long-term  results,  minus  a  bounded  worst-case  loss  due  to  the  game  ending  unexpectedly.  I  show  that  finding  sequences  of  actions  with  optimal  worst-case  loss  is  NP-hard,  and  I  propose  a  family  of  approximation  algorithms.
■520    ▼aSecond,  I  examine  stateful  domains,  where  one’s  choices  have  side-effects  that  influence  the  effects  of  actions  in  the  future.  I  introduce  a  multi-objective  genetic  algorithm  for  finding  good  tradeoff  points  between  beneficiaries  utilities  and  their  worst-case  losses.
■520    ▼aThird,  I  focus  on  decision-making  processes  which  have  been  decentralized  in  the  form  of  hierarchies.  I  propose  an  algorithm  based  on  my  stochastic  time-horizon  solution,  and  show  empirically  that  an  agent  hierarchy  running  that  algorithm  is  able  to  achieve  optimal  long-term  utilities.
■590    ▼aSchool  code:  0883.
■650  4▼aArtificial  Intelligence
■650  4▼aComputer  Science
■690    ▼a0800
■690    ▼a0984
■71020▼aGeorge  Mason  University.
■7730  ▼tDissertation  Abstracts  International▼g71-03B.
■790    ▼a0883
■79010▼aLuke,  Sean▼eadvisor
■791    ▼aPh.D.
■792    ▼a2009
■85640▼uKTLA/2013/3399161.pdf