Reinforcement learning-based off-equilibrium incentives to approximate the VCG mechanism Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/q237hw19t

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • Auctions are used to solve resource allocation problem between many agents and many items in real-world settings. Unfortunately, in most cases, it is possible for selfish agents to manipulate the system for their own interest at the expense of the social welfare. Such manipulation can be prevented using the Vickrey-Clarke-Groves mechanism, which guarantees complete truthfulness from the agents, and therefore, preserve optimal social welfare. However, the Vickrey-Clarke-Groves mechanism is computationally expensive, mainly due to the search for the optimal allocation of items (the “Winner Determination Problem”). In this work, we propose the use of off-equilibrium incentives to approximate the VCG mechanism, where the agents use reinforcement learning using “difference rewards” to compute those incentives. In one round of the reinforcement learning the agents: (i) declare their preferences in terms of allocation; (ii) compute their reward using the difference reward; (iii) and update their Q-table and move toward system efficiency. We demonstrate theoretically the equivalence of the off-equilibrium incentives and the VCG mechanism, and empirically show that this approximation of VCG mechanism leads to desirable outcomes in a congestion game.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Keyword
Subject
Rights Statement
Peer Reviewed
Language
Replaces
Additional Information
  • description.provenance : Rejected by Julie Kurtz(julie.kurtz@oregonstate.edu), reason: Your ScholarsArchive@OSU submission has been rejected because you attached a CC0 or Public Domain License to your work. These licenses mean that you have "dedicated the work to the public domain by waiving all of your rights to the work worldwide under copyright law, including all related and neighboring rights, to the extent allowed by law. Others can copy, modify, distribute and perform the work, even for commercial purposes, all without asking permission." We strongly suggest that you don't attach either of these licenses. We're assuming you probably meant to add a Creative Commons license to your work so that others could use it, but you intended to retain your copyrights. Please re-submit* your work and choose "Creative Commons License" from the License Type drop down box. You'll then be asked two questions about how you want people to use your work. You can also choose "No Creative Commons License". *To re-submit your work, log into ScholarsArchive@OSU. Your rejected submission will be in your Submissions & Tasks work file. You can just resume the submission. All your information will still be in the form; you need to change only the CC License page. If you have any questions or concerns, please contact Sue Kunda: sue.kunda@oregonstate.edu OR 541-737-7262. Thanks, Julie on 2013-12-27T17:12:17Z (GMT)
  • description.provenance : Made available in DSpace on 2014-01-17T00:05:40Z (GMT). No. of bitstreams: 2 license_rdf: 1089 bytes, checksum: 0a703d871bf062c5fdc7850b1496693b (MD5) MoissinacBeatriceS2013.pdf: 713515 bytes, checksum: aaa80a2d2984ebbddab61d5275c57056 (MD5) Previous issue date: 2013-11-22
  • description.provenance : Approved for entry into archive by Laura Wilson(laura.wilson@oregonstate.edu) on 2014-01-17T00:05:40Z (GMT) No. of bitstreams: 2 license_rdf: 1089 bytes, checksum: 0a703d871bf062c5fdc7850b1496693b (MD5) MoissinacBeatriceS2013.pdf: 713515 bytes, checksum: aaa80a2d2984ebbddab61d5275c57056 (MD5)
  • description.provenance : Submitted by Beatrice Moissinac (moissinb@onid.orst.edu) on 2013-12-16T19:10:11Z No. of bitstreams: 2 license_rdf: 1089 bytes, checksum: 0a703d871bf062c5fdc7850b1496693b (MD5) MoissinacBeatriceS2013.pdf: 713515 bytes, checksum: aaa80a2d2984ebbddab61d5275c57056 (MD5)
  • description.provenance : Approved for entry into archive by Julie Kurtz(julie.kurtz@oregonstate.edu) on 2014-01-15T15:53:01Z (GMT) No. of bitstreams: 2 license_rdf: 1089 bytes, checksum: 0a703d871bf062c5fdc7850b1496693b (MD5) MoissinacBeatriceS2013.pdf: 713515 bytes, checksum: aaa80a2d2984ebbddab61d5275c57056 (MD5)
  • description.provenance : Submitted by Beatrice Moissinac (moissinb@onid.orst.edu) on 2014-01-14T18:24:02Z No. of bitstreams: 2 license_rdf: 1089 bytes, checksum: 0a703d871bf062c5fdc7850b1496693b (MD5) MoissinacBeatriceS2013.pdf: 713515 bytes, checksum: aaa80a2d2984ebbddab61d5275c57056 (MD5)

Relationships

Parents:

This work has no parents.

Last modified

Downloadable Content

Download PDF

Items