Project 3: Flower Arrangements

As my other daughter Zoe explained to me, the marriage season in Flowerdale is much anticipated. People in Flowerdale interact by giving each other flowers, and judge potential mates by the quality of their flower arrangements. In Flowerdale, gender has no role in the choice of partner: only the flower exchange matters!

The courtship period extends for d days, where d is a parameter. On each day, every eligible person creates a bunch of flowers for every other eligible person in town. An empty bunch of flowers is a valid bunch, in case there is a shortage of flowers. Who knows, maybe somebody likes an empty bunch of flowers. After giving the bunch of flowers, the recipient informs the giver of two pieces of information: a score, and a current ranking. The score is a number between zero and one (inclusive) that indicates how much the recipient liked the arrangement. Zero means total dislike, whereas one means the arrangement was perfect, and cannot be improved upon. The current ranking is a number between 1 and p-1, where p is the number of people participating in the event. 1 means the arrangement has the highest score among all arrangements received by that person on that round. Along with the ranking, you will also be informed of how many others received that ranking. So a ranking of 1 with 7 ``ties'' may be less impressive than a ranking of 2 with no ``ties''. (Note that if there are seven ties for rank 1, then the next rank will be 8, not 2.) A recipient remembers the score they gave to each bunch of received flowers.

Each flower has one of four types: Rose, Chrysanthemum, Tulip, and Begonia. Each flower has one of three sizes: Small, Medium, Large. Each flower has one of six colors: White, Yellow, Red, Purple, Orange, Blue. A bunch of flowers may contain anywhere between 0 and 12 flowers. At the start of each round, a random assortment of 6(p-1) flowers is selected, corresponding to the mix of flowers available at the market that day. Every participant gets their own (identical) assortment, from which they assemble their bouquets. In this assortment, each of the 72 possible flowers is equally probable, and some flowers may be repeated while others are not present at all. It is not required that all flowers be used, but the union of all arrangements on a round must be a multiset-subset of the assortment. (A multiset is just a set with repetition allowed.)

Every participant encodes a deterministic scoring function that depends on the combination of flowers in an arrangement. Each participant's function f on multisets of flowers must conform to the following requirements:

• f(m)=1 for some possible multiset m.
• f(m)=0 for some possible multiset m.
• f(m) can be written as the sum s(m)+c(m)+t(m) of functions s, c, and t, where s depends only on the (multiset of) sizes of the flowers in m, c depends only on the colors of the flowers in m, and t depends only on the types of the flowers in m.

These conditions ensure that the full range from 0 to 1 is achievable in principle, and that it is possible to independently analyze the sizes, colors and types of the flowers in an arrangement. This independence will make the flower-giver's job easier by making the scores somewhat more interpretable. (How?)

As the courtship ritual progresses, each participant can try different combinations of flowers to see which combinations get positive responses, and which do not. For the actual marriage arrangement process, only the final round of flower-giving matters. Marriages are determined according to the following algorithm:

1. For each $i=1,\ldots,p$ calculate s_i as the score of the second-best scoring arrangement among all of the suitors of participant number i. We're going to define an outcome that will be positive (happy) if the top-ranked suitor with a score larger than s_i is chosen. The outcome will be neutral (zero) if a suitor with score s_i is chosen, and negative (regretful) if a suitor with score less than s_i is chosen.
2. Among all remaining participants i, define x_i to be the score of the first-ranked remaining suitor of participant i. Let d_i=x_i - s_i. As previously mentioned these scores are according to the arrangements from the final round. Let I be the value of i for which d_i is maximal, and let J be the corresponding first-ranked suitor for that participant. If there's a tie, the simulator will choose a participant among the ties at random.
3. Participants I and J are married, and each receives a final outcome of d_I.
4. Participants I and J are both removed from the marriage pool, and the process above (starting at step 2) is repeated if participants remain. With an even number of participants, everybody eventually is paired off, and the loop terminates.

The outcome is not a measure of absolute preference for the flowers, but instead a measure of regret-avoidance: how much worse or better would it have been had the second-best suitor been chosen. Also, both the chooser and the chosen participant get the same score determined by the chooser's ranking. This is not so strange: one participant believes they have made a good catch, while the other believes that they have something special to offer in the relationship!

The goal of this project is to maximize the outcome that your program receives. There are two interdependent ways to succeed: (a) By choosing a ``good'' function f, your player may get to choose its top-ranked marriage partner with a high score relative to the next-best option; (b) By cleverly understanding how each player scores flower arrangements, and targeting certain potential partners in the final round, your player might be chosen because your arrangement stands out compared to others.

Your program will know d and p at the beginning of the simulation. Your player will not know the identity of the other players, i.e., whose code they are running. While the function f must be deterministic throughout the simulation, it can be randomized in the sense that it is generated from a distribution of possible functions once at the start of each simulation. This may be important: What strategic disadvantage might accompany the use of a fixed function that other groups know in advance?

At the end of the project we'll run a tournament for various values of d and p. We will run different groupings to get different measures. We can mix different players to see who has the most positive outcomes in competition. We can have many instances of the same player, and determine which players tend to generate positive outcomes when run against themselves. We'll run many instances of the simulations to account for random variations, such as the choice of functions f and the available flower distribution.

Some initial things to think about:

1. What does it take for a function f to be ``good'' in the sense mentioned above?
2. How would a small value of d affect the strategy compared with a large value?
3. Can you see an analogy between the outcome computation and Vickrey auctions?