In revenue maximization of selling a digital product in a social network, the utility of an agent is often considered to have two parts: a private valuation, and linearly additive influences from other agents. We study the incomplete information case where agents know a common distribution about others' private valuations, and make decisions simultaneously. The "rational behavior" of agents in this case is captured by the well-known Bayesian Nash equilibrium. Two challenging questions arise: how to compute an equilibrium and how to optimize a pricing strategy accordingly to maximize the revenue assuming agents follow the equilibrium? In this paper, we mainly focus on the natural model where the private valuation of each agent is sampled from a uniform distribution, which turns out to be already challenging. Our main result is a polynomial-time algorithm that can exactly compute the equilibrium and the optimal price, when pairwise influences are non-negative. If negative influences are allowed, computing any equilibrium even approximately is PPAD-hard. Our algorithm can also be used to design an FPTAS for optimizing discriminative price profile.
Hartline, Mirrokni and Sundararajan @cite_1 study the explore and exploit framework. In their model the seller offers the product to the agents in a sequential manner, and assumes all agents are myopic , i.e., each agent is making the decision based on the known results of the previous agents in the sequence. As they have pointed out, if the pricing strategy of the seller and the private value distributions of the subsequent agents are publicly known, the agents can make more informed'' decisions than the myopic ones. In contrast to them, we consider perfect rational'' agents in the simultaneous-move game, where agents make decisions in anticipation of what others may do given their beliefs to other agents' valuations.
@cite_1
2017461072 2095540386 2311550555 2950679788
In this paper we consider online auction mechanisms for the allocation of M items that are identical to each other except for the fact that they have different expiration times, and each item must be allocated before it expires. Players arrive at different times, and wish to buy one item before their deadline. The main difficulty is that players act "selfishly" and may mis-report their values, deadlines, or arrival times. We begin by showing that the usual notion of truthfulness (where players follow a single dominant strategy) cannot be used in this case, since any (deterministic) truthful auction cannot obtain better than an M-approximation of the social welfare. Therefore, instead of designing auctions in which players should follow a single strategy, we design two auctions that perform well under a wide class of selfish, "semi-myopic", strategies. For every combination of such strategies, the auction is associated with a different algorithm, and so we have a family of "semi-myopic" algorithms. We show that any algorithm in this family obtains a 3-approximation, and by this conclude that our auctions will perform well under any choice of such semi-myopic behaviors. We next turn to provide a game-theoretic justification for acting in such a semi-myopic way. We suggest a new notion of "Set-Nash" equilibrium, where we cannot pin-point a single best-response strategy, but rather only a set of possible best-response strategies. We show that our auctions have a Set-Nash equilibrium which is all semi-myopic, hence guarantees a 3-approximation. We believe that this notion is of independent interest. We study the optimal pricing of a finite quantity of a fashion-like seasonal good in the presence of forward-looking (strategic) customers. We distinguish between two classes of pricing strategies: contingent and announced fixed-discount. In both cases, the seller acts as a Stackelberg leader announcing his pricing strategy, while consumers act as followers taking the seller's strategy as given and determining their purchasing behavior. In each case, we identify a subgame-perfect Nash equilibrium and show that given the seller's strategy, the equilibrium in the consumer subgame is unique and consists of symmetric threshold purchasing policies. For both cases, we develop a benchmark model in which customers are nonstrategic (myopic). We conduct a comprehensive numerical study to explore the impact of strategic consumer behavior on pricing policies and expected revenue performance. We show that strategic customer behavior suppresses the benefits of price segmentation, particularly under medium-to-high values of heterogeneity and modest rates of decline in valuations. However, when the level of consumer heterogeneity is small, the rate of decline is medium-to-high, and the seller can optimally choose the time of discount in advance, segmentation can be used quite effectively even with strategic consumers. We find that the seller cannot avoid the adverse impact of strategic consumer behavior even under low levels of initial inventory. We argue that while the seller expects customers to be more concerned about product availability at discount time, he cannot use high-price “betting” strategies as he would in the case of low inventory and myopic customers. Under certain qualifications, announced fixed-discount strategies perform essentially the same as contingent pricing policies in the case of myopic consumers. However, under strategic consumer behavior, announced pricing policies can be advantageous to the seller, compared to contingent pricing schemes. Interestingly, those cases that announced discount strategies offer a significant advantage compared to contingent pricing policies. They appear to offer only a minimal advantage in comparison to fixed-pricing policies. Finally, when the seller incorrectly assumes that strategic customers are myopic in their purchasing decisions, it can be quite costly, reaching potential revenue losses of about 20 . How should one sell an item to a buyer whose value for the item will only be realized next week? E.g. consider selling a flight to some executive who may or may not have a meeting with a client next week. Suppose that both the seller and the buyer only know a distribution, F, from which the buyer's value, v, for the item will be drawn. One way the seller could go about this sale is to make a take-it-or-leave-it offer today. The offer reads "pay the expected value today to get the item next week". A risk-neutral buyer would find this offer attractive, hence the seller would extract the full surplus. The unsettling feature of the afore-described mechanism is that, for some realizations of v, the bidder ends up with negative utility. In particular, while our mechanism is interim Individually Rational (IR), it is not ex-post IR. How could we fix this? One way is to wait until next week when the value is realized and make a take-it-or-leave-it offer of the item at an optimal monopoly price. The new mechanism is clearly ex-post IR, but its revenue could be much smaller than that of the previous one. Still, this trivial mechanism extracts the best possible revenue among all ex-post IR mechanisms, as a simple argument can establish. However, this optimality argument fails when several items are to be sold over consecutive periods. In this paper, we provide a characterization of the revenue-optimal, ex-post IR, dynamic mechanism selling k items over k periods to a bidder whose values are independent. In particular, we optimize the seller's revenue subject to the following strong individual rationality condition: at each period, the stage utility of the agent, defined to be the surplus from that period's allocation minus the agent's payment, must be non-negative. In particular, the non-negativity of the stage utilities implies that, at the end of each period, the agent's realized utility from participating in the mechanism so far is non-negative. We provide extensions to multiple bidders and an infinite horizon with discount factors. We consider settings in which we wish to incentivize myopic agents (such as Airbnb landlords, who may emphasize short-term profits and property safety) to treat arriving clients fairly, in order to prevent overall discrimination against individuals or groups. We model such settings in both classical and contextual bandit models in which the myopic agents maximize rewards according to current empirical averages, but are also amenable to exogenous payments that may cause them to alter their choices. Our notion of fairness asks that more qualified individuals are never (probabilistically) preferred over less qualified ones []. We investigate whether it is possible to design inexpensive subsidy or payment schemes for a principal to motivate myopic agents to play fairly in all or almost all rounds. When the principal has full information about the state of the myopic agents, we show it is possible to induce fair play on every round with a subsidy scheme of total cost @math (for the classic setting with @math arms, @math , and for the @math -dimensional linear contextual setting @math ). If the principal has much more limited information (as might often be the case for an external regulator or watchdog), and only observes the number of rounds in which members from each of the @math groups were selected, but not the empirical estimates maintained by the myopic agent, the design of such a scheme becomes more complex. We show both positive and negative results in the classic and linear bandit settings by upper and lower bounding the cost of fair subsidy schemes.