Thoughtful Thursday, Slater and Kemeny Voting Systems

Computing Slater Rankings Using Similarities Among Candidates

by Vincent Conitzer, Electroic Commerce 2006 (Search google.com or citeseerx.ist.psu.edu or scholar.google.com to find the full text of this article.)

As Dr. Connitzer wisely reminds us, the Slater index and Kemeny index are different but related. Let's say every voter gives us their preferences or rankings. Maybe the faculty in a department gives us their ranking of preferences for incoming graduate students. How do we get a ranking for every alternative. A Slater index gives us a ranking for the set where the least number of pairwise elections would be wrong.

We know from Arrow theory that one cannot find a reasonable algorithm to combine the rankings. One of the problems is that a mechanism might be disturbed by an irrelevant alternative. Assume that A wins an election against B, we throw in a candidate Q which everyone dislikes compared to A and B. Then, adding Q or deleting to the list of alternatives should not change whether A or B would win.

20%	20%	40%	20%
C	A	D	A
A	B	B	V
B	D	A	w
Q	Q	Q	B
V	V	V	Q

If A and B had a pairwise election, in the above example, A would win. Any ranking should hopefully have A above B but with Condorcet Paradox conditions, that may not be true. That is the final ranking might have B above A.

The Slater index just adds that ranking a blech factor of negative one with 40% preferring that to the more preferred A above B. If it rated V above Q, that would also be a blech factor negative one, even though only twenty percent would like that bad ranking. A Kemeny index looks at how many people dislike a combination. In the above case, the ranking would get a blech factor of 60% and the second a blech factor of 80%. The goal of both the Slater or Kemeny methods is to reduce the "blech" factor for the number of bad comparisons.

Unfortunately, finding the best ranking in either categorization is NP complete to evaluate. That is they are NP complete to find out what the best ranking would be.

Dr. Connitzer found a good way to compute the best ranking, by finding groups of candidates that can be treated the same for all other candidates, "similar" candidates. Example: A B C D E F G H I J are running.

A defeats E
A defeats F
B defeats E
B defeats F
C defeats E
C defeats F
D defeats E
D defeats F

E defeats G
F defeats G
E defeats H
F defeats H
E defeats I
F defeats I
E defeats J
F defeats J

Dr. Conitzer's would find that E and F are similar. He finds a hierarchy structure of sets and subsets thereof where each level in the hierarchy is a similarity set.

So what? If we have thirty candidates--they could be alternatives in a referendum, with ten issues and 191 voters, his algorithm can find the ranking instantaneously, while other algorithms take fourty seconds or so. And it finds a solution when other cannot.

Now this doesn't handle millions of voters--should we use some sort of approximation?

Improved Bounds for Computing Kemeny Rankings

Vincent Conitzer, Andrew Davenport, Jayant Kalagnanam.

Assume there is an election between two alternatives, A and B. The voters can only tell which is better or more correct with a probability of slightly above 50%. Each voter votes for the one that seems the best to them. We saw that if one simply takes the majority, there is a very high likelihood--in reasonable sized electorates, of getting the correct answer or best alternative. This is Condorcet's theorem.

But what if there are dozens of alternatives. It turns out that the Kemeny method would give us the best answer, and each voter had an imperfect idea of what was the best decision. And other voting systems correspond to other models, which is a different paper and a later Thoughtful Thursday.

Of course, there is no reliable way to solve large instances of these. Dr. Connitzer raised the issue of approximations to the Kemeny method--but is that what people were promised. We have seen very close elections, and certainly to have the result be an approximation that could be wrong. Dr. Connitzer developed algorithms to compute the Kemeny method. I won't give the detailed description because I doubt that the readers are interested and if they are, his article describes it far better than I could. But three idea of operations research/computer science are important

1. graph theory
2. linear programming
3. integer programming

Many other techniques in social choice theory represent elections as a graph. The nodes are the candidates and the edges represent the number of votes in a pairwise election. If A would beat b by 32 votes, then Dr. Connitzer's graph would have an arrow from A to B with a 32 on it. The linear programming relaxation has less than a one percent deviation from optimality which is measured by optiamlity. And if most people agree on an order, e. g., the Nazi Party candidate is not wanted, that improves dramatically the ability to find a good ranking. That seems good, but what if an electorate is highly polarized, say between socialized medicine and no government intervention. One interesting study would be to look at a population where there are two consensuses on very different formulations.

An interesting idea would be that after an election, one could have a competition to determine the optimal Kemeny ranking. Different groups of computing scientists could produce a ranking and its Kemeny distance. (It is very easy to verify the Kemeny distance of a given ranking.) The ranking with the minimum Kemeny distance would be the winner. Thus, an agrieved group who narrily lost an election could pay for supercomputer time to try and find a better ranking that hopefully would get what they wanted. One could have some sort of prize for the team of operations researchers and programmers that found a winner.

As I believe I mentioned, if there are thousands of alternatives, e. g. tax codes with slightly different structures, each voter would vote on a subset of alternatives. Drs. Kenyon-Mathieu and Schudy spoke about this in their article on "How to Rank with Few Errors" where they said "In statistics and psychology, one motivation is ranking by paired comparisons: here, you wish to sort some set by some objective but you do not have access to the objective, only a way to compare a pair and see which is better; for example, determining people's preferences for types of food" or perhaps preference for tax code. (I will Thoughtful Thursday this material here.) These would be combined in the same manner and described here as if each voter gave a full preference order.

NPR presentation on the sociology of the Tea Party Movement

I am sure most of the readers have heard of the American Tea Party movement. Seventeen million are sympathetic to that group, and several supported by them won major nominations in the Republican primary. But what is of interest to this blog is their structure, or lack thereof. is that they have no central hierarchy. They rely on social media to organize networks. The recognize, like Brian Martin did, that if one fights in one elections, one has to keep fighting every two years to keep one's gains.

Sociologists said that it is very difficult to have a national impact and be radically decentralized and not have a leader. Let's look at a example they raised. A member or pseudo-member makes a statement, perhaps a racist one. A news organization calls for a quote. If there is an office and a leader, the chief executive disowns the member and racism. Without an organization, there is noone to say they or are not a member or to expel them. However, with just a coordinator, she or he would summon a sortition jury who could prepare a statement. Of course, those who deal with an organization like a quick decision from the front office. But a randomly choosen group selected from those who made themselves available at a given time and contacted by cell phones can still respond quickly. My University is starting a Presidential Search as Dr. Alvin Goldfarb announced his retirement next June. I asked, "why do we need a Presdent." The issue of someone to be a spokesperson was raised.

deflation, bring it on

Fix the money supply--this causes at least a mild deflation, as technology improves and population increases. It causes a rally in your currency, To be both specific and chauvinistic I will speak in terms of dollars. Mr. Kessler talked in terms of reducing leverage to one in five instead of one in ten giving oil back down to fifty dollars a barrell. My proposal might see oil dropping back to the single digits.

By fixing the money supply, that means each dollar is numbered and tracked in the global electronic fund transfer scomputer system. Thus, it cannot be created by people or individuals or the computer system itself, as done in Heinlein's Moon is a Harsh Mistress. I talked about a global XML EContracting and fund tracking system in my DailyKos blog.

What does this have to do with this blog:

1. Deflation is bad for those who owe debts denominated in a fixed amount of money per month or year and which have to be paid back. Thus, don't do that! When one "borrows" morrow, one gives back a share of income, whether one is an individual or a corporation. If all prices go down, the amount given back to the lender goes down but it would have the same purchasing power. Of course, Dr. Weitzman proposed that workers be paid as a share of the companies gross reenues. Thus, we don't have to worry about the problem that it is hard to cut nominal wages.
2. There are many people who wish to save, particularly for a short term goal. They don't want to be an investor, determining which individuals and business enterprises would succeed. Now we have a financial services industry to put these two together, so people can put their money in a bank, earn a modest short term return, e.g. money market account, and then spend the money. I propose they would simply hold the money as cash. (Not as dollar bills under the mattress, but a computer record that they owned dollars serial-numbered 123463412, 1345632345, 13423455, and 7824563124.)

If there is a real problem with people holding on to cash, simply give sortition juries the right to require individuals or businesses with cash balances to either spend the money or invest the money. (since all money is in one system, one can't hide one's dollars in one bank account or another or in one's mattress--if the dollar is not on the system, it simply does not exist.) They could consider if one's goals or reasons for holding on to the cash for a short term goal are legitimate. If the person refuses, the sortition jury would have the right to simply do it for them--perhaps considering social impact of the investment more than the person would.

Would it not be great if fifty years from now, when senior citizens are talking -- "when I was a youth, a subway ride was two dollars, now I pay twenty cents."

Thoughtful Thursday, more foreign policy

This week we have another paper on international organizations from Democracy's Edges which was the subject for last week's Thoughtful Thursday. ("Citizenship in an era of globalization" of Will Kymlicka)

International organization. Should the individuals participate in its activities, like adding power to the European Parliament at the expense of the Council of Ministers, appointed by the governments. But the people are not pushing this increase. As usual, Wikipedia has an excellent article on European Parliament; it still does not have the formal power to introduce a bill, even though it does have considerable power.

How can people speaking different languages deliberate? The European parliament employs 350 full time interpreters and spends 118,000 Euros per day on interpreters. Would the people of a country prefer to vote on a referendum on how to vote on a Kyoto greenhouse warming treaty, or would the citizens of each country prefer to participate in some gran palaver?

What language? Google is well on the way to allow real-time voice-to-voice translation and it already has text-translation Auto-translation speculated to preserve small languages as there is less pressure on peoples of people who speak a language spoken by a few thousand people. Xiha Life shows that many people who speak different languages can converse.

Some have argued that the bond markets and internatational treaties such as the WTO restrict people's deomcratic options. Dr. Kymlicka is obviously Canadian and he points out how restricted their parliamentary system is. There is strict party discipline and most MP's have little power, just doing some constituent service. Reminds me of the New York State legislature and Three Men in a room.

Miscellaneous from NPR

Buchanan identified studies that most taxpayers don't know how much tax they truly are paying. Here is an estimate. Payroll taxes are 18.7% of income and other taxes such as the add-on to one's telephone bill work out to be 5.4% income. Thus, taxes are about a quarter of one's bill.

________________

I have long believed that college student loans should be replaced by a share of the income after college. A group is doing just that. Although I don't understand why they end after ten years, an arbitary period. If the graduate goes into teaching for the first ten years and then becomes an investment banker versus the reverse. I more see a middle-aged person paying for, or contributing to, a young person's college education. They would pay ten percent of their income for as long as that person lived, funding their retirement. The Tell Me More scenario was someone who started teaching in Mississippi at $31,000.00, who would then pay ten percent of their income for ten years.

___________

Sadly, although Egyptians are often blogging and tweeting about the problems in the country and fifteen million out of seventy-eight million have access to the web, the government remains autocratic. Some cases, they have helped and gotten international attention, in many cases other wise.

_______________________

I blogged about the role of share holders in a modern corporation, sadly often none. Companies would send out a proxy ballot with just one candidate for each position. Now, big share holders who have held three percent of the company for three years will have access. Of course, that is far short of what I advocated.

Miscellaneous

The Wall Street Journal February 4, 2010, A19 CCLV Number 28 "A Short History of American Populism"

Andrew Jackson -- libertarianism as populism. Government programs gave money to the rich. He is of course known for killing the Central Bank. In 1835, was the last time that the United States was debt free. And he opposed road/canal projects. After the Civil war, the Republicans sponsored aid to railroads. As I wrote earlier, the 1850's to 1890's where United States government sponsored the corporate form. The 1890's populism, William Jenning Bryan gave his Cross of Gold speech, because of the rampant deflation which was giving farmers who owed money a problem. But William Jenning Bryan ran several times for president, never winning and getting smaller and smaller percentages of the vote.

Andy Kessler, "Bernanke's Exit Strategy, Tighter Reserve Requirements" same issue

I wrote a lot about the system where banks can loan more money than their deposits. Currently, banks can loan ten dollars for every dollar they have on deposit. And in some cases more Goldman Sachs, Morgan Stanley, Merrill Lynch, Lehman Brothers and Bear Stearns all loaned out twenty times their capital. No wonder they have so much money for bonuses. Should the depositors all run on the bank, the FDIC is there to back the bank.

My Intermediate macroeconomics professor explained how this works, including how having multiple banks has the same effect as having one big bank. I asked him a simple question. Do the banks make profit on the difference between the interest on the deposits and the interest they change to the lender or the interest on all their loans. He said the latter. So if a bank charges an average of ten percent and pays five per cent to its depositors (a rate structure similar to the eighty's), it is earning 75% interest on every dollar deposited. No wonder, they are so willing to give away a free toaster to those who deposit in their accounts or bear the costs of processing checks for the free checking account with $1,000 minimum balance.

Mr. Kessler said this system caused all sixteen panics since 1812. The gold standard is neither necessary nor sufficient--Elizabeth gold smiths would write more gold receipts than gold they received. And in the first half of the 1800's, American State banks would do the same thing. I recall from Galbraith's Money that the Medici's did the same thing.

Stephen Greenhouse, "More Workers Face Pay Cuts, Not Furloughs" The New York Times New York Wednesday August Fourth 2010 Page A1 and A3

L. Weitzman's share economy is based upon the idea of avoiding layoffs by having one's salary be the gross revenue divided by the number of workers. A corrolary of that is a firm cutting pay during a recession or having a policy of no lay-offs. State and local governments are cutting salaries, in some case with agreement from Union. One report says that 22 percent of municipalities cut "some pay and benefits." On the business side, we have: Westin Hotel cutting wages twenty per cent, Sub-Zero, a Refrigerator Manufacturer, is asking for the same thing, threatening to move to another state, ABF Freight Systems asking Teamsters to agree to a fifteen percent cut and St. Louis Post-dispatch, Seattle Symphony and Newsday making about five percent cuts. Reed Smith, a large law firm, lowered first-year associate salaries to $130,000 from $160,000.

From NPR, on the Mortgage Crisis

I blogged several times about using the share economy idea to make mortgages payments a share of one's income. As I assume most know Freddie and Fannie have a major role in the mortgage market. They own or guarantee half of Federal mortgages 5.5 trilliion worth of mortgages. Our Federal Government guarantees them, at first implicitly , now explicitly but does not put this on the budget. Raj Date said that Fannie and Freddie accelerated the sub-prime meltdown by guaranteeing mortgages for lower-priced houses thus causing their value to inflate to bubble-proportions. These government sponsored entities represent a subsidy to "middle and upper middle income home owners." And, perhaps, we should go away from home ownership. Individuals move around much more than in the 1950's, so one has the problem of selling the house when one has to relocate for job reasons. Or in telling words, Americans should not buy an "illiquid, very large, concentrated, leveraged asset."

One of the problems is that a renter has no guarantee of being able to stay in the property long term. Personally, I was fortunate enough to negotiate a permanent lease in 1994, until either I changed jobs, had my parents come join me and we bought a house together, or on their side they remoddelled the place into something not compatible with residential living. It ended up in court when the landlord sold at a fire-sale basis. I tried to negotiate a similar deal with businesses and landlords in the area but was unsuccessful. More on that in a different blog.

Also, of course, there is also status in owning a home.

Happiness

NPR has had two series on happiness. Jiangyin in China is actively trying to make itself conducive to happiness. Xu Dongqing, the Communist party Committee's head of propaganda, said "they are trying to further use people's wisdom and suggestions to help the government do better," not provide "Western multiparty democracy." Research in the United States found that daily mood improves as one's income goes up to $75,000 per year. It does not go up as people increase their income. The famous Marmot Whitehall study found that people at the top of a hierarchy have a better health than those at the bottom, and it is a strict does-response. And those at the top of the hierarchy generally make more.

Thoughtful Thursday: Foreign Policy and International Organizations

Robert A. Dahl, "Can International Organizations be Democratic? A Skeptic's View" and James Tobin's comments that follow (pages 19 to 40).

in Democracy's Edges edited by Ian Shapiro and Casiano Hacker-Cordon

A familiar theme is the public does not have knowledge to exercise a meaningful vote on a plebiscite. These errors in understanding the factual basis for foreign policy issues goes back to the 1930's--and they are not unique to America. The Economist complained that Europeans were not prepared to discuss the European Monetary Union meaningfully when that was coming in.

Ceding sovereignty is an issue for countries with natural resources. Mexico's Constitution does not allow foreign companies to extract oil. At the age of eight, Mexico's children learned about the 1938 decision not to allow foreigners to extract oil. Mexico's oil field production is declining and it is not possible to have foreign invest on a joint-production basis. And it is a political hot potatoes. Could the people vote to approve a joint venture agreement. And in order to keep greedy politicians from restricting the agenda, any foreign oil company can submit a proposal to the populace for approval. (1) But other deeloping countries have had problems with ceding resources. (2) Paul Romer proposed to Madagascar, and others, a Hanseatic league Charter City modelled after Lubeck. A swath of land would be open to investors on an investor-friendly (low-taxes, rule-of-law, etc.) administration. But Madagascar populace was annoyed at leasing land and the president was deposed in a riots and a Fiji lesed mahogany forests to a British non-profit--and a demagogue ceized up against this, even though he supported a rival proposal.

Jimmy Carter, in an autobiographical book Keeping Faith, pointed out the treaty that returned the Panama Canal Zone to Panama at the turn of the Century. He praised the Senators who approved the treaty in spite of American public sentiment against it. He said bad things would have happened had we not been so gracious. As I recall the turnover--I watched discussions of it in 1999 on CSPAN--it passed uneventfully and without riots in the streets :-)

European countries used referenda in sovereignty issues--should all countries do so?

In an international organization, issue is how to weigh the votes. Many international organizations have one vote per country. Others argue that each countries vote should be weighted by population. China and India should have more of a voice in a world-organization than Nauru and Tonga. And Professor Yunker suggested a federal system for the world where one chamber has votes proportional to population as does the United States of America house of Representatives and with the other chamber proportional to wealth or GDP. He also proposed that countries should have the right to exit whenever they want as does Dr. Tobin.

What is the role of participatory democracy in respecting treaty obligations? Most countries do generally keep to their treaty, but dictators certainly have thrown them to the ground and trampled them under their feet. Should the demos be able to vote to abrogate a treaty with a 50.0001% vote, and just rely on people's natural desire to keep their word, or at least recognize the consequences of being unreliable?

Obviously, there are intercultural issues in negotiation between nations. He suggested that negotiators be trained to put themselves in the other shoes and not expect other countrie's negotiators to want to act And I read the, probably familiar, comments that the United States is oriented towards business, the literal content of letters and phone calls, and want to get things done quickly and not take time for socialization. While other nations want more of a time for the business people or negotiators to establish a personal relationship. How would this affect two sortition juries meeting to discuss a proposal to be brought to a plebiscite in both countries, or a sortition jury. Could Paul Kimmel better train a sortition jury than a top negotiator. The latter would have more background and experience and be "better educated." The randomly sselected citizens might be less arrogant and willing to learn.

References

1. Adam Thomson, "National Attitudes Put Break on Reforms" Financial Times London (UK) September 23, 2009, page four and The Economist "The Americas: How many Mexicans does it take to drill an oil well? Mexico's troubled Oil Industry
2. Atlantic Magazine July August 2010 "The Politically Incorrect Guide to Ending Poverty" by Sebastian Mallaby
3. Paul B. Kimmel "Cultural Perspectives on International Negotiations" Journal of Social Issues Volume 50 Number One 994 pae 179 to 196.