-
作者：Cominetti, Roberto; Quattropani, Matteo; Scarsini, Marco
作者单位：Universidad Adolfo Ibanez; Luiss Guido Carli University
摘要：We consider two classes of games in which players are the vertices of a directed graph. Initially, nature chooses one player according to some fixed distribution and gives the player a buck. This player passes the buck to one of the player's out-neighbors in the graph. The procedure is repeated indefinitely. In one class of games, each player wants to minimize the asymptotic expected frequency of times that the player receives the buck. In the other class of games, the player wants to maximize...
-
作者：Ahmadi, Amir Ali; El Khadir, Bachir
作者单位：Princeton University
摘要：We study time-varying semidefinite programs (TV-SDPs), which are semidefinite programs whose data (and solutions) are functions of time. Our focus is on the setting where the data vary polynomially with time. We show that under a strict feasibility assumption, restricting the solutions to also be polynomial functions of time does not change the optimal value of the TV-SDP. Moreover, by using a Positivstellensatz (positive locus theorem) on univariate polynomial matrices, we show that the best ...
-
作者：Cui, Ying; Liang, Ling; Sun, Defeng; Toh, Kim-Chuan
作者单位：University of Minnesota System; University of Minnesota Twin Cities; National University of Singapore; Hong Kong Polytechnic University; National University of Singapore
摘要：The doubly nonnegative (DNN) cone, being the set of all positive semidefinite matrices whose elements are nonnegative, is a popular approximation of the computationally intractable completely positive cone. The major difficulty for implementing a Newton-type method to compute the projection of a given large-scale matrix onto the DNN cone lies in the possible failure of the constraint nondegeneracy, a generalization of the linear independence constraint qualification for nonlinear programming. ...
-
作者：Caragiannis, Ioannis; Voudouris, Alexandros A.
作者单位：University of Patras; University of Oxford
摘要：We study the efficiency of mechanisms for allocating a divisible resource. Given scalar signals submitted by all users, such a mechanism decides the fraction of the resource that each user will receive and a payment that will be collected from her. Users are self-interested and aim to maximize their utility (defined as their value for the resource fraction they receive minus their payment). Starting with the seminal work of Johari and Tsitsiklis, a long list of papers studied the price of anar...
-
作者：Chen, Boxiao; Chao, Xiuli; Shi, Cong
作者单位：University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital; University of Michigan System; University of Michigan
摘要：We consider a joint pricing and inventory control problem in which the customer's response to selling price and the demand distribution are not known a priori. Unsatisfied demand is lost and unobserved, and the only available information for decision making is the observed sales data (also known as censored demand). Conventional approaches, such as stochastic approximation, online convex optimization, and continuum-armed bandit algorithms, cannot be employed, because neither the realized value...
-
作者：Bayraktar, Erhan; Zhang, Yuchong
作者单位：University of Michigan System; University of Michigan; University of Toronto
摘要：We analyze a mean field tournament: a mean field game in which the agents receive rewards according to the ranking of the terminal value of their projects and are subject to cost of effort. Using Schrodinger bridges we are able to explicitly calculate the equilibrium. This allows us to identify the reward functions which would yield a desired equilibrium and solve several related mechanism design problems. We are also able to identify the effect of reward inequality on the players' welfare as ...
-
作者：Arunachaleswaran, Eshwar Ram; Barman, Siddharth; Rathi, Nidhi
作者单位：University of Pennsylvania; Indian Institute of Science (IISC) - Bangalore; Indian Institute of Science (IISC) - Bangalore
摘要：We study the problem of fair rent division that entails splitting the rent and allocating the rooms of an apartment among agents in a fair manner (i.e., under the imposed rents, no agent has a strictly stronger preference for any other agent's room). The utility functions specify the cardinal preferences of the agents for the rooms for every possible room rent. Although envy-free solutions are guaranteed to exist under reasonably general utility functions, efficient algorithms for finding them...
-
作者：Amiet, Ben; Collevecchio, Andrea; Scarsini, Marco; Zhong, Ziwen
作者单位：Monash University; Luiss Guido Carli University
摘要：In finite games, mixed Nash equilibria always exist, but pure equilibria may fail to exist. To assess the relevance of this nonexistence, we consider games where the payoffs are drawn at random. In particular, we focus on games where a large number of players can each choose one of two possible strategies and the payoffs are independent and identically distributed with the possibility of ties. We provide asymptotic results about the random number of pure Nash equilibria, such as fast growth an...
-
作者：Filmus, Yuval; Kawase, Yasushi; Kobayashi, Yusuke; Yamaguchi, Yutaro
作者单位：Technion Israel Institute of Technology; University of Tokyo; Kyoto University; Kyushu University; Kyushu University
摘要：A set function is called XOS if it can be represented by the maximum of additive functions. When such a representation is fixed, the number of additive functions required to define the XOS function is called the width. In this paper, we study the problem of maximizing XOS functions in the value oracle model. The problem is trivial for the XOS functions of width 1 because they are just additive, but it is already nontrivial even when the width is restricted to 2. We show two types of tight boun...
-
作者：Peck, James; Rampal, Jeevant
作者单位：University System of Ohio; Ohio State University; Indian Institute of Management (IIM System); Indian Institute of Management Ahmedabad
摘要：This paper analyzes a monopoly firm's profit-maximizing mechanism in the following context. There is a continuum of consumers with a unit demand for a good. The distribution of the consumers' valuations is given by one of two possible demand distributions/states. The consumers are uncertain about the demand state, and they update their beliefs after observing their own valuation for the good. The firm is uncertain about the demand state but infers it from the consumers' reported valuations. Th...
