You are currently browsing the category archive for the ‘Uncategorized’ category.
A Markov Decision Problem (MDP) is a model for sequential decision making, in which the underlying state of nature evolves in a stationary way. An MDP is given by a set of states S, an initial state s(0) in S, a set of available actions A(s) for each state s in S, and, for each state s in S and available actions a in A(s), a payoff r(s,a) and a probability distribution q(. | s,a) on S.
The process starts at the initial state s(0). At every stage n, the current state s(n) is known, the decision maker chooses an action a(n) in A(s(n)), receives the stage payoff r(s(n),a(n)), and a new state s(n+1) is chosen according to q(. | s(n),a(n)) and is told to the decision maker. The decision maker’s goal is to maximize the discounted sum of his stage payoffs:
sum-over-n-from-0-to-infty of λ-to-the-power-n times r(s(n),a(n)).
The value of the MDP, that is, the maximum that the decision maker can obtain, depends on the discount factor λ. Denote by v(λ) the value function of the MDP. Which functions can be obtained as the value function of some MDP with finite sets of states and actions?
From now on I restrict the discussion to MDP’s with finite sets of states and actions. Blackwell (1965) proved that for every discount factor λ the decision maker has a pure stationary optimal strategy. It is easy to see that the payoff that corresponds to a pure stationary optimal strategy is the solution of a set of equations, which are linear in λ, and whose coefficients are determined by the payoff function r and the transition function q. It follows that for every pure stationary strategy σ, the corresponding payoff function g(λ ; σ,s) is a rational function of λ. Since there are finitely many pure stationary strategies, we deduce that the value function is the maximum of finitely many rational functions.
Can we obtain any maximum of rational functions as the value function of some MDP? The answer is negative. For example, since the set of states and actions are finite, the payoff function r is bounded, say, by M. In particular, the payoff function of any strategy is bounded by M/(1-λ). In particular, any rational function whose denominator has a root inside the unit ball of the complex plane, or that has a root on the unit ball of the complex plane that has multiplicity larger than 1, cannot be the value function of an MDP.
Is that the only restriction that we have? The answer is still negative. It is not difficult to see that the roots of the denominator of the payoff function of a pure stationary strategy are the inverse of the eigenvalues of the transition matrix, which by a known result in matrix theory must be unit roots, that is, for any root ω of the denominator (which is a complex number) there is an integer k such that ω-to-the-power-k is equal to 1. Thus, a rational function whose denominator has a root that lies on the unit ball of the complex plane and is not a unit root cannot be the value function of an MDP.
Is that all? Yes. Let F be the set of all rational functions f : [0,1) → R that satisfy the following property: any root of the denominator either (a) lies outside the unit ball of the complex plane, or (b) lies on the unit ball of the complex plane, has multiplicity 1, and is a unit root. Let V be the set of all functions that are the maximum of finitely many functions in F. A function v is the value function of some MDP if and only if it is in V.
In this post I outlined one direction of the proof. Anyone who is interested in reading the construction that proves the other direction is referred to this paper.
In a previous post I wrote on my experience as a consultant to participants in auctions. I was interested to hear the other side of the coin: how do the ones who set the rule of the auction perceive the competitive situation they are in charge of. To answer this question I met Dorit Levy Tyller, a well known Israeli advocate who has decades of auctions in her professional past.
According to Ms. Levy Tyller, the issue that bothers her most is coordination among the bidders. In a small country like Israel, in which everybody knows everybody else and have friends who know the rest, participants do their best to talk, exchange information, and dissuade others from increasing their bid. When the bidders are all present at the same hall, the auction turns into an oriental bazaar with a lot of psychological pressure on participants.
To overcome this difficulty, Ms. Levy Tyller assigns each participant to a different room and asks the participants to arrive to their designated rooms at different times. During the auction she moves with her team from one room to the next, informing each participant of the current highest bid and asking them whether they increase their bid. This is a slow process that requires the participants’ trust in the auctioneer, a trust that she gained with the dozens of auctions she had already organized.
What are the issues that affect the participants’ behavior? According to Ms. Levy Tyller, the expectation to win the auction and the tension that builds along the process causes the bidders to increase their bids. Pressure from other participants, on the other hand, hinders price increase.
Most winners are the calculated and level-headed participants. Anxious bidders who make plenty of noise usually quit before the end. Moreover, those who come prepared and know well the status of the auctioned item, tend to win more often.
At the end of our conversation Ms. Levy Tyller admitted that I was the first game theory consultant she ever met. I take it as a good sign: the utility function of game theorists puts higher weight to research and teaching than to consulting jobs. I am glad to be part of this group.
Trump’s rise in the republican polls puzzles many. It shouldn’t. He is the Putin that some republicans have longed for. Here is a sampling:
I looked the man in the eye. I found him to be very straight forward and trustworthy and we had a very good dialogue.
Mike Rogers, GOP chairman of the House Intelligence Committee:
Putin is playing chess while Obama is playing marbles.
Look it, people are looking at Putin as one who wrestles bears and drills for oil. They look at our president as one who wears mom jeans and equivocates and bloviates.
But he makes a decision and he executes it, quickly. Then everybody reacts. That’s what you call a leader.
If you think the comparison to Putin far fetched, here is Putin:
For the first time in the past 200–300 years, it (Russia) is facing the real threat of slipping down to the second, and possibly even third, rank of world states.
Now, compare with Trump’s slogan to make America great again.
Lamar Smith’s new bill to ensure that NSF research advances the national interest does not go far enough. Smith who is Chairman of the House Science, Space and technology committee writes:
We must set funding priorities that ensure America remains first in the global marketplace of basic research and technological innovation, while preventing misuse of Americans’ hard-earned tax dollars. Unfortunately, in the past NSF has funded too many questionable research grants – money that should have gone to projects in the national interest. For example, how does the federal government justify spending $220,000 to study animal photos in National Geographic? Or $50,000 to study lawsuits in Peru from 1600 – 1700? Federal research agencies have an obligation to explain to American taxpayers why their money is being used on such research instead of on more worthy projects.
To ensure that the NSF is not profligate, the bill requires that each grant award
“be accompanied by a non-technical explanation of the project’s scientific merits and how it serves the national interest.”
Why stop with the NSF? Public education consumes an even larger share of my tax dollars. Why must I support the good for nothing offspring of my neighbors who grow up to be actors, musicians and worse, number theorists? If they want their children to be artsy-fartsy pseudo intellectuals they should do it on their own dime. Would be parents should be required to submit, a grant proposal justifying their desire for children. Each successful award should be accompanied by an explanation of how their child will serve the national interest.
There are 16 republican party candidates vying for 10 slots in the first official debates to be hosted by Fox news. Disappointing is the fact that competition between TV networks has not risen to meet the challenge. MSNBC, for example, should take the opportunity to lean in and invite the 6 who don’t make the cut to a debate on their network. Better still, for the same day and time.
According the simulations in the New York Times, Kasich, Jindal, Fiorina, Graham and Pataki will most likely not make the cut. One of Perry, Christie and Santorum will by chance make the cut. Importantly, the alternative debate would not contain Trump. Or Cruz, who by some accounts has not left any part of Trump’s posterior unmoistened. Spun right, MSNBC could market their alternative debate as the one for grown ups while the official one would be for the children.
To make all this work, they should invite Kasich, Jindal, Florin, Graham, Pataki, Perry, Christie and Santroum now and ask for commitments before Fox announces it selections. For the three on the bubble, it gives them the chance to say no to Fox before being barred. This may be attractive to each of them. It might cause an unraveling of the Fox debate. Which debate would Bush, for example, prefer to be a part of?
Finally got around to reading the PCES report on economics education at Manchester. The Francis Urquhart half of my dual selves was duty bound to dislike it. My Urquhart self, would urge the authors to switch subjects and find fulfilling careers in one of the caring professions, like, personal incontinence counselor. My milquetoast self prevailed and I buckled down to read it.
The report raises two issues and its writers have made the mistake of conflating them or at least not separating them clearly enough. The first is the effectiveness with which economics is taught. The second is what is to be taught.
On the first, the report makes for depressing reading. It summarizes an economics education as dull as ice fishing. For those unfamiliar with ice fishing, it is a sport (and thats being charitable) practiced by the inhabitants of Minnesota and the remoter parts of Wisconsin. In dead of winter, one drives a large vehicle over a frozen lake. If that were insufficient to tempt fate, one then cuts a hole in the ice for the ostensible purpose of catching fish. In practice one sits around the hole drinking prodigously while trying not to fall in. Beans, flatulance and an absence of sanitation figure prominently.
On the second, the report’s authors write
Our economics education has raised one paradigm, often referred to as neoclassical economics, to the sole object of study. Alternative perspectives have been marginalised. This stifles innovation, damages creativity and suppresses constructive criticisms that are so vital for economic understanding. Furthermore, the study of ethics, politics and history are almost completely absent from the syllabus. We propose that economics cannot be understood with all these aspects excluded; the discipline must be redefined.
Exposure to history, psychology and politics? Of course, yes. Within the US system this happens naturally as a function of breadth requirements. Students are not shy about trying to reconcile what they have learnt in Psychology and what they are mastering in Economics. It makes for a lively classroom.
What about these alternative perspectives? In for a penny in for a pound, so I decided to read a paper by Steven Keen. Keen, as far as I can gather is one of the leading lights of these alternative perspectives. The paper I read (co-authored with Russell Standish) appeared in Physica A and can be found here. If you’ve not heard of it, there is a good reason for that. Continue to ignore it. Pauli might have described it thus:
Reading it lowered my IQ, something I can scarce afford to do. If this is representative of what passes for alternative perspectives, the writers of the PCES should leave economics and find fulfilling careers as incontinence counselors. Finally, for those who think my description of Keen and Standish uncharitable, I refer them to the following by Chris Auld. Stamping out ignorance is a thankless task and one is cheered to see there are some who take it on.
The urge to promote these alternative perspectives is to be found across the Channel as well. There, a sub group of scholars and nescafe society currently wished to form a separate group so that they may be evaluated by different norms. Jean Tirole, in a letter to the State secretary in charge of Higher education and Research in France, argued against this. A response can be found here.
This is not a post about academia, economics, or game theory. It is a post about life.
Today I am going to meet my French teacher for our weekly session, and I wanted to prepare an interesting topic for discussion. I pondered what can be an appropriate subject, and the words “the most gifted woman in the world” popped into my mind. Who is that woman and what did she do?
I typed “The most” in Google search bar. Auto-complete had few suggestions:
The most violent year
The most expensive car
The most expensive watch
The most dangerous game
The most beautiful woman
I went on. “The most gifted”. Auto-complete tried to read my mind:
The most gifted psychics
The most gifted child in the world
The most gifted man who ever lived
The tenth option was
The most gifted rapper in Nigeria
yet no mention of women.
Let’s continue. “The most gifted wo”. In how many ways can you complete this search? Two.
The most gifted child in the world
The most gifted person in the world
Fine, let’s add another letter. “The most gifted wom”.
Nothing. Not a single auto-completion. I beat Google. Probably everyone else know the answer and therefore nobody looked for it before me.
I am a stubborn guy. “The most gifted woman in the world”. Google is even more stubborn than me. They figured out that I mistyped my search phrase, and made few suggestions, in which the word “woman” was replaced by another boldfaced word: “child” and “person”. In fact, they thought that it is more probable that I search for “The most gifted psychics review” than for a gifted woman. Does this say something about me, about Google, or about the phrases that we search on the internet?
I did not give up and pressed “Enter”. The list that I got involved only (female) singers. Only? Almost. The tenth link was to “Support for Gifted Mothers: America Is Not a World Leader”.
I suspected that my misunderstanding with Google is due to language issues, and that the word “gifted” might refer to people’s vocal abilities, so I searched for “The most gifted man in the world”. Unfortunately I did not get any male singer. The first three pages referred me to the TV series “A Gifted Man”, number 30 pointed to King Solomon on a christian site, yet the title of number 32 was more promising: “Ten People with Unbelievable Talents”. Yes, I told myself, I finally got a proof that our world is full of chauvinism. I clicked on the link and found out that the most talented person in the list succeeded in pulling a truck with his XXXX. I did not bother to check the achievements of the other nine.
If this is the most significant accomplishment of men, no wonder auto-completion failed.
The world may be interested in the whereabouts of Vladimir Putin and whether Elton John’s boycott of Dolce and Gabbana turns out successful. Here, in the holy land, we wait for the elections to the parliament that will take place this Tuesday. The elections, which should have been an easy stroll for acting prime minister Benyamin Netanyahu, turned out to be a difficult trek.
There are 120 parliament members and two main candidates for the position of prime minister: Benyamin Netanyahu, who heads the right-wing parties, and Isaac Herzog, who heads the center-left parties. The way a government is formed is that after votes are counted and the 120 seats are divided among the parties, largely in proportion to the number of votes they got, the leader of each party recommends to the President of the state a person, which that party backs for the post of prime minister. The President then asks the person who he believes has the highest chance of creating a coalition to try and make a coalition. If that person fails, then the President asks another person to form a coalition, and so on.
Latest polls say that the parties that support Netanyahu will get about 55 seats, and the parties that support Herzog will get roughly the same number of seats. The remaining 10 seats will go to a newly formed party, headed by Moshe Kahlon, who said that he would recommend nobody to the President. Why did he say it? On the one hand, Kahlon was a parliament member of Netanyahu’s party (and a minister in Netanyahu’s government), and his voters come from the right wing. Saying that he will recommend Herzog is a death strike to his party. On the other hand, he was very critical about Netanyahu’s conduct and poses himself as “the true representative of the right wing”, and so he cannot say that he will recommend that person whom he thinks is not a good prime minister.
Who will then be the prime minister? PredictIT.com estimates at 56% the probability that Netanyahu is reelected. And if not? Then Herzog, as there is no one else.
Almost. Think of the situation from the eyes of game theory. Suppose that neither Netanyahu nor Herzog are recommended by more than half the votes. Herzog is in a bad shape: the Arab party is supposed to recommend Herzog, and polls predict that it will get about 13 seats. Traditionally the Arab parties are not invited to be part of the government: Herzog will have to make a coalition of more than 60 members excluding the Arab party; this is tough. Netanyahu is in a bad shape as well; polls predict that his party will lose quite a few seats, and if he will not be recommended by more than half the members of the parliament, he might be kicked out by his own party. So who can be the new prime minister?
I ask you to consider the swing voter, Kahlon. Since he comes from the right wing, all parties in the right wing will prefer him to Herzog. All the parties in the left wing will prefer him to Netanyahu or to any other candidate from the right wing. This is a hell of a reason not to recommend any of the two to the President.
Is my theory right? Will the swing voter use his power to become the real winner of the elections? We will have to wait a few weeks and see for ourselves.
This last week on Monday the Israeli Ministry of Communication auctioned 8 bands (each band of 5 mega-herz) for the use of fourth-generation cellular communication. The auction was interesting from a game theoretic perspective, and so I share it with the blog’s readers.
The rules of the auction are as follows:
- The auction is conducted on the internet, and each participant sits in his office.
- The minimum bid is 2,000,000 NIS per mega-herz (meaning 10M per band).
- Bids must be multiples of 100,000.
- No two bids can be the same: if a participant makes a bid that was already made by another participant, the e-system notifies the participant that his bid is illegal.
The auction is conducted in round.
In the first round:
- Each bidder makes a bid, which consists of the number of bands it asks for and the price he is willing to pay for each mega-herz. As mentioned above, no two participants can offer the same price.
- The e-system allocates the 8 band between the participants according to the bids: the bidder with the highest bid gets the number of bands it asked for, then the bidder with the second highest bid, and so on, until the 8 bands are exhausted.
- Each participant is told the number of bands it was allocated.
- The price in which the 8th band was allocated is called the threshold and posted publicly.
- The minimum price for the next round is the threshold + 200,000 NIS.