We consider the online auction<\/i> problem proposed by Bar-Yossef, Hildrum, and Wu [4] 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<\/i>(h<\/i>) additive loss term, where h<\/i> 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 [4, 5]. We further improve on the results from [5] for the online posted-price<\/i> problem by reducing their additive loss term from O<\/i>(h<\/i> log h<\/i> log log h<\/i>) to O<\/i>(h<\/i> log log h<\/i>). Finally, we define the notion of an (offline) attribute auction<\/i> 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.<\/p>\n","protected":false},"excerpt":{"rendered":"
We consider the online auction problem proposed by Bar-Yossef, Hildrum, and Wu [4] 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 […]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr-author-ordering":null,"msr_publishername":"ACM\/SIAM","msr_publisher_other":"","msr_booktitle":"","msr_chapter":"","msr_edition":"ACM\/SIAM Symposium on Discrete Algorithms (SODA)","msr_editors":"","msr_how_published":"","msr_isbn":"","msr_issue":"","msr_journal":"","msr_number":"","msr_organization":"","msr_pages_string":"1156-1163","msr_page_range_start":"1156","msr_page_range_end":"1163","msr_series":"","msr_volume":"","msr_copyright":"","msr_conference_name":"ACM\/SIAM Symposium on Discrete Algorithms (SODA)","msr_doi":"","msr_arxiv_id":"","msr_s2_paper_id":"","msr_mag_id":"","msr_pubmed_id":"","msr_other_authors":"Avrim Blum, Jason D. Hartline","msr_other_contributors":"","msr_speaker":"","msr_award":"","msr_affiliation":"","msr_institution":"","msr_host":"","msr_version":"","msr_duration":"","msr_original_fields_of_study":"","msr_release_tracker_id":"","msr_s2_match_type":"","msr_citation_count_updated":"","msr_published_date":"2005-01-01","msr_highlight_text":"","msr_notes":"","msr_longbiography":"","msr_publicationurl":"http:\/\/doi.acm.org\/10.1145\/1070597","msr_external_url":"","msr_secondary_video_url":"","msr_conference_url":"","msr_journal_url":"","msr_s2_pdf_url":"","msr_year":2005,"msr_citation_count":0,"msr_influential_citations":0,"msr_reference_count":0,"msr_s2_match_confidence":0,"msr_microsoftintellectualproperty":true,"msr_s2_open_access":false,"msr_s2_author_ids":[],"msr_pub_ids":[],"msr_hide_image_in_river":0,"footnotes":""},"msr-research-highlight":[],"research-area":[13554],"msr-publication-type":[193716],"msr-publisher":[],"msr-focus-area":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-146920","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-human-computer-interaction","msr-locale-en_us"],"msr_publishername":"ACM\/SIAM","msr_edition":"ACM\/SIAM Symposium on Discrete Algorithms (SODA)","msr_affiliation":"","msr_published_date":"2005-01-01","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"1156-1163","msr_chapter":"","msr_isbn":"","msr_journal":"","msr_volume":"","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":1,"msr_main_download":"","msr_publicationurl":"http:\/\/doi.acm.org\/10.1145\/1070597","msr_doi":"","msr_publication_uploader":[{"type":"url","title":"http:\/\/doi.acm.org\/10.1145\/1070597","viewUrl":false,"id":false,"label_id":0}],"msr_related_uploader":"","msr_citation_count":0,"msr_citation_count_updated":"","msr_s2_paper_id":"","msr_influential_citations":0,"msr_reference_count":0,"msr_arxiv_id":"","msr_s2_author_ids":[],"msr_s2_open_access":false,"msr_s2_pdf_url":null,"msr_attachments":[{"id":0,"url":"http:\/\/doi.acm.org\/10.1145\/1070597"}],"msr-author-ordering":[{"type":"text","value":"Avrim Blum","user_id":0,"rest_url":false},{"type":"text","value":"Jason D. Hartline","user_id":0,"rest_url":false}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[],"msr_project":[169501],"publication":[],"video":[],"msr-tool":[],"msr_publication_type":"inproceedings","related_content":{"projects":[{"ID":169501,"post_title":"Computational Game Theory","post_name":"computational-game-theory","post_type":"msr-project","post_date":"2005-12-05 17:02:01","post_modified":"2017-06-06 09:26:48","post_status":"publish","permalink":"https:\/\/www.microsoft.com\/en-us\/research\/project\/computational-game-theory\/","post_excerpt":"Overview We study several problems related to game theory. These problems are motivated by e-commerce applications and applications of game theory to computer system and network design. In mechanism design, we aim to develop mechanisms with useful properties which optimize an objective function, such as seller's revenue or global welfare of the system, in the worst- or average-case. Our work shows that techniques from learning, on-line algorithms, and coding theory can be applied to mechanism…","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/169501"}]}}]},"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/146920","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":1,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/146920\/revisions"}],"predecessor-version":[{"id":413081,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/146920\/revisions\/413081"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=146920"}],"wp:term":[{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=146920"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=146920"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=146920"},{"taxonomy":"msr-publisher","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publisher?post=146920"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=146920"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=146920"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=146920"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=146920"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=146920"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=146920"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=146920"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=146920"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}