Thursday, August 26, 2010

Killing the eBay sniper

When it comes to online auction, a sniper is a bidder who makes his bid at the last second with the intention to outbid the current highest bidder without giving him a chance to bid again. Here is an example of a sniper in action. Notice that the sniper (r***a), contrary to the name sniper may imply, is not actually very discreet. He started showing interest about an hour before the auction ends, but could not become the highest bidder until the last second.

We can see that f***f, the person who got outbid by the sniper, only bid once. He's a traditional eBay bidder who takes advantage of the so-called proxy bidding. Proxy bidding lets the winning bidder pay the amount bid by the second highest bidder plus a small increment, the least amount the winner bidder would have to bid in order to outbid the second person. While proxy bidding saves f***f tons of trouble, when he got sniped by r***a in the last second, he didn't have a chance to decide whether he wants to bid higher. Although one could argue that if f***f really wanted to pay more, he should have raised the first bid. However, a person also makes a bid to gauge interest level from fellow bidders. A sniper, by virtue of his operation, conceals his interest until the last second to keep the interest artificially low.

There is one thing eBay can do to discourage sniping: every time when a bid is made, whether it outbids the current highest bidder or not, the auction end time is extended by an hour. The sniper r***a in this case would have extended the end time by 20 hours. Another orthogonal policy adjustment is to limit the number of bids each bidder can make to a low number, say 5. This encourages more bidders to take advantage of proxy bidding, as well as limit the amount of time a bidder can extend the auction end time by bidding.

eBay, I hope you're listening.

Friday, August 13, 2010

The Equal Sign

I've long wanted to write about the equal sign but I've been putting it off. Now I have an excuse to write about it. It is reported that students don't understand what the equal sign means. I don't blame them because the symbol '=' is overloaded. It is given four meanings in grade-school curriculum.

The first meaning is reduction of computation, as in arithmetics. An example is 2 × 5 + 4 × 3 = 10 + 12 = 22. In this case, the reduction from a formula 2 × 5 + 4 × 3 to a value requires us to compute 2 × 5 = 10 and 4 × 3 = 12 first because of operator precedence, and then compute 10 + 12 = 22. When arithmetics is taught, the equal sign is taken to mean reduction. We kind of gloss over the fact that there is a specific order of reduction, but the order of reduction was never formally taught.

The second meaning of the equal sign, by the time you learn algebra, is constraint solving. You are asked to solve for the value of the variables given a system of constraints, for example, 2x - y = 7 and x + y = 5. The answer is x = 4 and y = 1. Here the equal sign represents a goal, and you are asked to give solution for the goal.

The third meaning of the equal sign, if you haven't flunk out of math class yet, is definition. You would learn in pre-calculus about how to define a function, e.g. f(x) = x2 - 3x + 7. The formula x2 - 3x + 7 has been assigned a name f(x), and there is some implicit notion of variable scoping and substitution. For example, if you were to compute f(4) - 5, you would first reduce the function f(4) to its definition x2 - 3x + 7, and then substitute x for 4, which gives you 42 - 3 × 4 + 7 = 11. Then you compute 11 - 5, which gives you 6. The equal sign here allows you to give a long formula a short name.

Finally, we encounter the fourth meaning in a very subtle way when we talked about constraint solving and function definition. That is, we also use the equal sign to denote a substitution. For example, you can verify that the system of constraints 2x - y = 7 and x + y = 5 yields the solution x = 4 and y = 1 if you substitute x for 4 and y for 1, so that 2 × 4 - 1 = 8 - 1 = 7, and 4 + 1 = 5. And to compute f(4), you will compute x2 - 3x + 7 in the context of x = 4 because of the function definition.

All four notions of the equal sign are different, but they all use the same symbol. That's why students get confused. And it takes a computer scientist to tell a mathematician about that!