Older blog entries for ladypine (starting at number 37)

Preparing Slides

Eli Billauer gave me a tip, which enabled me to complete the chain of operations, and produce a proper pdf:

dvips -Ppdf -G0 thesis.dvi
ps2pdf thesis.ps

My seminar will take place this Wednesday, unbelievably. Finally.

rms and Ted Ts'o In IBM HRL GnuLinux Seminar

On the evening before the Haifa seminar we (35 of us) went to Herzlia to have dinner with rms. Even though his plane was extremely late, he showed up, and was greeted with a great aplause. To my surprise, he did not look at all like his pictures. After we set some order in the crowd, and created a queue for asking his questions, and everybody finished eating and were able to sit down and listen for a change, some very interesting questions were asked.

For example, Stallman was asked about the GPL liscence in research, with regard to mosix. He said that there is no point in research selling out: since it would not increase the amount of money invested in research, it would only bring a temporary advantage to the first who sells out.

The two highlights of the seminar Indeed fulfilled what they promised. Ts'o's leccture was extremely interesting, and he is a great lecturer as well (I even took notes regarding how to make a lecture good, based on his lecture. I hope this proves helpful in my seminar).

Stallman, leaving his shoes by the side of the stage, had a very inspiring speech. He had a few points, in which he asked the audiance for participation. For example, he asked the people to call the operating system GNU/Linux, in order to stress the freedom, instead of the open source or the kernel.

Yesterday Dan Kenigsberg gave a lecture about Hspell. It was a good lecture, which interested a couple of rare birds such as people I work with who enjoy the beauty of Hebrew, as well as my sister. I, on the other hand, enjoyed her questions: what is GPL? what is a hash function? I wish I had been exposed to computers in such a way as haifux, instead of learning basic and pascal, and not knowing what I could do with them.

I hope I can contribute to Hspell more than a couple of odd words, but for that I will require a dictionary at home, which surprisingly enough, I do not have, and ...oh, right- time!

Working on slides for my thesis seminar

or

How to use open source tools to create a scientific presentation?

I had my doubts at the beginning, when I considered creating a presentation without proprietary software, but then I started doing it, and discovered that it was feasible, and even easier, to use those tools:

• LaTeX
  with packages slidesec and graphicx, to create the presentation. Vast equations were easily copied from them thesis. When I think of the horror of inserting them by hand, I get the shivers.
• xfig
  works great and flawlessly, in order to create the drawings I need. No more fighting objects to make them stay in one place!

• dvips -f thesis.dvi &gt thesis.ps
  converts from the dvi format to a postscript which is a more common format. In order to create a postscript which is landscape, instead of seascape, (in other words: Why does my presentation stand on its head??), insert the following line in the TeX file, close to the beginning, though not too soon, or xemacs will have a problem with syntax highlighting):

  \special{! TeXDict begin /landplus90{true}store end } 
  

• ghostview
  will display the presentation just fine.

Of course there are plenty of other open source tools to make presentations, but LaTex outdoes most of them, I believe, when it comes to equations. Now all I got to do is finish writing the slides, for my seminar on the 15 of January.

Once, I used to be a bookworm. Nowadays, I am a bookcrosser. hopefully, I will get more time to read.

Released a couple of books with mulix this morning.

Asked Lital for a logo for HaMakor, the NPO for open source in Israel.

rms and T'so in Israel

RMS intends to come to Israel, and already people are fighting over the right to get him free beer. I never managed to understand the direct link between Linux and beer. Someone raised the idea of interviewing him to an Israeli Linux website, but then nobody came up with questions they would like to ask him, that have not been thouroughly discussed before. I wonder, if we have nothing to ask, how come most of us are dying to see him?

valgrind

I got to the unlikely point of getting the wonderful valgrind to ask me to bug-report. The cause of the mess was the portland group fortran compiler, which made a mess inside glibc.so. g77, as well as other fortran compilers I know, behave quite the same on that specific error: when printing a number with a too short format, they print stars (******) instead. pgf90 chose to segfault. And valgrind went mad.

Founding an NPO

On Friday we had a "founding" meeting of the Israeli NPO for open source and free software. The voting process, which was much discussed, was rather fast. Every one agreed to nominate mulix, gby, sun, Katriel and Doron. Then everyone agreed that I and two other guys would be in the overseeing comittee. Then we had a break, and sun wished to tell Haim, the lawyer, that we used to be married. Haim just laughed, and dismissed the subject. Then nyh noted that mulix is my boyfriend. This fact now made Haim's smile turn solemn. He said that had he known that, he would not have let us run for those contradicting posts.

Later on, after pondering the matter, I resigned from the overseeing committee.

bram,

Revenue of second price auction

a second price auction gives the best revenue for the seller, when there are a lot of bidders: then the revenue approaches the maximal value that anyone is willing to pay- the first bidder's value.

However, if the seller inflates the minimum price to a point abov e the second bidder's bid, then the seller is taking a risk: in his greediness, he might lose the second bidder. After all, he does not know for sure that the first bidder would come. If the first bidder does not come, then the seller would sell nothing at all!

Match making

You are right about the match making: they are really a choice between Pareto efficient statuses. The loser case is still considered a Pareto efficient case, since if he stays alone, and nobody wants him, then he cannot collaborate with anyone to change the match.

Pareto efficiency Which is not Efficient

I will now actually come with an example from my soon-to-be thesis. Imagine you have a computer, and two tasks you wish to run on it. Imagine each task takes two hours. Now arrange so that at first you execute an hour of each task, and then, after 2 hours, you run the rest of the tasks. This allocation is Pareto efficient, since no one job owner can change the schedule alone. On the other hand, if the two job owners collaborated, and used the first two hour slot to execute the first task, and the second for the other. You might eve do it such that the one which finishes last anyway would finish last in this new schedule, as well. This way one would finish in two hours, and the other in four, instead of one in three and the other in four.

Finding the globally optimal solution is not always possible by neither heuristics, nor achieving Pareto efficiency.

bram, you are right claiming that the exchange of cost and benefit is a delicate point. We each have our own utility function, which is the connection between money and other things. This function indeed may be different with various people, or we might even have a utility from money which is not linear (I would care more about the difference beween a million dollar and nothing, than between one million and two).

But the fact that the utility is something which differs among people, and is secret (you usually cannot tell how much I am *really* willing to pay for that camera which is on auction right now, because my cousin gets them cheap), does not mean that you as an organizer of an auction, has to give in to that.

A first price auction, (sealed bid) is a bad mechanism in that sense: nobody ever proposes what they really think the item is worth, cause they are trying to gain something here. The lower they suggest, the more they gain *if* they win. But take the second prize auction: every user suggests a price, the one who suggested the highest price wins, and gets to but the good. At what price? the price that the second best offer gave. Example: Alice says 5, Bob says 10. Bob wins and pays 5.

Now, the user's best strategy is to tell the truth: his/her real valuation of the good. If the user names a lower price, then somebody might win the good at a price in which the user still gains. And why should the user care about the fact that the sum (s)he says is high? after all, it is not as if (s)he is actually paying it- the real price is set by the second high bid. Of course the user would never say more than her/his real valuation:)

Pareto efficiency is a term of stability. Stability is indeed reached when no small group (one, two, does not matter) can make an alteration to their status, without involving others, and be better off. This only means that this is a *local* optimum. Indeed, greedy algorithms are known to "finish", but what optimum do they give?

There is a whole theory about match making (cooperative games), for example, where a valid match is such that there are no two people (man and woman, in that case. I think the homosexual match making is more complicated) who prefer each other over their current status. Another variant is the match making of (US) medical students to hospitals. In both those similar algorithms, if the people who wish to be matched submit their preferences list, a main server can compute a valid, stable, Pareto efficient matching. The only question is, what matching would that be? The matching scheme that was implemented in the hospital-student algorithm creates the matching that is best for the hospitals and worst for the students. Running the algorithm the other way round yields the opposite outcomes, of course.

In short, Pareto efficiency just means the single person is helpless. An overall view of a server should be able to give better results, but then again the complexity of such an optimization is usually too hard.

artimage, what you are trying to do is design a mechanism. The best source of information I know would be

@BOOK{mas-colell, 
  Author="Mas-Collel A. and  M. Whinston and J. Green",
  year="1995",
  title=" Microeconomic Theory",
  publisher="Oxford University Press",
  note="Chapter 23: Incentives and Mechanism Design"
}

Keep in mind though, that file sharing is something usually done without any monetary transfers, while the method used in game theory to make users (in game theory speak- "agents") act according to some desired behaviour, is to introduce payments into the game. A famous mechanism in which truth telling is a dominant strategy is the Clark- Groves mechanism:

@ARTICLE{clarke,
   AUTHOR="E. Clarke",
   YEAR= "1971",
   TITLE="Multipart pricing of public goods" ,
   JOURNAL="Public Choice",
   VOLUME= "18",
   PAGES="19-33"
}

 @ARTICLE{groves,
   AUTHOR="T. Groves",
   YEAR= "1973",
   TITLE="Incentives in Teams",
   JOURNAL="Econometrica",
   VOLUME= "41",
   PAGES="617-631"
}

  

This mechanism is designed to maximize the sum of utilities of all agents, by choosing an optimal "social choice"- choice which affects everybody. In that mechanism, everybody is paid according to the sum of all the others' utilities (calculated according to their declarations). This way, if you tell the truth according to your utility (say, in an auction, you say how much you really think the item is worth). Then, since the server/organizer is maximizing the sum of utilities, and your overall utility is your real utility plus the others' (declared) utility, your own utility coicides whith whatever the server/organazer is trying to maximize. Hence- tell the truth and count on the server to maximize your *own* utility.

Some mails are worth the trouble. I am trying to get the weekly newsletter from the local wine and delicassy store in an open format, instead of a *.doc file. Now that I have explained the problem ("No, thank you, I do not want a fax"), they are working on it.