1 


2 


3  from geniusweb.issuevalue.Bid import Bid


4  from geniusweb.issuevalue.Domain import Domain


5  from geniusweb.issuevalue.Value import Value


6  from geniusweb.profile.utilityspace.LinearAdditive import LinearAdditive


7  from tudelft.utilities.immutablelist.AbstractImmutableList import AbstractImmutableList


8  from tudelft.utilities.immutablelist.FixedList import FixedList


9  from tudelft.utilities.immutablelist.ImmutableList import ImmutableList


10  from tudelft.utilities.immutablelist.JoinedList import JoinedList


11  from tudelft.utilities.immutablelist.MapList import MapList


12  from tudelft.utilities.immutablelist.Tuple import Tuple


13  from typing import List, Dict


14  from geniusweb.bidspace.IssueInfo import IssueInfo


15  from geniusweb.bidspace.Interval import Interval


16  from geniusweb.utils import val


17  from decimal import Decimal


18 


19  class BidsWithUtility :


20  '''


21  WARNING DO NOT USE, NOT YET WORKING CORRECTLY


22 


23  Tool class containing functions dealing with utilities of all bids in a given


24  {@link LinearAdditive}. This class caches previously computed values to


25  accelerate the calls and subsequent calls. Reuse the object to keep/reuse


26  the cache.


27  <h2>Rounding</h2> Internally, utilities of bids are rounded to the given


28  precision. This may cause inclusion/exclusion of some bids in the results.


29  See {@link #BidsWithUtility(LinearAdditive, int)} for more details


30  Immutable.


31  '''


32 


33 


34  def __init__(self, issuesInfo:List[IssueInfo] , precision:int ) :


35  '''


36  @param issuesInfo List of the relevant issues (in order of relevance) and


37  all info of each issue.


38  @param precision the number of digits to use for computations. In


39  practice, 6 seems a good default value.


40  <p>


41  All utilities * weight are rounded to this number of


42  digits. This value should match the max number of


43  (digits used in the weight of an issue + number of


44  digits used in the issue utility). To determine the


45  optimal value, one may consider the step size of the


46  issues, and the range of interest. For instance if the


47  utility function has values 1/3 and 2/3, then these have


48  an 'infinite' number of relevant digits. But if the goal


49  is to search bids between utility 0.1 and 0.2, then


50  computing in 2 digits might already be sufficient.


51  <p>


52  This algorithm has memory and space complexity O(


53  nissues 10^precision ). For spaces up to 7 issues, 7


54  digits should be feasible; for 9 issues, 6 digits may be


55  the maximum.


56  '''


57  if issuesInfo == None or len(issuesInfo)==0:


58  raise ValueError("sortedissues list must contain at least 1 element")


59  self._issueInfo = issuesInfo;


60  self._precision = precision;


61  # cache. Key = call arguments for {@link #get(int, Interval)}. Value=return


62  # value of that call.


63 


64  self._cache:Dict[Tuple[int, Interval], ImmutableList[Bid]] = {}


65 


66  @staticmethod


67  def create(space:LinearAdditive, precision:int=6) > "BidsWithUtility":


68  '''


69  Support constructor, uses default precision 6. This value seems practical


70  for the common range of issues, utilities and weights. See


71  {@link #BidsWithUtility(LinearAdditive, int)} for more details on the


72  precision.


73 


74  @param space the {@link LinearAdditive} to analyze


75  @param space the {@link LinearAdditive} to analyze. Optional, defaults to 6


76  '''


77  return BidsWithUtility(BidsWithUtility._getInfo(space, precision), precision);


78 


79 


80  def getRange(self) >Interval :


81  '''


82  @return the (rounded) utility {@link Interval} of this space: minimum and


83  maximum achievable utility.


84  '''


85  return self._getRange(len(self._issueInfo)  1)


86 


87  def getBids(self, range: Interval) > ImmutableList[Bid] :


88  '''


89  @param range the minimum and maximum utility required of the bids. to be


90  included (both ends inclusive).


91  @return a list with bids that have a (rounded) utility inside range.


92  possibly empty.


93  '''


94  return self._get(len(self._issueInfo)  1, range.round(self._precision));


95 


96  def getInfo(self) > List[IssueInfo] :


97  return self._issueInfo.copy()


98 


99  def getExtremeBid(self, isMax:bool) >Bid :


100  '''


101  @param isMax the extreme bid required


102  @return the extreme bid, either the minimum if isMax=false or maximum if


103  isMax=true


104  '''


105  map:Dict[str, Value] = {}


106  for info in self._issueInfo:


107  map[info.getName()] = info.getExtreme(isMax)


108  return Bid(map)


109 


110  def _get(self, n:int , goal:Interval) > ImmutableList[Bid] :


111  '''


112  Create partial BidsWithUtil list considering only issues 0..n, with


113  utilities in given range.


114 


115  @param n the number of issueRanges to consider, we consider 0..n here.


116  The recursion decreases n until n=0


117  @param goal the minimum and maximum utility required of the bids. to be


118  included (both ends inclusive)


119  @return BidsWithUtil list, possibly empty.


120  '''


121  if goal == None:


122  raise ValueError("Interval=null")


123 


124  # clamp goal into what is reachable. Avoid caching empty


125  goal = goal.intersect(self._getRange(n))


126  if (goal.isEmpty()):


127  return FixedList([])


128 


129  cachetuple = Tuple(n, goal)


130  if (cachetuple in self._cache):


131  return self._cache[cachetuple]


132 


133  result = self._checkedGet(n, goal)


134  self._cache[cachetuple]=result


135  return result


136 


137  @staticmethod


138  def _getInfo(space2:LinearAdditive , precision:int) > List[IssueInfo] :


139  dom = space2.getDomain()


140  return [IssueInfo(issue, dom.getValues(issue), \


141  val(space2.getUtilities().get(issue)), \


142  space2.getWeight(issue), precision) \


143  for issue in dom.getIssues()]


144 


145 


146  def _checkedGet(self, n:int, goal:Interval ) > ImmutableList[Bid] :


147  info = self._issueInfo[n]


148  # issue is the first issuesWithRange.


149  issue = info.getName()


150 


151  if n == 0:


152  return OneIssueSubset(info, goal)


153 


154  # make new list, joining all sublists


155  fulllist:ImmutableList[Bid] = FixedList([])


156  for val in info.getValues():


157  weightedutil = info.getWeightedUtil(val)


158  subgoal = goal.subtract(weightedutil)


159  # recurse: get list of bids for the subspace


160  partialbids = self._get(n  1, subgoal)


161 


162  bid = Bid({issue: val})


163  fullbids = BidsWithUtility.maplist(bid, partialbids)


164  if fullbids.size() != 0:


165  fulllist = JoinedList[Bid]([fullbids, fulllist])


166  return fulllist


167 


168  @staticmethod


169  def maplist(bid: Bid, partialbids: ImmutableList[Bid]) > ImmutableList[Bid]:


170  '''


171  this is just to force a scope onto bid


172  '''


173  return MapList[Bid, Bid](lambda pbid: pbid.merge(bid), partialbids)


174 


175  def _getRange(self, n:int) >Interval :


176  '''


177  @param n the maximum issuevalue utility to include. Use n=index of last


178  issue s= (#issues in the domain  1) for the full range of this


179  domain.


180  @return Interval (min, max) of the total weighted utility Interval of


181  issues 0..n. All weighted utilities have been rounded to the set


182  {@link #precision}


183  '''


184  value = Interval(Decimal(0),Decimal(0))


185  for i in range(0,n+1): # include end point


186  value = value.add(self._issueInfo[i].getInterval())


187  return value


188 


189  class OneIssueSubset (AbstractImmutableList[Bid]):


190  '''


191  List of all oneissue bids that have utility inside given interval.


192  '''


193  def __init__(self, info:IssueInfo , interval:Interval ) :


194  '''


195  @param info the {@link IssueInfo}


196  @param interval a utility interval (weighted)


197  '''


198  self._info = info;


199  self._interval = interval;


200  self._size = info._subsetSize(interval)


201 


202  #Override


203  def get(self, index:int) >Bid :


204  return Bid({self._info.getName():


205  self._info._subset(self._interval)[index]})


206 


207  #Override


208  def size(self) >int:


209  return self._size

