Learning about Auctions: Reconstructing Preferences and Mechanisms
Given only results of multi-agent interactions, this research explores reconstructing agents' preferences and needs from auction outcomes. It delves into the challenges of reconstructing preferences in repeated auctions and combinatorial auctions, aiming to uncover unknown mechanisms and agent demands through observation and analysis.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Learning about Auctions: Reconstructing Preferences and Mechanisms from Opaque Transactions Avrim Blum Carnegie Mellon University Joint with Yishay Mansour (TAU) and Jamie Morgenstern (Penn) [Simons Workshop on Uncertainty in Computation, 2016]
A very classic problem Given random samples of some function, learn a good approximation to that function. + + + + Basically, all of (supervised) machine learning.
A less-classic but still well-studied problem Given random observations of some agent s actions, learn what the agent is trying to optimize. Inverse reinforcement learning. [Ng-Russell00] [Abbeel-Ng04] [Syed-Schapire07] Learning from revealed preferences. [Beigman-Vohra06] [Zadimoghaddam-Roth12] [Balcan-Daniely-Mehta-Urner-Vazirani14]
Todays problem Suppose you don t have access to agents in isolation. Given only results of multi-agent interactions, can you reconstruct agents preferences / needs? Observing the outcomes of a series of auctions (just who won e.g, which ads appeared on pages), reconstruct agent preferences. From observing which agents end up happy in some allocation mechanism, reconstruct both the agent preferences and the mechanism.
Two models (high-level) Suppose you don t have access to agents in isolation. Given only results of multi-agent interactions, can you reconstruct agents preferences / needs? Repeated auction. Each agent ? bids ?? ??. (like Myerson) But we can t observe the ??, just who wins. Can also participate ourselves. Goal: recover (the recoverable part of) the ??.
Two models (high-level) Suppose you don t have access to agents in isolation. Given only results of multi-agent interactions, can you reconstruct agents preferences / needs? Repeated auction. Each agent ? bids ?? ??. (like Myerson) But we can t observe the ??, just who wins. Goal: recover (the recoverable part of) the ??. Can also participate ourselves. Combinatorial auction. Agents deterministic but prefs/needs unknown. Auctioneer mechanism also unknown. Goal: learn what agents want and allocation mechanism.
Consider the following scenario There are n bidders (jobs), Each day ?, some subset ?? of the bidders participate. Some end up happy, some not. Bidders have demand sets. Mechanism is allocating resources using some priority ordering unknown to us. and one auctioneer (allocator). Goal: reconstruct the unknowns from observations, or at least be able to predict well.
Consider the following scenario ? bidders. Each day ?, some subset ?? {1, ,?} of them arrive. ?items. Each bidder is single-minded . Mechanism has priority order: > > > > We just observe ?? and who ends up happy and who does not. Goal: predict correctly for new subsets of bidders ?? (bound # mistakes: want ????(?) not 2?, ? = #bidders)
Special case: 1 item (wanted by all) Say each day two bidders arrive Mechanism has priority order: > > > > Like inverse comparison-based sorting (adversary picks pair to compare, you predict outcome, you pay 1 per mistake). Can get ?(?log?) mistakes efficiently using efficient sampling of linear extensions of partial orders [KK91].
General case (single-minded) Idea: rather than trying to learn the subsets (since we can t see the items anyway), instead learn the conflict graph. At the same time as we try to learn the ordering > > > > At each time step ?, we observe (??,??) where ?? ? and ?? is a greedy maximal independent set of ?? based on the unknown priorities.
General case (single-minded) Start by assuming all are in conflict. Start with all bidders at the top of the ordering. { } Predict using conflict graph + arbitrary linearization of our partial order.
General case (single-minded) If correct answer includes a pair connected by an edge, can delete it. Start with all bidders at the top of the ordering. { } Predict using conflict graph + arbitrary linearization of our partial order.
General case (single-minded) If correct answer includes a pair connected by an edge, can delete it. If not but still a mistake, argue can safely demote some bidder(s). { } Predict using conflict graph + arbitrary linearization of our partial order.
General case (single-minded) Show: no bidder ever demoted past its correct level if update only 1st mistake. Use fact that our conflict graph is superset of correct one. If not but still a mistake, argue can safely demote some bidder(s). { } Overall, at most ?(?2) mistakes. (which is optimal)
How about unit-demand Bidders have subset of interest, but just want one. Have preference ordering and will take highest that s available. Seller has unknown priority over bidders. > > > > Let s say you see what each bidder exits with. Goal: predict what will happen (who gets what) on new set of bidders.
How about unit-demand Bidders have subset of interest, but just want one. Have preference ordering and will take highest that s available. One way to solve: by reduction to the previous case. For each bidder i, create m copies , one per item (?? total) Two copies in conflict if correspond to same bidder or same item. Observing who gets what Observing which copies are happy. Overall?(?2?2)mistakes total.
How about unit-demand Bidders have subset of interest, but just want one. Have preference ordering and will take highest that s available. Can do more efficiently by combining with inverse-sorting Use inverse-sorting algorithm for learning each bidder s ordering. Combined with previous algorithm for learning auctioneer s ordering. Overall?(?2?log?)mistakes total. Lower bound of (??log?). Improve one or the other?
Learning the presence of variable prices Each day has price-vector ?? in addition to set of bidders ??. 20 10 5 4 Bidders unit-demand (choose item maximizing ????? ????? if 0) or additive (choose all s.t. ????? ????? 0). Idea: again, maintain partial ordering of bidders where each bidder assigned to some level, and no bidder farther down than should be. On incorrect prediction, look at first mistake (in our ordering) and use to add new linear constraint for that bidder (separation oracle). Combine with online LP alg (like Ellipsoid).
Learning the presence of variable prices Each day has price-vector ?? in addition to set of bidders ??. 20 10 5 4 Bidders unit-demand (choose item maximizing ????? ????? if 0) or additive (choose all s.t. ????? ????? 0). In additive case, decisions are separable, so LP is just ? separate 1-dim l binary-searches per bidder. Overall ?(?2?log?) mistakes. In unit-demand case, need real LP alg. Get ?(?2?) where ? is mistake-bound of LP alg.
Now to Bayesian model Let s make the problem easier: just one item, auctioneer sells to highest bidder. (say at 2nd-highest price but won t see prices) But harder in that bidders are stochastic. Each bidder ? ?? bids ??,? ??. We just get to observe winner. Can participate ourselves too. Want to learn the ??.
Some difficulties Even if you get to see winning bid, it s not a representative draw from bidder s distribution. E.g., say each ?? is uniform in [0,1]. Winning bid is likely to be in [1 1/?,1]. (and not uniform in this range) In fact, let ?? be price s.t. Pr[winning price < ??] = ?. Can only hope to learn ?? s above ??.
A really useful tool: Kaplan-Meier estimator Doing a study of survival rates after a medical procedure. But patients keep dropping out of the study. Assume each patient ? lives ?? ?1 years and would drop out after ?? ?2 years (indep), and you see whichever is first. Goal is to recover ?1 (up to point where nearly everyone has dropped out) Idea: still getting good estimates of Pr(survive one more day | still in study). Chain together.
A really useful tool: Kaplan-Meier estimator Doing a study of survival rates after a medical procedure. But patients keep dropping out of the study. Assume each patient ? lives ?? ?1 years and would drop out after ?? ?2 years (indep), and you see whichever is first. This is like auction where ??= see winning bid. (first highest) , ??= max(others), if you
Back to the auction Here, we don t get to see winning bid, but can participate ourselves. Want to use to simulate Kaplan-Meier.
Back to the auction Two key ingredients: 1. By setting price ? and seeing how often some bidder ? wins, and seeing how that changes when we raise to price ? + ?, and also observing how often we win at those prices, We can estimate how often bidder ? bids in [?,? + ?]| nobody else bids above ?. So this is roughly how often bidder ? wins with a bid in that range | price ? + ? (which is the kind of statistic that Kaplan-Meier needs). ? + ? ? ?
Back to the auction Two key ingredients: 1. By setting price ? and seeing how often some bidder ? wins, and seeing how that changes when we raise to price ? + ?, and also observing how often we win at those prices, We can estimate how often bidder ? bids in [?,? + ?]| nobody else bids above ?. 2. Control the errors to make sure they don t blow up as you chain from high prices down to low prices. Key trick is viewing error as having both a multiplicative and additive component, which helps with the induction. ?
Back to the auction Can handle the case of subsets, or different numbers of each type, so long as ??is drawn independently from the draw of the ??,?. E.g., you don t have the event of person 2 showing up being correlated with the event of person 1 having a high value for the item ?
Extended models What if items have a common-value component? Each item has a (visible) feature vector ?. Bidders have an (unknown) common value-vector ?. Value of bidder ? on ? is ? ? + ??, where ?? ??. Goal: learn ? and each ??. ?
Open problems In first part: Analyze other natural allocation mechanisms? Analyze other natural valuation classes / add noise? Better mistake-bound for learning unit-demand bidders? In second part: Add combinatorial component? What if mechanism non-truthful, ?? over values not bids? ?
References Blum, Mansour, Morgenstern, Learning What s Going On: Reconstructing Preferences and Priorities from Opaque Transactions, Proc. ACM-EC 2015. Blum, Mansour, Morgenstern, Learning Valuation Distributions from Partial Observation, Proc. AAAI 2015.
