nep-gth New Economics Papers
on Game Theory
Issue of 2018‒09‒03
29 papers chosen by
Sylvain Béal
Université de Franche-Comté

  1. Allocating Positions Fairly: An Auction and its Relationship to the Shapley Value By Matt Van Essen; John Wooders
  2. Non-Altruistic Equilibria By Ohnishi, Kazuhiro
  3. Sustainability of global feeding.Coopetitive interaction among vegan and non-vegan food firms By Carfì, David; Donato, Alessia; Schilirò, Daniele
  4. The story of conflict and cooperation By Mehmet S. Ismail
  5. Dynamic Nash Bargaining Solution for Two-stage Network Games By Junnan, Jie
  6. A rational decentralized generalized Nash equilibrium seeking for energy markets By Lorenzo Nespoli; Matteo Salani; Vasco Medici
  7. Accuracy and Retaliation in Repeated Games with Imperfect Private Monitoring: Experiments By Yutaka Kayaba; Hitoshi Matsushima; Tomohisa Toyama
  8. Timing Games with Irrational Types: Leverage-Driven Bubbles and Crash-Contingent Claims By Hitoshi Matsushima
  9. The Unbinding Core for Coalitional Form Games By Takaaki Abe; Yukihiko Funaki
  10. Competition for Foreign Capital under Asymmetric Revenue-Orientation By Pal, Rupayan; Sharma, Ajay
  11. Stochastic Differential Game in High Frequency Market By Taiga Saito; Akihiko Takahashi
  12. Solving Quadratic Multi-Leader-Follower Games by Smoothing the Follower's Best Response By Michael Herty; Sonja Steffensen; Anna Th\"unen
  13. Transferable Deposits as a Screening Mechanism By David Lagziel; Ehud Lehrer
  14. Low Reserve Prices in Auctions By Audrey Hu; Steven Matthews; Liang Zou
  15. Promoting cooperation by reputation-driven group formation By Han-Xin Yang; Zhen Wang
  16. Reputation is required for cooperation to emerge in dynamic networks By Jose A. Cuesta; Carlos Gracia-L\'azaro; Yamir Moreno; Angel S\'anchez
  17. The revelation principle does not always hold when strategies of agents are costly By Wu, Haoyang
  18. Markets Beyond Nash Welfare for Leontief Utilities By Ashish Goel; Reyna Hulett; Benjamin Plaut
  20. Customer Sharing in Economic Networks with Costs By Bin Li; Dong Hao; Dengji Zhao; Tao Zhou
  22. $k$th price auctions and Catalan numbers By Abdel-Hameed Nawar; Debapriya Sen
  23. Gradual Bargaining in Decentralized Asset Markets By Tai-Wei Hu; Guillaume Rocheteau; Lucie Lebeau; Younghwan In
  24. Debarment and Collusion in Procurement Auctions By Claudia Cerrone; Author-Name: Yoan Hermstruwer
  25. Cartel Stability under Quality Differentiation By Bos, Iwan; Marini, Marco A.
  26. Egalitarian Allocation Principles By Dietzenbacher, Bas
  27. Inventory Management for High-Frequency Trading with Imperfect Competition By Sebastian Herrmann; Johannes Muhle-Karbe; Dapeng Shang; Chen Yang
  28. Welfare Effects of Open-Access Competition on Railway Markets By Broman, Emanuel; Eliasson, Jonas
  29. Greedy Algorithms for Maximizing Nash Social Welfare By Siddharth Barman; Sanath Kumar Krishnamurthy; Rohit Vaish

  1. By: Matt Van Essen; John Wooders (Division of Social Science)
    Abstract: We study the problem of fairly allocating heterogenous items, priorities, positions, or property rights to participants with equal claims, in an incomplete information environment. We introduce a dynamic auction for solving this problem and we characterize both Bayes Nash equilibrium and “maxmin perfect” play. Building on these characterizations we show that: (i) equilibrium play converges to maxmin perfect play as bidders become infinitely risk averse, and (ii) each bidder obtains his Shapley value when every bidder follows his maxmin perfect strategy. Hence, the equilibrium allocation converges to the Shapley value allocation as bidders become more risk averse. Together these results provide both noncooperative and decision theoretic foundations for the Shapley value in an environment with incomplete information.
    Date: 2018–08
  2. By: Ohnishi, Kazuhiro
    Abstract: Which choice will a player make if he can make one of two choices in which his own payoffs are equal, but his rival’s payoffs are not equal, i.e. one with a large payoff for his rival and the other with a small payoff for his rival? This paper introduces non-altruistic equilibria for normal form games and extensive form non-altruistic equilibria for extensive form games as equilibrium concepts of noncooperative games by discussing such a problem and examines the connections between their equilibrium concepts and Nash and subgame perfect equilibria that are important and frequently encountered equilibrium concepts.
    Keywords: Normal form game, extensive form game, non-altruistic equilibrium.
    JEL: C72
    Date: 2018–08–01
  3. By: Carfì, David; Donato, Alessia; Schilirò, Daniele
    Abstract: In this paper, we face the problem of global feeding sustainability and related environmental issues, with a strong attention to possible public heath improvements. Specifically, we shall consider food producers and sellers of vegan (or vegetarian) and non-vegan (or non-vegetarian) food. We propose possible quantitative agreements among different food producers, in order to develop a sustainable healthier diet for future generations, by using a mathematical co-opetitive approach and game theory. The co-opetitive approach used by the authors provides a game theory model, which could help producers of vegan food an easier entry in global market and obtain a considerable free publicity. Meanwhile, the model could allow big producers/sellers of non-vegetarian food a smooth rapid transaction to more sustainable and healthier vegan or vegetarian production/supply. In particular, we propose an exemplary complex agreement setting among McDonald's and Muscle of Wheat, a small but strongly innovative Italian food producer. We think that, on one hand, Muscle of Wheat cannot enter a global market without the help of a large globalized food producer already present in the market, on the other hand, we think equally difficult that a large static and poorly innovative producer cannot follow credibly and rapidly enough the increasing and challenging issues of global food sustainability. We remark that our game model represents an asymmetric R&D alliance between McDonald's and Muscle of Wheat. The aim of our contribution is twofold. Firstly, we explain the advantages of a vegan diet for the human health, environmental issues, food sustainability, population sustainability; in fact, the model explain how global food producers could improve environmental, social and health conditions of world population. Secondly, we show how game theory normal-form and extensive-form games can be used in coopetition studies in order to increase health conditions of people, address climate change, address hunger in the world, improve welfare in a particular market. The results of the mathematical study prove that we can find win-win solutions for both firms, which are also good for world environment, human healthy, human population sustainability and climate change.
    Keywords: Sustainability of Food Production, Environmental Sustainability; Game Theory; Co-petitive Games; Green Economy
    JEL: C71 C72 C78 Q56 Q57
    Date: 2018–06
  4. By: Mehmet S. Ismail
    Abstract: The story of conflict and cooperation has started millions of years ago, and now it is everywhere: In biology, computer science, economics, humanities, law, philosophy, political science, and psychology. Wars, airline alliances, trade, oligopolistic cartels, evolution of species and genes, and team sports are examples of games of conflict and cooperation. However, Nash (1951)'s noncooperative games - in which each player acts independently without collaboration with any of the others - has become the dominant ideology in economics, game theory, and related fields. A simple falsification of this noncooperative theory is scientific publication: It is a rather competitive game, yet collaboration is widespread. In this paper, I propose a novel way to rationally play games of conflict and cooperation under the Principle of Free Will - players are free to cooperate to coordinate their actions or act independently. Anyone with a basic game theory background will be familiar with the setup in this paper, which is based on simple game trees. In fact, one hardly needs any mathematics to follow the arguments.
    Date: 2018–08
  5. By: Junnan, Jie
    Abstract: In Contributions to game theory and management, vol. XI. Collected papers presented on the Eleventh International Conference Game Theory and Management / Editors Leon A. Petrosyan, Nikolay A. Zenkevich. - SPb.: Saint Petersburg State University, 2018. - 330 p. The collection contains papers accepted for the Eleventh International Game Theory and Management (June 28-30, 2017, St. Petersburg State University, St. Petersburg, Russia).
    Keywords: network, time-consistency, Nash Bargaining solution,
    Date: 2018
  6. By: Lorenzo Nespoli; Matteo Salani; Vasco Medici
    Abstract: We propose a method to design a decentralized energy market which guarantees individual rationality (IR) in expectation, in the presence of system-level grid constraints. We formulate the market as a welfare maximization problem subject to IR constraints, and we make use of Lagrangian duality to model the problem as a n-person non-cooperative game with a unique generalized Nash equilibrium (GNE). We provide a distributed algorithm which converges to the GNE. The convergence and properties of the algorithm are investigated by means of numerical simulations.
    Date: 2018–06
  7. By: Yutaka Kayaba (University of Tokyo); Hitoshi Matsushima (University of Tokyo); Tomohisa Toyama (International Christian University)
    Abstract: We experimentally examine repeated prisoner’s dilemma with random termination, in which monitoring is imperfect and private. Our estimation indicates that a significant proportion of subjects follow generous tit-for-tat strategies, stochastic extensions of tit-for-tat. However, the observed retaliating policies are inconsistent with the generous tit-for-tat equilibrium behavior. Contrary to the prediction of equilibrium theory, subjects tend to retaliate more with high accuracy than with low accuracy. They tend to retaliate more than the equilibrium theory predicts with high accuracy, while they tend to retaliate less with low accuracy.
    Date: 2018–04
  8. By: Hitoshi Matsushima (Faculty of Economics, University of Tokyo)
    Abstract: This study investigates a timing game with irrational types; each player selects a time in a fixed time interval, and the player who selects the earliest time wins the game. We assume the possibility of irrational types in that each player is irrational with a positive probability, thus selecting the terminal time. We show that there exists the unique Nash equilibrium; according to it, every player never selects the initial time. As an application, we analyze a strategic aspect of leverage-driven bubbles; even if a company is unproductive, its stock price grows up according to an exogenous reinforcement pattern. During the bubble, this company is willing to raise huge funds by issuing new shares. We regard players as arbitrageurs, who decide whether to ride the bubble or burst it. We demonstrate two models, which are distinguished by whether crash-contingent claim, i.e., contractual agreement such that the purchaser of this claim receives a promised monetary amount from its seller if and only if the bubble crashes, is available. The availability of this claim deters the bubble; without crash-contingent claim, the bubble emerges and persists even if the degree of reinforcement is insufficient. Without crash-contingent claim, high leverage ratio fosters the bubble, while with crash-contingent claim, it rather deters the bubble.
    Date: 2018–06
  9. By: Takaaki Abe (JSPS Research Fellow. Graduate School of Economics, Waseda University.); Yukihiko Funaki (School of Political Science and Economics, Waseda University.)
    Abstract: In this paper, we introduce a new concept of core by extending the de nition of deviation. The traditional de nition of deviation allows for players to deviate if some pro table allocation exists after their deviation, while our new de nition requires that all possible allocations are pro table. Hence, our core becomes a superset of the traditional core. We examine some properties that our new core satis es and provide a sufficient condition for being nonempty. Moreover, we apply Ray's (1989) credibility to our core.
    Keywords: cooperative game, core, credibility, deviation
    JEL: C71
    Date: 2018–07
  10. By: Pal, Rupayan; Sharma, Ajay
    Abstract: This paper develops a model of inter-regional competition for mobile capital considering that regions may have different revenue-orientations. It shows that, if regions are asymmetric in terms of revenue-orientation, the less revenue-orientated region obtains higher tax-revenue and higher social welfare in the equilibrium than the more revenue-oriented region. However, if regions are symmetric, the equilibrium tax-revenue and social welfare are higher in the case of greater revenue-orientation of regions. Moreover, regions spend on public-investment and end up with Pareto-inferior equilibrium outcome, regardless of whether regions are symmetric or asymmetric. It also analyses implications of public-investment spill-over on equilibrium outcomes.
    Keywords: Asymmetric revenue orientation, Competition for foreign capital, Prisoners’ Dilemma, Public investment, Spillover, Tax
    JEL: C72 F2 F21 H25 H87 R38 R5 R50 R53
    Date: 2016–12
  11. By: Taiga Saito (Graduate School of Economics, The University of Tokyo); Akihiko Takahashi (Graduate School of Economics, The University of Tokyo)
    Abstract: This paper presents an application of a linear quadratic stochastic differential game to a model in finance, which describes trading behaviors of different types of players in a high frequency stock market. Stability of the high frequency market is a central issue for financial markets. Building a model that expresses the trading behaviors of the different types of players and the price actions in turmoil is important to set regulations to maintain fair markets. Firstly, we represent trading behaviors of the three types of players, algorithmic traders, general traders, and market makers as well as the mid-price process of a risky asset by a linear quadratic stochastic differential game. Secondly, we obtain a Nash equilibrium for open loop admissible strategies by solving a forward-backward stochastic differential equation (FBSDE) derived from the stochastic maximum principle. Finally, we present numerical examples of the Nash equilibrium for open loop admissible strategies and the corresponding price action of the risky asset, which agree with the empirical findings on trading behaviors of players in high frequency markets. This model can be used to investigate the impact of regulation changes on the market stability as well as trading strategies of the players.
    Date: 2018–05
  12. By: Michael Herty; Sonja Steffensen; Anna Th\"unen
    Abstract: We derive Nash-s-stationary equilibria for a class of quadratic multi-leader-follower games using the nonsmooth best response function. To overcome the challenge of nonsmoothness, we pursue a smoothing approach resulting in a reformulation as smooth Nash equilbrium problem. We prove existence and uniqueness for all smoothing parameters. For a decreasing sequence of these smoothing parameters accumulation points of Nash equilibria exist and we show that they fullfill the conditions of s-stationarity. Finally, we propose an update on the leader variables for efficient computation and numerically compare nonsmooth Newton and subgradient method.
    Date: 2018–08
  13. By: David Lagziel (BGU); Ehud Lehrer (TAU)
    Keywords: Reward Schemes; Investment firms; Investment game; Market design; Portfolio management
    JEL: C72 G11 G14 G23 G24
    Date: 2018
  14. By: Audrey Hu (Department of Economics, City University of Hong Kong); Steven Matthews (Department of Economics, University of Pennsylvania); Liang Zou (Department of Economics, University of Amsterdam)
    Abstract: Received auction theory prescribes that a reserve price which maximizes expected profit should be no less than the seller's own value for the auctioned object. In contrast, a common empirical observation is that many auctions have reserve prices set below seller's values, even at zero. This paper revisits the theory to find a potential resolution of the puzzle for second-price auctions. The main result is that an optimal reserve price may be less than the seller's value if bidders are risk averse and have interdependent values. Moreover, the resulting outcome may be arbitrarily close to that of an auction that has no reserve price, an absolute auction.
    Keywords: reserve price, risk aversion, interdependent values, second-price auction
    JEL: D44 D82
    Date: 2017–03–13
  15. By: Han-Xin Yang; Zhen Wang
    Abstract: In previous studies of spatial public goods game, each player is able to establish a group. However, in real life, some players cannot successfully organize groups for various reasons. In this paper, we propose a mechanism of reputation-driven group formation, in which groups can only be organized by players whose reputation reaches or exceeds a threshold. We define a player's reputation as the frequency of cooperation in the last $T$ time steps. We find that the highest cooperation level can be obtained when groups are only established by pure cooperators who always cooperate in the last $T$ time steps. Effects of the memory length $T$ on cooperation are also studied.
    Date: 2018–02
  16. By: Jose A. Cuesta; Carlos Gracia-L\'azaro; Yamir Moreno; Angel S\'anchez
    Abstract: Melamed, Harrell, and Simpson have recently reported on an experiment which appears to show that cooperation can arise in a dynamic network without reputational knowledge, i.e., purely via dynamics [1]. We believe that their experimental design is actually not testing this, in so far as players do know the last action of their current partners before making a choice on their own next action and subsequently deciding which link to cut. Had the authors given no information at all, the result would be a decline in cooperation as shown in [2].
    Date: 2018–03
  17. By: Wu, Haoyang
    Abstract: The revelation principle asserts that for any indirect mechanism and equilibrium, there is a corresponding direct mechanism with truth as an equilibrium. Although the revelation principle has been a fundamental theorem in the theory of mechanism design for a long time, so far the costs related to strategic actions of agents spent in a mechanism have not been fully discussed. In this paper, we investigate the correctness of the revelation principle when strategies of agents are costly. We point out two key results: (1) The strategy of each agent in the direct mechanism is just to report a type. Each agent does not need to take any other action to prove himself that his reported type is truthful, and should not play the strategy as specified in the indirect mechanism. Hence each agent should not spend the strategic costs in the direct mechanism (see Proposition 1); (2) When strategic costs cannot be neglected in the indirect mechanism, the proof of revelation principle given in Proposition 23.D.1 of the book ``A. Mas-Colell, M.D. Whinston and J.R. Green, Microeconomic Theory, Oxford University Press, 1995'' is wrong (see Proposition 2). We construct a simple labor model to show that a Bayesian implementable social choice function is not truthfully implementable (see Proposition 4), which contradicts the revelation principle.
    Keywords: Revelation principle; Game theory; Mechanism design.
    JEL: D71 D82
    Date: 2018–07–11
  18. By: Ashish Goel; Reyna Hulett; Benjamin Plaut
    Abstract: We study the allocation of divisible goods to competing agents via a market mechanism, focusing on agents with Leontief utilities. The majority of the economics and mechanism design literature has focused on \emph{linear} prices, meaning that the cost of a good is proportional to the quantity purchased. Equilibria for linear prices are known to be exactly the maximum Nash welfare allocations. \emph{Price curves} allow the cost of a good to be any (increasing) function of the quantity purchased. We show that price curve equilibria are not limited to maximum Nash welfare allocations with two main results. First, we show that an allocation can be supported by strictly increasing price curves if and only if it is \emph{group-domination-free}. A similarly characterization holds for weakly increasing price curves. We use this to show that given any allocation, we can compute strictly (or weakly) increasing price curves that support it (or show that none exist) in polynomial time. These results involve a connection to the \emph{agent-order matrix} of an allocation, which may have other applications. Second, we use duality to show that in the bandwidth allocation setting, any allocation maximizing a CES welfare function can be supported by price curves.
    Date: 2018–07
  19. By: David Lagziel (BGU); Ehud Lehrer (TAU)
    Keywords: screening problem; competitions; manipulation
    JEL: C70 D49 D82
    Date: 2018
  20. By: Bin Li; Dong Hao; Dengji Zhao; Tao Zhou
    Abstract: In an economic market, sellers, infomediaries and customers constitute an economic network. Each seller has her own customer group and the seller's private customers are unobservable to other sellers. Therefore, a seller can only sell commodities among her own customers unless other sellers or infomediaries share her sale information to their customer groups. However, a seller is not incentivized to share others' sale information by default, which leads to inefficient resource allocation and limited revenue for the sale. To tackle this problem, we develop a novel mechanism called customer sharing mechanism (CSM) which incentivizes all sellers to share each other's sale information to their private customer groups. Furthermore, CSM also incentivizes all customers to truthfully participate in the sale. In the end, CSM not only allocates the commodities efficiently but also optimizes the seller's revenue.
    Date: 2018–07
  21. By: David Lagziel (BGU)
    Keywords: credit auctions, defaulting, first-price auctions, second-price auctions, bid-caps
    JEL: D44 D82 G33
    Date: 2018
  22. By: Abdel-Hameed Nawar; Debapriya Sen
    Abstract: This paper establishes an interesting link between $k$th price auctions and Catalan numbers by showing that for distributions that have linear density, the bid function at any symmetric, increasing equilibrium of a $k$th price auction with $k\geq 3$ can be represented as a finite series of $k-2$ terms whose $\ell$th term involves the $\ell$th Catalan number. Using an integral representation of Catalan numbers, together with some classical combinatorial identities, we derive the closed form of the unique symmetric, increasing equilibrium of a $k$th price auction for a non-uniform distribution.
    Date: 2018–08
  23. By: Tai-Wei Hu (University of Bristol); Guillaume Rocheteau (University of California, Irvine); Lucie Lebeau (UC Irvine); Younghwan In (KAIST)
    Abstract: We introduce a new approach to bargaining into a model of decentralized asset market with unrestricted portfolios. Gradual bargaining (O’Neill et al., 2004) captures the idea that portfolios of assets are sold sequentially, one unit of asset at a time. In contrast to Nash or Kalai solutions, it is both monotone and ordinal. Moreover, gradual bargaining reduces asset misallocation in decentralized markets and can implement first best with or without endogenous participation. We generalize the solution to allow for time-varying bargaining powers and time-intensive technologies to negotiate assets thereby capturing the notion of asset negotiability, i.e., some assets can take longer than others to negotiate due to their complexity. The model can explain the rate-of-return-dominance puzzle.
    Date: 2018
  24. By: Claudia Cerrone (Max Planck Institute for Research on Collective Goods); Author-Name: Yoan Hermstruwer (Max Planck Institute for Research on Collective Goods; Competition Authority, Lisboa, Portugal)
    Abstract: This paper explores the impact of debarment as a deterrent of collusion in first-price procurement auctions. We develop a procurement auction model where bidders can form bidding rings, and derive the bidding and collusive behavior under no sanction, debarment and fines. The model's predictions are tested through a lab experiment. We find that debarment and fines both reduce collusion and bids. The deterrent effect of debarment increases in its length. However, the debarment of colluding bidders reduces effciency and increases the bids of non-debarred bidders. The latter suggests that the market size reduction resulting from debarment may trigger tacit collusion.
    Keywords: debarment, collusion, procurement auctions, procurement law, sanctions
    JEL: C92 D03 D44 K21 K42
    Date: 2018–04
  25. By: Bos, Iwan; Marini, Marco A.
    Abstract: This note considers cartel stability when the cartelized products are vertically differentiated. If market shares are maintained at pre-collusive levels, then the firm with the lowest competitive price-cost margin has the strongest incentive to deviate from the collusive agreement. The lowest-quality supplier has the tightest incentive constraint when the difference in unit production costs is sufficiently small.
    Keywords: Cartel Stability, Collusion, Vertical Differentiation, Price Collusion.
    JEL: D2 D4 D43 L1 L4
    Date: 2018–07–31
  26. By: Dietzenbacher, Bas (Tilburg University, School of Economics and Management)
    Date: 2018
  27. By: Sebastian Herrmann; Johannes Muhle-Karbe; Dapeng Shang; Chen Yang
    Abstract: We study Nash equilibria for inventory-averse high-frequency traders (HFTs), who trade to exploit information about future price changes. For discrete trading rounds, the HFTs' optimal trading strategies and their equilibrium price impact are described by a system of nonlinear equations; explicit solutions obtain around the continuous-time limit. Unlike in the risk-neutral case, the optimal inventories become mean-reverting and vanish as the number of trading rounds becomes large. In contrast, the HFTs' risk-adjusted profits and the equilibrium price impact converge to their risk-neutral counterparts. Compared to a social-planner solution for cooperative HFTs, Nash competition leads to excess trading, so that marginal transaction taxes in fact decrease market liquidity.
    Date: 2018–08
  28. By: Broman, Emanuel (CTS - Centre for Transport Studies Stockholm (KTH and VTI)); Eliasson, Jonas (City of Stockholm Traffic Department)
    Abstract: In recent years, several countries have deregulated passenger railway markets to allow open access. The aim is for competition to lower fares and increase quality of service, thereby increasing demand, economic efficiency and overall social welfare. In this paper, we use a stylised simulation model to study how open access competition affects fares, demand, supply, consumer surplus and operator profits compared to a profit-maximising monopoly and to a welfare-maximising benchmark situation. We conclude that aggregate social welfare increases substantially when going from profit-maximising monopoly to duopoly competition, as consumers make large gains while operators’ profits fall. According to simulations, there generally exists a stable competitive Nash equilibrium with two or more profitable operators. Although operators are identical in the model setup, the Nash equilibrium outcome is asymmetric: one operator has more departures and higher average fares than the other. If operators are allowed to collude, however, for example by trading or selling departure slots, the equilibrium situation tends to revert to monopoly: it will be profitable for one operator to buy the other’s departure slots to gain monopoly power. The regulatory framework must therefore prevent collusion and facilitate market entry. Even the potential for competitive entry tends to increase social welfare, as the monopolist has incentives to increase supply as an entry deterrence strategy.
    Keywords: open access; rail reform; capacity allocation; passenger
    JEL: D43 R41 R48
    Date: 2018–08–23
  29. By: Siddharth Barman; Sanath Kumar Krishnamurthy; Rohit Vaish
    Abstract: We study the problem of fairly allocating a set of indivisible goods among agents with additive valuations. The extent of fairness of an allocation is measured by its Nash social welfare, which is the geometric mean of the valuations of the agents for their bundles. While the problem of maximizing Nash social welfare is known to be APX-hard in general, we study the effectiveness of simple, greedy algorithms in solving this problem in two interesting special cases. First, we show that a simple, greedy algorithm provides a 1.061-approximation guarantee when agents have identical valuations, even though the problem of maximizing Nash social welfare remains NP-hard for this setting. Second, we show that when agents have binary valuations over the goods, an exact solution (i.e., a Nash optimal allocation) can be found in polynomial time via a greedy algorithm. Our results in the binary setting extend to provide novel, exact algorithms for optimizing Nash social welfare under concave valuations. Notably, for the above mentioned scenarios, our techniques provide a simple alternative to several of the existing, more sophisticated techniques for this problem such as constructing equilibria of Fisher markets or using real stable polynomials.
    Date: 2018–01

This nep-gth issue is ©2018 by Sylvain Béal. It is provided as is without any express or implied warranty. It may be freely redistributed in whole or in part for any purpose. If distributed in part, please include this notice.
General information on the NEP project can be found at For comments please write to the director of NEP, Marco Novarese at <>. Put “NEP” in the subject, otherwise your mail may be rejected.
NEP’s infrastructure is sponsored by the School of Economics and Finance of Massey University in New Zealand.