I spent a few days running first-week errands, signing an apartment lease, getting a Brown ID, renting a parking space. In terms of the project, I've been familiarizing myself with the TAC game and reading papers about various agents, including RoxyBot. I have a basic understanding of the challenges of the game, and I've had a couple of meetings with Amy and Nicole to discuss how RoxyBot stands to be improved -- I'm just not exactly sure how to do that! The first thing Amy wants us to show is whether or not her bid determination algorithm outperforms the algorithm of one of the other agents from a previous competition. I spent the end of the week writing and debugging a short program that simulates part of an auction and used both algorithms to generate bids. Amy had a small party on Thursday night for the students she works with, so Nicole and I traveled to Boston for the first time. It was fun, although I was a little nervous about running through the bus station to catch one of the last buses back! This weekend is a long weekend, and I'm planning to drive to Connecticut to visit my sister and brother-in-law.
This week I've been testing the bidding algorithms. The auction simulation provides the algorithms with prices and valuations for a certain number of goods. Each algorithm uses those values to compute bids. The utility earned by each algorithm is the valuation of the combination of goods it bought, less the cost. The program also computes the optimal utility that can be earned, based on the price and valuation values. Since finding the optimal utility is an NP-hard problem, I've only been testing small numbers of goods. The good news -- the RoxyBot algorithm has consistently earned the highest attainable utility in all my simulations. The other algorithm has earned suboptimal utility a few times. Next on the agenda is to prove that RoxyBot will always bid optimally and that my results weren't just the product of insufficient testing, and determine what conditions cause the other algorithm to bid suboptimally. I have to finish my work at a reasonable hour on Friday, though, because I have to catch a flight to Omaha for my cousin's high school graduation!
June already! Part of my auction simulation provided the algorithms with prices, which are unknown in actual auctions, such as the TAC game. I'm modifying my simulation to use a normal distribution to generate prices and valuations; bidding algorithms will have to sample from the distribution to determine what bids to place. I'm implementing several different algorithms -- one that takes several samples and averages the bids it would have placed if those prices had been certain, and two that generate a set of bids for each sample and choose the best policy after sampling.
Good news -- the RoxyBot bidding strategy is optimal under price certainty. I drafted a short proof and am getting to work, proving that the marginal utility bidding algorithm is only suboptimal when there exist multiple optimal solutions to the completion problem. I also have a couple of ideas about an alternative bidding strategy. It is optimal under price certainty, and relies only on the valuations of goods, rather than their marginal utilities. I hope this will mean savings in terms of computation time, since finding the highest marginal utility for any set of goods is an NP-hard problem. The main problem I've run into so far is that sometimes the bids are higher than RoxyBot's, and sometimes lower. So it's hard to say what impact the strategy would have on the economy. I'm hoping we will be able to implement the strategy in RoxyBot for testing purposes and see how it does in the practice TAC games.
I've gotten preliminary results from my experiments comparing various bidding strategies under price uncertainty. The three main algorithms I'm comparing are a RoxyBot search strategy, marginal utility search strategy, and an average marginal utility bidder. I described the search strategies briefly a few weeks ago; the average marginal utility bidder just bids the average marginal utility for each good after a certain number of samples. When prices are sampled from a normal distribution, the RoxyBot search policy performs very well, and the marginal utility search policy slightly worse. The average marginal utility bidder performs significantly worse. I am curious about how much impact the price distribution has on the effectiveness of the bidding policies, so I think that will be the next factor I test.
As it turns out, my intuitions about the impact of different distributions on the performance of the bidding algorithms were completely backward! I ran the same simulations, skewing the price distribution in one case to make it more likely that goods are complementary and in the other to make it more likely that they are substitutable. I expected that RoxyBot would perform significantly better than the marginal utility bidder for substitutable goods, since that is one of its a pre-conditions for suboptimality. But the performance of all the strategies took a nosedive for these experiments, and RoxyBot suffered the worst. The graph of the complementary experiment is pretty much the same as the original distribution. So far I don't have any convincing ideas about why that happened. Maybe because RoxyBot commits itself to a small optimal subset of goods, it has less of a margin of safety for other samples in which the prices are drastically different. The marginal utility bidder hedges its bids by bidding marginal utility on all goods, not just goods in an optimal set, so it may be gaining more utility from non-optimal purchases than RoxyBot can earn by buying fewer, less valuable goods. Just a thought.
This week added another twist to the bidding strategy experiments I've been running. (I should have paid more attention in my software design classes! I know tweaking this simulation code should have been much simpler!) Currently RoxyBot defines the marginal utility of a good as the highest attainable utility when the good is owned, minus the highest attainable utility when the good cannot be purchased. We know that for all goods in the optimal set, the marginal utility is at least the ask price of the good, when prices are known. However, in many cases it is greater than the ask price -- and we have no way of measuring the impact our high bids have on the ask price in the future. So my next set of experiments involves the same algorithms, but instead of bidding marginal utility, one version of the RoxyBot bidder will bid the mean of the price distribution, and another version will bid in between the mean and the marginal utility. So far the mean bidder is significantly less successful than either the original RoxyBot or the mid-range bidder; the mid-range bidder has slightly less success than the original RoxyBot, but it's hard to say whether the lower bids justify that.
Until now, I've been working solely on offline simulations and have had minimal contact with the actual inner workings of our agent. But with the competition finals two weeks away, it's time to put my results to work in RoxyBot. I've been frantically learning enough Perl to write scripts to parse through all the log files created by the TAC server after each game. We want to isolate a few key features of the hotel auctions and study how they affect the ultimate closing price of each auction. Right now scripts are in place to download the log files from the semifinal games in which RoxyBot played and correlate the number of bids RoxyBot placed on a given hotel with its closing price. Graphs of these results confirm that our bids do have a considerable impact on the closing price; when RoxyBot wants four or five of the same hotel, its closing price is higher on average than when we want only one or two. The graphs are slightly misleading in that they don't show standard deviation data. All summer I've been scouring the net for a better Linux graphing application than scigraphica, but haven't found one. I'm very excited because Amy asked me if I want to go to Edmonton for the TAC workshop! Each qualifying team can send a representative to give a 15-minute presentation about their agent, but Amy can't make it to the conference. So I've been trying to figure out if I can get funding for the trip. If I go, I'll probably end up staying in Canada for a few days to attend part of the AAAI conference, too. This weekend's whirlwind travel plan: flying to Wisconsin for another cousin's wedding.
My goal for this week is to finish studying isolated features of the hotel auctions. The other features we're interested in are the day, time in the game, type of hotel, whether the other hotel is still open, and the current ask price. I am working on graphing each of those features for a given hotel, and possibly some combinations of them, against the closing price. Since there are 8 different hotels (4 days and 2 types of hotel for each day) and 12 minutes in each game, there is quite a lot of data to parse! I'm also frantically searching for reasonably priced flights and trying to find roommates for the conference in Edmonton. So far the only person I know who is going is my AI professor from Duke! I haven't had much time to get too nervous about the presentation, though, because there is too much work to do in the meantime! Nicole and I have to keep reminding each other that there is only one week left -- it's hard to believe!
This week has been extremely busy with last-minute adjustments to RoxyBot and preparations for the TAC workshop. The final rounds of the competition are on Sunday, July 28, so all of our modifications have to be in place by then. Nicole and I worked together implementing a new bidding scheme that samples from TAC's published semifinal statistics to generate hotel bids. It's an imperfect fix, because the stats given are closing prices rather than changes in price from minute to minute, so one of my tasks is to parse through all the semifinal data to generate a table of delta values to replace the table of closing prices. Also, if any of the agents have changed significantly since the semifinal rounds -- which is likely -- the historical data may not be particularly relevant. I've also been working on generating graphs to use in my presentation this weekend. The other day Amy and Nicole and I had a grad school discussion over lunch. I'm not sure if this summer confirmed my interest in pursuing computer science in grad school or sparked a completely new interest. I've definitely enjoyed working with Amy and Nicole, and I like that there are so many different aspects of AI that could be equally as rewarding. I'm pretty sure I want to do something completely different for a year or two before applying to grad school, but Amy and a few others have reassured me that that's a viable plan. But for now, it's time to say goodbye to Providence and all the people I've met here.