|
on Game Theory |
| 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 |
| URL: | http://d.repec.org/n?u=RePEc:nad:wpaper:20180019&r=gth |
| 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 |
| URL: | http://d.repec.org/n?u=RePEc:pra:mprapa:88347&r=gth |
| 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 |
| URL: | http://d.repec.org/n?u=RePEc:pra:mprapa:88400&r=gth |
| 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 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:1808.06750&r=gth |
| 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 |
| URL: | http://d.repec.org/n?u=RePEc:sps:cpaper:10476&r=gth |
| 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 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:1806.01072&r=gth |
| 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 |
| URL: | http://d.repec.org/n?u=RePEc:cfi:fseres:cf433&r=gth |
| 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 |
| URL: | http://d.repec.org/n?u=RePEc:cfi:fseres:cf439&r=gth |
| 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 |
| URL: | http://d.repec.org/n?u=RePEc:wap:wpaper:1805&r=gth |
| 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 |
| URL: | http://d.repec.org/n?u=RePEc:pra:mprapa:88366&r=gth |
| 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 |
| URL: | http://d.repec.org/n?u=RePEc:cfi:fseres:cf437&r=gth |
| 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 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:1808.07941&r=gth |
| 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 |
| URL: | http://d.repec.org/n?u=RePEc:bgu:wpaper:1808&r=gth |
| 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 |
| URL: | http://d.repec.org/n?u=RePEc:pen:papers:17-004&r=gth |
| 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 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:1802.01253&r=gth |
| 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 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:1803.06035&r=gth |
| 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 |
| URL: | http://d.repec.org/n?u=RePEc:pra:mprapa:87919&r=gth |
| 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 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:1807.05293&r=gth |
| By: | David Lagziel (BGU); Ehud Lehrer (TAU) |
| Keywords: | screening problem; competitions; manipulation |
| JEL: | C70 D49 D82 |
| Date: | 2018 |
| URL: | http://d.repec.org/n?u=RePEc:bgu:wpaper:1811&r=gth |
| 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 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:1807.06822&r=gth |
| By: | David Lagziel (BGU) |
| Keywords: | credit auctions, defaulting, first-price auctions, second-price auctions, bid-caps |
| JEL: | D44 D82 G33 |
| Date: | 2018 |
| URL: | http://d.repec.org/n?u=RePEc:bgu:wpaper:1810&r=gth |
| 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 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:1808.05996&r=gth |
| 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 |
| URL: | http://d.repec.org/n?u=RePEc:red:sed018:606&r=gth |
| 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 |
| URL: | http://d.repec.org/n?u=RePEc:mpg:wpaper:2018_05&r=gth |
| 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 |
| URL: | http://d.repec.org/n?u=RePEc:pra:mprapa:88335&r=gth |
| By: | Dietzenbacher, Bas (Tilburg University, School of Economics and Management) |
| Date: | 2018 |
| URL: | http://d.repec.org/n?u=RePEc:tiu:tiutis:01be3135-efa6-4f51-b2ef-06237b868eda&r=gth |
| 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 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:1808.05169&r=gth |
| 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 |
| URL: | http://d.repec.org/n?u=RePEc:hhs:ctswps:2018_012&r=gth |
| 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 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:1801.09046&r=gth |