Papers from the Eighth ACM Special Interest Group on Electronic Commerce 2007

From June 11th to June 15th, the ACM Special Interest Group on Electronic Commerce (SIGECOM) held its eighth conference in San Diego, California.

There were a good number of accepted papers for the conference, and I was able to hunt a few of them down online.

Budget Optimization in Search-Based Advertising Auctions (pdf)
Cliff Stein from Columbia University; Jon Feldman, S. Muthukrishnan, and Martin Pal from Google

Internet search companies sell advertisement slots based on users’ search queries via an auction. While there has been a lot of attention on the auction process and its game-theoretic aspects, our focus is on the advertisers. In particular, the advertisers have to solve a complex optimization problem of how to place bids on the keywords of their interest so that they can maximize their return (the number of user clicks on their ads) for a given budget.

Allocating online advertisement space with unreliable estimates (pdf)
Hamid Nazerzadeh and Amin Saberi from Stanford, and Mohammad Mahdian from Yahoo

Search engines such as Google, Yahoo!, and MSN use a simple but innovative auction mechanism for allocating the advertisement space on the side of search results. Goods that are being sold in these auctions, the search queries, have very interesting characteristics; most importantly, they should be allocated to the buyers in a fraction of a second or they will perish instantly. Moreover, they arrive in an online fashion and their total supply, the number of times the users search for a specific keyword, is unknown. The online nature of these auctions gives rise to interesting and challenging algorithmic problems. One of the most central problems in this context is finding the optimum allocation algorithm: given the current bids and budgets of the advertisers, what is the best algorithm for allocating each search query to the advertisers?

Optimal Delivery of Sponsored Search Advertisements Subject to Budget Constraints (pdf)
Zoe Abrams, Ofer Mendelevitch, and John A. Tomlin from Yahoo

We discuss an auction framework in which sponsored search advertisements are delivered in response to queries. In practice, the presence of bidder budgets can have a significant impact on the ad delivery process. We propose an approach based on linear programming which takes bidder budgets into account, and uses them in conjunction with forecasting of query frequencies, and pricing and ranking schemes, to optimize ad delivery. Simulations show significant improvements in revenue and efficiency.

On Threshold Behavior in Query Incentive Networks (pdf)
Esteban Arcaute and Sergei Vassilvitskii from Stanford, Adam Kirsch from Harvard, David Liben-Nowell from Carlton College, and Ravi Kumar from Yahoo.

In a world where billions of web pages are at one’s fingertips, the quest for information is no longer constrained by a lack of accessible data. Instead, one of the new prevailing limitations is that of reliability. Why would a web-page author carefully write a thoroughly investigated essay when there is little recourse if its facts turn out to have been fabricated? Why would a stranger give an honest appraisal of a product when he might be paid by the manufacturer to speak highly of it? Why should a user trust the information that she receives via a web page?

Trading Networks with Price-Setting Agents (pdf)
Larry Blume, David Easley, Jon Kleinberg, and Eva Tardos from Cornell

Our work differs from recent studies of how price is affected by network structure through our modeling of price-setting as a strategic activity carried out by a subset of agents in the system, rather than studying prices set via competitive equilibrium or by a truthful mechanism.

Greedy Bidding Strategies for Keyword Auctions (pdf)
Matthew Cary, Ioannis Giotis, Kurtis Heimerl, and Anna R. Karlin from the University of Washington; Aparna Das and Claire Mathieu from Brown University; Ben Edelman from Harvard; Michael Schwarz from Yahoo.

How should players bid in keyword auctions such as those used by Google, Yahoo! and MSN? We consider greedy bidding strategies for a repeated auction on a single keyword, where in each round, each player chooses some optimal bid for the next round, assuming that the other players merely repeat their previous bid. We study the revenue, convergence and robustness properties of such strategies.