The job market is a good example of a 2-sided matching market. On one side of the market are the job-seekers, who rank the companies each in weak-order preference and try to convince the companies that they should be ranked highly in their list of preferences. On the other side are the companies, who put a lot of money into recruitment – in other words, figuring out how highly they should rate their applicants. The actual selection process works a little bit like the Gale-Shapley algorithm with the companies being the men proposing, but with a ticking clock (being deadlines), so not all companies have the option to reach out to their top choices if they are late in proposing. The Gale-Shapley algorithm is proven to be optimal, but according to this article, up to 95% of companies “admit to recruiting the wrong people each year.” So if we have an optimal algorithm (for the companies and applicants that play the game right), why are so many companies left disillusioned at the end of the recruitment process?
The problem comes from the ineffective ranking system that companies use. They rely on somewhat insignificant things like college name, GPA, and other outside factors. They also look at where people have worked in the past. If companies see that a candidate has worked for a very prestigious firm, then they will instantly believe that that candidate is a better candidate, even if that person was the worst employee at the firm for that period of time. This is what Talify is looking to fix. By providing a test that actually tests personality, leadership and empathy, which they believe to be absolutely essential to job performance, Talify is giving companies a tool to rank their candidates more effectively, which will lead to closer to optimal recruiting cycles for companies and candidates alike.
Uber is a fairly recent startup that has become one of the biggest players in the ride-hailing industry. In fact, statistics reveal that the total number of Uber drivers signing up has been steadily doubling every 6 months for the past few years. As a company with thousands of registered drivers in a number of big cities, they provide car ride service to increasingly larger numbers of people every day.
What separates Uber from the more classical taxi companies and lead to their rise? Uber’s money-earner is an app that facilitates the workings of a huge producer-consumer market. People want taxi rides, and drivers are able to provide a limited number of this service per day; it is up to Uber to match these producers and consumers with one another at any possible opportunity. To do this, Uber uses software and underlying technology to balance supply and demand by controlling the pricing of fares and allocating drivers to patrol the city. Too many suppliers and precious gas and time is wasted cruising around neighborhoods; too few and drivers are hard-pressed to fulfill the demand.
When drivers have not been allocated effectively, prices can be adjusted to mitigate demand- this is where Uber’s somewhat infamous surge-pricing comes into play. Uber has been known to immensely inflate their prices during periods of time when demand skyrockets- examples being natural disasters and states of emergency. As stated by Uber, however, this does provide more incentive for drivers to get out onto the road, providing more supply.
This brings about a very interesting point; while it may seem on the surface that Uber is simply providing services while participating in the cab market, in a sense, they are also creating their own marketplace. Uber has an immense level of control over both the amount of consumers and suppliers. They can easily increase the amount of possible matchings made in their marketplace, while taking advantage of this situation to increase their earnings. It is no surprise, therefore, that they can easily compete with existing taxi companies, who do not have the capabilities to facilitate this and act more as independent providers, searching for the consumers. Add on the ease of interface, higher efficiency, and clear wait times and Uber can pretty much settle down in its position as overseer.
In effect, Uber has “produced a mirage of a marketplace” that “produces the sensation of independent riders and drivers responding to the natural fluctuations of supply and demand.” On a deeper subsurface level, they actually interfere and influence a considerable amount. Despite this, Uber often states that it simply provides a software application that simply allows connections to be made by drivers and riders. They imply that it is really the users of the app that are facilitating their rides. Uber hides behind its algorithms, foregoing all risk to the drivers and riders using their application.
I recently read an article in which Alvin Roth was interviewed on the topic of matching markets (http://qz.com/421547/nobel-prize-winner-alvin-roth-explains-the-hidden-economics-behind-tinder-marriage-and-college-admissions/). We mentioned the Nobel Prize winner in class when we spoke about his work on the kidney exchange clearinghouse. In the interview he brings up a few interesting examples of matching markets, such as Uber, which is a market between travelers and divers, and Airbnb, which is a market between travelers and hosts. Another very interesting idea he mentioned is the idea of repugnant transaction and its effects on matching markets.
He describes a repugnant transaction as a transaction that some people want to engage in, but others do not want them to engage despite not being personally harmed by it. He considers kidney exchange a repugnant transaction since people may want to engage in kidney exchange for money, but others are against it on principle even though they would not be directly harmed by the transaction. He interestingly points out that these transactions change over time. Another example he gave was same-sex marriage, which he says used to be a repugnant transaction but is becoming less repugnant. It used to be common that people were opposed to same sex marriges event though it would have no effect on them. Now, in light of recent supreme court rulings, this repugnance is not as strong.
In class, we talked about one-sided preference and how agents are matched to items in an efficient way, according to what their preference is. However, in reality, it is sometimes difficult for agents to rank their preferences in a clear and concise way and understand what they actually want. One of the examples given is that users in dating apps often say “no preference” on their profile towards the ethnicity or race of their ideal partner. However, data reveal that people usually gravitate to others like them. As a result, dating app, such as Coffee Meets Bagel, guides users to people of their own race or ethnicity, even if they say “no preference” on their profile. This way, users are able to find their potential partner within a smaller group of people in a more efficient way. That is why big data is so popular nowadays. Big data users statistical model to make decisions and predict what is likely to happen within a person’s life based on the information they have regarding the person. For example, college admissions are hiring are highly effected by big data. We all know that college admission can be a competitive process, because there are limited spots within a college, but there are so many students trying to get into a good college and receive good university education. People might think that a college is considering potential candidates on their merits, however this is not entirely the case. Since most colleges are trying to improve their rankings, they are very interested in increasing the graduation rates and the percentage of admitted students who enroll. Now, they have developed statistical programs to pick students who will do well on those measures, based on their sex, race, behavior on social media accounts and demographic factors. If these factors, according to the statistical program, do not contribute to their graduation rates and your percentage of accepting the college offer, you may find it harder to get into school.
Big data do have the potential to vastly expand our understanding of who we are and why we do what we do, based on scientific and numerical evidence. However, quantitative predicted results do not fully describe who each person is, because our personality and values cannot be quantified, and these characteristics play a big role in determining the future of our lives. People are more than data, hence, it is difficult for data to completely capture the life of a person. Some people are concerned with the fact that the community might give wrong prediction based on wrong data, and people might not get what they actually want. On the other hand, big data might be accurate in predicting what we want, however, won’t we always be exposed to things that we like? People might want to diversify things within their lives and try new things that they have never tried before. What happens when a dating program slowly pushes us to a more segregated society because it shows us the people it thinks we want to see? It is argued that big data is not in its beginning stage and have plenty of room for improvements and advancements. Do you think that big data will have a positive impact within the matching market?
Why are some trading card games more popular than others? Why do games like Pokemon and Yu-gi-oh die out while Magic: The Gathering thrives and expands without any sign of stopping? The simple answer could be due to the marketing of the game, but there is something deeper going on. One of the big reasons that Magic stays “fresh” and is due to the massive amount of trading that goes on. Players of trading card games know that trading and maintaining decks of cards is just as important (if not more for some) than actually playing the game. And the reason that Magic is able to sustain trading among players is due to how it is able to manage its card economy and the card preferences of the players.
When a player plays a card game, they come to the game with the desire to win at the game. However, in order to win the game, they need to have a special deck of cards which corresponds to the metagame of the time. The player has a strict list of ordered preferences for cards that they really want to obtain, yet the cards that they are endowed with are random cards from “booster packs” which they don’t necessarily want. In order to build a powerful deck, they need to engage in the act of trading to get rid of some of the cards they have which are hopefully more valuable to other players who are trying to achieve other metagame deck builds. Welcome to a large two-sided marketplace with initial endowments and strictly ordered preference lists. Time to run our favorite TTC algorithm and make everyone happy, right? Well, not quite. Unfortunately, players sometimes don’t actually know what they want until they see it. So there exists this very large preference for the unknown. Additionally, trades usually happen in small groups of trusted people… something that would not constitute a core matching. Over time, all these small trades between everyone could be said to approximate a large marketplace interaction between everyone, but it is not something that is necessarily efficient or makes everyone happy.
However, what happens when everyone is happy? What happens when everyone has obtained the deck builds that they have wanted via their trading? Well, this is what happened to games like Pokemon and Yu-gi-oh. The players stop trading and the game dies out. They’ve decided that they have achieved the optimal matching of cards and no more changes in strategies occur. Half the fun of the game is stripped away. On the other hand, Magic does something nifty to solve this problem – they release new cards every few months, cards which they manufacture to disrupt the previous metagame. This causes all the players to reevaluate their preference lists, and a whole new trading time period begins. The game stays afloat because the company making the cards forces new higher-order preferences on the players that want to play the game to win. Many people have caught on to this practice and openly call out the company for making the cards they own worth less and less with each new release of a card set, but ultimately it’s profitable business.
As most all are no doubt aware, Donald J Trump is the current frontrunner of the Republican presidential primary. His unorthodox candidacy has disturbed many within the Republican establishment, leading the 2012 Republican presidential candidate Mitt Romney to denounce him in a speech two weeks ago. Of note is Romney’s recommendation to combat Trump’s rise – “due to the party’s delegate apportionment process, he’d vote for Rubio in Florida or Kasich in Ohio, if he lived in any of those states”. This is a prime illustration of tactical voting, which demonstrates why the current US electoral system is not strategyproof.
Elections can be modeled as one sided markets in which voters (agents) select candidates (houses). Voters typically have weak preferences (Voter A may most prefer candidate X but be indifferent between Y and Z). The United States presidential election utilizes the First Past the Post (FPP) aka Winner Take All mechanism in which each voter privately indicates their top choice and the candidate with the most votes wins and is assigned to all voters, so to speak. The format of the primary election (that chooses the presidential candidate for each party) varies by party and state. The Republican primary in many states is at least partly FPP as well. Ideally this system results in a chosen candidate that is preferred by the most voters.
Tactical voting is when a voter does not vote according to their true preferences in order to prevent an undesirable outcome. Thus if tactical voting is a rational approach then the system definitely isn’t strategyproof. To show why tactical voting happens in FPP, let’s say we have voters A,B,C,D,E and candidates W,X,Y,Z. The preferences are as follows:
If everyone votes for their top choice, W gets 2 votes and everyone else gets 1 so W wins. However, W was the last choice for the three voters who did not vote for them. In addition, Z was the first or second choice for these voters. Thus C and D might tactically vote for Z instead of their top choice in order to ensure they receive a candidate (Z>W) that they prefer.
How would voters know which of their first, second, third, etc. choices are their best bet for preventing their last choice from succeeding? Those factors vary, but in a state primary that is often the local candidate (such as Rubio in Florida or Kasich in Ohio).
None of this is applicable when there are only two candidates, such as in the current Democratic primary. And it may not seem applicable in the general election either, but that is because FPP results in a two-party system that makes third party candidates susceptible to being shafted by a tactically safer pick from the two main parties. The CGP Grey video linked below explains this in more detail!
When we consider the problem of college admissions, we often model the problem as a variant of the Gale-Shapely Algorithm. We say that our agents in the system are both students and universities, and each of the groups of agents have strict preferences. However, what are the metrics that go into this process in a real-world situation? According to the New York Times and The Atlantic, a lot more factors come into the decision process than we think.
Jennifer Wallace reports that for prospective students, high school is a “time for maturation, self-discovery, learning and fun.” Selecting which colleges to apply to is one of the most important decisions most high school students make, and their decision can affect the rest of their lives. What factors are considered when forming the preferences on the student side? Course of study: Students may primarily select a school based on what options they have for academics/course of study. Academic Environment: The academic environment involved with a college application can either be very stimulating or very discouraging depending on the drive and intelligence of others. Diversity: For many students, attending a campus with great diversity is important. Deadline/Application: Deadlines and more rigorous applications themselves can actually serve as a dissuasive construct for students on a tight time budget. Extracurricular Activities: The spread of a school’s options of extracurricular activities or sports can also be an important factor in choosing a school.
However, it seems that universities themselves have a much different range of qualities that they look for in a candidate. What factors are considered when forming the preferences on the university side? Numerical Indicators: Perhaps the most initially restricting metric that colleges use are numerical indicators, primarily a student’s GPA and SAT/ACT scores. However, The Atlantic reports that rather than some inherent rank of individuals, admissions teams rather focus on fulfilling Diversity Goals. For example, a college has certain quotas it must meet for sports teams, bands, alumni relations, and a variety of other disciplines. Well-Roundedness: As a result of this process, colleges put a strong weight on having both well-rounded individuals as well as diversity and a well-rounded admissions class. Demographics: Conley reports that race, gender, age, ethnicity, and legacies are by far the most significant determinants of the admissions decision. Interviews: For applicants admissions officers are on the fence about, an interview may sway their decision one way or another.
Is the Gale-Shapely algorithm a good model? As we have seen, the Gale-Shapely algorithm deals primarily with rank-order preferences. However, the process that we have described is so diverse, and has a wide range of qualities that both students and universities have preferences for. Some factors for either students or universities become more important, and even at different stages in the process. Diversity Goals may not be officially advertised on the marketing materials of a university, but that doesn’t mean they aren’t an important factor. Hitting diversity goals does play a large factor in the process. Colleges also consider the admissions classes as wholly as possible, and have a lot of goals to meet as far as diversity and well-roundedness go. Thus, rank-order preferences perhaps do not do an adequate job of describing how a college prefers one applicant to another and vice versa.
Airbnb is a rapidly growing start-up based in Northern California that matches people who are looking for temporary housing with hosts would like to rent out their place for a specific period of time. The founders originally got their idea because of the skyrocketing cost of housing in the Silicon Valley. Hosts can accept or reject requests depending on their preferences. Airbnb is an interesting application of stable matching with respect to the mobile exchange economy. This stable matching involves two-way choices. The original algorithm for Airbnb relied on the following assumptions: there is an equal number of hosts and guests, the hosts sort the guests by preference, no host prefers to leave their house empty, and every guest wants a room (they can’t be homeless). With these assumptions, it is possible to find a Pareto efficient matching using some form of Gale and Shapley’s algorithm. Host preferences are decided by the desire to maximize compensation and the most time-appropriate guests.
Additionally, Airbnb takes personal ratings for both the hosts and guests into account in the matching. However, Airbnb is also still a relatively new company and their algorithm is not perfect, i.e their mechanism is not strategy-proof. Recall that a mechanism is strategy-proof if telling the true preferences is a dominant strategy. In the case of Airbnb, a guest can actually improve their matching by lying about the amount of time that they require housing, either overstating or under-stating the time. For instance, a host will list a housing with the preference that they want a guest who will stay for at least 4 days. The guest who wants that listing can then lie and say that they will stay for that period of time and then simply leave early. This effects their rating, but many people just create new accounts for next time. So, Airbnb is a great new company with lots of potential but it still has some quirks and the company recently has started using machine learning to solve these issues.
I talked to a recruiter here at Cornell.
Microsoft’s Xbox One is perhaps most famous for its online multiplayer experience. Call of Duty and Halo are two notable series that attract a high number of online players. These games involve team matches as well as free for all matches. The skill the online participants varies dramatically, and it is therefore reasonable to expect that Microsoft matches opponents with similar skill, while simultaneously attempting to minimize the time it takes to find a match in order to increase the enjoyment for all involved.
Microsoft uses a complex method to determine the ‘skill’ level of each player based on the numbers of wins and losses against players of certains ‘skill’ levels. This ‘skill’ level then determine the non-strict rank order preferences for this player as they prefer players with a ‘skill’ level similar to theirs. In order to begin a matching, a few random players, known as the ‘host’, are selected from the list of waiting players. These ‘hosts’ then acts as the ‘agents’ and the remaining players act as the ‘goods.’ Some ordering over these agents must then be formed. It seems reasonable that this ordering would consider the time each ‘host’ has been waiting and prioritize those with the longest wait time. Teams are then be formed as the ‘hosts’ match with the players whose ‘skill’ level is closest to theirs. When a full team is formed, all participating players begin their respective games. This process is repeated indefinitely with the remaining players.
This method is not pareto efficient as the player’s ranking are not strict. It is also interesting to note that this method does not necessarily minimize the time that each player is waiting, rather it prioritizes the matchings with similar ‘skill’ levels and only consider time when determining the order of the ‘hosts.’ This is obvious when one attempts to play online games on Xbox One when a low number of participants are online as the time it takes to find a match can increase significantly.
On a very basic level, financial markets can be understood as matching markets with both constantly changing agent preferences, object availability, and agents. Instead of thinking of people as agents in this market, think of dollars as agents where sets of dollars happen to have the preferences of a particular person. This simplifies the market from one person – multiple financial instruments to one dollar – fraction of a financial instrument. A dollar’s preferences are defined by what fraction of each particular financial instrument it sees itself equal or greater in value to, and ordered by how underpriced the dollar thinks an instrument is. For instance, if a dollar thinks it is equal to 1 share of stock A and 2 shares of stock B, it would be ambivalent between matching with 2 shares of stock A and 4 shares of stock B, but it would prefer to match with 2 shares of stock A as opposed to 3 shares of stock B. A dollar will not match with an instrument it thinks is worth less than it. Accordingly, preferences in this market are neither strict nor complete.
Objects are financial instruments (e.g. stocks, bonds, futures, etc.) differentiated by both type (Stock A vs. Stock B) and price. To simplify matching, assume that an object is a fraction of a financial instrument valued at exactly $1 by the seller.
The market is thus a bipartite matching between dollars and fractions of financial instruments, where each dollar’s owner (a person) controls its preferences, and each object’s owner (also a person) sets its price (the fraction of that security in the market for $1). To make the market function, we must impose a matching strategy. A type of serial dictatorship is a natural fit for this market, and indeed the only possible strategy. Since the buyer may decide not to go through with a proposed transaction, the most efficient way for the market to function is for a dollar, when it is its turn, to be paired with one of its most preferred financial instruments. If this is not the case, then the dollar will decline the offer. This is possible because many transactions may be carried out simultaneously, so all dollars have the same priority. If two dollars simultaneously try to match with the same security, then some priority may be enforced over the dollars.
This market does not stop instantly because of peoples’ changing preferences. A person may decide to sell a financial instrument at any time or to buy an instrument at any time, so the lists of agents and objects are constantly growing as more buy & sell orders are placed, and shrinking as matches are made.
It is possible to use this agent-based setup of a financial market to create a rather good simulation of actual financial markets. As LeBaron discusses in his paper “Agent-based Financial Markets: Matching Stylized Facts with Style,” the price behavior & trade volume of a market can be simulated by tuning the behavior of the people in the market. LeBaron’s approach was to give different simulated people in the market constantly-updating preferences based on some variable amount of history and some variable set of financial statistics to care about. He finds that many market properties such as trade volume and volatility among others may be drastically changed by range of preferences he gives people in the market. Increasing the amount of historical data participants in the market consider and increasing the similarity of the factors that market participants consider in deciding their preferences tends to decrease volatility in the market, while increasing heterogeneity in statistics considered & decreasing memory length of participants significantly increased volatility.
This approach to analyzing financial markets is distinct in both its ability to model trading volume and its intuitive sense.
Blake LeBaron, Brandeis University: Agent-based Financial Markets: Matching Stylized Facts with Style, retrieved from http://people.brandeis.edu/~blebaron/wps/style.pdfkeep looking »