The Dating Game / Secretary Problem

Question

The bots are looking for love. Can you help them?

The rules

The goal of this game is find the bot you have the highest compatibility with. However, robots, who are inexperienced at dating are unable to tell how well a date went.

In the game, bots take turns "speed dating" some other bot. After each date, each bot chooses whether to get married or to continue dating. If both bots agree to get married both are removed from the dating pool and their compatibility rank (100% is if you found the best one, 0% for the worst one) is their final score.

Bots won't be able to tell what the compatibility is, but they can compare dates. For example if bot A went on a date with bot B and C, they'll be able to tell if B or C was more compatible but not by how much.

Bot A's compatibility with B does not equal B's compatibility with A, but they are correlated.

If every bot has dated every other bot, the ordering is shuffled and any remaining bots can try again. However, everyone's final score is reduced by 25% (exponential) for every round they stay single. If a entire round ends without any new marriages the game ends and all remaining bots get a score of 0.

Example bot

class BetterThanFirst:
    """
    This bot will use its first date as a reference, then marry any bot that's better than it
    """

    def __init__(self, nrof_bots, rng): # rng is a seeded PRNG you can use, no other forms of randomness allowed
        # nrof_bots is the total number of bots playing
        self.first_date = None

    def round_finished(self, nrof_remaining_bots): # the number of bots still in the game
        pass # called if a full round finished, optional

    def date(self, other) -> bool: # Return True if you want to marry this bot, False otherwise
        if self.first_date is None:
            self.first_date = other
        else:
            return other > self.first_date

Other rules

• No IO
• No RNG except via the provided PRNG
• No inspecting other bots. You are only allowed to use the >, <, <=, >=, == operators on other bots.
• No exploiting the controller.

Controller

The controller repo is here: https://codeberg.org/Mousetail/KOTH-dating-game

Results, and the active game (if any) can be viewed here: https://koth.mousetail.nl/

Answer 1

Optimal Average

class OptimalAverage:
    def __init__(self, nrof_bots, rng):
        self.test_num = round((nrof_bots - 1)**0.5)
        self.tests = []

    def round_finished(self, nrof_remaining_bots):
        self.test_num = round((nrof_remaining_bots - 1)**0.5)
        self.tests = []

    def date(self, other) -> bool:
        if len(self.tests) < self.test_num:
            self.tests.append(other)
            return False
        else:
            return all(f <= other for f in self.tests)

Similar to @Spitemaster's answer but we skip the first \$\sqrt{n}\$ bots instead. While their strategy has been proven optimal for maximizing one's chance at getting the best candidate, this strategy is optimal for obtaining the best average score assuming that there is value in candidates that are not the best, which is the case here. Of course this still misses the same important notes; that the opposing bot won't always agree, and that bots will be dropping out as it goes along.

Answer 2

Optimal Stopping Time

class OptimalStoppingTime:
    def __init__(self, nrof_bots, rng):
        import math
        self.dates_left = math.ceil((nrof_bots - 1)/ 2.718)
        self.dates = []

    def round_finished(self, nrof_remaining_bots):
        pass

    def date(self, other) -> bool: # Return True if you want to marry this bot, False otherwise
        if self.dates_left > 0:
            self.dates_left -= 1
            self.dates += [other]
        else:
            return all(other >= x for x in self.dates)

The optimal stopping time for the secretary problem is to skip the first n/e and then accept any better than the best seen so far. There may be a better strategy because it's not symmetric and other bots may not agree - and it doesn't account for bots dropping out.

Answer 3

Always Accepts

class EveryoneIsFine:
    """This bot just accepts everyone"""
    def __init__(self, nrof_bots, rng):
        self.botmotto="Accept everyone."
    def round_finished(self, nrof_remaining_bots):
        pass
    def date(self, other) -> bool:
        return True

This bot just doesn't care who they're married to.

Answer 4

Naive Elitist

class NaiveElitist:
    def __init__(self, nrof_bots, rng):
        self.best = None
    
    def round_finished(self, nrof_remaining_bots):
        pass
    
    def date(self, other) -> bool:
        if self.best is None or other >= self.best:
            self.best = other
        return other >= self.best

This bot will settle for nothing less than the best!

...But it can't imagine that anything better than what it's already found could be possible, even if it's only experienced a single date.

Answer 5

Crossing out options

class crossing_out_options:
    """accepts any bot at least as good as the best remaining bot which it hasn't accepted yet"""
    def __init__(self, nrof_bots, rng):
        self.candidates = []
        self.rejected_me = []
        self.pool = []
        self.first_date = True
    def round_finished(self, nrof_remaining_bots):
        self.candidates = [x for x in self.candidates if x in self.pool]
        self.pool = []
    def date(self, other) -> bool:
        self.pool += [other]
        if self.first_date:
            self.candidates = [other]
            self.first_date = False
            return False
        if other in self.rejected_me:
            return True  # no shame
        if all(other >= x for x in self.candidates):
            self.candidates = [x for x in self.candidates if x != other]
            self.rejected_me += [other]
            return True
        if not other in self.candidates:
            self.candidates += [other]
        return False

This bot keeps a list of all the "candidate" bots it has dated but not accepted, and which ones it tried to accept. It accepts the best bot from the candidate list. (Or any better bot, even if they rejected it before! No grudges!). At the end of the round it removes bots from the candidate list if it didn't encounter them this round.

The result is that it accepts any bot that "better than first" would accept, but learns and moves on if its best matches are already taken or don't love it back.

Answer 6

C+ dater

class c_plus_dater:
    def __init__(self, nrof_bots, rng): # rng is a seeded PRNG you can use, no other forms of randomness allowed
        # nrof_bots is the total number of bots playing
        self.round = 0
        self.betterbots = 0
        self.bestbot = None

    def round_finished(self, nrof_remaining_bots): # the number of bots still in the game
        self.round += 1

    def date(self, other) -> bool: # Return True if you want to marry this bot, False otherwise
        marry = False
        if self.bestbot is None:
            self.bestbot = other
        else:
            if other > self.bestbot:
                self.betterbots += 1
                self.bestbot = other
                if self.betterbots >= 3:
                     marry = True
        return marry

Edited to avoid comparing a bot to a constant, instead only to each other. This bot takes any bot that is better than at least 3 other bots. But it probably gets buggy in the second round.

Old version: Bot takes anything above 70% in the first round, and lowers its standard each round after that.

[I'm counting on compatibility being between 0 and 1]

Answer 7

Logger

class Logger:
 """Logs how everyone was on the first round (rejecting all) and uses that to determine the best bot."""
 def __init__(self, nrof_bots, rng):
  self.botlist=[]
  self.counter=0
  self.bots=nrof_bots
 def round_finished(self, nrof_remaining_bots):
  self.counter=self.counter+1
  if nrof_remaining_bots!=self.bots:
   self.counter=0
   self.bots=nrof_remaining_bots
 def date(self, other):
  if self.counter==0:
   self.botlist.append(other)
   return False
  else:
   return other==max(self.botlist)

This bot gets the best bot by logging each bot and picking the one with the best compatibility. If the bot with the best compatibility marries a bot other than the Logger, the Logger is screwed the logger only notices at the end of the round and re-evaluates each bot.

Answer 8

The Hopeless Romantic

This hopelessy romantic bot falls in love with the first robot it ever sees, and will pursue its subject of aspirations til the end of times. Which, it turns out, is quite long for robots.

class HopeLessRomantic:
    """
    This hopelessy romantic bot falls in love with the first robot it ever sees, and will pursue its subject of aspirations til the end of warranty. Which is long for robots.
    """

    def __init__(self, nrof_bots, rng):
        # nrof_bots is the total number of bots playing
        self.firstlove= None

    def round_finished(self, nrof_remaining_bots):
        #alas! the light of my live has rejected me. *sad robot noise*
        pass 

    def date(self, other) -> bool:  
        if self.firstlove is None:
            self.firstlove= other              # madly fall in robolove
            return True
        elif self.firstlove==other:
            return True
        else:
            return False

Answer 9

Optimal Cutoffs

import math
    
def value(n, k, j):
    return sum(i*math.comb(i,j)*math.comb(n-i-1,k-j-1) for i in range(j,n-k+j+1)) / math.comb(n,k)

def get_cutoff(n, k0):
    cutoff = {}
    for k in range(n,0,-1):
        if k >= k0: bst = 0
        z=0
        cutoff[k] = k
        for j in range(k-1,-1,-1):
            v = value(n,k,j)
            if v > bst:
                z += v
            else:
                cutoff[k] = j+(v<bst)
                z += (j+1)*bst
                break
        bst=z/k
    return cutoff

class OptimalCutoffs:
    def __init__(self, nrof_bots, rng):
        self.first_round = True
        n = nrof_bots - 1
        self.cutoff = get_cutoff(n, int(n * 3/4))
        self.met = []
    def round_finished(self, nrof_remaining_bots):
        self.first_round = False
    def date(self, other):
        if not self.first_round: return True
        self.met.append(other)
        self.met.sort()
        if self.met.index(other) >= self.cutoff[len(self.met)]:
            self.met.remove(other)
            return True
        else:
            return False

Uses dynamic programming to calculate the optimal cutoffs assuming the bot will meet 3/4 of the other bots, the other bot will always accept, and there is no payoff after the first round. Always accepts in rounds after the first.

Answer 10

Third Time Lucky

class ThirdTimeLucky:
    """Picks the bot from the third date"""
    def __init__(self, nrof_bots, rng): # rng is a seeded PRNG you can use, no other forms of randomness allowed
        # nrof_bots is the total number of bots playing
        self.number = 1

    def round_finished(self, nrof_remaining_bots): # the number of bots still in the game
        self.number = 1

    def date(self, other) -> bool: # Return True if you want to marry this bot, False otherwise
        if self.number >= 3:
            self.number = 1
            return True
        else:
            self.number += 1
            return False

This bot believes that three dates is the correct number to go on and will be happy to marry the third bot. If the other bot refuses, then they go on another three dates, accepting only the third.

Answer 11

Lower standards

class lower_standards:
    def __init__(self, nrof_bots, rng):
        self.sample_size = round((nrof_bots-1)**0.5)
        self.sample = [] # sample of dates (from the first round)
        self.curr = [] # all dates from the current round
        self.prev = [] # all dates from the previous round
        self.pool = nrof_bots - 1 # size of the dating pool
        self.round = 0 # round number
    def round_finished(self, nrof_remaining_bots):
        self.pool = nrof_remaining_bots - 1
        self.prev = self.curr
        self.curr = []
        self.round += 1
    def date(self, other) -> bool:
        self.curr += [other]
        if self.round == 0 :
            if len(self.sample) < self.sample_size :
                self.sample += [other]
                return False
            if all(other >= x for x in self.sample) :
                return True
        else :
            if sum(x > other for x in self.prev) <= len(self.prev) - self.pool + self.round - 1:
                return True
        return False

In the first round, this bot behaves like OptimalAverage.

On the second round, it behaves like a much more pessimistic version of Logger. Rather than assuming the current dating pool is the same as in the previous round, it takes into account that some bots have left. When the round ends, it looks at the number of bots still in the dating pool, and assumes that the remaining options are the worst possible subset of the previous round. It then accepts any bot which would be best in this reduced pool.

On the third and subsequent rounds, it becomes even less picky, accepting second best in the pessimistically reduced pool, then 3rd best, etc.

Answer 12

Wait for it...

class wait_for_it:
    """always rejects in the first round,
     then only accepts the top 2 it saw in the previous round,
     until it sees that the game is about to end,
     at which point it panics and accepts anyone."""
    def __init__(self, nrof_bots, rng):
        self.pool_size = nrof_bots
        self.curr = []  # all dates from the current round
        self.prev = []  # all dates from the previous round
        self.end_count = 0  # number of rounds with no matches made
    def round_finished(self, nrof_remaining_bots):
        if nrof_remaining_bots == self.pool_size:
            self.end_count += 1
        else:
            self.end_count = 0
        self.pool_size = nrof_remaining_bots
        self.prev = self.curr
        self.curr = []
    def date(self, other) -> bool:
        self.curr += [other]
        if not self.prev:
            return False
        if self.end_count == 2:
            return True
        if sum(x > other for x in self.prev) <= 1:
            return True
        return False

This bot is always a step behind. In each round, it will accept either of the top 2 matches it saw in the previous round. However, it also keeps tabs on the end condition, and if two rounds have gone without a match being made, it will accept anyone to avoid ending up alone.

Answer 13

Optimal Desperation

class optimal_desperation:
    """
    starts out believing in a beautiful theorem it heard about,
    but if that doesn't work out, it takes what it can get
    """
    def __init__(self, nrof_bots, rng):
        import math
        self.dates_left = math.ceil((nrof_bots-1)/2.718)
        self.best = None
        self.desperate = False
    def round_finished(self, nrof_remaining_bots):
        pass
    def date(self, other) -> bool:
        if self.desperate:
            return True
        if self.best is None:
            self.best = other
            self.dates_left -= 1
            return False
        if self.dates_left > 0:
            self.dates_left -= 1
            self.best = max(other, self.best)
            return False
        if other >= self.best:
            self.desperate = True
            return True
        return False

Inspired by Spitemaster's Optimal Stopping Time, but when its optimally true love rejects it, it gets desperate and says "yes" to anyone and everyone.

Answer 14

Partygoer

While sober, the partygoer doesn't care for dating. However, it likes meeting new people, so, just for the sake of it, the partygoer decided to join the - hey, look! Beer!

class Partygoer:
    """
    Decides when to marry depending on how sober it is. Then, it drinks.
    """

    def __init__(self, nrof_bots, rng):
        self.sobriety = 1.0
        self.rng = rng

    def round_finished(self, nrof_remaining_bots):
        self.sobriety -= .05

    def date(self, other) -> bool:
        limit = self.rng.random()
        flag = False
        if limit > self.sobriety:
            flag = True
        self.sobriety -= 0.01
        return flag

Uses the PRNG to decide a limit. Every time it goes on a date, it checks its sobriety. If it's greater than the limit, it decides to marry. Regardless, though, it takes a drink, decreasing its sobriety a little. If an entire round goes past without getting married, it decreases sobriety by a larger margin.

Answer 15

Anything but the worst

class AnythingButTheWorst:
    """
    Will accept anyone as long as there is someone worse
    """

    # rng is a seeded PRNG you can use, no other forms of randomness allowed
    def __init__(self, nrof_bots, rng):
        # nrof_bots is the total number of bots playing
        self.worst = None

    # the number of bots still in the game
    def round_finished(self, nrof_remaining_bots):
        pass  # called if a full round finished, optional

    def date(self, other) -> bool:  # Return True if you want to marry this bot, False otherwise
        if self.worst is None:
            self.worst = other
        else:
            self.worst = min(self.worst, other)

        return other > self.worst

Will settle for any bot except the worst one.

Answer 16

Adaptive Better-than-median

class adaptive_better_than_median:
    """
    accepts bots better than the median,
    while updating the median as the game evolves
    """
    def __init__(self, nrof_bots, rng):
        self.curr = []
        self.prev = None

    # the number of bots still in the game
    def round_finished(self, nrof_remaining_bots):
        self.prev = self.curr
        self.curr = []

    def date(self, other) -> bool:
        self.curr += [other]
        if self.prev is None:
            return sum(other > x for x in self.curr) >= len(self.curr)//2
        return sum(other > x for x in self.prev) >= len(self.curr)//2

Just what the name says; behaves in the first and second rounds like "Better than Median", but then adjusts the median based on who dropped out in previous rounds.

Answer 17

Top Three Previous

class TopThreePrevious:
    """
    Will marry any of the top three it has seen from the previous round.
    If it's the first round, it flips a coin instead.
    """

    def __init__(self, nrof_bots, rng):
        self.rng = rng
        self.best = []
        self.previousBest = []
        self.bots = []

    def round_finished(self, nrof_remaining_bots):
        self.best = []
        self.bots.sort(reverse = True)
        for i in range(3):
            self.best.append(self.bots[i])
        self.bots = []

    def date(self, other) -> bool:
        self.bots += [other]
        if len(self.best) == 0:
            return self.rng.random()>0.5
        return other in self.best

This bot simply checks if the bot it's currently dating was one of the top three it has seen in the previous round, or flips a coin if it's the first round (it uses the length of self.best to determine this).

Answer 18

T

*** not working ***

class T:
    def __init__(self, nrof_bots, rng):
        self.NR    =  nrof_bots
        self.d     =  {}
        self.mc    =  0
        self.r     = 1
        self.rc    = 1
        self.xrs   = []               # unseen in current round
        self.x     = set()            # seen in previous round
        self.xn    = []               # seen in this round
        self.c     =  0              # for debugging
    def update(self, other):
        self.c += 1
        self.rc += 1
        if other not in self.d: self.d[other] = 0 # Set if new
        self.d[other] += 1
        self.mc = max(self.mc, self.d[other])     # Highest number seen
        if self.mc > self.r: # update round
            missing_in_round = set(self.x).difference(set(self.xn))
            NR_ = self.NR - len(missing_in_round)
            self.NR = NR_
            self.r = self.mc                         # set round
            self.x = set(self.xn)                        # seen in prev round
            self.xrs = self.xn                           # All are unseen
            self.xn = []                                 # reset round
            self.rc = 1
        self.xn.append(other)
        xrs_ = set(self.xrs).difference({other})      # update unseen
        self.xrs  = list(xrs_)
        self.xrs.sort()                               # sort unseen

    def get1(rc, NR, xrs, xn):
         average_acceptance = 0.3
         N_ = NR - rc * 0.3
         dec = 0.7 * N_ / (N_+ 1)
         return dec

    def getd(rc, NR, xrs, xn):
        if len(xrs) == 0: # end of round
            xn_ = xn.copy()
            xn_.sort()
            dec = xn_[round(len(xn_) * 0.7)]
        else:
            dec = xrs[min(round(NR*0.7 - rc*0.14), len(xrs) - 1)]
        return dec

    def round_finished(self, nrof_remaining_bots):
        return None

    def date(self, other): # Return True if you want to marry this bot, False otherwise
        self.update(other)
        espouse = other >= (T.getd,T.get1)[self.r==1](self.rc, self.NR, self.xrs, self.xn)
        print(f'{self.c}:{other:3.2f} :::{espouse}')
        return espouse

Answer 19

class IDK_bot:
    """
    This bot will use its first date as a reference, then marry any bot that's better than it
    """
    def __init__(self, nrof_bots, rng): # rng is a seeded PRNG you can use, no other forms of randomness allowed
        # nrof_bots is the total number of bots playing
        import math
        self.rng=rng
        self.numbots=nrof_bots
        self.dates=[]
        self.cutoff=int(self.numbots/math.e)**(4/5))
        self.num=0
        self.rounds=0

    def round_finished(self, nrof_remaining_bots): # the number of bots still in the game
        import math
        self.numbots=nrof_remaining_bots
        self.cutoff=int(self.numbots/math.e)**(4/5))
        self.rounds+=1

    def date(self, other) -> bool: # Return True if you want to marry this bot, False otherwise
        self.dates.append(other)
        self.dates.sort()
        self.num+=1
        if self.num<self.cutoff:
            return False
        score=self.dates.index(other)/self.num
        if score<0.5:
            return False
        return self.rng.random()<=score*(self.num/self.bots*1.2)**(1/3)*(1+self.rounds/5)

The bot defines a "cutoff" based on the n/e rule which has been proven to be approximately optimal for the secretary problem. However, since you aren't guaranteed to see every possible date, that limit is raised to the 4/5th power (an arbitrary number I selected) to give more potential candidates to select.

The actual selection is based on RNG. The bot first calculates the date's score, which is the relative ranking of the date in relation to the other dates it has seen, represented as a number from 0 to 1. The bot rejects any candidate with a score less than 0.5. The bot multiplies the score by a bunch of math, effectively taking into account the fraction of dates seen so far and how many rounds it has been in.

This lets the "score" be the largest part in deciding whether or not to accept a candidate, but also makes it so that the probability of acceptance increases as more bots are seen and as more rounds pass.

I haven't been able to test this, so please let me know if there are any bugs I need to fix.