Watch and learn: optimizing from revealed preferences feedback

DOI10.1145/2897518.2897579MaRDI QIDQ5361893zbMATH OpenOpenAlexFDO

Authors Aaron Roth, Zhiwei Steven Wu, Jonathan Ullman

Publication date 29 September 2017

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.01033

zbMATH Keywords

game theorylearningoptimizationrevealed preferences

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Hierarchical games (including Stackelberg games) (91A65) Individual preferences (91B08)

Abstract: A Stackelberg game is played between a leader and a follower. The leader first chooses an action, then the follower plays his best response. The goal of the leader is to pick the action that will maximize his payoff given the follower's best response. In this paper we present an approach to solving for the leader's optimal strategy in certain Stackelberg games where the follower's utility function (and thus the subsequent best response of the follower) is unknown. Stackelberg games capture, for example, the following interaction between a producer and a consumer. The producer chooses the prices of the goods he produces, and then a consumer chooses to buy a utility maximizing bundle of goods. The goal of the seller here is to set prices to maximize his profit---his revenue, minus the production cost of the purchased bundle. It is quite natural that the seller in this example should not know the buyer's utility function. However, he does have access to revealed preference feedback---he can set prices, and then observe the purchased bundle and his own profit. We give algorithms for efficiently solving, in terms of both computational and query complexity, a broad class of Stackelberg games in which the follower's utility function is unknown, using only "revealed preference" access to it. This class includes in particular the profit maximization problem, as well as the optimal tolling problem in nonatomic congestion games, when the latency functions are unknown. Surprisingly, we are able to solve these problems even though the optimization problems are non-convex in the leader's actions.

Recommendations

• Stackelberg packing games
• Stackelberg network pricing games
• Stackelberg network pricing games
• Computation of Stackelberg equilibria of finite sequential games
• Incentive strategies dealing with uncertainty about the follower's MCDM behaviour

Cited in

(10)

• Social welfare and profit maximization from revealed preferences
• Achieving target equilibria in network routing games without knowing the latency functions
• Learning and Optimizing with Preferences
• Demand-independent optimal tolls
• Optimally Deceiving a Learning Leader in Stackelberg Games
• Adaptive constraint satisfaction for Markov decision process congestion games: application to transportation networks
• Adversarial bandits with knapsacks
• Stackelberg risk preference design
• Optimal private payoff manipulation against commitment in extensive-form games
• On the dual gradient descent method for the resource allocation problem in multiagent systems

This page was built for publication: Watch and learn: optimizing from revealed preferences feedback

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361893)