
A special case of Myerson's classic result describes the revenueoptimal
equilibrium when a seller offers a single item to a buyer. We study a repeated
sales extension of this model: a seller offers to sell a single fresh copy of
an item to the same buyer every day via a posted price. The buyer's private
value for the item is drawn initially from a publicly known distribution $F$
and remains the same throughout. A key aspect of this game is that the seller
might try to learn the buyer's private value to extract more revenue, while the
buyer is motivated to hide it. We study the Perfect Bayesian Equilibria (PBE)
in this setting with varying levels of commitment power to the seller. We find
that the seller having the commitment power to not raise prices subsequent to a
purchase significantly improves revenue in a PBE.

We study games in which a network mediates strategic spillovers and
externalities among the players. How does a planner optimally target
interventions that change individuals' private returns to investment? We
analyze this question by decomposing any intervention into orthogonal principal
components, which are determined by the network and are ordered according to
their associated eigenvalues. There is a close connection between the nature of
spillovers and the representation of various principal components in the
optimal intervention. In games of strategic complements (substitutes),
interventions place more weight on the top (bottom) principal components, which
reflect more global (local) network structure. For large budgets, optimal
interventions are simple  they involve a single principal component.

Classic cakecutting algorithms enable people with different preferences to
divide among them a heterogeneous resource (``cake''), such that the resulting
division is fair according to each agent's individual preferences. However,
these algorithms either ignore the geometry of the resource altogether, or
assume it is onedimensional. In practice, it is often required to divide
multidimensional resources, such as landestates or advertisement spaces in
print or electronic media. In such cases, the geometric shape of the allotted
piece is of crucial importance. For example, when building houses or designing
advertisements, in order to be useful, the allotments should be squares or
rectangles with bounded aspectratio. We thus introduce the problem of fair
land division  fair division of a multidimensional resource wherein the
allocated piece must have a prespecified geometric shape. We present
constructive division algorithms that satisfy the two most prominent fairness
criteria, namely envyfreeness and proportionality. In settings where
proportionality cannot be achieved due to the geometric constraints, our
algorithms provide a partiallyproportional division, guaranteeing that the
fraction allocated to each agent be at least a certain positive constant. We
prove that in many natural settings the envyfreeness requirement is compatible
with the best attainable partialproportionality.

Ranking alternatives is a natural way for humans to explain their
preferences. It is being used in many settings, such as school choice, course
allocations and residency matches. In some cases, several `items' are given to
each participant. Without having any information on the underlying cardinal
utilities, arguing about fairness of allocation requires extending the ordinal
item ranking to ordinal bundle ranking. The most commonly used such extension
is stochastic dominance (SD), where a bundle X is preferred over a bundle Y if
its score is better according to all additive score functions. SD is a very
conservative extension, by which few allocations are necessarily fair while
many allocations are possibly fair. We propose to make a natural assumption on
the underlying cardinal utilities of the players, namely that the difference
between two items at the top is larger than the difference between two items at
the bottom. This assumption implies a preference extension which we call
diminishing differences (DD), where X is preferred over Y if its score is
better according to all additive score functions satisfying the DD assumption.
We give a full characterization of allocations that are
necessarilyproportional or possiblyproportional according to this assumption.
Based on this characterization, we present a polynomialtime algorithm for
finding a necessarilyDDproportional allocation if it exists. Using
simulations, we show that with high probability, a necessarilyproportional
allocation does not exist but a necessarilyDDproportional allocation exists,
and moreover, that allocation is proportional according to the underlying
cardinal utilities. We also consider chore allocation under the analogous
condition  increasingdifferences.

Interactiveproof games model the scenario where an honest party interacts
with powerful but strategic provers, to elicit from them the correct answer to
a computational question. Interactive proofs are increasingly used as a
framework to design protocols for computation outsourcing.
Existing interactiveproof games largely fall into two categories: either as
games of cooperation such as multiprover interactive proofs and cooperative
rational proofs, where the provers work together as a team; or as games of
conflict such as refereed games, where the provers directly compete with each
other in a zerosum game. Neither of these extremes truly capture the strategic
nature of service providers in outsourcing applications. How to design and
analyze noncooperative interactive proofs is an important open problem.
In this paper, we introduce a mechanismdesign approach to define a
multiprover interactiveproof model in which the provers are rational and
noncooperativethey act to maximize their expected utility given others'
strategies. We define a strong notion of backwards induction as our solution
concept to analyze the resulting extensiveform game with imperfect
information.
Our protocols provide utility gap guarantees, which are analogous to
soundness gap in classic interactive proofs. At a high level, a utility gap of
u means that the protocol is robust against provers that may not care about a
utility loss of 1/u.
We fully characterize the complexity of our proof system under different
utility gap guarantees. For example, we show that with a polynomial utility
gap, the power of noncooperative rational interactive proofs is exactly
P^NEXP.

We consider the problem of designing a revenueoptimal mechanism in the
twoitem, singlebuyer, unitdemand setting when the buyer's valuations, $(z_1,
z_2)$, are uniformly distributed in an arbitrary rectangle
$[c,c+b_1]\times[c,c+b_2]$ in the positive quadrant. We provide a complete and
explicit solution for arbitrary nonnegative values of $(c,b_1,b_2)$. We
identify five simple structures, each with at most five (possibly stochastic)
menu items, and prove that the optimal mechanism has one of the five
structures. We also characterize the optimal mechanism as a function of $b_1,
b_2$, and $c$. When $c$ is low, the optimal mechanism is a posted price
mechanism with an exclusion region; when $c$ is high, it is a posted price
mechanism without an exclusion region. Our results are the first to show the
existence of optimal mechanisms with no exclusion region, to the best of our
knowledge.

We consider the design of a revenueoptimal mechanism when two items are
available to be sold to a single buyer whose valuation is uniformly distributed
over an arbitrary rectangle $[c_1,c_1+b_1]\times[c_2,c_2+b_2]$ in the positive
quadrant. We provide an explicit, complete solution for arbitrary nonnegative
values of $(c_1,c_2,b_1,b_2)$. We identify eight simple structures, each with
at most $4$ (possibly stochastic) menu items, and prove that the optimal
mechanism has one of these eight structures. We also characterize the optimal
mechanism as a function of $(c_1,c_2,b_1,b_2)$. The structures indicate that
the optimal mechanism involves (a) an interplay of individual sale and a bundle
sale when $c_1$ and $c_2$ are low, (b) a bundle sale when $c_1$ and $c_2$ are
high, and (c) an individual sale when one of them is high and the other is low.
To the best of our knowledge, our results are the first to show the existence
of optimal mechanisms with no exclusion region. We further conjecture, based on
promising preliminary results, that our methodology can be extended to a wider
class of distributions.

We study decentralized protection strategies against
SusceptibleInfectedSusceptible (SIS) epidemics on networks. We consider a
population game framework where nodes choose whether or not to vaccinate
themselves, and the epidemic risk is defined as the infection probability at
the endemic state of the epidemic under a degreebased meanfield
approximation. Motivated by studies in behavioral economics showing that humans
perceive probabilities and risks in a nonlinear fashion, we specifically
examine the impacts of such misperceptions on the Nash equilibrium protection
strategies. We first establish the existence and uniqueness of a threshold
equilibrium where nodes with degrees larger than a certain threshold vaccinate.
When the vaccination cost is sufficiently high, we show that behavioral biases
cause fewer players to vaccinate, and vice versa. We quantify this effect for a
class of networks with powerlaw degree distributions by proving tight bounds
on the ratio of equilibrium thresholds under behavioral and true perceptions of
probabilities. We further characterize the socially optimal vaccination policy
and investigate the inefficiency of Nash equilibrium.

Game Theory (GT) has been used with significant success to formulate, and
either design or optimize, the operation of many representative communications
and networking scenarios. The games in these scenarios involve, as usual,
diverse players with conflicting goals. This paper primarily surveys the
literature that has applied theoretical games to wireless networks, emphasizing
use cases of upcoming MultiAccess Edge Computing (MEC). MEC is relatively new
and offers cloud services at the network periphery, aiming to reduce service
latency backhaul load, and enhance relevant operational aspects such as Quality
of Experience or security. Our presentation of GT is focused on the major
challenges imposed by MEC services over the wireless resources. The survey is
divided into classical and evolutionary games. Then, our discussion proceeds to
more specific aspects which have a considerable impact on the game usefulness,
namely: rational vs. evolving strategies, cooperation among players, available
game information, the way the game is played (single turn, repeated), the game
model evaluation, and how the model results can be applied for both optimizing
resourceconstrained resources and balancing diverse tradeoffs in real edge
networking scenarios. Finally, we reflect on lessons learned, highlighting
future trends and research directions for applying theoretical model games in
upcoming MEC services, considering both network design issues and usage
scenarios.

In this paper we study several monotonicity axioms in approvalbased
multiwinner voting rules. We consider monotonicity with respect to the support
received by the winners and also monotonicity in the size of the committee.
Monotonicity with respect to the support is studied when the set of voters does
not change and when new voters enter the election. For each of these two cases
we consider a strong and a weak version of the axiom. We observe certain
incompatibilities between the monotonicity axioms and wellknown representation
axioms (extended/proportional justified representation) for the voting rules
that we analyze and provide formal proofs of incompatibility between some of
these axioms and perfect representation.

We provide simple and approximately revenueoptimal mechanisms in the
multiitem multibidder settings. We unify and improve all previous results, as
well as generalize the results to broader cases. In particular, we prove that
the better of the following two simple, deterministic and Dominant Strategy
Incentive Compatible mechanisms, a sequential posted price mechanism or an
anonymous sequential posted price mechanism with entry fee, achieves a constant
fraction of the optimal revenue among all randomized, Bayesian Incentive
Compatible mechanisms, when buyers' valuations are XOS over independent items.
If the buyers' valuations are subadditive over independent items, the
approximation factor degrades to $O(\log m)$, where $m$ is the number of items.
We obtain our results by first extending the CaiDevanurWeinberg duality
framework to derive an effective benchmark of the optimal revenue for
subadditive bidders, and then analyzing this upper bound with new techniques.

Budgets play a significant role in realworld sequential auction markets such
as those implemented by Internet companies. To maximize the value provided to
auction participants, spending is smoothed across auctions so budgets are used
for the best opportunities. Motivated by a mechanism used in practice by
several companies, this paper considers a smoothing procedure that relies on
{\em pacing multipliers}: on behalf of each buyer, the auction market applies a
factor between 0 and 1 that uniformly scales the bids across all auctions.
Reinterpreting this process as a game between buyers, we introduce the notion
of {\em pacing equilibrium}, and prove that they are always guaranteed to
exist. We demonstrate through examples that a market can have multiple pacing
equilibria with large variations in several natural objectives. We show that
pacing equilibria refine another popular solution concept, competitive
equilibria, and show further connections between the two solution concepts.
Although we show that computing either a socialwelfaremaximizing or a
revenuemaximizing pacing equilibrium is NPhard, we present a mixedinteger
program (MIP) that can be used to find equilibria optimizing several relevant
objectives. We use the MIP to provide evidence that: (1) equilibrium
multiplicity occurs very rarely across several families of random instances,
(2) static MIP solutions can be used to improve the outcomes achieved by a
dynamic pacing algorithm with instances based on a realworld auction market,
and (3) for the instances we study, buyers do not have an incentive to
misreport bids or budgets provided there are enough participants in the
auction.

We study an independent bestresponse dynamics on network games in which the
nodes (players) decide to revise their strategies independently with some
probability. We provide several bounds on the convergence time to an
equilibrium as a function of this probability, the degree of the network, and
the potential of the underlying games. These dynamics are somewhat more
suitable for distributed environments than the classical better and
bestresponse dynamics where players revise their strategies "sequentially",
i.e., no two players revise their strategies simultaneously.

Communities are an important feature of social networks. In fact, it seems
that communities are necessary for a social network to be efficient. However,
there exist very few formal studies of the actual role of communities in social
networks, how they emerge, and how they are structured. The goal of this paper
is to propose a mathematical model to study communities in social networks. For
this, we consider a particular case of a social network, namely information
networks. We assume that there is a population of agents who are interested in
obtaining content. Agents differ in the type of content they are interested in.
The goal of agents is to form communities in order to maximize their utility
for obtaining and producing content. We use this model to characterize the
structure of communities that emerge in this setting. While the proposed model
is very simple, the obtained results suggest that it indeed is able to capture
key properties of information communities.

Taobao, as the largest online retail platform in the world, provides billions
of online display advertising impressions for millions of advertisers every
day. For commercial purposes, the advertisers bid for specific spots and target
crowds to compete for business traffic. The platform chooses the most suitable
ads to display in tens of milliseconds. Common pricing methods include cost per
mille (CPM) and cost per click (CPC). Traditional advertising systems target
certain traits of users and ad placements with fixed bids, essentially regarded
as coarsegrained matching of bid and traffic quality. However, the fixed bids
set by the advertisers competing for different quality requests cannot fully
optimize the advertisers' key requirements. Moreover, the platform has to be
responsible for the business revenue and user experience. Thus, we proposed a
bid optimizing strategy called optimized cost per click (OCPC) which
automatically adjusts the bid to achieve finer matching of bid and traffic
quality of page view (PV) request granularity. Our approach optimizes
advertisers' demands, platform business revenue and user experience and as a
whole improves traffic allocation efficiency. We have validated our approach in
Taobao display advertising system in production. The online A/B test shows our
algorithm yields substantially better results than previous fixed bid manner.

We consider a market in which capacityconstrained generators compete in
scalarparameterized supply functions to serve an inelastic demand spread
throughout a transmission constrained power network. The market clears
according to a locational marginal pricing mechanism, in which the independent
system operator (ISO) determines the generators' production quantities to
minimize the revealed cost of meeting demand, while ensuring that network
transmission and generator capacity constraints are met. Under the stylizing
assumption that both the ISO and generators choose their strategies
simultaneously, we establish the existence of Nash equilibria for the
underlying market, and derive an upper bound on the allocative efficiency loss
at Nash equilibrium relative to the socially optimal level. We also
characterize an upper bound on the markup of locational marginal prices at Nash
equilibrium above their perfectly competitive levels. Of particular relevance
to ex ante market power monitoring, these bounds reveal the role of certain
market structuresspecifically, the \emph{market share} and \emph{residual
supply index} of a producerin predicting the degree to which that producer
is able to exercise market power to influence the market outcome to its
advantage. Finally, restricting our attention to the simpler setting of a
twonode power network, we provide a characterization of market structures
under which a Braesslike paradox occurs due to the exercise of market
powerthat is to say, we provide a necessary and sufficient condition on
market structure under which the strengthening of the network's transmission
line capacity results in the (counterintuitive) increase in the total cost of
generation at Nash equilibrium.

This paper considers a class of reinforcementbased learning (namely,
perturbed learning automata) and provides a stochasticstability analysis in
repeatedlyplayed, positiveutility, finite strategicform games. Prior work in
this class of learning dynamics primarily analyzes asymptotic convergence
through stochastic approximations, where convergence can be associated with the
limit points of an ordinarydifferential equation (ODE). However, analyzing
global convergence through an ODEapproximation requires the existence of a
Lyapunov or a potential function, which naturally restricts the analysis to a
fine class of games. To overcome these limitations, this paper introduces an
alternative framework for analyzing asymptotic convergence that is based upon
an explicit characterization of the invariant probability measure of the
induced Markov chain. We further provide a methodology for computing the
invariant probability measure in positiveutility games, together with an
illustration in the context of coordination games.

This paper contains an extensive combinatorial analysis of the singlepeaked
domain restriction and investigates the likelihood that an election is
singlepeaked. We provide a very general upper bound result for domain
restrictions that can be defined by certain forbidden configurations. This
upper bound implies that many domain restrictions (including the singlepeaked
restriction) are very unlikely to appear in a random election chosen according
to the Impartial Culture assumption. For singlepeaked elections, this upper
bound can be refined and complemented by a lower bound that is asymptotically
tight. In addition, we provide exact results for elections with few voters or
candidates. Moreover, we consider the P\'{o}lya urn model and the Mallows model
and obtain lower bounds showing that singlepeakedness is considerably more
likely to appear for certain parameterizations.

DevicetoDevice (D2D) communication is offering smart phone users a choice
to share files with each other without communicating with the cellular network.
In this paper, we discuss the behaviors of two characters in the D2D data
transaction model from an economic point of view: the data buyers who wish to
buy a certain quantity of data, as well as the data sellers who wish to sell
data through the D2D network. The optimal price and purchasing strategies are
analyzed and deduced based on game theory.

Approvalpreferential voting is problematical since it combines two different
kinds of information that could by themselves lead to different choices. This
article analyses the problem and studies a new proposal to deal with it. The
existing methods are overviewed with special attention to several desirable
properties that are not always met. Particular emphasis is made on certain
rather unknown views of Condorcet about this subject. The proposed procedure
definitely aims for a choice in the spirit of approval voting. However, it
still makes use of the preferential information so as to improve the approval
one. This is done by means of the path scores, in common to Schulze's method
for preferential voting. The resulting method, that we call pathrevised
approval choice, is shown to enjoy several good properties. In particular, it
fulfils in a welldefined sense Condorcet's latest view that a surely good
option should prevail over a doubtfully best one.

This article considers a twoplayer strategic game for network routing under
link disruptions. Player 1 (defender) routes flow through a network to maximize
her value of effective flow while facing transportation costs. Player 2
(attacker) simultaneously disrupts one or more links to maximize her value of
lost flow but also faces cost of disrupting links. Linear programming duality
in zerosum games and the MaxFlow MinCut Theorem are applied to obtain
properties that are satisfied in any Nash equilibrium. A characterization of
the support of the equilibrium strategies is provided using graphtheoretic
arguments. Finally, conditions under which these results extend to
budgetconstrained environments are also studied. These results extend the
classical minimum cost maximum flow problem and the minimum cut problem to a
class of security games on flow networks.

This paper develops tools for welfare and revenue analyses of BayesNash
equilibria in asymmetric auctions with singledimensional agents. We employ
these tools to derive price of anarchy results for social welfare and revenue.
Our approach separates the standard smoothness framework into two distinct
parts, isolating the analysis common to any auction from the analysis specific
to a given auction. The first part relates a bidder's contribution to welfare
in equilibrium to their contribution to welfare in the optimal auction using
the price the bidder faces for additional allocation. Intuitively, either an
agent's utility and hence contribution to welfare is high, or the price she has
to pay for additional allocation is high relative to her value. We call this
condition value covering; it holds in every BayesNash equilibrium of any
auction. The second part, revenue covering, relates the prices bidders face for
additional allocation to the revenue of the auction, using an auction's rules
and feasibility constraints. Combining the two parts gives approximation
results to the optimal welfare, and, under the right conditions, the optimal
revenue. In mechanisms with reserve prices, our welfare results show
approximation with respect to the optimal mechanism with the same reserves.
As a centerpiece result, we analyze the singleitem firstprice auction with
individual monopoly reserves. When each distribution satisfies a regularity
condition the auction's revenue is at least a $2e/(e1) \approx 3.16$
approximation to the revenue of the optimal auction. We also give bounds for
matroid auctions with firstprice or allpay semantics, and the generalized
firstprice position auction. Finally, we give an extension theorem for
simultaneous composition, i.e., when multiple auctions are run simultaneously,
with singlevalued, unitdemand agents.

We study linear Fisher markets with satiation. In these markets, sellers have
earning limits and buyers have utility limits. Beyond natural applications in
economics, these markets arise in the context of maximizing Nash social welfare
when allocating indivisible items to agents. In contrast to markets with either
earning or utility limits, markets with both limits have not been studied
before. They turn out to have fundamentally different properties.
In general, the existence of competitive equilibria is not guaranteed. We
identify a natural property of markets (termed money clearing) that implies
existence. We show that the set of equilibria is not always convex, answering a
question of Cole et al. [EC'17]. We design an FPTAS to compute an approximate
equilibrium and prove that the problem of computing an exact equilibrium lies
in the intersection of complexity classes PLS and PPAD. For a constant number
of buyers or goods, we give a polynomialtime algorithm to compute an exact
equilibrium.
We show how (approximate) equilibria can be rounded and provide the first
constantfactor approximation algorithm (with a factor of 2.404) for maximizing
Nash social welfare when agents have budgetadditive valuations. Finally, we
significantly improve the approximation hardness for additive valuations to
\sqrt{8/7} > 1.069 (over 1.00008 by Lee [IPL'17]).

Recently, Dallal, Neider, and Tabuada studied a generalization of the
classical gametheoretic model used in program synthesis, which additionally
accounts for unmodeled intermittent disturbances. In this extended framework,
one is interested in computing optimally resilient strategies, i.e., strategies
that are resilient against as many disturbances as possible. Dallal, Neider,
and Tabuada showed how to compute such strategies for safety specifications. In
this work, we compute optimally resilient strategies for a much wider range of
winning conditions and show that they do not require more memory than winning
strategies in the classical model. Our algorithms only have a polynomial
overhead in comparison to the ones computing winning strategies. In particular,
for parity conditions, optimally resilient strategies are positional and can be
computed in quasipolynomial time.

In this paper we consider the price of anarchy (PoA) in multicommodity flows
where the latency or delay function on an edge has a heterogeneous dependency
on the flow commodities, i.e. when the delay on each link is dependent on the
flow of individual commodities, rather than on the aggregate flow. An
application of this study is the performance analysis of a network with
differentiated traffic that may arise when traffic is prioritized according to
some type classification. This study has implications in the debate on
netneutrality. We provide price of anarchy bounds for networks with $k$ (types
of) commodities where each link is associated with heterogeneous polynomial
delays, i.e. commodity $i$ on edge $e$ faces delay specified by
$g_{i1}(e)f^{\theta}_1(e) + g_{i2}(e)f^{\theta}_2(e) + \ldots +
g_{ik}(e)f^{\theta}_k(e) + c_i(e), $ where $f_i(e)$ is the flow of the $i$th
commodity through edge $e$, $\theta \in {\cal N}$, $g_{i1}(e), g_{i2}(e),
\ldots, g_{ik}(e)$ and $c_i(e)$ are nonnegative constants. We consider both
atomic and nonatomic flows.
For networks with decomposable delay functions where the delay induced by a
particular commodity is the same, i.e. delays on edge $e$ are defined by
$a_1(e)f_1^\theta(e) + a_2(e)f_2^\theta(e) + \ldots + c(e)$ where $\forall j ,
\forall e: g_{1j}(e) = g_{2j}(e) = \ldots = a_j(e)$, we show an improved bound
on the price of anarchy.
Further, we show bounds on the price of anarchy for uniform latency functions
where each edge of the network has the same delay function.