You are currently browsing the category archive for the ‘Uncategorized’ category.
I am not the right person to write about Lloyd Shapley. I think I only saw him once, in the first stony brook conference I attended. He reminded me of Doc Brown from Back to The Future, but I am not really sure why. Here are links to posts in The Economist and NYT following his death.
Shapley got the Nobel in 2012 and according to Robert Aumann deserved to get it right with Nash. Shapley himself however was not completely on board: “I consider myself a mathematician and the award is for economics. I never, never in my life took a course in economics.” If you are wondering what he means by “a mathematician” read the following quote, from the last paragraph of his stable matching paper with David Gale
The argument is carried out not in mathematical symbols but in ordinary English; there are no obscure or technical terms. Knowledge of calculus is not presupposed. In fact, one hardly needs to know how to count. Yet any mathematician will immediately recognize the argument as mathematical…
What, then, to raise the old question once more, is mathematics? The answer, it appears, is that any argument which is carried out with sufficient precision is mathematical
In the paper Gale and Shapley considered a problem of matching (or assignment as they called it) of applicants to colleges, where each applicant has his own preference over colleges and each college has its preference over applicants. Moreover, each college has a quota. Here is the definition of stability, taken from the original paper
Definition: An assignment of applicants to colleges will be called unstable if there are two applicants and who are assigned to colleges and , respectively, although prefers to and prefers to .
According to the Gale-Shapley algorithm, applicants apply to colleges sequentially following their preferences. A college with quota maintains a `waiting list’ of size with the top applicants that has applied to it so far, and rejects all other applicants. When an applicant is rejected from a college he applies to his next favorite college. Gale and Shapley proved that the algorithm terminates with a stable assignment.
One reason that the paper was so successful is that the Gale Shapley method is actually used in practice. (A famous example is the national resident program that assigns budding physicians to hospitals). From theoretical perspective my favorite follow-up is a paper of Dubins and Freedman “Machiavelli and the Gale-Shapley Algorithm” (1981): Suppose that some applicant, Machiavelli, decides to `cheat’ and apply to colleges in different order than his true ranking. Can Machiavelli improves his position in the assignment produced by the algorithm ? Dubins and Freedman prove that the answer to this question is no.
Shapley’s contribution to game theory is too vast to mention in a single post. Since I mainly want to say something about his mathematics let me mention Shapley-Folkman-Starr Lemma, a kind of discrete analogue of Lyapunov’s theorem on the range of non-atomic vector measures, and KKMS Lemma which I still don’t understand its meaning but it has something to do with fixed points and Yaron and I have used it in our paper about rental harmony.
I am going to talk in more details about stochasic games, introduced by Shapley in 1953, since this area has been flourishing recently with some really big developments. A (two-player, zero-sum) stochastic game is given by a finite set of states, finite set of actions for the players, a period payoff function , a distribution over for every state and actions , and a discount factor . At every period the system is at some state , players choose actions simultaneously and independently. Then the column player pays to the row player. The game then moves to a new state in the next period, randomized according to . Players evaluate their infinite stream of payoofs via the discount factor . The model is a generalization of the single player dynamic programming model which was studied by Blackwell and Bellman. Shapley proved that every zero-sum stochastic game admits a value, by imitating the familiar single player argument, which have been the joy and pride of macroeconomists ever since Lucas asset pricing model (think Bellman Equation and the contraction operators). Fink later proved using similar ideas that non-zero sum discounted stochastic games admit perfect markov equilibria.
A major question, following a similar question in the single player setup, is the limit behavior of the value and the optimal strategies when players become more patient (i.e., goes to ). Mertens and Neyman have proved that the limit exists, and moreover that for every there strategies which are -optimal for sufficiently large discount factor. Whether a similar result holds for Nash equilibrium in -player stochastic games is probably the most important open question in game theory. Another important question is whether the limit of the value exists for zero-sum games in which the state is not observed by both players. Bruno Zilloto has recently answered this question by providing a counter-example. I should probably warn that you need to know how to count and also some calculus to follow up this literature. Bruno Zilloto will give the Shapley Lecture in Games2016 in Maastricht. Congrats, Bruno ! and thanks to Shapley for leaving us with some much stuff to play with !
Credit for the game that bears his name is due to to Borel. It appears in a 1921 paper in French. An English translation (by Leonard Savage) may be found in a 1953 Econometrica.
The first appearance in print of a version of the game with Colonel Blotto’s name attached is, I believe, in the The Weekend Puzzle Book by Caliban (June 1924). Caliban was the pen name of Hubert Phillips one time head of Economics at the University of Bristol and a puzzle contributor to The New Statesman.
Blotto itself is a slang word for inebriation. It does not, apparently, derive from the word `blot’, meaning to absorb liquid. One account credits a French manufacturer of delivery tricycles (Blotto Freres, see the picture) that were infamous for their instability. This inspired Laurel and Hardy to title one of their movies Blotto. In it they get blotto on cold tea, thinking it whiskey.
Colleagues outside of Economics often marvel at the coordinated nature of the Economics job market. The job market is so efficient, that the profession no longer wastes resources by having everyone read each candidate’s job market paper. That task is assigned to one person (Tyler Cowen) who reports back to the rest of us. In case you missed the report, here it is
Economics is not alone in having a coordinated job market. Philosophy has one, but it has begun to show signs of unraveling. The ability to interview via Skype, for example, has reduced the value in the eyes of many, for a preliminary interview at their annual meeting. In response, the American Philosophy Association posted the following statement regarding the job market calendar:
For tenure-track/continuing positions advertised in the second half of the calendar year, we recommend an application deadline of November 1 or later. It is further recommended that positions be advertised at least 30 days prior to the application deadline to ensure that candidates have ample time to apply.
In normal circumstances a prospective employee should have at least two weeks for consideration of a written offer from the hiring institution, and responses to offers of a position whose duties begin in the succeeding fall should not be required before February 1.
When advertising in PhilJobs: Jobs for Philosophers, advertisers will be asked to confirm that the hiring institution will follow the above guidelines. If an advertiser does not do so, the advertisement will include a notice to that effect.
Its natural to wonder if the Economics market is not far behind. Skype interviews are already taking place. The current set up requires a department to evaluate and select candidates for preliminary interviews within a month (roughly the middle of November to mid December) which is hardly conducive to mature reflection (and argument).
When analyzing a mechanism it is convenient to assume that it is direct. The revelation principle allows one to argue that this restriction is without loss of generality. Yet, there are cases where one prefers to implement the indirect version of a mechanism rather than its direct counterpart. The clock version of the English ascending auction and the sealed bid second price auction are the most well known example (one hopes not the only). There are few (i.e. I could not immediately recall any) theorems that uniquely characterize a particular indirect mechanism. It would be nice to have more. What might such a characterization depend upon?
1) Direct mechanisms require that agents report their types. A concern for privacy could be used to `kill’ off a direct mechanism. However, one would first have to rule out the use of trusted third parties (either human or computers implementing cryptographic protocols).
2) Indirect mechanism can sometimes be thought of as an extensive form game and one might look for refinements of solution concepts for extensive form games that have no counterpart in the direct version of the mechanism. The notion of obviously dominant strategy-proof that appears here is an example. However, indirect mechanisms may introduce equilibria, absent in the direct counterpart, that are compelling for the agents but unattractive for the designers purposes.
3) One feature of observed indirect mechanisms is that they use simple message spaces, but compensate by using multiple rounds of communication. Thus a constraint on message spaces would be needed in a characterization but coupled with a constraint on the rounds of communication.
From Kris Shaw, a TA in for my ECON 101 class, I learnt that the band Van Halen once required that brown M&M’s not darken their dressing room door. Why? Maybe it was a lark. Perhaps, a member of the band (or two) could not resist chuckling over the idea of a minor factotum appointed to the task of sorting the M&Ms. When minor factotum is asked what they did that day, the response was bound to elicit guffaws. However, minor factotum might have made it a point to not wash their hands before sorting the M&Ms. Then, who would be laughing harder?
A copy of the M&M rider can be found here. Along with van Halen’s explanation of why the rider was included:
……the group has said the M&M provision was included to make sure that promoters had actually read its lengthy rider. If brown M&M’s were in the backstage candy bowl, Van Halen surmised that more important aspects of a performance–lighting, staging, security, ticketing–may have been botched by an inattentive promoter.
So the rider helps screen, apparently, whether the promotor pays attention to detail. I think the explanation problematic. It suggests that it is hard to monitor effort expended by promoter on important things like staging for example. So, monitor something completely irrelevant. The strategic promoter should shirk on the staging and expend effort on the M&Ms.
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?