The answer to Problem 18, "Rating Trading", has been posted.
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.
Monday, October 31, 2011
Sunday, October 30, 2011
Mini News Quiz #2
According to a recent article in the Wall Street Journal, a controversial new breed of iPhone apps claim to be able to do what?
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.
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
Hints for Gaming Math Problem 18
ROT13 to read:
18A. Qba'g sbetrg gung pbfgf pna or artngvir.
18B. Fcyvg rnpu abqr vagb gjb.
18C. Guvf zvtug vaibyir nqqvat fbzr nqqvgvbany abqrf.
18A. Qba'g sbetrg gung pbfgf pna or artngvir.
18B. Fcyvg rnpu abqr vagb gjb.
18C. Guvf zvtug vaibyir nqqvat fbzr nqqvgvbany abqrf.
Gaming Math - Problem 18
Problem 18: Rating Trading
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.
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
More Gaming Math Problems Coming Soon!
As you probably have noticed, I haven't posted up many Gaming Math problems in a while though. However, that will soon change. Today at board game night I learned about a new big thing in board game related commerce called "Math Trades." These "Math Trades" are generally run on the web site Board Game Geek and the way they work is everyone posts what games they want and what games they want to trade. Then a computer program uses a mathematical algorithm to figure out how to maximize the number of beneficial trades, which often involves "trade circles" - i.e. if person A has a game that person B wants, person B has a game that person C wants, and person C has a game that person A wants, they can they can trade in a circle. Obviously there are a lot of interesting math problems in here, but I haven't posted any up today because I will have to think about the problem some more in order to figure out what the right way to formulate the problem is. (Of course, I could just read the web site for the software that explains how it works, but where's the fun in that?)
Sunday, October 23, 2011
Shipping Jobs Overseas?
One of the members of our local Belegarth group, John Degraffenreid, is running for Congress as an independent candidate. One of the planks of his platform (direct link won't work; click on "Platform" then "Trade") is that it is "time to hold corporations accountable for moving jobs overseas" and that American corporations should be required to pay overseas workers a "fair wage" to protect other countries from being "taken advantage of" and to eliminate the advantage of "moving jobs overseas."
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).
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).
Subscribe to:
Posts (Atom)