## Abstract

We consider the online auction problem proposed by Bar-Yossef, Hildrum, and Wu in which an auctioneer is selling identical items to bidders arriving one at a time. We give an auction that achieves a constant factor of the optimal profit less an O(h) additive loss term, where h is the value of the highest bid. Furthermore, this auction does not require foreknowledge of the range of bidders' valuations. On both counts, this answers open questions from. We further improve on the results from for the online posted-price problem by reducing their additive loss term from O(h log h log log h) to O(h log log h). Finally, we define the notion of an (offline) attribute auction for modeling the problem of auctioning items to consumers who are not a-priori indistinguishable. We apply our online auction solution to achieve good bounds for the attribute auction problem with 1-dimensional attributes.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms |

Pages | 1156-1163 |

Number of pages | 8 |

State | Published - Jul 1 2005 |

Event | Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States Duration: Jan 23 2005 → Jan 25 2005 |

### Other

Other | Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country/Territory | United States |

City | Vancouver, BC |

Period | 1/23/05 → 1/25/05 |

## ASJC Scopus subject areas

- Software
- Mathematics(all)