Monday, October 31, 2011
Problem 19: Rating Trading, Part 2
Consider the following generalization of the Math Trade Problem, which I came up with while thinking about how to use a similar "math trade" process to trade Magic cards. The difficulty with trading Magic cards using math trades is that Magic cards vary extremely widely in value, so the restriction of one-for-one trades is likely to be prohibitive. Therefore, suppose that we have the following Generalized Math Trade Problem:
Consider a group of N players, each of which has one or more cards to trade. Each player has a separate "subjective value" of each object - i.e. one player might value a given card at $12, while another might value it at only $8. The goal is to redistribute the cards among the players so as to maximize the sum of the amount each player values the cards he ends up with, subject to the constraint that each player ends up with cards that he values at least as much as the cards he started out with.
The "decision problem variation" of the Generalized Math Trade Problem is as follows: given an instance of the Generalized Math Trade Problem and a target value, determine if there is a solution such that the sum of the amount each player values the cards he ends up with is at least the target value (subject to all the other constraints of course).
Problem 19: Show that the decision problem variation of the Generalized Math Trade Problem is NP-complete.
Hints (ROT13 to read; you can read them one at a time)
1. Gur erqhpgvba vf gb gur fhofrg-fhz ceboyrz.
2. Gur fbyhgvba vaibyirf bayl gjb cnegvpvcnagf.
3. Bar bs gur cnegvpvcnagf unf bayl bar vgrz.
And the solution.
Sunday, October 30, 2011
1. Trick automated phone systems into connecting you with a human being faster.
2. Detect electromagnetic fields believed to indicate the presence of ghosts.
3. Display rapidly-changing images that hypnotize viewers into breaking bad habits.
4. Transmit voices across long distances using invisible waves of energy.
Saturday, October 29, 2011
Consider the following problem, which we will refer to as the Math Trade Problem:
Consider a set of N players, each of which has one game that they want to trade. Assume that each player has a different game. Each person also has a list of games that he wants (You may assume that nobody lists a game they already have as a game they "want".) The goal is to determine how to distribute the games between players such that the number of trades (i.e. the number of people that end up with a game they want) is maximized subject to the constraint that everyone ends up with exactly one game, and each person ends up with either a game he wants or he keeps the game he already has.
The minimum-cost network flow problem with node capacities is as follows:
Consider a graph G with a set of vertices V (also known as "nodes") and (directed) edges E between these vertices. Each edge has a maximum capacity, which states how many units of flow can be sent along that edge, and a "cost", which gives the cost of sending each unit of flow along that edge. The goal is to find a way of sending flow such that the amount of flow going into each node is the same as the amount of flow going out, and the total cost of all the flow sent is minimized. Additionally, nodes may have "node capacities" which give the maximum amount of flow that can flow through that node. (In some versions of the network flow problem, there can be "source" nodes or "sink" nodes for which the amount of flow going in need not be the same as the amount going out, but these will not be necessary for our purposes.)
Problem 18A. Given an instance of the Math Trade Problem, show how to transform it into an instance of the Minimum-Cost Network Flow Problem with Node Capacities, such that a solution to the network flow problem will give a solution to the given Math Trade Problem.
Problem 18B. Given an instance of the Minimum-Cost Network Flow Problem with Node Capacities, show how to transform it into an instance of the Minimum-Cost Network Flow problem without node capacities. (There are several well-known algorithms that can be used to solve this problem.)
Problem 18C. Consider the following generalization of the problem. Suppose that each player owns multiple games, and we want to maximize the number of trades (i.e. total number of games that people want that they get) subject to the constraint that each player ends up with the same number of games he or she started out with, and each of those games is either one he already had or one that he wants. However, we also add the complication that several players may want to trade the same game, and nobody wants to end up with two or more copies of the same game.
I will put some hints up later tonight and I will put the solution up tomorrow.
Tuesday, October 25, 2011
Sunday, October 23, 2011
Of course, most economists would say that most "moving jobs overseas" is actually a net benefit because each country can specialize in what it produces best, thus improving overall output - i.e., if a company saves money by "moving jobs overseas" and importing products rather than producing them in the U.S., that just creates jobs for the people in the U.S. that produce exports to exchange for the imports, and this analysis is not affected by whether the reduced costs are caused by the overseas workers being "taken advantage of". Of course, this argument has been discussed to death, and I don't really have anything new or interesting to say about it.
What I find more interesting is the implied moral claim that there is something blameworthy about a corporation "moving jobs overseas", such that the corporation needs to be held "accountable" for it. (Of course, I'm not picking on Degraffenreid here; lots of the public and politicians seem to have similar view, which is part of why I find this interesting.) Consider the following two cases:
A. Acme Corporation currently employs 100 American workers. It has an opportunity to expand into a new market and hire 50 more American workers, but instead decides to stay its current size.
B. Acme Corporation currently employs 100 American workers. It has an opportunity to expand into a new market and hire 50 more American workers, but instead it builds a factory in Pakistan and hires 200 Pakistani workers instead because it is cheaper.
I doubt very many people would say that in case (A) Acme Corporation did anything blameworthy, but in case (B) they would say that Acme Corporation was "shipping jobs overseas." But in either case, the change in number of American workers was exactly the same - zero. What principle could justify the difference? You can't just say that corporations have a responsibility to hire as many American workers as possible, because that would make (A) as blameworthy as (B). One possibility is to say that corporations have a responsibility NOT to hire foreign workers, but that seems hard to justify. Why is giving an American worker a job good but giving a Pakistani worker a job bad? I can understand why Americans value other Americans more than they do Pakistanis, but I don't understand why people would put a negative value on Pakistani jobs.
One possibility is that people think that Pakistani workers aren't actually being helped by the new jobs. But that doesn't make sense, because if the new jobs were really inferior to whatever they would be doing in the absence of the new jobs, then why would anyone take the new jobs? Another possibility is that people think that corporations have a responsibility to hire foreign workers AND pay them well, so that their lot would be improved by even more than before. But that doesn't explain attitudes like Degraffenreid's, since he says (probably correctly) that making American firms pay foreign workers more will induce them to hire fewer foreign workers. (Unless the idea is that it is better to help a few foreign workers a lot than to help a lot of foreign workers a little each.)
Possibly a better explanation might be to go back to the principle that "American companies have an obligation to hire as many American workers as possible", and explain the reluctance of people to assign blame in case (A) a different way. One possible explanation would be that my premise (that people don't assign blame in cases like A) is false. After all, people do sometimes consider companies blameworthy when they lay off workers, and Barack Obama did exhort companies to start investing and spending more if they had the money to do it. Another explanation might be that people think that (A) is theoretically blameworthy, it's just that "not expanding as much as you can" is much less visible than "opening up factories in foreign countries".
Here is another question: let's say that reforms designed to "bring jobs home" were implemented, and because of that, corporations pulled their investments out of Pakistan and brought them "back home" to the United States. In that situation, would Pakistanis be right to complain that the corporations are "sending jobs overseas" back to the United States? If so, then why does a corporation that operates in both the U.S. and Pakistan have greater obligations to American workers than to Pakistani workers? If not, then what is the relevant distinction?
Finally, consider the following third case:
(C) Acme Corporation currently employs 100 American workers. It sees room to expand and hire 50 more American workers. Instead, it buys more machinery to make each worker more productive, so that it doesn't need to hire any new workers.
I think most people would think there's nothing wrong with (C); or at least much less wrong with (C) than with (B). Sometimes people do lament the fact that technology puts people out of work, but certainly I have never heard any politician saying that we have to slow down progress on labor-saving technology in order to preserve jobs. But in both cases (B) and (C) you are choosing an option that allows you to hire fewer American workers in order to reduce costs. So a general principle that "it's wrong to hire fewer workers just so you can reduce costs" is not the driving force here.
A possibility is that there is some sort of (implicit) cost-benefit analysis going on. That is, people think that reducing costs is a legitimate benefit, but that it has to be balanced against the (perceived) costs of putting people out of work. With labor-saving technology, it's really obvious that the benefits are enormous: if we had never developed any labor-saving technology whatsoever, we would still be hunter-gatherers living in caves. But with international trade, the benefits are a lot less obvious, so it is easier for people to think that the costs exceed the benefits.
Of course, a lot of this is just speculation, and I don't know what the right answer is. I found an interesting web site called "Experimental Philosophy" that discusses research where they do surveys to ask people these types of questions in order to understand how people actually form judgements about these questions (like what makes someone morally responsible for something, or when it makes sense to say that someone "intended" for something to happen.) Reading that web site is part of what gave me the idea to think about this issue in this way, although I don't see any posts on that web site that discuss political/economic questions like this one. Also see here for a related discussion about "moving overseas" and moral responsibility (although I think that discusses a slightly different issue).
Wednesday, September 21, 2011
I am writing to urge you to vote against the TRAIN Act, which will delay implementation of key environmental protections that could save thousands of lives. While proponents of the TRAIN Act claim that they are interested in ensuring that the benefits of regulation exceed the economic costs, their actual actions clearly show that this is not what they are concerned about. First of all, the EPA already does cost-benefit analyses of its regulations. If TRAIN Act proponents believe these analyses are flawed, why wouldn't they just fix them, rather than wasting time starting all over? Second, the latest version of the TRAIN Act explicitly blocks the Cross-State Air Pollution Rule and Mercury and Air Toxics standards. If proponents were really interested in making an honest inquiry as to the costs and benefits, why would they write into the bill what conclusions they want before even doing the analysis? Finally, the pro-pollution lobby's own words prove their dishonesty. The American Coalition for Clean Coal Electricity, a key pro-polluter lobbying group, on the front page of its website (www.americaspower.org) states that proposed EPA regulations would "eliminate more than a million American jobs". However, if you click through to their own analysis you will find that is not true - they actually claim it will eliminate 1.4 million "job-years", totaled over an 8-year period, which is not the same thing. If the pro-polluter lobby can't even get basic facts straight, why should we believe anything they say?
I'm not too hopeful as to what Gardner will think about this issue, given that he is a staunch conservative and as far as I can tell from his votes, has hasn't voted on the pro-environment side on any recent bills. I don't see anything on his web site where he supports "protecting the environment." However, one of the proposals he supports, the Business Cycle Balanced Budget Amendment, says it will "force government to budget itself in a countercyclical manner", which actually makes economic sense. However, the actual proposal says that the budget limit for each year is an (inflation-adjusted) average of revenues for the past three years, and I don't think that's what "countercyclical" means.
Tuesday, September 20, 2011
What I was interested in is just what, in particular, proponents believed the flaws of the EPA studies were. The American Association for Clean Coal Electricity, (ACCCE), a power-company lobbying group, has a web page that discusses the issue from their point of view. They identify two perceived flaws: first, that the EPA considers only one proposed rule at a time and does not lump multiple proposed rules together in its analysis; and second, that the EPA does not consider other negative economic effects such as lost jobs. (Note that on the association's front page, they claim that the regulations the TRAIN Act will block will cost 1.4 million jobs. However, on the actual page that discusses the TRAIN Act, they say it will cost 1.4 million job-years, totalled over an 8-year period. These are very different.)
Anyway, the first criticism does not, at first, seem to make any sense. If regulation A has costs which exceed benefits, and regulation B has costs which exceed benefits, then added together, regulations A and B will collectively have costs which exceed benefits. The only way this will not be true is if either:
(a) The benefits of implementing both regulations A and B are less than the benefits of implementing A alone plus the benefits of implementing B alone.
(b) The costs of implementing both regulations A and B are greater than the costs of implementing A alone plus the costs of implementing B alone.
This, of course, raises the question of in what circumstances these can be true. For case (a), I can think of a simple example: suppose that both regulations will reduce exposure to the same pollutant, and the pollutant has a hormetic dose-response relationship. But for some reason I don't think that's the case that the ACCCE is thinking about. For case (b), I can think of a different case, that seems to be the case that the ACCCE is discussing. Suppose that both regulations reduce the production of electricity, and electricity (like most goods) has diminishing marginal value. Then just looking at each regulation individually, and estimating the cost by multiplying the current price by the amount of reduction (let's say), will understate the total costs. In the diagram below, the true cost is C+D but the "looking at each regulation individually) approach will give you something closer to C.
We can now estimate about how big this difference is. For the sake of argument, I will use the assumptions that are most favorable to the ACCCE's position. They mention that there will be a total reduction in coal power production of 30 to 100 gigawatts (GW) due to "these and other rules". 100 GW is equivalent to 876,000,000 MWh over the course of a year, or about 25 percent of the total U.S. electricity consumption 3,741,485,000 MWh per year. Of course this is not a good estimate of total electricity consumption lost because some of the capacity lost in coal gets replaced by other energy sources. If I am interpreting the chart labeled "2016 CATR+MACT impacts" of their own report correctly (it's on page 6 of the PDF, or page 5 going by the page numbers on the page), it looks like about 60 percent of capacity lost in coal gets made up in increased natural gas. So you end up with a total of about 10 percent reduced consumption. According to the review here, the short-run price elasticity of demand for electricity is about 0.2. So 10 percent reduced consumption corresponds to about a 50 percent increase in price. That means that the triangular area D is about 25 percent of the area C.
However, my understanding (at least based on what it says here) is that for most of these regulations the benefits exceed the costs by at least several times. So just a 25 percent error won't make a significant difference.
The comment about jobs, however, is more interesting conceptually, and I think they have it backwards. Here's how I am thinking about it. Let's say that electricity and labor are perfect complements, so a business can produce a "widget" by using one worker and one unit of electricity. Suppose that currently the business is producing X widgets, and so it is using X units of electricity, and the new regulation will increase the price by Y. Suppose you ignore the issue of jobs. Presumably that means you assume that the business will just produce the same number of widgets as before. Then the total cost is X times Y. But suppose you take jobs into account, and you take into account the fact that now the business will produce fewer widgets because the cost of producing them went up. But if they made this change, then that means the change was beneficial (compared to just absorbing the extra cost). In other words, the "reduction in jobs" is partially a benefit because it means that you are now using less of the more expensive electricity.
Of course, conservatives aren't the only ones who often use faulty economic reasoning when talking about environmental issues. During the 2008 presidential campaign, Barack Obama claimed that oil companies had 68 million acres of land they were "not using" and that we needed to make them "use it or lose it." Most importantly, this claim was false: most of the 67 million acres of "non-producing land" was actively being explored and prepared, it's just that no oil was coming out of it yet. But even if it was true that oil companies were deliberately ignoring large portions of their land, why is that necessarily a problem? There are only two reasons I can think of as to why they would do that. One reason is because they think that oil will become more expensive in the future and they would rather wait and sell the oil when it's more expensive rather than extract and sell the oil now. But if that's the case, then the oil companies' actions would raise the price now (when it's cheaper) and lower the price when they get around to extracting it (when it's more expensive), thus reducing the volatility of oil prices over time. Isn't that a good thing; to save it for when it's scarcer? Another possible reason is if they are colluding to reduce supply in order to raise the price now. But that theory doesn't seem to hold water because oil is traded on a world market, and the vast majority of world oil and gas reserves are controlled by companies outside the United States, so it doesn't seem like U.S. oil companies could reduce the world supply that much just by drilling a bit less. And in any case, if the problem is that we are using too much oil, isn't it good if the oil price goes up because that means that people will have an incentive to switch to renewable sources?
Saturday, September 10, 2011
Friday, August 26, 2011
Transportatoin will be slightly more difficult here than in Champaign. I live in Fort Collins, then about 10 miles south of Fort Collins is downtown Loveland, and about 4 miles east of downtown Loveland is where I work. There is a bus system (Transfort) in Fort Collins, which I don't need ot use much because I can just bike everywhere in Fort Collins that I want to go usually. In order to get to work, I need to take the "Flex Bus" down to Loveland, then get on a COLT (City of Loveland Transit) bus to get to where I work. The last Flex Bus northbound from Loveland leaves at 7:12 PM, so I have some time to do stuff thereafter work. One problem with the bus system is that none of the buses run on Sundays (see below to find out why that is a problem). I did try riding my bike down all the way from Fort Collins to Loveland once, but I don't think it's something I will want to do very often. There is also a taxicab company (Denver Yellow Cab) here. According to here, it gets horrible reviews for customer service, but I have used it three times and so far have no problems, except that sometimes I get put on hold for a few minutes while calling for the cab. It is about $30 to go all the way from Loveland to Fort Collins.
There is a major street (College Avenue) with all the usual chain stores like Target, Best Buy, Barnes + Noble, and so on. Another thing I have noticed here is that there seems to be a lot of outdoor stuff, camping, and hunting going around here, because I've seen several outdoor equipment stores including a dedicated archery store. Also I have seen lots of signs for gun shows - I wonder if those are geared toward hunters. Also, when I was in Loveland I saw the store Phoenix Nest, which sells Renaissance-style garb and they also do custom made leather products. I will probably be back there a few times to get stuff for live-action role playing (see below). Another store that is cool is in downtown Fort Collins, and it is called Science Toy Magic. It is a very small store but it is packed full of cool toys that demonstrate principles of science, and the guy who runs it does really fun demonstrations. A couple weeks ago I saw a sign indicating that they would get new toys in, so I went back to see the demonstration of the new toy, which was called the "Invisible High Bouncing Ball". The demonstration was okay, but it was a little hard to see what was going on. You can also watch this YouTube video here. Here's another thing which obviously won't affect me directly, because I am not going to use any illegal drugs, but might be interesting: I saw in the newspaper that Fort Collins is considering banning medical marijuana, and if you have been here you will understand why lots of Fort Collins residents complained that the ban would screw up their economy.
There are two main game stores in Fort Collins: the Haunted Game Cafe and Gryphon Games and Comics. They all have things going on almost every night, including role-playing games, miniatures games, and board games. The Haunted Game Cafe has a shelf full of games you can borrow to play in the store., and they sell drinks and snacks there. Each of these stores is a little bit bigger than the ones in Champaign. I haven't played any role-playing games yet here so I don't know what the scene there is like. As far as miniatures go, it seems like I may be in luck. I like miniatures games because of the strategy and tactics, but I don't really like haveing to paint and maintain all the miniatures. At the Haunted Game Cafe, I saw a game called Malifaux, which is a miniatures game where each side only has a few miniatures (a starter army has about 5 miniatures, compared with several dozen for a game like Warhammer). One of the factions in the game has the ability to summon new units during a battle, which adds clever new strategies and tricks you can do. Back in Champaign, I looked into Malifaux and they advised against that faction because you have to have the additional miniatures for the extra units in order to be able to summon the extra units. I asked about that here, and they said they don't play that way here. When we came here before on our house finding trip we saw a game store called Duelist Kingdom in Loveland, but that store is closed now. Fortunately, it turned out that the reason it was closed was because it was bought out by a bigger game store called Grand Slam Games and Comics, but I have only been there once so far.
Live Action Role Playing
There is an Amtgard group in Fort Collins, which meets on Sundays, and one in Denver, which meets on Saturdays. I went to the one in Denver just to check it out. It was sizable - about 20 people showed up - but it was not nearly spectiacular enough to be worth the trip all the way up there on a regular basis (I had to take an airport shuttle from Fort Collins to the Denver airport, then another airport shuttle from the airport to the park). During the battlegame there I aplayed an archer, and about halfway through the game the person running the game pulled me aide and said "we have to talk about your arrows." For a second I thought I was doing something wrong, but the real problem was that I was so effective with the arrows he thought it was unfair for the other team. (Part of the reason was that the scenario had the opposing team transporting a torch between two locations, and they are required to stay near the torch. This made it so they were all in one place and easy to hit, and they were unable to chase me down.) I went to the group in Fort Collins, and I was originally planning to take the bus there but I forgot that the buses don't run on Sundays, so I had to take a cab. When I got there the people there said I must be really dedicated to the game in order to be willing to take a cab. There weren't a lot of people here that day so we didn't do a whole lot exciting (apparently the previous week was a big tournament, so everyone was tired from that, plus it's the first week of school). Additionally, I learned that there is a Belegarth group in Loveland that also meets on Sundays. That group has a "small" practice with 20-25 people each Sunday, and then ion the first Sunday of each month they have a "big battle" with 50-75 people.
Wednesday, August 3, 2011
Actually, I'm not technically done yet. First of all, the form is submitted but there's still an electronic thesis deposit process I have to go through. Also, my advisor still thought that some of the citations weren't adequate, so I agreed not to do the electronic thesis deposit until after I had fixed those issues. Also, I have to make sure that all the documentation for the software is updated. But I can easily do all that from Colorado, and I have plenty of time between now and when my job starts.
Anyway, I'm off to GenCon now, and then on to Colorado! I'll make sure to keep you updated.
Tuesday, July 19, 2011
Second of all, another thing I did at Origins is the following. Last time, I mentioned that I didn't get a chance to tell the author of the Hero System books about what I thought about the quality of his writing, but this time, I did. Of course, he said that he "disagreed completely" that the writing was too wordy, and said that the reason for the wordy writing was that his customers demand detailed rules. I am under the opinion that the same information could have been provided in a more concise way.
Rather then talk more about the details of the Hero System, the rest of this post will be about a more general topic - how the differences of opinion between me and some of the other people I play with about the rules of various games reflect fundamentally different ways of looking at game rules.
Consider the following conversation that I had with another Amtgard player. (This was a long time ago, so some of the details like the names of the spells are probably incorrect, but the general idea was the same.)
Him: "There's a gray area in the rules with the 'Dimensional Portal' spell. If two people are both under its effects, can they cast spells at each other?"
Me: "Why? What's unclear about it? The spell says that it takes a player out of game. Under the definition of out of game, it says you can't be affected by anything. So it seems obvious that they can't affect each other."
Him: "Yes, but it's the same out-of-game area."
Me: "What do you mean, out-of-game area? The rules don't say anything about out-of-game areas. You're either out-of-game, or you're not."
Him: "But in Dungeons & Dragons, the 'Dimensional Portal' spell does work that way."
Me: "This game is not Dungeons & Dragons. The rules of Dungeons & Dragons have no force in Amtgard."
The cause of our disagreement was that I was looking at the rules as a self-contained set of information, while he was thinking of the rules as codifying some pre-existing conception of how he thought the game should operate (if you're both transported to the same other dimension, you should both be able to affect each other).
A similar thing happened when the new 4th edition of Dungeons and Dragons came out a few years ago. I was reading some articles online discussing the new system and comparing it to the previous editions, and one of the most common complaints was that the new system "didn't make sense." For example, in the previous edition, fighters generally had only one or a few attacks that they had to keep using, while wizards had lots of spells that they could each use only a couple times per day and after those were done their powers were very weak. 4th edition balanced out the two classes by giving all classes some powers that they could use all the time, and some powers that were restricted to once per encounter or once per day. Lots of people didn't think this made sense because why would a fighter not be able to use a specific move once he had used it once earlier in the day? At first, I was really confused about why this would be a problem. I mean, true, maybe it isn't realistic. But I can't think of any criterion of realism that "I can magically throw a fireball, but only once per day" would pass, but "I can stab the dragon with a sword a certain way, but only once per day" would fail. And there are all sorts of physical phenomena that do happen in real life that are counterintuitive (have you ever watched MythBusters?) so I don't see why the fact that it doesn't fit with your intuitions about how fighting should work should be a problem. Again, this was a case where I understood what was going on because I just looked at the rules as a self-contained system, while others got bogged down because they tried to fit how the rules worked with their pre-existing conceptions of whoe combat should work.
Of course, sometimes things work out the other way around and my method of thinking is a hindrance. One example is some problems I was having with archery in Belegarth. There was a rule that you had to draw your bow back only half way when shooting at an opponent within 15 feet. (The issue is that if you shoot a target at full draw at close range, then the arrow will be going very fast, and is likely to hurt.) People were complaining that I was not following this rule, so I brought a tape measure so I could practice judging distance. This didn't completely help, so I came up with the idea like taking video and then going over it afterward so we can see what the distances were, and whether I was judging them correctly. They said that it wouldn't work because "there are too many variables." I was confused - I thought there was only one relevant variable: the distance to the target. At one point one of them tried to help me by asking me to stand in one place, then backing away and saying "okay, this is 15 feet." When I asked to measure to ensure that his judgement was accurate, he said that "it doesn't matter" whether it's accurate or not. This made me even more confused: how can it possibly not matter?
The problem here seemed to be that I was focusing on the particular rule about 15 feet, while what they probably had in mind was a more general concept about how to do Belegarth archery safely, which is why they thought there were "too many variables," and getting the distance right isn't the most important factor. It seems to me, though, that if the 15 foot rule isn't a good proxy for safety, then why is it in there at all? It would make more sense to say something like "The velocity at impact shouldn't be more than X feet per second," with X chosen appropriately. Then you could test to see what combination of draw distance and ranges given you that velocity (this would only need to be done once for each bow, before any battles).
Basically, I tend to interpret things based on what they say. If the game mentions 15 feet, I assume that they mean 15 feet. If they actually mean something else, then they should say something else.
Sunday, July 10, 2011
PLOT: A small, ragtag resistance force tries to overthrow a universally hated dictator.
PROBLEM: If the dictator is universally hated, why is the resistance force so small? (Perhaps most people are too afraid to rise up, but in order to project his power the dictator would need a police force and army, and those people at least would have to support him.)
PLOT: The last two humans on Earth seek shelter from the vampires.
PROBLEM: If there are only two more humans on Earth, where are all the vampires getting their blood to feed?
Overall, both seminars were fun to go to. One thing that was funny was during the "Internal Consistency" seminar when Zahn was talking about how writers can make their stories more consistent. One example he gave was the "Jurassic Park" movies and television shows, where the security system that is used to keep the dinosaurs in was very poorly designed - "even zoos have better systems for keeping animals penned in." He suggested that one thing writers can do to make their stories better is to do more research. For example, Zahn suggested, if you were writing a story like that you could "call up your local zoo and ask them to explain how to design an impenetrable system to keep animals in = and how that system could be beaten." Of course everyone in the room laughed, because we all had exactly the same reaction - that the response you would get is similar to what would happen if you wore this "Personal Electronics Vest" when going through airport security.
Saturday, July 2, 2011
Leader: “I offer this magic ring worth 120 gold pieces for the girl!”
Boss: “There's no way that's worth that much.”
Leader: “Even if I were overstating its value by half, it would still be worth 60 gold pieces.”
I tried to point out the mathematical error but he didn't understand it. Anyway the boss tried to double-cross us but we got rid of the bad guys. Also, I volunteered as an NPC so I could see the adventure from the monster's eyes.
In TerrorWerks, we were soldiers trying to invade a robotics research facility where a bad guy has uploaded a virus to the central computer which reprogrammed the robots to be hostile. Our goal was to fight through the robots and get to the central computer to install the antivirus software. I played the engineer, and my special power was to unlock the doors – I had a kit with wires that I was supposed to connect between certain points on a grid to light up a bulb, and I also had a gun to defend myself. There were also computers that had information on them, such as that the big “super-robot” at the end has a control panel on the back that you could use to turn it off. When we got to the robot, one of the other players disabled it with a grenade while I ran around back to the control panel. The robot turned back on and no matter how many switches I flipped I couldn't turn it back off. When I tried to run back away from it I tripped over one of the poles holding up a wall and dropped my gun, but fortunately my teammates where there to back me up. Eventually we got rid of the evil robots, put the antivirus in, and got out.
Rising Lash was a relatively straightforward zombie game. We go through a series of rooms fighting zombies, and if you get hit you fall down. You can be healed by a doctor, but you get infected, reducing your combat capabilities. You can get rid of the infection with an antivirus (the biological kind this time, not the software kind) but there are a limited number of those. At the end of the scenario, if you survived without getting infected (or have an antivirus to heal you) then in the next scenario you level up and get extra powers. The scenario we did this time was pretty easy and pretty much we all got out alive.
By the way, if you are into video games you have probably heard about the so-called “freemium” business model. This is where the main game is free but you can spend real money for benefits in the game, such as in-game items. A lot of free-to-play MMORPGs use this model, and apparently some of the LARPs have caught on to the idea. For instance, in the zombie game if you buy one of their promotional T-shirts and wear it to the game you get extra armor. TerrorWerks also sells promotional “swag” and has a tiered reward system where one piece of swag gives you extra health, two pieces gives you a healing item, and so on.
Also, in keeping with the whole “being a hero and helping people” theme, there was a blood drive going on. There was an announcement on the PA systme that said they wanted as many people to donate as possible because there was a “critically fortunately I wasn't able to because I went to Vietnam last year.
Tuesday, June 28, 2011
So here are a few things I learned. First of all, always check to see if there is a bus or train before booking a flight. Second, I wonder why sites like Travelocity don't also incorporate things like buses and trains into their tool - it seems like it would be useful to have a tool that figures out the best/cheapest way of getting from point A to point B whether that involves a bus, train, plane, or some combination. I guess it just doesn't come up that often. Third, always book directly through the airline if you can because it is easier to change your flight that way if necessary. Fourth, according to the Bureau of Transportation Statistics, the Champaign-Urbana airport has an average of 28% of its flights delayed and 6% cancelled, compared with the national average of 20% delayed and 3% cancelled. After I move to Colorado I will usually be using Denver International Airport, which is better at 18% delayed and 1.6% cancelled, which of course makes sense because the people who work at the secret underground base there wouldn't want their evil plans ruined by flight problems. Of course, if there really was an evil conspiracy going on there, information about it wouldn't stay posted on Wikipedia. Or maybe that's just what they want you to think, and it's a clever diversion. (Of course, I don't actually believe that there's a conspiracy or anything, I just thought it was funny.)
But that's just part of the adventure. Next time I will tell you about what happened after I got there!
Friday, June 17, 2011
Things that are...
... things that were...
...and some things which have not yet come to pass.
I wonder what the "non-simplified" version of this game looks like?
Although gamers are not usually major consumers of personal hygiene products, this manufacturer has developed an innovative way to market to this under-served demographic.
A recent "Magic: The Gathering" card set focuses on the conflict between the artifact-based Mirrans (not shown) and the virulent Phyrexians (represented by the symbol on the box). Evidently, the City of Champaign public works department supports the Phyrexians.
Thursday, June 16, 2011
- Clearly, the socially optimal amount to charge for swipe fees is equal to the marginal cost. And the marginal cost is probably very small; I imagine most of the costs of running the transaction system are fixed costs that don't depend that much on number of transactions.
- Of course, that only really matters if debit card transactions are at least somewhat price-elastic; i.e. number of transactions is affected by how much they cost. If the number of transactions is unaffected by cost, then changing the fee just redistributes money; it doesn't affect overall efficiency. (Of course, people do care about how the money is distributed.) And I would imagine that the price elasticity is very low: consumers don't care about swipe fees when they use their debit card (since they don't pay them) and most retailers don't choose not to accept debit cards just because of the fees (except sometimes for small transactions).
- The discussion from both sides seems to be centered on whether it will help or hurt consumers, which is reasonable. The pro-regulation side says that businesses will pass the savings on to consumers, while the anti-regulation side says that will not necessarily occur and banks will be forced to increase other fees or reduce perks like free checking to make up for the lost revenue.
- From the retailer's perspective, the swipe fee is like a tax on the transaction, so whether it's the consumer or the producer that ends up paying it depends on the relative elasticity of supply and demand for the goods, as described here. Of course, almost none of the coverage that expresses opinions about this questions even mentions price elasticity. (You could do a similar analysis to answer the question about whether banks will increase other fees; think of the reduction in swipe fees as like a tax on the banks based on how often their customers use debit cards).
- Of course, I don't have any data on the questions above, so I don't know who is correct. But one thing I did notice is that pro-regulation advocates say it will "help small businesses" and take money away from the "big banks", while anti-regulation advocates say that it "helps giant retailers" at the expense of "small credit unions." My question is: How did the whole "big business equals bad, small business equals good" thing start? I mean, isn't the theory behind capitalism that the way businesses become bigger is by improving efficiency to lower costs and responding to the needs of their customers to increase revenue? Maybe Joe Kernen is right that we are being indoctrinated with anti-capitalist values.
Monday, June 6, 2011
(a) The Auditors, which features stories of taxpayers who have been audited by the IRS, from the initial contact through the final accounting of taxes owed.
(b) Extreme Couponing, in which shoppers save thousands of dollars through strategic use of coupons, store promotions, and similar deals.
(c) Health Care Hustle, which features a "behind-the-scenes" look at the business side of a doctor's office in Oakland, California.
(d) Wikipedia Wars, where contestants compete to use Wikipedia to find the answers to trivia questions while strategically editing it to confuse their opponents.
2. Which of the following is an actual recent scientific finding?
(a) The gene responsible for blonde hair also produces neurotoxins which lower intelligence.
(b) Using Twitter and Facebook immediately after studying for exams improves grades.
(c) The most important factor in determining how much students learn in college classes is how funny they think their professor is.
(d) Showing Apple fans images of Apple products activates the same areas of the brain as showing religious believers images of deities.
3. Sarah Palin recently made which of the following false claims about American history in an interview?
(a) Part of the purpose of Paul Revere's famous ride was to warn the British that they would face American resistance.
(b) Alexander Hamilton once gave a speech warning of the dangers of financial bailouts.
(c) Abraham Lincoln freed the slaves because he wanted to sabotage the Southern economy.
(d) President Kennedy ordered Predator drone strikes on Cuba during the Cuban missile crisis.
Saturday, June 4, 2011
In order to do that, though, they'll first need to cut excessive spending. Unfortunately, nobody wants their own pet program cut.
Maybe the cause of the budget problems is that our children are being indoctrinated with anti-capitalist values in our schools. (He must have gone to a different school than I did, because I don't remember being indoctrinated with anything.)
Friday, June 3, 2011
Wednesday, June 1, 2011
Apparently, this port replicator is not a Jedi Master yet. And what's that on top of it?
As it turns out, its just a little thing to change the "gender" of a VGA connection. (On many different types of connectors, the part that sticks out is referred to as the "male" side, and the socket you stick it into is referred to as the "female" side. The intended metaphor is left as an exercise for the reader. For the answer, see here.)
This pinball machine is in the ACM (Association of Computing Machinery) lounge. As you can see, not all computer science students are just into software; they like to do stuff with hardware too.
This computer is hooked up to a vending machine, and enables you to pay for caffeinated drinks using your university ID. It keeps track of the total amount of calories and milligrams of caffeine purchased.
Not all advancements in technology involve high-tech electronics. One example is the microwave popcorn bag. While versions of this technology date back to 1973, a recent breakthrough holds the promise to significantly reduce cleanup effort.
Tuesday, May 24, 2011
I just finished my classes, so no more tests or exams ever! But I still have plenty of work to do because I have to write a paper for a conference which is due on July 6, and then I have to expand that paper into a thesis which is due on August 8.
Today in the mall in Champaign I found a stall selling "Power Balance" bracelets which are similar to the bracelets I mentioned in the previous post in that they work by the placebo effect. They cost about $30, but you can save a lot of money and buy functionally equivalent "placebo bands" here.
Another thing I am planning to do more often on this blog is to post links to other web sites which I find interesting. One interesting web site I found is Cheap Talk, a blog written by two economists. They have lots of discussions of economic theory applied to a variety of topics including game theory and ticket scalping. (Under the "game theory" tag if you scroll down you will see a post called "how to get bumped" about how to score free airline tickets, and below that is one about ticket prices in restaurants which is also interesting.)
I just got an email asking me to support Illinois athletics by switching my energy provider to "Fighting Illini Energy." One of the options that they say they offer is the ability to choose a plan that provides 50% or 100% of your energy from renewable energy sources. (What does that even mean? I mean, isn't electricity fungible? All of it goes from the power plants, onto the grid, and then into your home. I didn't even think it was possible to track a particular "unit" of electricity from the power plant to your home.)
The gaming club on Saturdays at UIUC is still going on over the summer. Since it is summer the building we normally play in - the English Building - was locked so we ad to go into the student unoin. The only problem was that the area of the student union we played in had a TV tuned to MTV, so whenever a song came on that any of the other players had heard before, they would all start singing along and making lots of noise, and they kept doing that even after I asked them to stop several times. Apparently they thought it was funny. I think what I will do next time is say something like "Let's say you had a friend who was in a wheelchair, and you kept taking the wheelchair away so he couldn't get around. Now maybe you might think it was funny but probably he wouldn't think it was funny. So just like some people have a hard time getting around without wheelchairs, I have a hard time playing games when everyone is making lots of noise. Maybe you might think it's funny to make lots of noise so I can't concentrate, but I don't think it is funny."
Thursday, May 19, 2011
Another thing sort of related - in the mall today I found a stall selling "negative ion bracelets" for $25. It is an ordinary rubber bracelet that (according to the person selling it) had a small amount of volcanic ash embedded in it to emit "negative ions" that supposedly improve your strength and balance. I asked for a demo and he gave me a "balance test" with and without the bracelet, but the bracelet didn't make much of a difference, which makes sense because there's no scientific evidence that the bracelets do anything. Also, it seems that the people who wrote the brochure about it didn't know much science either, because it said something like "negative ions are natural ... when water mist falls to earth, it loses an electron, which turns it into a negative ion." (Of course, electrons have a negative charge, so if the water "lost" an electron it would gain a positive charge.)
And also, something that might be interesting on the Internet - the web site I linked to above is part of a network of "Stack Exchange" web sites which allow you to ask questions and get and look up answers on a variety of topics - it started off with computer programming but on expanded into lots of other fields like math and statistics. It works a lot like Wikipedia in that it is entirely community driven where people post answers to and edit each others' questions.
Tuesday, May 10, 2011
Lots of interesting stuff happened on the interview for Numerica. My flight was originally scheduled to leave at 7:00 AM. I overslept and woke up at 6:30, and rushed out the door in the vain hope of getting to the airport in time. I got there at about 7:10 but fortunately the flight was delayed until that afternoon. I got rebooked on a 2:15 PM flight which gave me time to go back home, do some stuff at school that I needed to do, get the charge for my laptop (which I left at home), then go back to the airport. On the flight from Champaign to Chicago a different professor I know was also on this flight. I landed at the Denver airport and took a taxi out to Loveland. The hotel was next to a strip mall so I was able to go out to dinner and also finish up a presentation on my research, which I gave as part of the interview. The interview went vrey well. During lunch, I mentioned that I was interested in board games, and one of the people who worked there was also interested in board games and knew of some board game stores in the area, and offered to take me to them that evening. It was probably the best interview experience I have ever had.
So I decided to accept their offer, and I will be starting work by the end of August. I definitely think that stopping with a Masters degree rather than continuing with a Ph.D. was the right thing to do. I'll be able to continue doing what I love doing, and I'll also be making a lot more money than I am as a graduate student. I am not sure what I will do with all that money, but there are other people in this world who need the money a lot more than I do.
Monday, May 9, 2011
Monday, April 4, 2011
"Some proposals in Congress would significantly cut student aid - the U.S. House voted to slash Pell Grant funding by $5.7 billion – cutting, on average, $785 in financial aid for over 9 million students."
"over 9 million" * $785 is over $7 billion, not $5.7 billion. (On the other hand, this may make sense if the $785 number is the median, and not the mean.)
Friday, April 1, 2011
Monday, March 28, 2011
The following quote appeared:
"Noyes is one of 103 public schools here that have had erasure rates that surpassed D.C. averages at least once since 2008. That's more than half of D.C. schools."
This statement is not too surprising. If the distribution of erasure rates were symmetrical, then in any given year half of them will be above average. Since the schools above average will change from year to year (if only due to random variation), then over a 3-year period more than half of the schools will be above average in at least one of those years. (For instance, if the erasure rates are random and independent, then each year each school will have a 1/2 probability of being above average, so each school will have a 7/8 probability of being above average in at least one year.)
Aside from this sentence, the rest of the article was actually fairly good statistically. It mentioned that this particular school hasd erasure rates so far higher that it wasn't due to chance, and included a lengthy discussion of possible alternative explanations for the data.
Friday, March 18, 2011
Problem 17: Seeds of Victory
According to the web site, the probability that all four 1-seeded teams will go to the Final Four is 1 in 31.82, while the probability that two 1-seeded teams, one 2-seeded teams, and one 3-seeded team will go to the Final Four is 1 in 14.05.
In the article, Jacobson made the following statement:
"But I can tell you that if you want to go purely with the odds, choose a Final Four with seeds 1, 1, 2, 3.”
For concreteness, suppose that you are asked to pick, for each region, which team is going to the Final Four, and you are only considered "successful" if you correctly pick all four regions. Assuming that the probabilities given by Jacobson's model are accurate, is it true that picking a (1,1,2,3) split is more likely to be successful than a (1,1,1,1) split?
The answer is here.
Wednesday, March 16, 2011
I went to the Engineering Career Services office and got my resume and cover letter looked at, and they basically had me rewrite the whole thing using the format described in the career guide, which made it look much better. I took the new resume and cover letter over to the Graduate College's career services office, and they told me that my resume and cover letter looked very good, and they only had a couple minor stylistic changes. I searched for jobs online and through job posting on bulletin boards in the Computer Science department. So far I have submitted resumes to 9 companies, and have gotten phone interview requests from 2 of them. One of them was MathWorks, which makes Matlab. Another was Palantir Technologies, which makes a data analysis and visualization platform (read the web site if you are interested). They wanted to interview me for a "Business Development" position, and I'm very interested in what that position entails. I'll report back when I see how the interviews go.
And one more thing. When I was in elementary school and people asked me what I wanted to be when I grew up, I would answer "math test-question editor", because I took lots of math tests like the Math Olympiad during that time and often I found the test questions ambiguous. During my online job search, I found an online job advertisement for a math test-question editor. But things have changed a lot in the past 15 years, and I decided not to apply for that job.
Thursday, March 3, 2011
I have two pieces of good news to report:
First, I passed my qual! I haven't got the “official” announcement yet but Jeff told me that the qual has been graded and I passed it.
Second, all the votes are in and I am now going to be an official member of House Valdemar in Belegarth. They are in the process of making the special tunic for me and I will have an official “initiation ritual” next Saturday, March 12.
EDIT: I typed "not" instead of "now" before.
Monday, February 28, 2011
1. So-called "Castle Doctrine" laws give citizens the right to do what?
A. Participate in medieval re-enactment.
B. Use lethal force to defend their homes.
C. Engage in collective bargaining over rent payments.
D. Build moats around their property.
2. Which of the following companies have been recently praised by gay-rights advocates, and why?
A. Verizon, for canceling a planned ad campaign that featured two characters getting "stuck" in a same-sex relationship due to a competitor's poor cell-phone service.
B. Bioware, a video game company, for announcing that the highly anticipated space-adventure video game sequel "Mass Effect 3" will provide the option to have the player's character engage in same-sex relationships with aliens.
C. Facebook, for giving users the option to set their Facebook status to "in a civil union" or "in a domestic partnership."
D. Wizards of the Coast, for printing a series of "Magic: The Gathering" cards that feature pairs of same-sex characters that get bonuses if you have both of them on the field at the same time.
3. A new iPhone app is designed to make it easier for religious believers to do what?
D. Find churches
4. The University of Illinois computer science department took it as praise recently when a report came out showing that the department is number one in what?
A. Academic integrity violations
B. Nobel Prize winners
C. Percentage of students using alcohol
D. Average number of Facebook friends
Thursday, February 24, 2011
The video game "Fallout 3", and its sequel, "Fallout: New Vegas", are set in a post-nuclear-war world where most civilization has been destroyed and the few people remaining alive must scavenge for supplies to stay alive. Each piece of loot that you can pick up has a weight and value. There is a limit to how much weight you can carry, and when you get to a town you can sell your loot for bottle caps (the game's currency) based on its value. The problem of maximizing the total value of items you can pick up while staying within your weight capacity is known as the "knapsack problem" and is a well-known NP-complete problem.
In the game, however, there is an additional complication. You only observe each item one at a time, and because of the dangers and rival scavengers it is impossible to go back and pick up an item that you dropped or left behind. So you have to make a decision about whether to pick up each item, as well as which items to drop in order to make room, as you see each item.
(a) Is there an algorithm that gives the optimal result in all situations? (There is no limit on the running time of the algorithm.)
(b) The "competitive ratio" of an algorithm is the worst-case ratio of the value of the solution found by the algorithm to the optimal solution. For instance, if an algorithm always gives you a set of items with value at least equal to half the value of the optimal solution, then its competitive ratio is 0.5. Does there exist an algorithm for this problem with competitive ratio greater than 0? If so, give one; if not, prove it is impossible.
(Hint: Imagine there was an "adversary" controlling the capacity and sequence of items, and it gets to observe which items the algorithm selects before deciding which new items to present.)
(c) Suppose that the capacity is C, and the highest weight of any one item is M. Give an algorithm for this problem with competitive ratio 1-(M/C).
The solution is here.
Wednesday, February 23, 2011
Tuesday, February 22, 2011
I think Echo360 is a very useful tool, but there are some other features that would help. One thing I think would be useful is to integrate a discussion forum with the lecture capture. The way I would envision this working is that when a student is watching the lecture online, if he has a question he can click a button and type his question in, then the question would be tagged with a timestamp indicating what point in the lecture he asked that. And there would be a way to link to a particular timestamp in the lecture. Then the instructors/TAs can log on and look at the questions, and when you looked at a given question you would have a link to the associated point in the lecture. Or an instructor could answer by pointing the student toward a particular place in the lecture. This would be useful to me because oftentimes when I talk to students, they say the instructor told them something which doesn't sound right to me, but it's hard to clear up the confusion without the lecture in front of me.
Another problem, which is a little more technical, has to do with the sound. The way our setup works is that there are two microphones, one worn by the instructor and one "shotgun" microphone. The one the instructor wears has much better sound quality but only captures what the instructor says, while the shotgun microphone can capture everything in the room. So one of the things I have to do is when the instructor pauses for students to ask questions, switch to the shotgun microphone, and then switch back when the instructor starts talking. This often isn't very reliable and you don't get all the questions. So a useful tool would be to have two or more audio channels going into the system, and it would automatically switch between them depending on who is talking.
I'm also taking a TA training seminar where we are reading the book "Teaching At Its Best: A Research-Based Resource for College Instructors" by Linda B. Nilson. That book talks a lot about how traditional lectures aren't very good at promoting student understanding, and has lots of suggestions for how to improve lectures. For instance, one way of improving lectures is to periodically stop and give students a question to answer and discuss in order to keep them engaged. Something like this could be incorporated into Echo360 - if you had a system like the one I described in the first paragraph, then the instructor could put a question on the whiteboard and ask students to answer it by posting something. It might even be possible to set up a system where the instructor can set the lecture to automatically pause and ask the student a question, and not to continue until the student gives an answer.
Saturday, February 19, 2011
Another thing is they're in the process of voting to see whether I get to become a full member of House Valdemar. So far the vote is going in my favor, but not all the votes are in and several of the key members who are supposed to vote haven't been out to practices in a while and we haven't been able to get ahold of them to get their votes. Maybe they're hiding in Wisconsin.
One thing that this does mean for the blog is that you will get to see more of my "Gaming Math" problems. The main reason I haven't been able to put up more of those problems recently is not because I haven't played any games with interesting math or computer science problems in them, but rather because most of the time I can't actually solve the problems I come up with. But preparing for the qual has helped me get better at solving those kinds of problems so that means that you will see more of them.
Here is a problem:
Gaming Math - Problem 15: "For Science!"
In the board game "Battlestations," players control crew members aboard a spacecraft, and they are sent on dangerous missions. In one of the missions, the players are trapped in a region of space containing N wormholes, and the only way to get out is to go through the wormholes in a specified sequence. The only way of finding out what that sequence is is by using the ship's Science Bay, which allows the player to ask any yes-or-no question about the sequence.
1. In the scenario described in the game, N=4. What is the minimum number of questions required to guarantee figuring out the correct sequence?
2. For an arbitrary N, what is the minimum number of questions required? Find an algorithm that achieves this minimum number, and prove its optimality.
(Hint: Don't forget that you can ask any yes-or-no question about the sequence.)
The answer is here.
Monday, February 14, 2011
- I have my Ph.D. qualifying examination this Thursday and Friday. I have looked at most of the previous quals and it seems like I pretty well prepared for it. Another thing is even if I do decide to only get a Masters degree, passing the qual is a good idea because if I pass the qual I am exempt from the distributional requirements for a Masters (there are still two distributional requirements, hardware and systems, that I haven't taken courses in so I would need to do that if I were to go that route).