
The assortment problem in revenue management is the problem of deciding which
subset of products to offer to consumers in order to maximise revenue. A simple
and natural strategy is to select the best assortment out of all those that are
constructed by fixing a threshold revenue $\pi$ and then choosing all products
with revenue at least $\pi$. This is known as the revenueordered assortments
strategy. In this paper we study the approximation guarantees provided by
revenueordered assortments when customers are rational in the following sense:
the probability of selecting a specific product from the set being offered
cannot increase if the set is enlarged. This rationality assumption, known as
regularity, is satisfied by almost all discrete choice models considered in the
revenue management and choice theory literature, and in particular by random
utility models. The bounds we obtain are tight and improve on recent results in
that direction, such as for the Mixed Multinomial Logit model by
Rusmevichientong et al. (2014). An appealing feature of our analysis is its
simplicity, as it relies only on the regularity condition.
We also draw a connection between assortment optimisation and two pricing
problems called unit demand envyfree pricing and Stackelberg minimum spanning
tree: These problems can be restated as assortment problems under discrete
choice models satisfying the regularity condition, and moreover revenueordered
assortments correspond then to the wellstudied uniform pricing heuristic. When
specialised to that setting, the general bounds we establish for
revenueordered assortments match and unify the best known results on uniform
pricing.

We study the assortment optimization problem under the Sequential Multinomial
Logit (SML), a discrete choice model that generalizes the multinomial logit
(MNL). Under the SML model, products are partitioned into two levels, to
capture differences in attractiveness, brand awareness and, or visibility of
the products in the market. When a consumer is presented with an assortment of
products, she first considers products in the first level and, if none of them
is purchased, products in the second level are considered. This model is a
special case of the PerceptionAdjusted Luce Model (PALM) recently proposed by
Echenique et al (2018). It can explain many behavioural phenomena such as the
attraction, compromise, similarity effects and choice overload which cannot be
explained by the MNL model or any discrete choice model based on random
utility. In particular, the SML model allows violations to regularity which
states that the probability of choosing a product cannot increase if the offer
set is enlarged.
This paper shows that the seminal concept of revenueordered assortment sets,
which contain an optimal assortment under the MNL model, can be generalized to
the SML model. More precisely, the paper proves that all optimal assortments
under the SML are revenueordered by level, a natural generalization of
revenueordered assortments that contains, at most, a quadratic number of
assortments. As a corollary, assortment optimization under the SML is
polynomialtime solvable. This result is particularly interesting given that
the SML model does not satisfy the regularity condition and, therefore, it can
explain choice behaviours that cannot be explained by any choice model based on
random utility.

We study the dynamic pricing problem faced by a monopolistic retailer who
sells a storable product to forwardlooking consumers. In this framework, the
two major pricing policies (or mechanisms) studied in the literature are the
preannounced (commitment) pricing policy and the contingent (threat or history
dependent) pricing policy. We analyse and compare these pricing policies in the
setting where the good can be purchased along a finite time horizon in
indivisible atomic quantities. First, we show that, given linear storage costs,
the retailer can compute an optimal preannounced pricing policy in polynomial
time by solving a dynamic program. Moreover, under such a policy, we show that
consumers do not need to store units in order to anticipate price rises.
Second, under the contingent pricing policy rather than the preannounced
pricing mechanism, (i) prices could be lower, (ii) retailer revenues could be
higher, and (iii) consumer surplus could be higher. This result is surprising,
in that these three facts are in complete contrast to the case of a retailer
selling divisible storable goods Dudine et al. (2006). Third, we quantify
exactly how much more profitable a contingent policy could be with respect to a
preannounced policy. Specifically, for a market with $N$ consumers, a
contingent policy can produce a multiplicative factor of $\Omega(\log N)$ more
revenues than a preannounced policy, and this bound is tight.

We propose a new discrete choice model that generalizes the random utility
model (RUM). We show that this model, called the \emph{Generalized Stochastic
Preference} (GSP) model can explain several choice phenomena that can't be
represented by a RUM. In particular, the model can easily (and also exactly)
replicate some well known examples that are not RUM, as well as controlled
choice experiments carried out since 1980's that possess strong regularity
violations. One such regularity violation is the \emph{decoy effect} in which
the probability of choosing a product increases when a similar, but inferior
product is added to the choice set. An appealing feature of the GSP is that it
is nonparametric and therefore it has very high flexibility. The model has
also a simple description and interpretation: it builds upon the well known
representation of RUM as a stochastic preference, by allowing some additional
consumer types to be nonrational.

This paper considers trialoffer markets where consumer preferences are
modeled by a multinomial logit with social influence and position bias. The
social signal for a product is given by its current market share raised to
power r. The paper shows that, when r is strictly between 0 and 1, and a static
position assignment (e.g., a quality ranking) is used, the market converges to
a unique equilibrium where the market shares depend only on product quality,
not their initial appeals or the early dynamics. When r is greater than 1, the
market becomes unpredictable. In many cases, the market goes to a monopoly for
some product: Which product becomes a monopoly depends on the initial
conditions of the market. These theoretical results are complemented by an
agentbased simulation which indicates that convergence is fast when r is
between 0 and 1, and that the quality ranking dominates the wellknown
popularity ranking in terms of market efficiency. These results shed a new
light on the role of social influence which is often blamed for
unpredictability, inequalities, and inefficiencies in markets. In contrast,
this paper shows that, with a proper social signal and position assignment for
the products, the market becomes predictable, and inequalities and
inefficiencies can be controlled appropriately.

This paper studies assortment and pricing optimization problems under the
TwoStage Luce model (2SLM), a discrete choice model introduced by Echenique
and Saito (2018) that generalizes the multinomial logit model (MNL). The model
employs an utility function as in the the MNL, and a dominance relation between
products. When consumers are offered an assortmentS , they first discard all
dominated products in S and then select one of the remaining products using the
standard MNL. This model may violate the regularity condition, which states
that the probability of choosing a product cannot increase if the offer set is
enlarged. Therefore, the 2SLM falls outside the large family of discrete choice
models based on random utility which contains almost all choice models studied
in revenue management. We prove that the assortment problem under the 2SLM is
polynomialtime solvable. Moreover, we show that the capacitated assortment
optimization problem is NPhard and but it admits polynomialtime algorithms
for the relevant special cases cases where (1) the dominance relation is
attractivenesscorrelated and (2) its transitive reduction is a forest. The
proofs exploit a strong connection between assortments under the 2SLM and
independent sets in comparability graphs. Finally, we study the associated
joint pricing and assortment problem under this model. First, we show that well
known optimal pricing policy for the MNL can be arbitrarily bad. Our main
result in this section is the development of an efficient algorithm for this
pricing problem. The resulting optimal pricing strategy is simple to describe:
it assigns the same price for all products, except for the one with the highest
attractiveness and as well as for the one with the lowest attractiveness.

A durable good is a longlasting good that can be consumed repeatedly over
time, and a duropolist is a monopolist in the market of a durable good. In
1972, Ronald Coase conjectured that a duropolist who lacks commitment power
cannot sell the good above the competitive price if the time between periods
approaches zero. Coase's counterintuitive conjecture was later proven by Gul et
al. (1986) under an infinite time horizon model with nonatomic consumers.
Remarkably, the situation changes dramatically for atomic consumers and an
infinite time horizon. Bagnoli et al. (1989) showed the existence of a
subgameperfect Nash equilibrium where the duropolist extracts all the consumer
surplus. Observe that, in these cases, duropoly profits are either arbitrarily
smaller or arbitrarily larger than the corresponding static monopoly profits 
the profit a monopolist for an equivalent consumable good could generate. In
this paper we show that the result of Bagnoli et al. (1989) is in fact driven
by the infinite time horizon. Indeed, we prove that for finite time horizons
and atomic agents, in any equilibrium satisfying the standard skimming
property, duropoly profits are at most an additive factor more than static
monopoly profits. In particular, duropoly profits are always at least static
monopoly profits but never exceed twice the static monopoly profits.
Finally we show that, for atomic consumers, equilibria may exist that do not
satisfy the skimming property. For two time periods, we prove that amongst all
equilibria that maximize duropoly profits, at least one of them satisfies the
skimming property. We conjecture that this is true for any number of time
period.

Trialoffer markets, where customers can sample a product before deciding
whether to buy it, are ubiquitous in the online experience. Their static and
dynamic properties are often studied by assuming that consumers follow a
multinomial logit model and try exactly one product. In this paper, we study
how to generalize existing results to a more realistic setting where consumers
can try multiple products. We show that a multinomial logit model with
continuation can be reduced to a standard multinomial logit model with
different appeal and product qualities. We examine the consequences of this
reduction on the performance and predictability of the market, the role of
social influence, and the ranking policies.

We propose a model of interdependent scheduling games in which each player
controls a set of services that they schedule independently. A player is free
to schedule his own services at any time; however, each of these services only
begins to accrue reward for the player when all predecessor services, which may
or may not be controlled by the same player, have been activated. This model,
where players have interdependent services, is motivated by the problems faced
in planning and coordinating largescale infrastructures, e.g., restoring
electricity and gas to residents after a natural disaster or providing medical
care in a crisis when different agencies are responsible for the delivery of
staff, equipment, and medicine. We undertake a gametheoretic analysis of this
setting and in particular consider the issues of welfare maximization,
computing best responses, Nash dynamics, and existence and computation of Nash
equilibria.

The purchasing behaviour of consumers is often influenced by numerous
factors, including the visibility of the products and the influence of other
customers through their own purchases or their recommendations.
Motivated by trialoffer and freemium markets and a number of online markets
for cultural products, leisure services, and retail, this paper studies the
dynamics of a marketplace ran by a single firm and which is visited by
heterogeneous consumers whose choice preferences can be modeled using a Mixed
Multinomial Logit. In this marketplace, consumers are influenced by past
purchases, the inherent appeal of the products, and the visibility of each
product. The resulting market generalizes recent models already verified in
cultural markets.
We examine various marketing policies for this market and analyze their
longterm dynamics and the potential benefits of social influence. In
particular, we show that the heterogeneity of the customers complicates the
market significantly: Many of the optimality and computational properties of
the corresponding homogeneous market no longer hold. To remedy these
limitations, we explore a market segmentation strategy and quantify its
benefits. The theoretical results are complemented by Monte Carlo simulations
conducted on examples of interest.

We introduce oneway games, a framework motivated by applications in
largescale power restoration, humanitarian logistics, and integrated
supplychains. The distinguishable feature of the games is that the payoff of
some player is determined only by her own strategy and does not depend on
actions taken by other players. We show that the equilibrium outcome in oneway
games without payments and the social cost of any expost efficient mechanism,
can be far from the optimum. We also show that it is impossible to design a
BayesNash incentivecompatible mechanism for oneway games that is
budgetbalanced, individually rational, and efficient. To address this negative
result, we propose a privacypreserving mechanism that is incentivecompatible
and budgetbalanced, satisfies expost individual rationality conditions, and
produces an outcome which is more efficient than the equilibrium without
payments. The mechanism is based on a singleoffer bargaining and we show that
a randomized multioffer extension brings no additional benefit.

Social influence is ubiquitous in cultural markets, from book recommendations
in Amazon, to song popularities in iTunes and the ranking of newspaper articles
in the online edition of the New York Times to mention only a few. Yet social
influence is often presented in a bad light, often because it supposedly
increases market unpredictability.
Here we study a model of trialoffer markets, in which participants try
products and later decide whether to purchase. We consider a simple policy
which ranks the products by quality when presenting them to market
participants. We show that, in this setting, market efficiency always benefits
from social influence. Moreover, we prove that the market converges almost
surely to a monopoly for the product of highest quality, making the market both
predictable and asymptotically optimal. Computational experiments confirm that
the quality ranking policy identifies "blockbusters" in reasonable time,
outperforms other policies, and is highly predictable. These results indicate
that social influence does not necessarily increase market unpredicatibility.
The outcome really depends on how social influence is used.

Social influence has been shown to create significant unpredictability in
cultural markets, providing one potential explanation why experts routinely
fail at predicting commercial success of cultural products. To counteract the
difficulty of making accurate predictions, "measure and react" strategies have
been advocated but finding a concrete strategy that scales for very large
markets has remained elusive so far. Here we propose a "measure and optimize"
strategy based on an optimization policy that uses product quality, appeal, and
social influence to maximize expected profits in the market at each decision
point. Our computational experiments show that our policy leverages social
influence to produce significant performance benefits for the market, while our
theoretical analysis proves that our policy outperforms in expectation any
policy not displaying social information. Our results contrast with earlier
work which focused on showing the unpredictability and inequalities created by
social influence. Not only do we show for the first time that dynamically
showing consumers positive social information under our policy increases the
expected performance of the seller in cultural markets. We also show that, in
reasonable settings, our policy does not introduce significant unpredictability
and identifies "blockbusters". Overall, these results shed new light on the
nature of social influence and how it can be leveraged for the benefits of the
market.

Motivated by applications in retail, online advertising, and cultural
markets, this paper studies how to find the optimal assortment and positioning
of products subject to a capacity constraint. We prove that the optimal
assortment and positioning can be found in polynomial time for a multinomial
logit model capturing utilities, position bias, and social influence. Moreover,
in a dynamic market, we show that the policy that applies the optimal
assortment and positioning and leverages social influence outperforms in
expectation any policy not using social influence.