Yurong Chen  陈昱蓉

Stackelberg equilibrium describes the optimal strategies of a player, when she (the leader) first credibly commits to a strategy. Her opponent (the follower) will best respond to her commitment. To compute the optimal commitment, a leader must learn enough follower’s payoff information. The follower can then potentially provide fake information, to induce a different final game outcome that benefits him more than when he truthfully behaves. We study such follower’s manipulation in extensive-form games. For all four settings considered, we characterize all the inducible game outcomes. We show the polynomial-time tractability of finding the optimal payoff function to misreport. We compare the follower’s optimal attainable utilities among different settings, with the true game fixed. In particular, one comparison shows that the follower gets no less when the leader’s strategy space expands from pure strategies to behavioral strategies. Our work completely resolves this follower’s optimal manipulation problem on extensive-form game trees.

This paper considers the hidden-action model of the principal-agent problem, in which a principal incentivizes an agent to work on a project using a contract. We investigate whether contracts with bounded payments are learnable and approximately optimal. Our main results are two learning algorithms that can find a nearly optimal bounded contract using a polynomial number of queries, under two standard assumptions in the literature: a costlier action for the agent leads to a better outcome distribution for the principal, and the agent’s cost/effort has diminishing returns. Our polynomial query complexity upper bound shows that standard assumptions are sufficient for achieving an exponential improvement upon the known lower bound for general instances. Unlike the existing algorithms which relied on discretizing the contract space, our algorithms directly learn the underlying outcome distributions. As for the approximate optimality of bounded contracts, we find that they could be far from optimal in terms of multiplicative or additive approximation, but satisfy a notion of mixed approximation.

In online ad markets, a rising number of advertisers are employing bidding agencies to participate in ad auctions. These agencies are specialized in designing online algorithms and bidding on behalf of their clients. Typically, an agency usually has information on multiple advertisers, so she can potentially coordinate bids to help her clients achieve higher utilities than those under independent bidding. In this paper, we study coordinated online bidding algorithms in repeated second-price auctions with budgets. We propose algorithms that guarantee every client a higher utility than the best she can get under independent bidding. We show that these algorithms achieve maximal social welfare and discuss bidders’ incentives to misreport their budgets, in symmetric cases. Our proofs combine the techniques of online learning and equilibrium analysis, overcoming the difficulty of competing with a multi-dimensional benchmark. The performance of our algorithms is further evaluated by experiments on both synthetic and real data. To the best of our knowledge, we are the first to consider bidder coordination in online repeated auctions with constraints.

We consider a Stackelberg scenario where the leader commits optimally based on the follower’s type (i.e., the follower’s payoff function). Despite its rationality, such commitmentoptimizing behavior inadvertently reveals information about the leader’s incentive, especially when one gets access to the leader’s optimal commitments against different follower types. In this paper, we study to what extent one can learn about the leader’s payoff information by actively querying the leader’s optimal commitments. We show that, by using polynomially many queries and operations, a learner can learn a payoff function that is strategically equivalent to the leader’s original payoff function, in the sense that it preserves: 1) the leader’s preference over fairly broad sets of strategy profiles and 2) the set of all possible (strong) Stackelberg equilibria the leader may engage in, considering all possible follower types. As an application, we show that a follower can use the learned information to induce an optimal Stackelberg equilibrium (w.r.t. the follower’s payoff) by imitating a different type, without knowing the leader’s payoff function beforehand. To the best of our knowledge, we are the first to extend this equilibrium inducing problem to the incomplete information setting